2019节点不对称转移概率的网络社区发现算法-许平华 , 胡文斌 , 邱振宇 , 聂聪 , 唐传慧 , 高旷 , 刘中舟.pdf

上善若水

296

17页

0次

2022-05-23

免费下载

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn

Journal of Software,2019,30(12):3829−3845 [doi: 10.13328/j.cnki.jos.005593] http://www.jos.org.cn

节点不对称转移概率的网络社区发现算法

∗

许平华

胡文斌

邱振宇

聂

聪

唐传慧

高

旷

刘中舟

(武汉大学计算机学院,湖北武汉 430072)

通讯作者: 胡文斌, E-mail: hwb@whu.edu.cn

摘要: 社区发现是当前社会网络研究领域的一个热点和难点,现有的研究方法包括:(1) 优化以网络拓扑结构为

基础的社区质量指标;(2) 评估节点间的相似性并进行聚类;(3) 根据特定网络设计相应的社区模型等.这些方法存

在如下问题:(1) 通用性不高,难以同时在无向网络和有向网络上发挥出好的效果;(2) 无法充分利用网络的结构信

息,在真实数据集上表现不佳.针对上述问题,提出一种基于节点不对称转移概率的网络社区发现算法 CDATP.该算

法通过分析网络拓扑结构来设计节点转移概率,并使用 random walk 方法评估节点对网络社区的重要性.最后,以重

要性较高的节点作为核心构造网络社区.与现有的基于 random walk 的方法不同,CDATP 为网络中节点设计的转移

概率具有不对称性,并只通过节点局部转移来评估节点对社区的重要程度.通过大量仿真实验表明,CDATP 在人工

模拟数据集和真实数据集上均比其他最新算法有更好的表现.

关键词: 复杂网络;社区结构;社区发现;随机游走;核心系数

中图法分类号: TP311

中文引用格式: 许平华, 胡文斌,邱振宇,聂聪,唐传慧, 高旷,刘中舟. 节点不对称转移概率的网络社区发现算法.软件学

报,2019,30(12):3829−3 845. http://www.jos.org.cn/1 000-9825/5593.htm

英文引用格式: Xu PH, Hu WB, Qiu ZY, Nie C, Tang CH, Gao K, Liu ZZ. A community detection algorithm based on

asymmetric transition probability of nodes. Ruan Jian Xue Bao/Journal of Software, 2019,30(12):3829−3845 (in Chinese).

http://www.jos.org.cn/1000-9825/5 593.htm

Community Detection Algorithm Based on Asymmetric Transition Probability of Nodes

XU Ping-Hua,

HU Wen-Bin,

QIU Zhen- Yu,

NIE Cong,

TANG Chuan-Hui,

GAO Kuang,

LIU Zhong-Zhou

(School of Computer Science, Wuhan University, Wuh an 430072, China)

Abstra ct : Community detection is a popular and difficult problem in the field of social network analysis. Most of the curr ent researches

mainly focus on optimizing the modularity index, evaluating the similarity of nodes, and designing different models to fit particular

networks. These approaches usually suffer from following problems: (1) just a few of them can deal with directed networks as well as

undirected networks; and (2) real-world networks being more complex than synthetic networks, many community detection strategies

cannot perform well in real-world networks. To solve these problems, this paper presents an algorithm for community detection in

complex networks based on random walk method. Different from existing methods based on random walk method, the asymmetric

transition probability is designed for the nodes according to network topology and other information. The event propagation law is also

applied to the evaluation of nodes i mportance. The algorith m CDATP performs well on both real-world n etworks and s ynthetic networks.

Key words: complex networks; community structure; community detection; random walk; core index

社会网络中的社区由网络中一定数量的节点组成,其内部有着较为紧密的结构.研究网络中的社区结构可

以帮助分析复杂网络、预测社会网络的发展趋势,而且在广告投放和作弊用户检测等实际场景中得到应用.

∗ 基金项目: 国家自然科学基金(61711530238, 61572369); 国家重点基础研究发展计划(973)(2012CB719905)

Foundation item: National Natural Science Foundation of China (61711530238, 61572369); National Program on Key Basic

Research Project of China (973) (201 2CB719905)

收稿时间: 2017-09-04; 修改时间: 2017-11-14, 2018-02-03; 采用时间: 2018-04-24

3830

Journal of Software 软件学报 Vol.30, No.12, December 2019

相关文献中已经有很多种社区发现方法被提出,其中一类是优化与图的拓扑结构相关联的社区质量指标,

例如由 Newman 等人

[1]

提出的模块度.基于优化指标数值来获得更加可靠的社区结构的这一思路,有很多学者

提出了相关的社区发现算法,其中较为典型的有优化变体模块度的 BiLPA 算法

[2]

、优化结构密度的 IsoFdp 算

法

[3]

和对混合指标进行优化的 EFA 算法

[4]

、MOCD-P SO 算法

[5]

等.这些算法一般是通过相应的迭代步骤来更新

需要优化的指标,并在最后输出最优指标对应的社区结构.这类算法的优点是实现简单,在人工构造的网络上可

以发挥出很好的效果.然而真实世界的网络要比人工构造的网络复杂许多,很多时候真实社区结构对应的质量

指标并不是最优的,导致了上述基于指标优化的算法难以正确地检测到社区.同时,由于上述部分算法是基于全

局拓扑结构来进行优化,因此会受到分辨率极限

[6]

的限制.并且,某些并不具有明显社区结构的网络同样会具有

很高的质量指标,例如某些树或类树结构

[7]

.因此,这些缺陷都在一定程度上限制了上述方法的应用场景.

另外有一些学者从节点相似性的角度提出了基于 random walk 的社区发现方法

[8−16]

,这类方法以马尔可夫

模型为理论基础,通常是通过节点的随机转移来评估节点的相似度,并将相似度较高的节点划分到同一社区中.

在真实网络中,同一社区质量指标与不同类型的社区结构的匹配程度变化较大,由此可能会导致基于社区质量

指标的社区发现算法适应性较弱,而基于 random walk 的算法受社区类型的影响较小,具有更好的适应性.但是,

基于“利用 random walk 来评价节点相似度”这一思路的社区发现算法对游走过程的迭代次数非常敏感,往往需

要先验知识来辅助决策.

将现实世界中的复杂系统抽象为图论中的网络虽然便于研究工作的开展,但也不可避免地会遗漏掉一些

重要的信息.例如,Reddit 中属于同一兴趣组的用户往往有着相同的兴趣标签,若能将属性信息转化为网络的一

部分,可能会使得社区内部的结构更加紧密,也能使处于社区边缘位置上的节点有更大概率被划分到正确的社

区中.然而,现有的仅从网络结构层面划分社区的算法无法利用节点的属性信息.

基于以上分析,本文提出了一种可用于无向和有向网络的社区发现算法 CDATP(community detection

algorithm based on asymmetric transition probability of nodes),此算法可以将节点的属性转化为拓扑结构的一部

分,并且受到事件在网络中的传播规律的启发,根据网络的拓扑结构计算每一节点向邻接节点转移的概率,以带

有限制的 random walk 来模拟逆向的事件传播过程,并以此为基础,评估节点在社区中的重要程度(核心系数).

在聚类时,无需预先指定社区的数目,节点会根据转移概率等参数向所属社区转移.本文的主要工作可以总结

如下:

(1) 充分利用了网络拓扑结构信息,为节点设计了不对称的转移概率,能够反映节点间的不对等关系;

(2) 参考了事件在网络中传播的规律,提出一种基于 random walk 且具有固定转移步长的方法来评估节

点对于社区的重要程度,基于该重要程度指标的聚类不需要预先指定社区数目.

本文第 1 节介绍相关研究工作.第 2 节详细介绍 CDA

TP 算法.第 3 节为实验和分析.第 4 节是总结与展望.

1 相关工作

近年来,普遍存在于网络中的社区结构已经受到了国内外学者的广泛关注.关于社区发现的研究也已经被

应用到了许多领域中,并取得了不错的成果.

基于社区质量指标来划分社区是一类很经典的方法,这类方法通常先定义一个基于网络拓扑结构的社区

质量指标,若一种社区划分与预先定义的质量指标的“含义”越接近(如社区内部的边数远多于社区边缘上的边

数),那么该社区划分的得分越高.这类方法的优点是思路简洁明了,在确定了质量指标后只需通过一系列迭代

运算来搜索最优社区划分.但同时,如何确定社区质量指标也成了最大的问题.因为若一个社区质量指标不能较

好地体现真实社区的“含义”,或者说一种社区划分得分很高但却与真实社区结构相差甚远,那么基于该质量指

标的后续工作都将变得没有意义.经过长时间的研究,学者们提出了一些表现较好的经典社区质量指标,包括结

构密度和模块度等.结构密度的大小和社区内部边的数量与社区内部节点的数量比值相关,一般来说,结构较为

紧密的社区对应的结构密度较大.You 等人

[3]

提出的 IsoFdp 算法将网络数据映射到低维空间并自动找出社区的

中心节点,然后再以中心节点为基础建立社区,并通过对结构密度的优化来搜索更好的社区划分.相较于传统的

of 17

免费下载

软件学报计算机技术

关注

评论