针对有向图的局部扩展的重叠社区发现算法

被引：7

作者：

张海燕 ^{[1
,2
]}

梁循 ^{[1
]}

周小平 ^{[1
]}

机构：

[1] 中国人民大学信息学院

[2] 宁夏大学数学计算机学院

来源：

数据采集与处理 | 2015年 / 30卷 / 03期

基金：

北京市自然科学基金;

关键词：

有向图; 社区发现; 共社区邻近相似性; 带权无向图; 重叠社区;

D O I：

10.16337/j.1004-9037.2015.03.025

中图分类号：

O157.5 [图论];

学科分类号：

070104 ;

摘要：

当前社区发现算法主要是针对无向图研究社区结构,但在实际复杂网络中,链接关系时常表现出非对称性或方向性,比如Twitter的用户关注关系,文献网络的引用关系,网页之间的超链接关系等应用网络。因此,本文依据信息在复杂网络中的传播规律和流动方向性,提出了k-Path共社区邻近相似性概念及计算方法,用于衡量结点在同一社区的相似性程度,并给出了把有向图转换为带方向权值的无向图的方法。基于带权无向图提出了一种从局部扩展来探测社区的重叠社区发现算法(Local and wave-like extension algorithm of detecting overlapping community,LWS-OCD)。在真实数据集上的实验表明,共社区邻近相似性概念实现了有向到无向的合理转换,而且提高了社区结点的聚集效果,LWSOCD算法能够有效地发现带权无向图中的重叠社区。

引用

页码：683 / 693

页数：11

共 16 条

[1]

Uncovering the overlapping community structure of complex networks in nature and society. Palla Gergely,Derényi Imre,Farkas Illés,Vicsek Tamás. Nature . 2005

[2]

The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations[J] . David Lusseau,Karsten Schneider,Oliver J. Boisseau,Patti Haase,Elisabeth Slooten,Steve M. Dawson. &nbspBehavioral Ecology and Sociobiology . 2003 (4)

[3]

Finding and evaluating community structure in networks. Newman M E J,Girvan M. Physical Review . 2004

[4]

Detecting the overlapping and hierarchical community structure in complex networks. LANCICHINETTI A,FORTUNATO S,KERT J. New Journal of Physics . 2009

[5]

An algorithm to find overlapping community structure in networks. S. Gregory. Knowledge Discovery in Databases: PKDD 2007 . 2007

[6]

An algorithm to find overlapping community structure in networks. S. Gregory. Knowledge Discovery in Databases: PKDD 2007 . 2007

[7]

Symmetrizations for clustering directed graphs. Satuluri V,Parthasarathy S. Proceedings of the 14th International Conference on Extending Database Technology . 2011

[8]

Networks, Crowds, and Markets: Reasoning About a HighlyConnected World. Easley D,Kleinberg J. Journal of Women s Health . 2010

[9] 一种自适应网络舆情演化建模方法 [J].

周耀明 ;

李弼程 .

数据采集与处理, 2013, 28 (01) :69-76

[10] 复杂网络的社区结构 [J].

程学旗 ;

沈华伟 .

复杂系统与复杂性科学, 2011, 8 (01) :57-70

← 1 2 →