В предыдущем разделе мы определили степень модульности для оценки качества разделения сообщества. Затем все остальное — оптимизация вокруг оптимизации модульности. Алгоритм Fast Unfolding — это основанный на модульности алгоритм обнаружения сообщества.
Алгоритм быстрого развертывания
Введение
Алгоритм Fast Unfolding — это основанный на модульности алгоритм обнаружения сообщества. Основная идея состоит в том, что узлы в сети пытаются обойти метки сообщества всех соседей и выбрать метку сообщества, которая максимизирует приращение модульности. После максимизации модульности каждое сообщество рассматривается как новый узел, и это повторяется до тех пор, пока модульность больше не увеличивается. Оригинал статьи может означать:Fast unfolding of communities in large networks.
Детали алгоритма
Стадия оптимизации модульности: каждая нода использует себя как собственную метку сообщества. Каждый узел проходит через все свои соседние узлы, пытается обновить свою метку сообщества до метки сообщества соседнего узла и выбирает метку сообщества с наибольшим приращением модульности (жадное мышление) до тех пор, пока все узлы не смогут увеличить модуль, изменив метку сообщества. Тратить.
Стадия сплоченности сети: каждое сообщество объединяется в новый суперузел, а вес ребра суперузла представляет собой сумму весов ребер всех узлов в исходном сообществе для формирования новой сети..
Вышеуказанные два этапа выполняются итеративно до тех пор, пока модульность больше не увеличивается.
Диаграмма ниже хорошо описывает эти два этапа. На первой итерации, после этапа оптимизации модульности, алгоритм делит 16 узлов на 4 сообщества, на этапе агрегации сети 4 сообщества объединяются в 4 суперузла, и повторно обновляются веса ребер. Затем введите вторую итерацию.
Алгоритм Fast Unfolding позволяет избежать попадания в локальный оптимум, вызванный жадной идеей, путем введения идеи пошаговой итерации (аналогично алгоритму EM).
Преимущества и недостатки
преимущество
1. Низкая временная сложность, подходит для крупномасштабных сетей.
2.Результаты разделения сообществ стабильны, и существуют специальные показатели для оценки качества разделения сообществ.
3.Устранено ограничение модульного разрешения. Так как модульность является глобальным показателем, при максимизации сложно найти небольшие сообщества, а объединить небольшие сообщества легко. Первая итерация алгоритма использует один узел в качестве гранулярности сообщества, что позволяет избежать этой проблемы.
4.Естественно, существует иерархический результат разделения сообщества.Результат разделения сообщества каждой итерации может быть сохранен как промежуточный результат разделения сообщества и может быть выбран.
недостаток
1. Сообщество слишком велико, чтобы сойтись во времени. Если мы сравним модульность с функцией потерь, жадное мышление, принятое Fast Unfolding на этапе оптимизации модульности, может легко разделить все сообщество на «переоснащение». Поскольку быстрое развертывание предназначено для обхода точек, легко добавить несколько периферийных точек к исходному компактному сообществу, что приведет к неправильному слиянию. Это разделение иногда хорошо с локальной точки зрения, но становится плохим с глобальной точки зрения.
Направление улучшения
Ввиду недостатков алгоритма мы можем принять идею «ранней остановки» для установки порога приращения модульности
.
На этапе оптимизации модульности мы можем установить инкрементный порог
. При обходе каждого узла, если модульность увеличивается
, тег сообщества не будет обновлен.
После фазы оптимизации модульности мы можем установить инкрементный порог
. Когда получен результат разделения сообщества, если модульность увеличивается
, фаза сцепления сети не выполняется, и алгоритм завершается непосредственно.
Увеличение модульности
Очень важным показателем, задействованным в алгоритме , является инкремент модульности. Поскольку алгоритм должен пройти через каждый узел и попытаться присоединиться к сообществу каждого соседнего узла, чтобы вычислить приращение модульности, если приращение модульности трудно вычислить, это окажет большое влияние на временную сложность всего алгоритма.
К счастью, согласно знаниям о модульности в предыдущем разделе, мы обнаружили, что модульность на самом деле представляет собой накопление каждого сообщества, а это означает, что когда узел
, присоединиться к его соседним узлам
общество
Когда меняется вся модульность, только задействованные узлы
,
и расчеты сообщества, все остальное постоянно. Итак, когда узел
присоединиться к узлу
сообщества, мы можем рассчитать приращение модульности
.
как узел
присоединиться к узлу
общество
Затем мы можем рассчитать модульность:
в
сообщество
,
сообщество
градусов внутри,
узел
сообществу
в два раза больше степени ребра всех узлов (поскольку узел
был включен в сообщество
, согласно методу расчета модульности, ребро сообщества должно учитываться дважды, потому что узел может использоваться как конечная точка ребра, а также может использоваться как начальная точка ребра).
Он представляет собой степень узлов в сообществе в случайной сети, поскольку узлы
Также включены в сообщество, поэтому
.
как узел
узел еще не подключен
общество
Ранее модульность представляла собой сумму этих двух частей:
![[\frac{\sum in}{2m} - (\frac{\sum tot}{2m})^2] + [0-(\frac{k_i}{2m})^2]](https://s3.timeweb.com/newworld58-e1e8f297-7d39-4eff-9f5d-42281e40a914/UnderSkyAi-3d6cb6f97e07898ecd7352201344ab0e34b4dd13e877fbb063ef77e42784451ed832c973.svg)
Таким образом, мы можем рассчитать приращение модульности, которое должно рассчитываться каждый раз, когда эвристика присоединяется к сообществу.
:
![[\frac{\sum in + k_{i,in}}{2m} - (\frac{\sum tot + k_i}{2m})^2] - [\frac{\sum in}{2m} - (\frac{\sum tot}{2m})^2-(\frac{k_i}{2m})^2]](https://s3.timeweb.com/newworld58-e1e8f297-7d39-4eff-9f5d-42281e40a914/UnderSkyAi-c81b19609cd0ef05681f4e116cb0644064a3ef922f6f782c8bed294807f8ca71155a45fe.svg)
Подробный код
Код разбит на два файла, первый файл — это класс алгоритма построения, второй файл отвечает за ввод и вывод, а алгоритм реализуется путем чтения данных графа из файла.
Стоит отметить, что на входе этого файла на одну строку больше, чем раньше. Исходные три столбца по-прежнему имеют формат данных таблицы ребер, а именно node_in, node_out, edge_weight, а четвертая строка — идентификатор сети, который этот файл.Поддерживается несколько сетей. Если у вас несколько сетей, хорошо отметьте четвертый столбец, и те, у кого одинаковые отметки, будут считаться одной сетью. Если у вас только одна сеть, вы можете установить для всего четвертого столбца одно значение или изменить код самостоятельно.
fast_unfloding.py
import networkx as nx
from itertools import permutations
from itertools import combinations
from collections import defaultdict
class Louvain(object):
def __init__(self):
self.MIN_VALUE = 0.01 #early_stop，Q_t_2
self.node_weights = {} #节点权重
# 函数入口
def getBestPartition(self, graph, param=1.):
i = 1
partition_list = []
node2com, edge_weights = self._setNode2Com(graph) #初始化点和边
# 得到节点->社区的关系
node2com = self._runFirstPhase(node2com, edge_weights, param)
best_modularity = self.computeModularity(node2com, edge_weights, param)
# 第一次节点->社区的关系要存储下来，之后就是社区->社区的关系，需要这份数据去映射
partition = node2com.copy()
partition_list.append(partition.copy())
# 阶段二会根据阶段一的结果完成社区->大节点的操作，此时的new_node2com已经是社区作为节点，将自己更新为自己的社区标签（类似初始化）
new_node2com, new_edge_weights = self._runSecondPhase(node2com, edge_weights)
while True:
print ("----------------------------")
print ("第",i,"次迭代，网络模块度为",best_modularity)
i = i + 1
new_node2com = self._runFirstPhase(new_node2com, new_edge_weights, param)
modularity = self.computeModularity(new_node2com, new_edge_weights, param)
# print (new_node2com)
# 如果一轮迭代后整体网络的模块度增益过小，则跳出
if abs(best_modularity - modularity) < self.MIN_VALUE:
break
best_modularity = modularity
# 此时需要对初始的社区划分进行社区更新。
partition = self._updatePartition(new_node2com, partition)
partition_list.append(partition.copy())
#print (partition)
_new_node2com, _new_edge_weights = self._runSecondPhase(new_node2com, new_edge_weights)
new_node2com = _new_node2com
new_edge_weights = _new_edge_weights
print ("最好的模块度：", best_modularity)
print ("----------------------------")
return partition_list
"""
初始化
node2com是一个dict，key是node编号，value是node所属的社区，先初始化为自己的index
edge_weights是一个dict的dict，key是node，value是dict，key是另一个node，value是edge_weight
edge_weights 形式：{'a': defaultdict(<class 'float'>, {'c': 1.0, 'b': 1.0})}
"""
def _setNode2Com(self,graph):
node2com = {}
edge_weights = defaultdict(lambda: defaultdict(float))
for idx,node in enumerate(graph.nodes()):
node2com[node] = idx #给每一个节点初始化赋值一个团id
for edge in graph[node].items():
edge_weights[node][edge[0]] = edge[1]["weight"]
#print (node2com, edge_weights)
return node2com,edge_weights
"""
第一阶段：遍历所有的节点，尝试将节点并入邻居节点的社区，选择模块度增益最大的社区，直到所有节点都不能通过改变社区来增加模块度。
"""
def _runFirstPhase(self, node2com, edge_weights, param):
"""
双重循环，遍历所有的edge_wieght，等价
for start in edge_weights.keys() ：
for end, weight in edge_weights[start].items() ：
weight
用以计算Tr(e),就是∑e_ii的和
"""
all_edge_weights = sum(
[weight for start in edge_weights.keys() for end, weight in edge_weights[start].items()]) / 2
"""
计算每个节点的a_i
"""
self.node_weights = self.updateNodeWeights(edge_weights) #输出一个字典，每个node对应node上边的权重和
status = True
while status:
statuses = []
for node in node2com.keys(): # 逐一选择节点和周边连接的节点进行比较
statuses = []
com_id = node2com[node] # 获取节点对应的社团编号
neigh_nodes = [edge[0] for edge in self.getNeighborNodes(node, edge_weights)] #获取连接的所有边节点
max_delta = 0 # early_stop，用于计算比对，#Q_t_1
max_com_id = com_id # 默认当前社团id为最大社团id
communities = {}
"""
遍历每个节点的邻居节点，
"""
for neigh_node in neigh_nodes:
node2com_copy = node2com.copy()
if node2com_copy[neigh_node] in communities:
continue
communities[node2com_copy[neigh_node]] = 1
node2com_copy[node] = node2com_copy[neigh_node] # 将节点分配到邻居节点的社区中，也就是将邻居节点的社区更新给该节点
"""
计算节点i加入社区前后的模块度之差，选择能最大化的模块度增益的社区
"""
delta_q = 2 * self.getNodeWeightInCluster(node, node2com_copy, edge_weights) - (self.getTotWeight(
node, node2com_copy, edge_weights) * self.node_weights[node] / all_edge_weights) * param
"""
设置增益阈值，防止由于贪婪思想导致没有及时收敛
"""
if delta_q > max_delta:
max_delta = delta_q # max_delta 选择最大的增益的node
max_com_id = node2com_copy[neigh_node] # 对应 max_com_id 选择最大的增益的临接node的id
node2com[node] = max_com_id
statuses.append(com_id != max_com_id)
# 直到所有节点都不能通过改变社区来增加模块度，完成第一阶段
if sum(statuses) == 0:
break
return node2com
"""
计算每个节点的度（无权图），将所有边权重求和。
node_weights是一个dict, key是node，value是节点的度node_weight。
"""
def updateNodeWeights(self, edge_weights):
node_weights = defaultdict(float)
for node in edge_weights.keys():
node_weights[node] = sum([weight for weight in edge_weights[node].values()])
return node_weights
"""
dict.items(),返回的是(key,value)组成的tuple的list，取[0]就是key，也就是邻居节点
"""
def getNeighborNodes(self, node, edge_weights):
if node not in edge_weights:
return 0
#print (edge_weights[node].items())
return edge_weights[node].items()
"""
节点与社区内其他节点的边权重之和
"""
def getNodeWeightInCluster(self, node, node2com, edge_weights):
neigh_nodes = self.getNeighborNodes(node, edge_weights)
node_com = node2com[node]
weights = 0.
for neigh_node in neigh_nodes:
if node_com == node2com[neigh_node[0]]:
weights += neigh_node[1]
return weights
"""
社区内所有节点的度数之和
"""
def getTotWeight(self, node, node2com, edge_weights):
nodes = [n for n, com_id in node2com.items() if com_id == node2com[node] and node != n]
weight = 0.
for n in nodes:
weight += sum(list(edge_weights[n].values()))
return weight
"""
计算网络整体的模块度
"""
def computeModularity(self, node2com, edge_weights, param):
q = 0
all_edge_weights = sum(
[weight for start in edge_weights.keys() for end, weight in edge_weights[start].items()]) / 2
com2node = defaultdict(list)
for node, com_id in node2com.items():
com2node[com_id].append(node)
for com_id, nodes in com2node.items():
node_combinations = list(combinations(nodes, 2)) + [(node, node) for node in nodes]
cluster_weight = sum([edge_weights[node_pair[0]][node_pair[1]] for node_pair in node_combinations])
tot = self.getDegreeOfCluster(nodes, node2com, edge_weights)
q += (cluster_weight / (2 * all_edge_weights)) - param * ((tot / (2 * all_edge_weights)) ** 2)
return q
"""
将社区com_id看做node，rebuild成新网络重新进行社区划分，同时社区间的边权重更新为新节点间的边权重
举个例子，节点1,2划分a，3,4划分为b。那么新的网络就是2个点a,b。边a->b的权重就是(1->3)+(1->4)+(2->3)+(2->4)
"""
def _runSecondPhase(self, node2com, edge_weights):
com2node = defaultdict(list)
new_node2com = {}
new_edge_weights = defaultdict(lambda: defaultdict(float))
for node, com_id in node2com.items():
com2node[com_id].append(node) #添加同一一个社团id对应的node，用来计算
if com_id not in new_node2com:
new_node2com[com_id] = com_id
nodes = list(node2com.keys())
node_pairs = list(permutations(nodes, 2)) + [(node, node) for node in nodes]
#print ("node_pairs!", node_pairs)
for edge in node_pairs:
new_edge_weights[new_node2com[node2com[edge[0]]]][new_node2com[node2com[edge[1]]]] += edge_weights[edge[0]][
edge[1]]
return new_node2com, new_edge_weights
def getDegreeOfCluster(self, nodes, node2com, edge_weights):
weight = sum([sum(list(edge_weights[n].values())) for n in nodes])
return weight
def _updatePartition(self, new_node2com, partition):
reverse_partition = defaultdict(list)
for node, com_id in partition.items():
reverse_partition[com_id].append(node)
for old_com_id, new_com_id in new_node2com.items():
for old_com in reverse_partition[old_com_id]:
partition[old_com] = new_com_id
return partition
@classmethod
def convertIGraphToNxGraph(cls, igraph):
node_names = igraph.vs["name"]
edge_list = igraph.get_edgelist()
weight_list = igraph.es["weight"]
node_dict = defaultdict(str)
for idx, node in enumerate(igraph.vs):
node_dict[node.index] = node_names[idx]
convert_list = []
for idx in range(len(edge_list)):
edge = edge_list[idx]
new_edge = (node_dict[edge[0]], node_dict[edge[1]], weight_list[idx])
convert_list.append(new_edge)
convert_graph = nx.Graph()
convert_graph.add_weighted_edges_from(convert_list)
return convert_graph
test.py
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Fri Apr 3 14:38:58 2020
@author: xxx
"""
import networkx as nx
from fast_unfolding import *
from collections import defaultdict
def makeSampleGraph(file_path):
"""
:return: 获取一个图
"""
g_dict = {}
with open(file_path) as fp:
for line in fp.readlines():
n1,n2,weight,cate = line.strip().split("\t")
# if cate == "纪录片":
g_dict.setdefault(cate, nx.Graph())
g_dict[cate].add_edge(n1, n2, weight = float(weight))
return g_dict
if __name__ == "__main__":
tag_net = "/Users/xxx/Desktop/TagNet/tag_net.txt"
sample_graph_dict = makeSampleGraph(tag_net)
#先清空
filename = "/Users/xxx/Desktop/TagNet/tag_result.txt"
file_object = open(filename, 'w')
file_object.close()
for cate, sample_graph in sample_graph_dict.items():
#print(sample_graph.nodes,sample_graph.edges)
print ("----------------------------")
print("“",cate,"”类目的网络开始执行")
louvain = Louvain()
partition_list = louvain.getBestPartition(sample_graph)
p = defaultdict(list)
i = 1
for partition in partition_list:
for node, com_id in partition.items():
p[str(i) + "_" +str(com_id)].append(node)
i = i + 1
pre_partition = partition
#写入文件
with open(filename, 'a') as file_object:
for com, nodes in p.items():
file_object.write(str(com) + "\t" + str(nodes) + "\t" + cate + "\n")
#print(com, nodes, cate)
file_object.close()