快捷导航

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

2022-10-20 18:56| 发布者: Fuller| 查看: 588| 评论: 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算法的基本流程如下:

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

3  使用方法

操作顺序是:

  1. 在GooSeeker分词和文本分析软件上创建文本分析任务并导入包含待分析内容的excel,分析完成后导出共词矩阵表
  2. 将导出的excel表放在本notebook的data/raw文件夹中
  3. 从头到尾执行本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算法

  1. 计算网络中各条边的边介数;
  2. 找出边介数最大的边,并将它移除(如果最大边介数的边不唯一,那么既可以随机挑选一条边断开也可以将这些边同时断开);
  3. 重新计算网络中剩余各条边的边介数;
  4. 重复第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

并没有看到改善,再往下看一层试试:

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

second_level_co_word_bt_weight

11  总结

经过上面的实验过程,我们仅仅练习了networkx的社区发现的编程方法,但是,并没有从GooSeeker分词软件导出的共词矩阵中有所发现。

我们期望能否发现多个词从语义方面形成的聚集,但是,上述实验没有达到目的。每一层社区分解只能分出一个词。因为这个数据集从知乎上用网络爬虫采集下来的,每篇内容都很长,那么,词与词之间的关系十分稠密,从上图就能看出来,几乎都全互联的,那么介数这个指标几乎没有太大意义。

我们尝试了调整权重的值,最多取5个不同的值,但是,用发现社区算法效果依然不好。至此,我们自然会想到,可以先对图进行裁剪,剩下骨干词以后再进行社区发现。

我们此前发布的Jupyter Notebook探索了文本处理中的选词矩阵的作用,以及在其上进行协方差处理的意义,然后再对协方差矩阵形成的图进行裁剪,可以观察到很好的词聚集现象。参看《对共词关系求协方差矩阵后是否有更好的社会网络分析结果?》。那么,接下来一个notebook将专门进行探索。

12  下载源代码

下载Jupyter Notebook源代码,请进入《对共词关系求协方差矩阵后再用Girvan-Newman算法做社区发现


鲜花

握手

雷人

路过

鸡蛋

最新评论

GMT+8, 2022-12-7 07:28