社区发现算法Girvan-Newman(GN)是否能应用于共词矩阵？

2022-10-20 18:56| 发布者: Fuller| 查看: 6935| 评论: 0

摘要: 我们将用多个notebook和文章演示社群划分的方法。本篇notebook先演示用Python实现Girvan-Newman算法。演示了两种方法：1，手工写Girvan-Newman算法；2，使用networkx的函数。手工写Girvan-Newman算法仅作演示用，不 ...

1 前言

此前，我们学习了一篇和Gephi相关的研究范文《基于引文网络和语义分析的技术演化路径识别及拓展研究》，该范例作者使用Gephi软件作为网络分析的工具，同时运用Girvan-Newman算法对引文网络进行社群划分和主路径提取。接下来我们将用多个notebook和文章演示社群划分的方法。本篇notebook先演示用Python实现Girvan-Newman算法。演示了两种方法：1，手工写Girvan-Newman算法；2，使用networkx的函数。手工写Girvan-Newman算法仅作演示用，不建议在实际项目项目中使用。下面手工写的Girvan-Newman算法也没有经过大量测试，所以，要采用第二种方法。

我们今天就Girvan-Newman算法做一次编程练习和实验，期望能够形成一个初步认识：针对什么样的数据可以做社>**(不当用词)现。

另外，Gephi也有社群分析功能，我们将在接下来的文章中介绍Gephi的用法，这里先做个简单介绍。

Gephi是一款很强的网络可视化分析软件，下面是Gephi官网提到的几个功能：

社交网络分析：轻松创建社交数据连接器，以映射社区组织和小世界网络。
探索性数据分析：通过网络操作进行实时直觉分析。
链接分析：揭示对象之间关联的底层结构。
生物网络分析：表示生物数据的模式。
海报制作：通过高质量的可打印地图进行科学的工作推广。

有关Gephi的学习，可以参考我们发布的系列文章：

另外，我们也发布了多篇Jupyter Notebook，使用Python进行各种算法的演练，比如在这篇《对共词关系求协方差矩阵后是否有更好的社会网络分析结果？》中，我们演练了怎样用协方差矩阵表示共词矩阵，同时讲解了使用协方差矩阵的意义，并且设想了更进一步编程探索的方向。

2 Girvan-Newman算法是什么？

Girvan-Newman算法是一种社交网络的聚类方法，简称GN算法。

以下对社区发现和GN算法的解释和图片，参考了这2篇知乎文章：《Girvan和Newman社团发现算法》，《社区发现算法-GN》。

2.1 网络中的社区/社群是什么？

所谓社区/社群就是：其内部顶点的连接稠密，而与其他社区内的顶点连接稀疏。

这就意味着社区与社区之间联系的通道比较少，一个社区到另一个社区至少要通过这些通道中的一条。

下面，我们将混用“社区”和“社群”，当成一回事。

2.2 什么是社区发现

一个社区由一组连接紧密的结点组成，同时这些结点与社区外部的结点连接稀疏，如下图所示。那么，社区发现就是在复杂网络中发现这些连接紧密的社区结构。其实，社区发现可以理解为网络中的结点聚类。下图引用自《社区发现算法-GN》

2.3 什么是Girvan-Newman算法(GN算法)？

GN算法是社区发现中的第一个算法，也就是它开启了这个研究领域。它的基本思想是删除掉那些社区之间的连接，那么剩下的每个连通部分就是一个社区。那么问题来了，就是哪些是社区之间的边呢？作者巧妙地借助最短路径解决了这个问题，他们定义一条边的介数(betweeness)为网络中所有结点之间的最短路径中通过这条边的数量，而介数高的边要比介数低的边更可能是社区之间的边。其实，这也比较好理解，因为两个社区中的结点之间的最短路径都要经过那些社区之间的边，所以它们的介数会很高。

GN算法每次都删除网络中介数最大的边，直至网络中的所有边都被删除。这样GN的过程对应着一颗自顶向下构建的层次树。在层次树中选择一个合适的层次分割即可。下图引用自《社区发现算法-GN》

GN算法的基本流程如下：

计算网络中各条边的边介数；
找出边介数最大的边，并将它移除(如果最大边介数的边不唯一，那么既可以随机挑选一条边断开也可以将这些边同时断开)；
重新计算网络中剩余各条边的边介数；
重复第2)、3)步,直到网络中所有的边都被移除。

3 使用方法

操作顺序是：

在GooSeeker分词和文本分析软件上创建文本分析任务并导入包含待分析内容的excel，分析完成后导出共词矩阵表
将导出的excel表放在本notebook的data/raw文件夹中
从头到尾执行本notebook的单元

注意：GooSeeker发布的每个notebook项目目录都预先规划好了，具体参看Jupyter Notebook项目目录规划参考。如果要新做一个分析项目，把整个模板目录拷贝一份给新项目，然后编写notebook目录下的ipynb文件。

4 实验数据

本Notebook针对不同的实验数据使用不同的计算方法做了多个实验，通过对比选择最好的方法：

实验一：使用了networkx自带的空手道俱乐部数据，分别实验自定义Girvan-Newman算法和networkx提供的算法

实验二：使用了从知乎采集得到的有关话题“二舅”的社交媒体数据，经GooSeeker分词软件选词处理后导出的共词矩阵表（一共100个词频数高并且文档频数也高的词）。

实验三：针对“二舅”数据，不使用缺省的中介中心度，而是采用其他指标进行社区发现

5 修改历史

2022-10-15：第一版发布

6 版权说明

本notebook是GooSeeker大数据分析团队开发的，所分析的源数据是GooSeeker分词和文本分析软件生成的或者基于测试数据，本notebook中的代码可自由共享使用，包括转发、复制、修改、用于其他项目中。

7 准备运行环境

7.1 引入需要用到的库

# -*- coding: utf-8 -*-

import networkx as nx
import matplotlib.pyplot as plt
import os
import numpy as np
import pandas as pd
import pylab

%xmode Verbose
import warnings

# 软件包之间配套时可能会使用过时的接口，把这类告警忽略掉可以让输出信息简练一些
warnings.filterwarnings("ignore", category=DeprecationWarning)

# 把RuntimeWarning忽略掉，不然画图的时候有太多告警了
warnings.filterwarnings("ignore", category=RuntimeWarning)
%matplotlib inline

7.2 设置中文字体

因为含有中文，pyplot画图有可能会显示下面的错误信息：

C:\ProgramData\Anaconda3\lib\site-packages\matplotlib\backends\backend_agg.py:238: RuntimeWarning: Glyph 32993 missing from current font. font.set_text(s, 0.0, flags=flags)

这是因为找不到中文字体，所以在图上的中文显示不出来，为了解决pyplot显示找不到字体的问题，参看glyph-23130-missing-from-current-font，先做如下设置。

#plt.rcParams['font.sans-serif']=['SimHei']
# 上面一行在macOS上没有效果，所以，使用下面的字体
plt.rcParams['font.sans-serif'] = ['Arial Unicode MS']
plt.rcParams['axes.unicode_minus'] = False
# 下面的配置用于解决windows下画图不显示中文的问题
#plt.rcParams['font.sans-serif'] = [u'SimHei']
#plt.rcParams['axes.unicode_minus'] = False

8 实验一：基于networkx自带数据

networkx自带的空手道俱乐部测试数据做Girvan-Newman算法实验，从下面的网络图可以看到，这个数据集有很好的分群特征。

8.1 基于测试数据生成图并显示

# load the graph
G = nx.karate_club_graph()
nx.draw(G, with_labels = True)

8.2 输出图的节点数和边条数

len(G.nodes), len(G.edges)

输出结果：

(34, 78)

8.3 算法1: 使用自定义Girvan Newman算法

仅作为演示和体验算法原理只用，在实际项目中尽量采用networkx和numpy等程序库现有的算法，以获得更好的性能。

自定义算法有下面特点：

只根据介数进行分拆
只要分拆到非连通图，就停止分拆

8.3.1 定义函数：执行后返回目前需要删除的边

按GN算法的定义，选择介数中心性最大的边作为需要删除的边

def edge_to_remove(graph):
G_dict = nx.edge_betweenness_centrality(graph)
edge = ()

# extract the edge with highest edge betweenness centrality score
for key, value in sorted(G_dict.items(), key=lambda item: item[1], reverse = True):
edge = key
break

return edge

8.3.2 定义函数：实现GN算法

计算网络中各条边的边介数；
找出边介数最大的边，并将它移除(如果最大边介数的边不唯一，那么既可以随机挑选一条边断开也可以将这些边同时断开)；
重新计算网络中剩余各条边的边介数；
重复第2)、3)步,直到网络中所有的边都被移除。

def girvan_newman(graph):
# find number of connected components
sg = nx.connected_components(graph)
sg_count = nx.number_connected_components(graph)

while(sg_count == 1):
to_remove = edge_to_remove(graph)
graph.remove_edge(to_remove[0], to_remove[1])
sg = nx.connected_components(graph)
sg_count = nx.number_connected_components(graph)

return sg

8.3.3 针对已经生成的测试图，寻找社区并输出节点

# find communities in the graph
c = girvan_newman(G.copy())

# find the nodes forming the communities
node_groups = []

for i in c:
node_groups.append(list(i))

8.3.4 输出图，不同社区的节点以不同颜色显示

# plot the communities
color_map = []
for node in G:
if node in node_groups[0]:
color_map.append('blue')
else:
color_map.append('green')

nx.draw(G, node_color=color_map, with_labels=True, font_color='white')
plt.show()

8.4 算法2: 使用networkx提供的算法

networkx的community算法有很多，不只是Girvan Newman算法，所以尽量采用networkx提供的算法，熟练使用networkx以期获得最大能力和性能。

networkx提供的girvan_newman算法生成了分层的社区，根据需要选择深入观察到第几层。可以发现，如果观察到第一层，那么结果跟自定义算法是一样的

from networkx.algorithms import community

8.4.1 拆分社区

communities_generator = community.girvan_newman(G.copy())
top_level_communities = next(communities_generator)
top_level_communities

输出结果：

({0, 1, 3, 4, 5, 6, 7, 10, 11, 12, 13, 16, 17, 19, 21},

{2, 8, 9, 14, 15, 18, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33})

如果拆分到第二层，看到的结果是这样的

next_level_communities = next(communities_generator)
next_level_communities

输出结果：

({0, 1, 3, 4, 5, 6, 7, 10, 11, 12, 13, 16, 17, 19, 21},

{2, 8, 14, 15, 18, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33},

{9})

还可以继续拆分成第三层，是这样的

third_level_communities = next(communities_generator)
third_level_communities

输出结果：

({0, 1, 3, 7, 11, 12, 13, 17, 19, 21},

{2, 8, 14, 15, 18, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33},

{4, 5, 6, 10, 16},

{9})

8.4.2 转换成数组

因为数组比较好处理

top_level_array = sorted(map(sorted, top_level_communities))
top_level_array

输出结果：

[[0, 1, 3, 4, 5, 6, 7, 10, 11, 12, 13, 16, 17, 19, 21],

[2, 8, 9, 14, 15, 18, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33]]

8.4.3 定义更通用的标注社区的画图程序

# 用这个函数，可以最多画4种颜色不同的社区
def plot_communities(G, group_array):
color_map = []
for node in G:
found = False
for idx, group in enumerate(group_array):
if node in group:
found = True
if idx == 0:
color_map.append('blue')
elif idx == 1:
color_map.append('green')
elif idx == 2:
color_map.append('orange')
elif idx == 3:
color_map.append('red')
else:
color_map.append('purple')
if found == False:
color_map.append('black')

nx.draw(G, node_color=color_map, with_labels=True, font_color='white')
plt.show()

一层层画图

plot_communities(G, top_level_array)

plot_communities(G, sorted(map(sorted, next_level_communities)))

plot_communities(G, sorted(map(sorted, third_level_communities)))

9 实验二：发现GooSeeker分词软件导出的共词矩阵表中的社群

使用GooSeeker分词软件导出的共词矩阵表做Girvan-Newman算法实验，下面不再使用自定义函数，而是使用networkx自带的函数。

9.1 常量和配置

在我们发布的一系列Jupyter Notebook中，凡是处理GooSeeker分词软件导出的结果文件的，都给各种导出文件起了固定的名字。为了方便大家使用，只要把导出文件放在data/raw文件夹，notebook就会找到导出文件，赋值给对应的文件名变量。下面罗列了可能用到的文件名变量：

file_all_word：词频表

file_chosen_word: 选词结果表

file_seg_effect: 分词效果表

file_word_occurrence_matrix: 选词矩阵表（是否出现）

file_word_frequency_matrix: 文档词频对应矩阵

file_word_document_match: 选词匹配表

file_co_word_matrix: 共词矩阵表

pd.set_option('display.width', 1000) # 设置字符显示宽度
pd.set_option('display.max_rows', None) # 设置显示最大
# np.set_printoptions(threshold=np.inf) # threshold 指定超过多少使用省略号，np.inf代表无限大

# 存原始数据的目录
raw_data_dir = os.path.join(os.getcwd(), '../../data/raw')
# 存处理后的数据的目录
processed_data_dir = os.path.join(os.getcwd(), '../../data/processed')
filename_temp = pd.Series(['词频','分词效果','选词矩阵','选词匹配','选词结果','共词矩阵'])
file_all_word = ''
file_seg_effect = ''
file_word_occurrence_matrix = ''
file_word_frequency_matrix = ''
file_word_document_match = ''
file_chosen_word = ''
file_co_word_matrix = ''

9.2 检测data\raw目录下是否有GooSeeker分词结果表

在本notebook只使用共词矩阵表，下面的代码将检查data/raw中有没有这个表，如果没有会报错，后面的程序就没法执行了。

# 0:'词频', 1:'分词效果', 2:'选词矩阵', 3:'选词匹配', 4:'选词结果', 5:'共词矩阵'
print(raw_data_dir + '\r\n')

for item_filename in os.listdir(raw_data_dir):
if filename_temp[5] in item_filename:
file_co_word_matrix = item_filename
continue

if file_co_word_matrix:
print("共词矩阵表：", "data/raw/", file_co_word_matrix)
else:
print("共词矩阵表：不存在")

输出结果如下：

C:\Users\work\notebook\社区发现算法Girvan-Newman(GN)学习-对比\notebook\eda\../../data/raw
共词矩阵表： data/raw/ 共词矩阵-知乎-二舅.xlsx

9.3 读取共词矩阵表并存入矩阵

读入过程不展开讲解，具体参看《共词分析中的共词关系是怎么得到的？》。这篇文章也对比了共词矩阵和选词矩阵的不同使用场合。为了更好的分辨社区，本notebook也会展示用选词矩阵得到的分析效果。

9.3.1 用pandas dataframe读入共词矩阵

df_co_word_matrix = pd.read_excel(os.path.join(raw_data_dir, file_co_word_matrix))
df_co_word_matrix.head(2)

9.3.2 提取字段名

将用于给graph的node命名

coword_names = df_co_word_matrix.columns.values[1:]
print("There are ", len(coword_names), " words")
coword_names

输出结果如下：

There are 100 words
array(['世界', '时候', '作品', '东西', '故事', '现实', '个人', '时间', '人生', '时代', '人民',
'事情', '社会', '苦难', '感觉', '人们', '中国', '问题', '精神', '年轻人', '底层', '回村',
'内耗', '作者', '一生', '孩子', '命运', '态度', '残疾', '经历', '普通人', '农村', '价值',
'原因', '媒体', '城市', '房子', '力量', '母亲', '观众', '地方', '本质', '评论', '国家',
'意义', '角度', '办法', '老人', '内心', '文案', '流量', '方式', '鸡汤', '能量', '医生',
'能力', '年代', '内容', '电影', '环境', '情况', '老师', '农民', '关系', '视角', '大众',
'情绪', '条件', '压力', '文化', '分钟', '朋友', '穷人', '人物', '村里', '资本', '想法',
'观点', '大学', '心理', '思想', '父母', '群众', '文艺创作', '个体', '机会', '悲剧', '历史',
'艺术', '励志', '残疾人', '文艺', '平台', '生命', '身体', '编剧', '物质', '热度', '医疗',
'官方'], dtype=object)

9.3.3 生成矩阵数据结构

# 使用astype函数对数据类型进行转换，否则，下面画图的时候可能会报错
array_co_word_matrix = df_co_word_matrix.values[:, 1:].astype(float)
array_co_word_matrix

word_num = len(array_co_word_matrix)
word_num

输出结果如下：

100

9.3.4 对角线赋0

为了避免对角线上画出来自环边。

np.fill_diagonal(array_co_word_matrix, 0)
array_co_word_matrix

9.4 生成图并进行探索

9.4.1 从NumPy数组生成networkx图

参看networkx文档，有专门的函数从其他数据结构直接生成graph

#graph_co_word_df = nx.from_pandas_adjacency(df_co_word_matrix)
graph_co_word_matrix = nx.from_numpy_array(array_co_word_matrix)
print(nx.info(graph_co_word_matrix))
#graph_co_word_matrix.edges(data=True)

输出结果如下：

Name:

Type: Graph

Number of nodes: 100

Number of edges: 4746

Average degree: 94.9200

9.4.2 给node加上label

如果不加label，画出来的图上的每个节点只是一个编号，加上label可以看到节点对应的词。

根据get_node_attributes，查看现在的note labels

coword_labels = nx.get_node_attributes(graph_co_word_matrix,'labels')
coword_labels

输出结果如下：

{}

根据How-do-I-label-a-node-using-networkx-in-python，重新命名labels

for idx, node in enumerate(graph_co_word_matrix.nodes()):
print("idx=", idx, "; node=", node)
coword_labels[node] = coword_names[idx]
graph_co_word_matrix = nx.relabel_nodes(graph_co_word_matrix, coword_labels)
sorted(graph_co_word_matrix)

for idx, node in enumerate(graph_co_word_matrix.nodes()):
print("idx=", idx, "; node=", node)

9.4.3 画图

figure函数的使用方法参看pyplot官网。其他参考资料：

# 方案1：用pylab画图
#pos=nx.shell_layout(graph_co_word_matrix)
#nx.draw(graph_co_word_matrix,pos,with_labels=True, node_color='white', edge_color='grey', node_size=1200, alpha=1 )
#pylab.title('co-word matrix',fontsize=25)
#pylab.show()

# 方案2
#pos = nx.circular_layout(maximum_tree)
pos = nx.spring_layout(graph_co_word_matrix)
plt.figure(1,figsize=(10,10))
nx.draw(graph_co_word_matrix, pos, node_size=10, with_labels=True, font_size=10, font_color="red")
#nx.draw(graph_co_word_matrix, pos, with_labels=True)
#nx.draw_networkx_labels(graph_co_word_matrix, pos, labels)
plt.show()

graph_co_word_dis_15 = graph_co_word_matrix.copy()
edges = graph_co_word_dis_15.edges(data=True)
for u, v, d in edges:
d["weight"] //= 15

pos = nx.spring_layout(graph_co_word_dis_15)
plt.figure(1,figsize=(10,10))
nx.draw(graph_co_word_dis_15, pos, node_size=10, with_labels=True, font_size=10, font_color="red")
plt.show()

9.5 社区发现

针对已经生成的图，寻找社区并输出节点。你会发现效果很不好，在每一层只能分出一个词。因为这个数据集从知乎上用网络爬虫采集下来的，每篇内容都很长，那么，词与词之间的关系十分稠密，从上图就能看出来，几乎都全互联的，那么介数这个指标几乎没有太大区分的作用。

9.5.1 分拆社区

communities_generator = community.girvan_newman(graph_co_word_matrix.copy())
top_level_co_word = sorted(map(sorted, next(communities_generator)))
top_level_co_word

第一层的效果很不好，只有一个词“官方”分出来了。因为“二舅”这批数据是用网络爬虫从知乎回答爬下来的，每个回答比较长，所有的词之间的连接很稠密，不同词之间的中介中心性基本一致。

试试第二层

second_level_co_word = sorted(map(sorted, next(communities_generator)))
second_level_co_word

9.5.2 画社区图

虽然分到第二层，效果依然不好。前面已经分析了原因，继续分拆下去也不会有理想的结果，所以，我们要尝试其他计算指标。暂时先画一下第二层的社区图，几乎看不到有意义的信息。

plot_communities(graph_co_word_matrix, second_level_co_word)

10 实验三：为共词矩阵定义其他社区发现指标

networkx提供的girvan_newman函数，允许提供一个函数参数，这个函数用来计算其他指标。参看networkx community案例

我们自然会想到图上面的边的权重。在共词矩阵中，权重表示共现发生的次数，用这个权重叠加到中介中心性上，可以将原先中介中心性相同的区分开来。

10.1 利用权重属性

10.1.1 定义most_valuable_edge函数

我们定义了两个函数。如果权重越大越重要，那么就应该使用第二个，把权重小的先剔除。

from operator import itemgetter
def heaviest(G):
u, v, w = max(G.edges(data="weight"), key=itemgetter(2))
return (u, v)

from operator import itemgetter
def lightest(G):
u, v, w = min(G.edges(data="weight"), key=itemgetter(2))
return (u, v)

10.1.2 探索edge属性

edges = graph_co_word_matrix.edges(data=True)
for edge in edges:
print(edge)
#for u, v in edges:
# print("u = ", u, "\nv = ", v)

graph_co_word_matrix.edges(data="weight")

print("u = ", u, "; v = ", v, ", w = ", w)

输出结果如下：

u = 精神 ; v = 内耗 , w = 147.0

10.1.3 使用权重分拆社区

#com_gen = community.girvan_newman(graph_co_word_matrix.copy(), most_valuable_edge=heaviest)
com_gen = community.girvan_newman(graph_co_word_matrix.copy(), most_valuable_edge=lightest)
top_level_co_word_weight = sorted(map(sorted, next(com_gen)))
top_level_co_word_weight

second_level_co_word_weight = sorted(map(sorted, next(com_gen)))
second_level_co_word_weight

third_level_co_word_weight = sorted(map(sorted, next(com_gen)))
third_level_co_word_weight

10.1.4 画社区图

可以看到，经过三轮分拆，每次拆出一个词，分拆速度太慢了，画图效果如下，很不好。需要想办法提高分拆速度。

plot_communities(graph_co_word_matrix, third_level_co_word_weight)

10.2 压缩权重的层级

前面我们在画原始数据图的时候，尝试了压缩权重的层级。原先最大权重是147，也就是说，可能有147级。如果压缩成7级，分拆速度是否会快很多？

经过实验发现，社区发现算法其实也在逐步裁剪边，但是，这个算法不是为裁剪边设计的，用它来裁剪边的速度太低了，一次裁掉一个。

graph_co_word_dis_5 = graph_co_word_matrix.copy()
edges = graph_co_word_dis_5.edges(data=True)
for u, v, d in edges:
d["weight"] //= 20

pos = nx.spring_layout(graph_co_word_dis_5)
plt.figure(1,figsize=(10,10))
nx.draw(graph_co_word_dis_5, pos, node_size=10, with_labels=True, font_size=10, font_color="red")
plt.show()

edges

com_gen = community.girvan_newman(graph_co_word_dis_5.copy(), most_valuable_edge=lightest)
top_level_co_word_dis_5 = sorted(map(sorted, next(com_gen)))
top_level_co_word_dis_5

second_level_co_word_dis_5 = sorted(map(sorted, next(com_gen)))
second_level_co_word_dis_5

third_level_co_word_dis_5 = sorted(map(sorted, next(com_gen)))
third_level_co_word_dis_5

forth_level_co_word_dis_5 = sorted(map(sorted, next(com_gen)))
forth_level_co_word_dis_5

fifth_level_co_word_dis_5 = sorted(map(sorted, next(com_gen)))
fifth_level_co_word_dis_5

sixth_level_co_word_dis_5 = sorted(map(sorted, next(com_gen)))
sixth_level_co_word_dis_5

10.3 权重加中介中心性

10.3.1 定义most_valuable_edge函数

from networkx import edge_betweenness_centrality as betweenness
def most_central_edge(G):
centrality = betweenness(G, weight="weight")
return max(centrality, key=centrality.get)

10.3.2 分拆社区

下面的计算会花很长时间。因为这个数据集有100个节点，但是，计算结果依然没有改善。因为由girvan_newman算法决定了不会有理想的结果，只会一层层把当前层数值最大的一个节点筛选出来。

com_gen = community.girvan_newman(graph_co_word_matrix, most_valuable_edge=most_central_edge)
top_level_co_word_bt_weight = sorted(map(sorted, next(com_gen)))
top_level_co_word_bt_weight