Введение в обнаружение сообщества
Сообщество обнаружило, что проблема на самом деле возникла из проблемы сегментации подграфов. В социальной сети некоторые пользователи связаны очень тесно, а некоторые пользователи связаны редко.Эти тесно связанные пользователи могут рассматриваться как сообщество, а связи между сообществами разрежены. На рисунке ниже показано открытие сообщества.
Текущие проблемы обнаружения сообществ делятся на две категории: обнаружение непересекающихся сообществ и обнаружение перекрывающихся сообществ. Проблема обнаружения непересекающихся сообществ описывает: в сети каждый узел может принадлежать только одному и тому же сообществу, а это означает, что между сообществом и сообществом нет пересечения. В непересекающихся алгоритмах обнаружения сообществ существуют разные виды решений:
- 1. Алгоритм обнаружения сообщества на основе модульности
Основная идея состоит в том, чтобы измерить, является ли разделение сообщества относительно хорошим результатом, путем определения модульности, чтобы преобразовать проблему обнаружения сообщества в проблему максимизации модульности для решения. Это будет обсуждаться позже. - 2. Алгоритм обнаружения сообщества на основе распространения тегов
Основная идея состоит в том, чтобы обновить информацию о метках немаркированных узлов, пометив информацию о метках узлов, и распространить ее по всей сети до конвергенции. Наиболее представительным из них является Алгоритм распространения меток (LPA, Label Propagation Algorithm).
Алгоритм распространения метки
Введение
Алгоритм распространения меток — это алгоритм обнаружения локального сообщества, основанный на распространении меток. Основная идея заключается в том, что метка узла (сообщества) зависит от информации метки его соседних узлов, а степень влияния определяется сходством узлов и стабилизируется итеративными обновлениями посредством распространения. Оригинал статьи может означать:Near linear time algorithm to detect community structures in large-scale networks.
Детали алгоритма
Алгоритмический процесс
Фаза инициализации: каждый узел инициализирует себя как тег сообщества.
Фаза распространения: пройти все узлы в сети и найти все соседние узлы текущего узла. Получите метки сообщества всех соседних узлов и найдите метку сообщества с наибольшим весом (идея голосования) (для взвешенного графа это сумма весов ребер всех одинаковых меток сообщества; для невзвешенного графа ребро вес считается равным 1, что означает, что тег сообщества появляется чаще), измените его, чтобы обновить собственный тег сообщества.
Стадия определения конвергенции: пройтись по всем узлам в сети и найти все узлы-соседи текущего узла. Получите метки сообщества всех соседних узлов, найдите метку сообщества с наибольшим весом и определите, является ли она вашей собственной меткой сообщества.Если все они проходят, алгоритм завершается. Для предотвращения колебаний необходимо задать максимальное количество итераций. Также выход после достижения максимального количества итераций.
На этапе распространения метки сообщества, если мы назначаем каждому соседу
Как распространяются ярлыки
Существует два способа распространения меток: синхронное обновление и асинхронное обновление.
1. Синхронное обновление: в первом
На следующей итерации каждый узел зависит от предыдущей итерации соседнего узла.
тег сообщества в то время.
2. Асинхронное обновление: в первом
На следующей итерации каждый узел зависит от метки сообщества текущего соседнего узла.Если соседний узел обновляется, это зависит от
Тег сообщества в то время, если он не обновляется, это зависит от
тег сообщества в то время.
Преимущества и недостатки
преимущество
1.Логика алгоритма проста, временная сложность низкая, а сложность близка к линейной.Он будет иметь отличную производительность в сверхбольших сетях и подходит для базовых показателей.
2. Нет необходимости определять функцию оптимизации и заранее указывать количество сообществ.Алгоритм будет использовать свою собственную сетевую структуру для управления распространением меток.
недостаток
1. Эффект лавины: результаты сообщества нестабильны и случайны. Потому что, когда веса меток сообщества соседних узлов одинаковы, один из них будет выбран случайным образом. В результате небольшая ошибка на ранней стадии распространения непрерывно усиливалась, и в итоге не было получено соответствующих результатов. Особенно в случае асинхронных обновлений разница в порядке обновления также приведет к различным окончательным результатам разделения сообщества.
Например, на приведенном выше рисунке показан процесс алгоритма распространения метки.
На этапе инициализации каждый узел использует себя в качестве метки сообщества. Например, сообщество а — это а, а сообщество с — это с. При входе в фазу распространения узел c имеет всего 4 соседних узла: a, b, c, d. И метка сообщества тоже 4: a, b, c, d, если предположить, что a выбрано случайно. Если это асинхронное обновление, в это время в метке сообщества соседних узлов трех узлов b, d и e есть два a, поэтому они будут немедленно обновлены до a. Если c случайным образом выбирает b в это время, то d и e будут обновлены до b, в результате чего доминирующая метка сообщества будет b, а окончательное разделение сообщества будет b.
2. Эффект шока: результаты сообщества колеблются взад и вперед без сходимости. Когда режим распространения обновляется синхронно, это очень легко сделать, особенно для структуры двудольного графа или подграфа.
В качестве примера на приведенном выше рисунке показан поток алгоритма распространения меток в двудольном графе.
При синхронном обновлении каждый узел зависит от тега сообщества предыдущей итерации. Когда левая сторона двудольного графа представляет собой a, а правая сторона — b, все узлы в сообществе a являются в данный момент соседними узлами, а все узлы в сообществе b в это время являются соседними узлами. правило, все узлы в сообществе a будут обновлены до b, все узлы сообщества b будут обновлены до a. В это время алгоритм не может сходиться, вызывая колебания всей сети.
Реализация алгоритма
формат входных данных
использует формат данных таблицы ребер, то есть данные имеют три столбца, а именно node_in, node_out, edge_weight.
код питона
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
import matplotlib.pyplot as plt
import pandas as pd
import numpy as np
import string
def loadData(filePath):
f = open(filePath)
node_dict = {}
edge_list_dict = {}
for line in f.readlines():
lines = line.strip().split("\t")
for i in range(2):
if lines[i] not in node_dict:
node_dict[lines[i]] = (lines[i]) # 每个节点的社区标签就是自己
edge_list = [] # 存放每个节点的所有邻居节点及边权重
if len(lines) == 3:
edge_list.append(lines[1 - i] + ":" + lines[2])
else:
edge_list.append(lines[1 - i] + ":" + "1") # 无权图默认权重是1
edge_list_dict[lines[i]] = edge_list
else:
edge_list = edge_list_dict[lines[i]]
if len(lines) == 3:
edge_list.append(lines[1 - i] + ":" + lines[2])
else:
edge_list.append(lines[1 - i] + ":" + "1")
edge_list_dict[lines[i]] = edge_list
return node_dict, edge_list_dict
def get_max_community_label(node_dict, adjacency_node_list):
label_dict = {}
for node in adjacency_node_list:
node_id_weight = node.strip().split(":")
node_id = node_id_weight[0]
node_weight = int(node_id_weight[1])
# 按照label为group维度，统计每个label的weight累加和
if node_dict[node_id] not in label_dict:
label_dict[node_dict[node_id]] = node_weight
else:
label_dict[node_dict[node_id]] += node_weight
sort_list = sorted(label_dict.items(), key=lambda d: d[1], reverse=True) # 返回weight累加和最大的社区标签
return sort_list[0][0]
def check(node_dict, edge_dict):
for node in node_dict.keys():
adjacency_node_list = edge_dict[node] # 获取该节点的邻居节点
node_label = node_dict[node] # 获取该节点当前label
label = get_max_community_label(node_dict, adjacency_node_list) # 从邻居节点列表中选择weight累加和最大的label
if node_label >= label:
continue
else:
return 0 # 找到weight权重累加和更大的label
return 1
def label_propagation(node_dict, edge_list_dict, iteration_max):
t = 0
while True:
if t > iteration_max:
break;
# 收敛判定阶段
if (check(node_dict, edge_list_dict) == 0):
t = t + 1
print ('iteration: ', t)
# 每轮迭代都更新一遍所有节点的社区label
for node in node_dict.keys():
# adjacency_node_list存放该节点的所有邻居节点及边权重
adjacency_node_list = edge_list_dict[node]
# 传播阶段，将所有邻居节点最大的社区标签更新为自己的社区标签
node_dict[node] = get_max_community_label(node_dict, adjacency_node_list)
else:
break
return node_dict
if __name__ == '__main__':
# 加载文件
filePath = 'xx/xx.txt'
print ("初始化阶段开始！")
# node_dict表示每个节点归属社区的状态，key是node，value是社区标签。
# edge_list表示每个节点的所有所有邻居节点及边权重，key是node,value是一个list,list中的每个item就是该node的一个邻居节点及边权重。
node_dict, edge_list_dict = loadData(filePath)
iteration_max = 1000 # 设置最大迭代次数
print ("初始化阶段结束！")
print ("标签传播算法开始！")
node_dict = label_propagation(node_dict, edge_list_dict, iteration_max)
print ("标签传播算法结束！")
print ("最终的结果为：")
print (node_dict)
Направление оптимизации
Улучшения фазы инициализации
Вручную маркируйте или используйте алгоритмы, чтобы выделить некоторые близкие подструктуры, определить прототип сетевого сообщества, а затем распространить его.
Улучшения этапа распространения
В соответствии с конкретными бизнес-сценариями тщательно определите вес ребра edge_weight, вес точки node_weight, оптимизируйте приоритет распространения распространения метки, хорошее определение веса может неявно разделить структуру сети, что более способствует обнаружению сообщества.