陈云伟
, 张瑞红
Chen Yunwei, Zhang Ruihong
中图分类号: G350
通讯作者:
收稿日期: 2018-05-14
修回日期: 2018-05-14
网络出版日期: 2018-10-25
版权声明: 2018 《数据分析与知识发现》编辑部 《数据分析与知识发现》编辑部
基金资助:
展开
摘要
【目的】对复杂网络领域典型的社团划分算法进行全面系统的比较, 为情报研究人员开展相关社团划分研究提供参考。【方法】比较几种经典社团划分算法在理论、计算方法上的异同并展示其在小型的经典数据集上的划分结果; 扩大研究数据集, 选取适用数据规模范围较广的Louvain算法、Louvain多级细分算法及SLM算法, 进一步验证其在合作网络与引文网络上的划分效果。【结果】在小型数据上, GN算法与FN算法的划分结果类似, SLM算法的划分效果优于Louvain算法及其多级细分算法。在图书情报领域通常涉及的数以千计的机构合作网络、引文网络而言, 分辨率设定值为0.5左右即可获得较利于解析的社团划分结果, 此时SLM算法获得的社团划分结果与Louvain及其多级细分算法存在相对较大的差异, 后两者的社团划分结果基本相近, 当分辨率设定为1.0时, 二者社团划分结果的差异性逐步显著。【局限】尽管Louvain算法、Louvain多级细分算法及SLM算法仍然适用于大型网络的社团划分, 但本文仅对数千个节点的中型网络开展比较研究, 并未涉及大规模数据网络的划分比较。【结论】Louvain算法、Louvain多级细分算法及SLM算法在时间效率上均优于早期的GN算法与FN算法, 且针对中小型数据集的划分效果也较好。其中, SLM算法在引文网络上的社团划分效果优于Louvain算法及其多级细分算法。
关键词：
Abstract
[Objective] This paper compares community detection algorithms in the field of complex network analysis, aiming to support related information science studies. [Methods] First, we identified the similarities and differences of several community detection algorithms (i.e. theoretical frameworks and calculation methods). Then, we examined these algorithms with small data sets. Third, we expanded the sample size, and evaluated the performance of Louvain algorithm, Louvain algorithm with multilevel refinement, and the SLM algorithm with the collaboration and citation networks. [Results] On small dataset, the detection results of GN and FN algorithms were similar, and the results of SLM algorithm were better than those of the Louvain algorithm and Louvain algorithm with multilevel refinement. In the field of library and information science, setting the resolution at 0.5 could help us analyze the detection results. The results of SLM algorithm were different to those of the Louvain algorithm or Louvain algorithm with multilevel refinement. Results of the latter two were almost the same, which were different with the resolution of 1.0. [Limitations] The dataset needs to be expanded. [Conclusions] The Louvain algorithm, Louvain algorithm with multilevel refinement and SLM algorithm are better than traditional algorithms. Among them, the SLM algorithm is the best option for us to analyze the community of citation network.
Keywords：
社团结构是复杂网络非常重要的性质, 是在生物网络、万维网、社会网络、合作网络、引文网络等网络中常见的特征[1]。社团可以看作是在网络中属性相似或角色相近的节点的集合, 在结构上最直观的表现就是社团内部节点之间连接紧密, 而社团之间的节点连接稀疏。为了识别网络中的社团结构, 学者提出了大量方法, 如KL算法[2]、谱分解法[3,4]和分层聚类算法[5]等。然而, 这些传统的算法存在准确度不高、时间复杂度大以及需要事先知道网络中社团大小等缺 点[6]。
过去20多年涌现出大量可用于检测网络社团结构的工具, 其中以2002年Girvan和Newman提出GN算法最具里程碑意义[7], GN算法的提出开启了新社团研究的热潮。随后, Newman在2004年又提出FN贪婪算法[8], 并基于模块度函数Q[9]值最大化进行社团划分。然而, 由于以上算法的时间复杂度较高, 所以仅适用于数据规模较小的网络。为此, Blondel等提出Louvain算法[10], 该算法可以相对快速地处理含有数以亿计节点的网络。随后Rotta等在Louvain算法的基础上提出Louvain算法的多级细分[11]。Waltman等又基于这两种算法提出SLM算法[12]。
当前针对社团划分算法的优化研究较多[13,14,15], 且通常针对方法效率和处理能力进行比较, 而从实证分析角度观察不同算法划分结果差异的研究较少。因此, 本文利用过去20年间典型的社团划分算法针对经典的空手道俱乐部网络的社团划分的研究结果进行对比介绍, 并在自行构建的合作网络与引文网络数据集上进行实验, 包括几百个节点数的小型网络和数千个节点的中型网络, 比较不同算法的效用, 以期为情报分析人员提供参考。
本节对GN、FN、Louvain、Louvain多级细分、SLM等算法在原理、方法上进行介绍, 并比较他人利用这些算法对空手道俱乐部网络[16]的社团划分结果。同时介绍最常用的、用于衡量社团划分效果的模块度函数Q。
Q函数由Newman和Girvan于2004年提出[9]。其含义是网络中连接社团内部顶点的边所占的比例与另外一个随机网络中连接社团内部顶点的边所占比例的期望值相减得到的差值。这个随机网络的构造方法为: 保持每个顶点的社团属性不变, 顶点间的边根据顶点的度随机连接, 如果社团结构划分得好, 则社团内部连接的稠密程度高于随机连接网络的期望水平。一般认为, 模块度值越大, 所得到的划分也越好。Q函数已成为当前衡量社团划分效果所采用的最为广泛的方法[12], 可用于任何类型网络的社团划分[17]。
GN算法的基本流程是: 首先计算网络中所有边的介数[18], 然后找到介数最高的边并将其从网络中移除, 不断重复第二步, 直到每个节点成为一个独立的社团为止[7]。
图1是Newman和Girvan利用GN算法对Zachary’s空手道俱乐部网络进行社团划分的结果, 节点1代表教练, 节点34代表管理方, 其他节点代表会员。因管理方和教练的矛盾导致俱乐部拆分后形成两个团体, 圆形表示跟随管理方留在原俱乐部的会员; 方框表示跟随教练加入新俱乐部的会员。利用GN社团划分算法, 仅节点3被错误地划分到教练所成立的新俱乐部社团, 其他会员均准确地划分到与实际情况完全相符的社团。
FN算法的基本流程是: 首先将每个节点视为一个社团, 然后将社团不断进行合并计算Q值的变化, 每次合并都按照Q值增加最大的方向进行, 直到所有节点都并入同一个社团。在此过程中, Q值最大时得到最佳的社团划分[8]。图2是利用FN算法对空手道俱乐部网络进行社团划分的结果, Q函数峰值为0.381, 仅有会员10被错误地分配到教练所在社团。
Louvain算法及其多级细分算法、SLM算法的基础都是局域启发式移除算法(LMH), 其思想是按照Q值增加的方向, 将一个社团的节点不断移至另一个社团, 直至Q函数达到峰值后停止移动。LMH算法采取随机的方式进行迭代, 其特点在于效率高, 可以处理大规模网络。
Louvain算法[10]以Q函数为衡量指标, 执行过程分两个步骤并反复迭代:
(1) 运行LMH算法: 每个节点i视为一个社团, 其所在社团为C, U为与节点i邻接的社团, 如果将i从C移到U后模块度增量最大, 则执行此次移动, 否则i不移动。网络中每个节点都重复以上过程, 直到没有Q值的增加。
(2) 社团合并: 将上述划分好的社团作为一个新的节点(即简化网络), 新节点之间边的权重, 采用两个相邻新节点之间边的权重之和。
步骤(2)结束后则返回步骤(1)进行迭代计算, 直到没有更大的模块度产生, 算法结束。
利用Louvain算法对空手道俱乐部网络进行社团划分, 结果如图3所示。
Louvain算法的多级细分的特点在于除了利用LMH算法产生社团并不断合并外, 还可以在划分好的社团间按照增加Q值的方向移动节点, 直到无法移动为止[11]。例如, 在利用Louvain算法获得的图3中, 再运行LMH算法, 将节点28和24同时移动到右上 方的社团, Q值可提高到0.4198, 社团划分效果如图4所示。
SLM算法的第一步与Louvain算法的步骤(1)相同, 然后也要运行类似步骤(2)构建简化网络, 区别是在构建简化网络前, 还需增加几个步骤:
首先, 将步骤(1)划分的6个社团视为6个子网络, 然后在各子网络中分别再次运行LMH算法, 可能产生两种结果: 其一, 一个子网络中所有节点都被划分到一个社团; 其二, 一个子网络被拆分为多个社团。利用该步骤将空手道俱乐部网络划分为8个社团(图5(a))。其次, 将上述8个社团均为视为一个新节点作为简化网络(图5(b)), 来自同一个子网络的新节点首先被划分为同一个新社团(图5(b))。最后, 开始循环迭代, 针对简化网络运行LMH算法, 重复迭代前两个步骤, 直到网络不再继续简化为止, 得到如图5(c)所示的社团划分结果。
SLM算法的特点在于允许已经被划分社团的节点被重新划分。因此无需再运行Louvain算法的多级细分而实现社团划分, 同时解决了社团合并和单个节点在社团间移动的问题[12]。对于三个基于LMH的算法而言, 尽管每运行一次SLM需要进行更多的迭代次数, 但运行一次SLM算法获得的社团划分效果已经优于多次运行Louvain算法及其多级细分算法的社团划分效果, 这意味着利用SLM算法进行社团划分无需多次重复运行。通常SLM算法运行2-5次 迭代已经可以超过Louvain算法及其多级细分算法的效果。
通过相关文献与实践验证, 发现普通计算机运行早期的GN算法处理数以千计的节点时很难完成任务, 而与GN算法相比, FN算法的时间复杂度下降, 可用于计算节点众多的引文网络、合作网络以及因特网上规模较大的网络, 时间复杂度为O((m+n)n)。后续优化的像Louvain算法等适合大规模网络的社团划分算法, 在运行过程中呈现出线性时间复杂度, 时间效率大大提升。Louvain算法在处理拥有1.18亿个节点的复杂网络时, 探测社团的时间仅为152分钟[12]。对几种典型社团划分算法的特性归纳如表1所示。
表1 几种典型社团划分算法比较
| 算法 | 类型 | 核心思想 | 时间复杂度 (m条边, n个节点) | 模块度 (针对空手道俱乐部数据) |
|---|---|---|---|---|
| GN算法 | 分裂法 | 将边介数最高的边从网络中移除 | O(mn2) | 0.4左右 |
| FN算法 | 聚合法 | 将社团向着模块度增量最多的方向合并 | O((m+n)n) | 0.381 |
| Louvain算法 | 聚合法 | 基于模块度的LMH算法 | O(n) | 0.4151 |
| Louvain多级细分算法 | 聚合法 | 基于模块度的LMH算法 | -- | 0.4198 |
| SLM算法 | 聚合法 | 基于模块度的LMH算法 | -- | -- |
本文介绍的5种经典算法中, GN算法和FN算法存在局限性。GN算法的缺点在于其处理数据规模较大的网络时, 时间效率十分低下, 不建议使用。FN算法虽然理论上可以处理大型网络, 但其计算精度和计算效率并没有优势。鉴于本文目的是为情报分析人员从事科学数据的网络社团研究提供参考, 所选取数据对象也是科技论文的合作网络与引文网络数据集, Louvain算法、Louvain多级细分算法和SLM算法的时间效率与划分精度更具有可接受度与可信度, 因此, 只对这三类算法进行实证比较研究。
以Scientometrics期刊1978年-2010年期间发表的2 541篇文献(研究论文、会议论文和综述三种类型)为基础, 利用SCI2工具构建机构合作网络[19]。数据下载日期为2010年12月。
该网络拥有1 061个节点, 为了便于可视化解读社团划分结果, 本实证仅选择其含有497个节点、853条边的最大主成分, 从无权和加权(基于合作论文数量)两个角度开展比较, 同时测试设定不同分辨率值(分辨率越低, 划分获得的社团数量越少)对社团划分的影响。可视化图仅呈现论文数量大于10的前40个节点。
表2统计了不同算法及不同分辨率情况下有权和无权网络的社团划分情况。在分辨率设定为0.1时, 如果不考虑权重, 三种社团划分算法的社团划分结果完全相同。如果考虑权重, Louvain多级细分和SLM算法的划分结果完全相同, 总计获得6个社团, 而Louvain算法可划分得到8个社团。
表2 机构合作网络主成分三种算法社团划分结果比较
| 网络 | 算法 | 分辨率 | ||||
|---|---|---|---|---|---|---|
| 0.1 | 0.5 | 1.0 | ||||
| 无权网络 | Louvain | 7 | 15 | 19 | ||
| Louvain多级细分 | 7 | 15 | 19 | |||
| SLM | 7 | 16 | 21 | |||
| 加权网络 (基于合作论文数) | Louvain | 8 | 13 | 23 | ||
| Louvain多级细分 | 6 | 13 | 22 | |||
| SLM | 6 | 13 | 22 | |||
当分辨率提高到0.5时, 如果不考虑权重, Louvain及其多级细分算法的社团划分结果完全相同(15个社团), 而SLM算法则总计得到16个社团。如果考虑权重, 三种算法的社团划分结果均为13个, 但有大量节点在三种社团划分结果中被划分在不同的社团中。
当分辨率提高到1.0时, 不论是否考虑权重, 社团划分的数量均增加, 而且就497个单个节点而言, 利用不同的算法, 其被划分的社团归属情况也存在大量的变化。
表3统计了论文数量大于10的前40个节点利用不同社团划分算法以及不同分辨率获得的社团划分结果情况(L-Louvain算法, LM-Louvain多级细分算法)。
表3 40个节点利用三种算法、不同分辨率社团划分结果比较
| 序号 | 机构 | 论文数 | 分辨率=0.5 | 分辨率=1 | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 未加权 | 加权 | 未加权 | 加权 | |||||||||||
| L | LM | SLM | L | LM | SLM | L | LM | SLM | L | LM | SLM | |||
| 1 | Katholieke Univ Leuven | 85 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 3 | 0 | 1 | 0 |
| 2 | Hungarian Acad Sci | 85 | 0 | 0 | 0 | 0 | 0 | 0 | 2 | 1 | 2 | 0 | 1 | 0 |
| 3 | Natl Inst Sci Technol & Dev Studies | 61 | 0 | 0 | 0 | 9 | 0 | 10 | 7 | 7 | 9 | 13 | 14 | 14 |
| 4 | Leiden Univ | 59 | 9 | 9 | 8 | 2 | 1 | 1 | 2 | 1 | 2 | 8 | 7 | 7 |
| 5 | Csic | 57 | 1 | 1 | 2 | 2 | 1 | 1 | 4 | 6 | 4 | 2 | 3 | 3 |
| 6 | Univ Granada | 35 | 1 | 1 | 2 | 3 | 3 | 3 | 11 | 10 | 11 | 3 | 2 | 2 |
| 7 | Univ Sussex | 30 | 0 | 0 | 0 | 0 | 0 | 0 | 3 | 4 | 3 | 0 | 1 | 0 |
| 8 | Khbo | 26 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 |
| 9 | Univ Amsterdam | 25 | 3 | 3* | 1* | 1 | 2 | 2 | 1 | 2 | 1 | 4 | 9 | 4 |
| 10 | Univ Instelling Antwerp | 24 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 |
| 11 | Wolverhampton Univ | 21 | 3 | 3* | 1* | 1 | 2 | 2 | 1 | 2 | 1 | 4 | 5 | 4 |
| 12 | Royal Sch Lib & Informat Sci | 19 | 5 | 5 | 4 | 6 | 7 | 7 | 5 | 5 | 5 | 6 | 4 | 5 |
| 13 | Res Assoc Sci Commun & Informat Ev | 19 | 0 | 0 | 0 | 0 | 0 | 0 | 2 | 1 | 2 | 0 | 1 | 0 |
| 14 | Univ New S Wales | 18 | 6 | 6 | 5 | 3 | 3 | 3 | 0 | 0 | 0 | 1 | 0 | 1 |
| 15 | Limburgs Univ Ctr | 18 | 0 | 0 | 0 | 0 | 0 | 0 | 8 | 8 | 7 | 3 | 2 | 2 |
| 16 | Univ Hasselt | 17 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 |
| 17 | Univ Antwerp | 17 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 |
| 18 | Helsinki Univ Technol | 16 | 0 | 0 | 0 | 0 | 0 | 0 | 3 | 4 | 3 | 0 | 1 | 0 |
| 19 | Univ Fed Rio De Janeiro | 16 | 10 | 10 | 9 | 10 | 10 | 11 | 12 | 12 | 12 | 11 | 10 | 10 |
| 20 | Inra | 15 | 2 | 2 | 3 | 3 | 3 | 3 | 0 | 0 | 0 | 1 | 0 | 1 |
| 21 | Henan Normal Univ | 15 | 0 | 0 | 0 | 0 | 0 | 0 | 10 | 3 | 10 | 3 | 2 | 2 |
| 22 | Karnatak Univ | 14 | 0 | 0 | 0 | 9 | 0 | 10 | 2 | 1 | 2 | 0 | 1 | 0 |
| 23 | Lorand Eotvos Univ | 14 | 0 | 0 | 0 | 0 | 0 | 0 | 7 | 7 | 9 | 13 | 14 | 14 |
| 24 | Umea Univ | 13 | 9 | 9 | 8 | 0 | 0 | 0 | 5 | 5 | 5 | 6 | 4 | 5 |
| 25 | Fraunhofer Inst Syst & Innovat Res | 13 | 4 | 4* | 11* | 5 | 6 | 6 | 4 | 6 | 4 | 2 | 3 | 3 |
| 26 | Bar Ilan Univ | 13 | 1 | 1 | 2 | 2 | 1 | 1 | 2 | 1 | 2 | 0 | 1 | 0 |
| 27 | Univ Tokyo | 13 | 5 | 5 | 4 | 6 | 7 | 7 | 13 | 13 | 15 | 12 | 13 | 13 |
| 28 | Indiana Univ | 12 | 8 | 8 | 7 | 8 | 9 | 8 | 6 | 3 | 6 | 9 | 8 | 8 |
| 29 | Cnrs | 12 | 2 | 2 | 3 | 4 | 5 | 5 | 16 | 15 | 17 | 15 | 16 | 16 |
| 30 | Inst Sci & Tech Informat China | 12 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| 31 | City Univ London | 12 | 2 | 2* | 10* | 11 | 4 | 4 | 14 | 11 | 14 | 5 | 12 | 12 |
| 32 | Max Planck Inst Festkorperforsch | 11 | 0 | 0 | 0 | 0 | 0 | 0 | 4 | 6 | 4 | 2 | 3 | 3 |
| 33 | Drexel Univ | 11 | 4 | 4* | 1* | 5 | 6 | 6 | 3 | 4 | 13 | 10 | 11 | 11 |
| 34 | Univ Politecn Valencia | 11 | 15 | 15 | 16 | 2 | 1 | 1 | 3 | 4 | 13 | 10 | 11 | 11 |
| 35 | Georgia Inst Technol | 11 | 4 | 4* | 1* | 5 | 6 | 6 | 10 | 3 | 10 | 3 | 2 | 2 |
| 36 | Univ Western Ontario | 11 | 8 | 8 | 7 | 8 | 9 | 8 | 15 | 14 | 16 | 14 | 15 | 15 |
| 37 | Hebrew Univ Jerusalem | 11 | 1 | 1 | 2 | 2 | 1 | 1 | 17 | 17 | 18 | 18 | 19 | 19 |
| 38 | Observ Sci & Tech | 11 | 2 | 2 | 3 | 3 | 3 | 3 | 2 | 1 | 2 | 0 | 1 | 0 |
| 39 | Eth | 11 | 13 | 13 | 14 | 12 | 12 | 12 | 19 | 19 | 20 | 2 | 3 | 3 |
| 40 | Univ Carlos Iii Madrid | 11 | 1 | 1 | 2 | 2 | 1 | 1 | 4 | 6 | 4 | 2 | 3 | 3 |
图6呈现了分辨率=0.5情况下SLM算法与Louvain算法社团划分结果的不同(仅显示40个节点), SLM算法的改进并不是在于增加或合并社团, 而是既有社团的合并也有拆分。在Louvain算法中分属社团3、社团4的4个机构(Univ Amsterdam、Wolverhampton Univ、Drexel Univ、Georgia Inst Technol)在SLM算法中被划分在同一个社团1中。而City Univ London则从Louvain算法的社团2移到SLM算法的社团10。需要强调的是, 虽然许多社团序号发生改变, 但多数节点仅是在不同算法结果中的序号发生改变, 实质社团划分结果并未改变, 仅以星号标注的节点存在社团的变化。
以文献[20]采用的2 046篇“引文网络演化”相关文献(研究论文、信函、会议论文和综述4种类型)开展引文网络社团划分研究, 数据下载日期为2015年7月14日。删除仅作为参考文献出现的节点, 以及没有参考文献的节点, 总计获得拥有2 036个节点(文章)的无权网络, 为了便于分析, 选择包含525个节点、1 118条边的最大主成分进行分析。测试设定不同分辨率值对引文网络社团划分的影响。
表4统计了不同算法及不同分辨率情况下引文网络的社团划分情况。分辨率为0.1时, 三种社团划分算法得到的社团数均为2个, 且每个节点所属社团情况均相同。分辨率提高到0.5时, Louvain及其多级细分算法的社团划分结果完全相同, 得到7个社团, 而SLM算法也得到7个社团, 但某些节点所属的社团发生变化。分辨率提高到1.0时, 社团划分的数量均增加, 节点的社团归属也发生较大变化。表5统计了被引频次≥10的前26个节点的社团划分情况。
表5 前26篇被引频次≥10的论文社团划分结果比较
| 标签n | 被引频次 | 分辨率=0.5 | 分辨率=1.0 | 标签n | 被引频次 | 分辨率=0.5 | 分辨率=1.0 | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| L | LM | SLM | L | LM | SLM | L | LM | SLM | L | LM | SLM | |||||
| 131 | 42 | 1* | 1* | 1* | 0 | 0 | 1 | 210 | 15 | 4 | 4 | 1 | 0 | 0 | 1 | |
| 469 | 29 | 2 | 2 | 4 | 3 | 3 | 3 | 315 | 15 | 4 | 4 | 1 | 0 | 0 | 1 | |
| 59 | 27 | 3 | 3 | 3 | 4 | 4 | 4 | 268 | 14 | 2 | 2 | 4 | 3 | 3 | 3 | |
| 125 | 27 | 5 | 5 | 5 | 5 | 6 | 5 | 304 | 13 | 5 | 5 | 5 | 5 | 6 | 5 | |
| 341 | 26 | 1 | 1 | 2 | 2 | 2 | 2 | 72 | 12 | 0 | 0 | 0 | 1 | 1 | 0 | |
| 79 | 20 | 3 | 3 | 3 | 4 | 4 | 4 | 383 | 12 | 0 | 0 | 0 | 1 | 1 | 0 | |
| 318 | 20 | 1 | 1 | 2 | 2 | 2 | 2 | 492 | 12 | 0 | 0 | 0 | 1 | 1 | 0 | |
| 207 | 18 | 1* | 1* | 1* | 0 | 0 | 1 | 29 | 11 | 0 | 0 | 0 | 1 | 1 | 0 | |
| 303 | 18 | 2 | 2 | 4 | 3 | 3 | 3 | 130 | 11 | 5 | 5 | 5 | 5 | 6 | 5 | |
| 150 | 17 | 2* | 2* | 2* | 2 | 3 | 2 | 180 | 11 | 0 | 0 | 0 | 1 | 1 | 0 | |
| 194 | 17 | 0 | 0 | 0 | 1 | 1 | 0 | 259 | 11 | 3 | 3 | 3 | 4 | 4 | 4 | |
| 364 | 16 | 3 | 3 | 3 | 4 | 4 | 4 | 444 | 11 | 6 | 6 | 6 | 6 | 5 | 6 | |
| 522 | 16 | 1 | 1 | 2 | 2 | 2 | 2 | 447 | 10 | 2 | 2 | 4 | 3 | 3 | 3 | |
图7比较了分辨率=0.5情况下, SLM算法与Louvain算法社团划分结果的不同, 在被引频次≥10的前26个节点中, 仅星号标注的点存在社团划分上的变化, 即n150、n207和n131。
论文n131(Visualizing a discipline: An author co-citation analysis of information science)和n207(Pathfinder networks and author cocitation analysis: A remapping of paradigmatic information scientists), 核心工作都是有关作者共引的研究, 对结果进行一定的可视化呈现。利用Louvain算法, 这两篇论文与另外三篇可视化算法和技术研究的论文(CiteSpace II: Detecting and visualizing emerging trends and transient patterns in scientific literature, Searching for intellectual turning points: Progressive knowledge domain visualization, Mapping the backbone of science)划分在同一个社团。而利用SLM算法, 论文n131和n207则与“The evolution of the intellectual structure of operations management-1980-2006: A citation/co- citation analysis”和“The intellectual structure of the strategic management field: An author co-citation analysis”划分在同一个社团, 这两篇论文的主题均是关于共引分析方法的研究。因此, 从结果角度分析, SLM算法的划分结果与论文的研究主题分布情况更加吻合。
论文n150(The simultaneous evolution of author and paper networks)的主题是有关作者和论文网络同步演化的研究, Louvain算法将其与“Citation statistics from 110 years of Physical Review”、“Measuring preferential attachment in evolving networks”、“Effect of aging on network structure”、“Modelling aging characteristics in citation networks” 4篇网络结构共性问题(如优先连接问题)研究的论文划分在同一社团。而SLM算法将其与有关学科领域可视化算法和技术研究的论文划分在同一社团。可见, n150在SLM算法中的社团划分结果更优。从这个角度而言, SLM算法的划分结果与实际情况更相符。
以上实证分析的小型网络节点均不超过1 000个, 为了在中型网络中比较几种社团划分算法的效用, 以基因编辑领域(以CRISPR为主题词进行检索)所有年份的575篇高被引文献为基础, 构建作者合作网络。数据下载时间为2018年6月4日。
该作者合作网络具有3 400个节点, 28 464条边, 平均路径长度较短为4.558, 且聚类系数高达0.931, 说明该合作网络具有小世界的特征。表6统计了三种算法在不同分辨率情况下针对无权网络和有权(基于合作论文数量)网络的社团划分情况。
表6 作者合作网络社团划分结果比较
| 分辨率 | Louvain | Louvain多级细分 | SLM | |||
|---|---|---|---|---|---|---|
| 未加权 | 加权 | 未加权 | 加权 | 未加权 | 加权 | |
| 0.1 | 123 | 125 | 123 | 125 | 124 | 124 |
| 0.2 | 127 | 130 | 127 | 130 | 131 | 131 |
| 0.3 | 131 | 133 | 132 | 131 | 133 | 135 |
| 0.4 | 135 | 134 | 136 | 135 | 135 | 135 |
| 0.5 | 138 | 139 | 138 | 140 | 138 | 139 |
| 0.6 | 137 | 140 | 140 | 141 | 139 | 141 |
| 0.7 | 141 | 145 | 141 | 142 | 141 | 144 |
| 0.8 | 140 | 143 | 141 | 143 | 143 | 144 |
| 0.9 | 146 | 144 | 144 | 147 | 146 | 146 |
| 1.0 | 144 | 147 | 148 | 148 | 148 | 151 |
Louvain算法未加权时在不同分辨率下的社团数量在123-144间变化, 极差为21。Louvain多级细分算法在不同分辨率下的社团数量在123-148间变化, 极差为25。SLM算法在不同分辨率下的社团数量在124-148间变化, 极差为24。可以看出三种算法在社团划分的波动范围上相差不大, 这也体现出三者的算法核心思想在本质上是一致的。
一般情况下, 分辨率越高, 划分的社团数量也越多。利用三种算法, 分辨率小于0.5时, 社团数量以较快的速率逐渐增加。而当分辨率大于0.5后, 对于加权网络与未加权网络而言, 社团数量总体依旧呈现上升趋势, 不过上升速率降低。多数情况下, SLM算法得到的社团数量略高于另外两种算法。
通过比较研究发现, Louvain算法、Louvain多级细分算法、SLM算法切实可用于划分拥有大量节点和边的合作网络及其引文网络。通过设定不同的分辨率值, 也可以获得不同精细水平的社团结果, 分辨率的设定越高, 获得的社团数量越多。根据实证比较分析结果可知, 分辨率值设定在0.5左右即可获得较好的社团划分效果。对合作网络而言, 可进一步考虑权重(即合作论文数量)的影响, 以获得不同的社团划分结果。
通过针对引文网络的实证分析比较发现, SLM算法的社团划分效果优于Louvain算法及其多级细分算法, 鉴于这三种算法的理论基础都是局域启发式移除算法(LMH), 也都是采用Q函数衡量社团划分结果, 因此, 建议研究人员在开展相关社团划分工作中优先选用SLM算法, 分辨率建议设定在0.5左右。
本文研究尚存在进一步深入的空间。例如, 在针对小型网络的实证中, 可以通过可视化形式观察具体节点在不同算法间被划分社团的移动情况, 进而深入到节点主题层面, 通过与社团内其他节点的主题进行比对, 判断社团划分的效果。而对中型网络而言, 涉及到社团迁移的节点非常多, 很难做到针对每个节点的主题衡量社团划分效果。此时需要引入更高效的方法开展社团划分效果的评估, 例如基于MeSH词表等进行相似度计算, 等等。
另外, 当前开展的引文网络社团划分并没有考虑每条引用边权重和方向的影响, 也就是说将所有的引用关系都视为等同。事实上, 引用目的、引用行为和习惯等都会对引文的重要性产生影响, 甚至有些引用是负面的批判性引用。在引文网络中, 文献之间的引用关系隐藏了大量知识与流动信息, 而节点本身也蕴含了丰富的信息。将所有引文都不加以区分, 划分的社团在反映真实结构属性时的效力就会下降。因此, 有必要考虑文本相似度、论文节点属性(如作者、机构和主题)、引用动机等对引文网络社团结构的影响, 需要在开展引文网络的社团划分时, 全方面考虑这些因素对引文网络进行加权, 再实现加权后的引文网络的社团划分。加权的引文网络社团划分方法, 将有利于提高引文网络社团划分的精准性, 更能真实反映学科结构和演化脉络, 对分析学科结构及其相关研究具有十分重要的意义。
同理, 合作网络虽然考虑了基于合作论文数量权重, 但并未考虑合作机构对论文贡献度的差异, 也没有考虑单篇论文中合作机构数量对合作边权重的影响, 因此, 还需对基于合作论文数量的权重加以优化和改良, 提高合作网络社团划分的准确性。
陈云伟: 提出研究思路, 设计研究方案, 采集、处理数据, 前两个实证分析, 撰写论文;
张瑞红: 修改论文, 完成第三个?实证分析。
所有作者声明不存在利益冲突关系。
支撑数据由作者自存储, E-mail: chenyw@clas.ac.cn。
[1] 陈云伟. 期刊-2013 Scientometrics- Mapping the Development of Scientometrics 1978-2010. 逐年网络文件.
[2] 陈云伟. citation evolv-2263. citation evolve.
| [1] |
Community Structure in Graphs [OL]. [2009-03-10]. . |
| [2] |
An Efficient Heuristic Procedure for Partitioning Graphs [J].https://doi.org/10.1002/bltj.1970.49.issue-2 URL [本文引用: 1] |
| [3] |
Algebraic Connectivity of Graphs [J]. |
| [4] |
Partitioning Sparse Matrices with Eigenvectors of Graphs [J].https://doi.org/10.1137/0611030 URL [本文引用: 1] 摘要
The problem of computing a small vertex separator in a graph arises in the context of computing a good ordering for the parallel factorization of sparse, symmetric matrices. An algebraic approach for computing vertex separators is considered in this paper. It is, shown that lower bounds on separator sizes can be obtained in terms of the eigenvalues of the Laplacian matrix associated with a graph. The Laplacian eigenvectors of grid graphs can be computed from Kronecker products involving the eigenvectors of path graphs, and these eigenvectors can be used to compute good separators in grid graphs. A heuristic algorithm is designed to compute a vertex separator in a general graph by first computing an edge separator in the graph from an eigenvector of the Laplacian matrix, and then using a maximum matching in a subgraph to compute the vertex separator. Results on the quality of the separators computed by the spectral algorithm are presented, and these are compared with separators obtained from other algorith...
|
| [5] |
Complex Networks: Structure and Dynamics [J].https://doi.org/10.1016/j.physrep.2005.10.009 URL [本文引用: 1] 摘要
Coupled biological and chemical systems, neural networks, social interacting species, the Internet and the World Wide Web, are only a few examples of systems composed by a large number of highly interconnected dynamical units. The first approach to capture the global properties of such systems is to model them as graphs whose nodes represent the dynamical units, and whose links stand for the interactions between them. On the one hand, scientists have to cope with structural issues, such as characterizing the topology of a complex wiring architecture, revealing the unifying principles that are at the basis of real networks, and developing models to mimic the growth of a network and reproduce its structural properties. On the other hand, many relevant questions arise when studying complex networks鈥 dynamics, such as learning how a large ensemble of dynamical systems that interact through a complex wiring topology can behave collectively. We review the major concepts and results recently achieved in the study of the structure and dynamics of complex networks, and summarize the relevant applications of these ideas in many different disciplines, ranging from nonlinear science to biology, from statistical mechanics to medicine and engineering.
|
| [6] |
三种经典复杂网络社区结构划分算法研究 [J].https://doi.org/10.3969/j.issn.1005-1228.2011.04.014 URL [本文引用: 1] 摘要
社团结构是复杂网络的重要特征之一。针对复杂网络中社团划分问题，文章给出了三种经典的社团划分算法，阐述了各种算法的基本原理，并对各算法进行了适当的分析和比较，为实际应用中社团划分算法的选择提供了参考。
The Research of Three Typical Community Detection Algorithmsin Complex Networks [J].https://doi.org/10.3969/j.issn.1005-1228.2011.04.014 URL [本文引用: 1] 摘要
社团结构是复杂网络的重要特征之一。针对复杂网络中社团划分问题，文章给出了三种经典的社团划分算法，阐述了各种算法的基本原理，并对各算法进行了适当的分析和比较，为实际应用中社团划分算法的选择提供了参考。
|
| [7] |
Newman M E J. Community Structure in Social and Biological Networks [J].https://doi.org/10.1073/pnas.122653799 URL PMID: 12060727 [本文引用: 2] 摘要
Abstract A number of recent studies have focused on the statistical properties of networked systems such as social networks and the Worldwide Web. Researchers have concentrated particularly on a few properties that seem to be common to many networks: the small-world property, power-law degree distributions, and network transitivity. In this article, we highlight another property that is found in many networks, the property of community structure, in which network nodes are joined together in tightly knit groups, between which there are only looser connections. We propose a method for detecting such communities, built around the idea of using centrality indices to find community boundaries. We test our method on computer-generated and real-world graphs whose community structure is already known and find that the method detects this known structure with high sensitivity and reliability. We also apply the method to two networks whose community structure is not well known--a collaboration network and a food web--and find that it detects significant and informative community divisions in both cases.
|
| [8] |
Fast Algorithm for Detecting Community Structure in Networks [J].https://doi.org/10.1103/PhysRevE.69.066133 URL [本文引用: 3] |
| [9] |
Finding and Evaluating Community Structure in Networks [J].https://doi.org/10.1103/PhysRevE.69.026113 URL [本文引用: 3] |
| [10] |
Fast Unfolding of Communities in Large Networks [J]. |
| [11] |
Multilevel Local Search Algorithms for Modularity Clustering [J].https://doi.org/10.1145/1963190.1970376 URL [本文引用: 2] 摘要
Modularity is a widely used quality measure for graph clusterings. Its exact maximization is NP-hard and prohibitively expensive for large graphs. Popular heuristics first perform a coarsening phase, where local search starting from singleton clusters is used to compute a preliminary clustering, and then optionally a refinement phase, where this clustering is improved by moving vertices between clusters. As a generalization, multilevel heuristics coarsen in several stages, and refine by moving entire clusters from each of these stages, not only individual vertices. This article organizes existing and new single-level and multilevel heuristics into a coherent design space, and compares them experimentally with respect to their effectiveness (achieved modularity) and runtime. For coarsening by iterated cluster joining, it turns out that the most widely used criterion for joining clusters (modularity increase) is outperformed by other simple criteria, that a recent multistep algorithm [Schuetz and Caflisch 2008] is no improvement over simple single-step coarsening for these criteria, and that the recent multilevel coarsening by iterated vertex moving [Blondel et al. 2008] is somewhat faster but slightly less effective (with refinement). The new multilevel refinement is significantly more effective than the conventional single-level refinement or no refinement, in reasonable runtime. A comparison with published benchmark results and algorithm implementations shows that multilevel local search heuristics, despite their relative simplicity, are competitive with the best algorithms in the literature.
|
| [12] |
A Smart Local Moving Algorithm for Large-scale Modularity-based Community Detection [J].https://doi.org/10.1140/epjb/e2013-40829-0 URL [本文引用: 6] 摘要
We introduce a new algorithm for modularity-based community detection in large networks. The algorithm, which we refer to as a smart local moving algorithm, takes advantage of a well-known local moving heuristic that is also used by other algorithms. Compared with these other algorithms, our proposed algorithm uses the local moving heuristic in a more sophisticated way. Based on an analysis of a diverse set of networks, we show that our smart local moving algorithm identifies community structures with higher modularity values than other algorithms for large-scale modularity optimization, among which the popular “Louvain algorithm”. The computational efficiency of our algorithm makes it possible to perform community detection in networks with tens of millions of nodes and hundreds of millions of edges. Our smart local moving algorithm also performs well in small and medium-sized networks. In short computing times, it identifies community structures with modularity values equally high as, or almost as high as, the highest values reported in the literature, and sometimes even higher than the highest values found in the02literature.
|
| [13] |
Louvain算法的并行化处理 [J].Parallel Processing of the Louvain Algorithm [J]. |
| [14] |
改进的Louvain社团划分算法 [J].https://doi.org/10.3969/j.issn.1001-0548.2012.06.022 URL [本文引用: 1] 摘要
社团划分在生物化学、社会学、生态系统等方面有广泛的应用。划分结果的可靠性和算法效率是研究的重点。Louvain算法是一个划分结果相对可靠、算法效率较高的算法。该文针对Louvain算法在处理叶节点方面进行了改进。通过研究叶节点的特性和Louvain算法的不足之处,在改进算法中基于叶节点特性进行提前剪枝,以避免多余运算。用改进算法和Louvain算法分别对18组人工数据和一组某个机构的实际邮件数据进行处理,将结果进行对比发现改进算法在保持划分结果准确度不变的情况下,有效地提高了处理速度。
Improved Algorithm of Louvain Communities Dipartition [J].https://doi.org/10.3969/j.issn.1001-0548.2012.06.022 URL [本文引用: 1] 摘要
社团划分在生物化学、社会学、生态系统等方面有广泛的应用。划分结果的可靠性和算法效率是研究的重点。Louvain算法是一个划分结果相对可靠、算法效率较高的算法。该文针对Louvain算法在处理叶节点方面进行了改进。通过研究叶节点的特性和Louvain算法的不足之处,在改进算法中基于叶节点特性进行提前剪枝,以避免多余运算。用改进算法和Louvain算法分别对18组人工数据和一组某个机构的实际邮件数据进行处理,将结果进行对比发现改进算法在保持划分结果准确度不变的情况下,有效地提高了处理速度。
|
| [15] |
改进的Louvain算法及其在推荐领域的研究 [J].https://doi.org/10.13274/j.cnki.hdzj.2017.11.032 URL [本文引用: 1] 摘要
文中在深入研究社区发现算法、个性化推荐技术和Spark集群实现技术的基础上,提出了基于叶子社区的社区发现算法和对应的个性化推荐设计方案。采用Scala语言,结合Spark Graph X图计算技术在Spark集群上实现该方案。与传统推荐技术相比,基于社区发现的个性化推荐方法在推荐效率以及正确度方面都得到大幅度提升。
Optimization of Louvain Algorithm and Its Application in Personalized Recommendation [J].https://doi.org/10.13274/j.cnki.hdzj.2017.11.032 URL [本文引用: 1] 摘要
文中在深入研究社区发现算法、个性化推荐技术和Spark集群实现技术的基础上,提出了基于叶子社区的社区发现算法和对应的个性化推荐设计方案。采用Scala语言,结合Spark Graph X图计算技术在Spark集群上实现该方案。与传统推荐技术相比,基于社区发现的个性化推荐方法在推荐效率以及正确度方面都得到大幅度提升。
|
| [16] |
An Information Flow Model for Conflict and Fission in Small Groups [J].
Data from a voluntary association are used to construct a new formal model for a traditional anthropological problem, fission in small groups. The process leading to fission is viewed as an unequal flow of sentiments and information across the ties in a social network. This flow is unequal because it is uniquely constrained by the contextual range and sensitivity of each relationship in the network. The subsequent differential sharing of sentiments leads to the formation of subgroups with more internal stability than the group as a whole, and results in fission. The Ford-Fulkerson labeling algorithm allows an accurate prediction of membership in the subgroups and of the locus of the fission to be made from measurements of the potential for information flow across each edge in the network. Methods for measurement of potential information flow are discussed, and it is shown that all appropriate techniques will generate the same predictions.
|
| [17] |
Community Structure of the Physical Review Citation Network [J].https://doi.org/10.1016/j.joi.2010.01.001 URL [本文引用: 1] 摘要
We investigate the community structure of physics subfields in the citation network of all Physical Review publications between 1893 and August 2007. We focus on well-cited publications (those receiving more than 100 citations), and apply modularity maximization to uncover major communities that correspond to clearly identifiable subfields of physics. While most of the links between communities connect those with obvious intellectual overlap, there sometimes exist unexpected connections between disparate fields due to the development of a widely applicable theoretical technique or by cross fertilization between theory and experiment. We also examine communities decade by decade and also uncover a small number of significant links between communities that are widely separated in time.
|
| [18] |
Scientific Collaboration Networks. II. Shortest Paths, Weighted Networks, and Centrality [J].https://doi.org/10.1103/PhysRevE.64.016132 URL PMID: 11461356 [本文引用: 1] 摘要
Using computer databases of scientific papers in physics, biomedical research, and computer science, we have constructed networks of collaboration between scientists in each of these disciplines. In these networks two scientists are considered connected if they have coauthored one or more papers together. Here we study a variety of nonlocal statistics for these networks, such as typical distances between scientists through the network, and measures of centrality such as closeness and betweenness. We further argue that simple networks such as these cannot capture variation in the strength of collaborative ties and propose a measure of collaboration strength based on the number of papers coauthored by pairs of scientists, and the number of other scientists with whom they coauthored those papers.
|
| [19] |
Evolving Collaboration Networks in Scientometrics in 1978-2010: A Micro-Macro Analysis [J].https://doi.org/10.1007/s11192-012-0895-2 URL [本文引用: 1] |
| [20] |
引文网络演化研究进展分析 [J].
从引文网络演化研究的发展史、 国际格局、 主题与功能三大角度， 对引文网络演化研究进展进行了综述性研究。采用的研究方法包括基于文献的计量和主路径分析， 以及对重要文献的解读和归纳。研究发现， 引文网络演化研究在 2008年以后迎来发展热潮； 重要主题包括知识扩散、 知识流与主路径分析， 科学结构与学科交叉分析，共引网络演化分析， 基于引文的评价研究， 宏观层面的科学或学科演化特征分析等。文章还从引文网络演化结构特征、 知识流、 技术路径、 科学结构演变、 评新方法和新应用进行了解读。价与预测五个角度对重要的研究成果进行了分析， 重点对新概念、
Development of Evolving Citation Network Analysis [J].
从引文网络演化研究的发展史、 国际格局、 主题与功能三大角度， 对引文网络演化研究进展进行了综述性研究。采用的研究方法包括基于文献的计量和主路径分析， 以及对重要文献的解读和归纳。研究发现， 引文网络演化研究在 2008年以后迎来发展热潮； 重要主题包括知识扩散、 知识流与主路径分析， 科学结构与学科交叉分析，共引网络演化分析， 基于引文的评价研究， 宏观层面的科学或学科演化特征分析等。文章还从引文网络演化结构特征、 知识流、 技术路径、 科学结构演变、 评新方法和新应用进行了解读。价与预测五个角度对重要的研究成果进行了分析， 重点对新概念、
|
/
| 〈 |
|
〉 |
