基于贡献函数的重叠社区划分算法

刘功申; 孟魁; 郭弘毅; 苏波; 李建华

doi:10.11999/JEIT161109

基于贡献函数的重叠社区划分算法

doi: 10.11999/JEIT161109

基金项目:

国家973关键技术研究项目(2013CB329603)，国家自然科学基金(61472248)

计量
- 文章访问数: 514
- HTML全文浏览量: 67
- PDF下载量: 392
- 被引次数: 0
出版历程
- 收稿日期: 2016-10-18
- 修回日期: 2017-04-24
- 刊出日期: 2017-08-19

Overlapping-communities Recognition Algorithm Based on Contribution Function

Funds:

The National 973 Key Basic Research Program of China (2013CB329603), The National Natural Science Foundation of China (61472248)

摘要

摘要: 现实世界中的网络结构呈现出重叠社区的特征。在研究经典的标签算法的基础上，该文提出基于贡献函数的重叠社区发现算法。算法将每个节点用三元组(阈值、标签、从属系数)集合来表示。节点的阈值是每次迭代过程中标签淘汰的依据，该值由多元线性方程自动计算而来。从属系数用于衡量当前节点与标签所标识社区的相关度，从属系数的值越大说明该节点与标签所标识社区的关联性越强。在每一次迭代的过程中，算法依据贡献函数计算每个节点的从属系数，并生成新的三元组集合。然后依据标签决策规则淘汰标签，进行从属系数规范化。通过对真实的复杂网络和LFR(Lancichinetti Fortunato Radicchi)自动生成的网络进行测试可知，该算法的社区划分准确率高，而且划分结果稳定。
- 复杂网络 /
- 社区发现 /
- 重叠社区
Abstract: Overlapping is one of the most important characteristics of real-world networks. Based on the classic labeling algorithm, the overlapping-community orientated label propagation algorithm based on contribution function is proposed. In this algorithm, each node is indicated by a set of triples (threshold, label, and coefficient). The threshold value of every node is used as a metric for labels decision, which is calculated automatically by multiple linear regression equation. The dependent coefficient is used to measure the relevance of the current node with the correspondent community which is marked by the label. A greater value of dependent coefficient means a stronger association between the node and the community. During each iteration process, the dependent coefficients are calculated through Contribution Function (CF) of each node, and new triples are produced. Then the labels in terms of decision rules are selected, and the dependent coefficients of the node are normalized. According to the tests with real-world networks and automatic generation of LFR (Lancichinetti Fortunato Radicchi) test network, the algorithm can divide communication with high accuracy and robust result.
- Complex networks /
- Communities detecting /
- Overlapping communities

HTML全文

参考文献(15)

[1]	WANG Xiaofeng, LIU Gongshen, PAN Li, et al. Uncovering fuzzy communities in networks with structural similarity[J]. Neurocomputing, 2016, 210(1): 26-33.
[2]	PALLA G, DERENVI I, FARKAS I, et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005, 435(7043): 814-818.
[3]	LEE C, REID F, McDAID A, et al. Detecting highly overlapping community structure by greedy clique expansion [C]. ACM International Conference on Paper Presented at SNA-KDD Workshop, Washington DC, USA, 2010. arXiv: 1002.1827.
[4]	GREGORY S. An algorithm to find overlapping community structure in networks[J]. LNCS, 2007, 4702(12): 91-102.
[5]	SHI Xiaohua. Community detection in social network with pair wisely constrained symmetric non-negative matrix factorization[C]. Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, Paris, France, 2015: 541-546.
[6]	LIU Xiao, WEI Yiming, WANG Jian, et al. Community detection enhancement using no-negative matrix factorization with graph regularization[J]. International Journal of Modern Physics B, 2016, 30(20): 1650130.
[7]	WANG Zhaoxian, WANG Wenjun, XUE Guixiang, et al. Semi-supervised community detection framework based on non-negative factorization using individual labels[C], The Sixth International Conference on Swarm Intelligence, Beijing, China, 2015, 349-359
[8]	RAGHAVAN U N, ALBERT R, and KUMARA S. Near linear time algorithm to detect community structures in large-scale networks[J]. Physical Review E Statistical Nonlinear Soft Matter Physics, 2007, 76(3 Pt 2):036106.
[9]	GREGORY S. Finding overlapping communities in networks by label propagation[J]. New Journal of Physics, 2009, 12(10): 2011-2024.
[10]	ULRIK B. A faster algorithm for betweenness centrality[J]. Journal of Mathematical Sociology, 2001, 25(2): 163-177.
[11]	EPPSTEIN D and WANG J. Fast approximation of gentrality[J]. Journal of Graph Algorithms and Applications, 2004, 8(1): 39-45.
[12]	KLEINBERG J M. Authoritative sources in a hyperlinked environment[J]. Journal of the ACM (JACM), 1999, 46(5): 604-632.
[13]	NICOSIA V, MANGIONI G, CARCHIOLO V, et al. Extending the definition of modularity to directed graphs with overlapping communities[J]. Journal of Statistical Mechanics Theory Experiment, 2009, 2009(3): 3166-3168.
[14]	LANCICHINETTI A, FORTUNATO S, and RADICCHI F. Benchmark graphs for testing community detection algorithms[J]. Physical Review E Statistical Nonlinear Soft Matter Physics, 2008, 78(2): 046110.
[15]	CAO Xiaochun, WANG Xiao, JIN Di, et al. Identifying overlapping communities as well as hubs and outliers via nonnegative matrix factorization[J]. Scientific Reports, 2013, 03: 2993. doi: 10.1038/srep02993.

相关文章(20)

[1]	王凯, 李星, 兰巨龙, 卫红权, 刘树新. 一种基于资源传输路径拓扑有效性的链路预测方法, 电子与信息学报. doi: 10.11999/JEIT190333
[2]	杨书新, 梁文, 朱凯丽. 基于三级邻居的复杂网络节点影响力度量方法, 电子与信息学报. doi: 10.11999/JEIT190440
[3]	张震, 刘迪洋, 张进, 谢记超. 基于节点冗余容量动态控制的复杂网络鲁棒性研究, 电子与信息学报. doi: 10.11999/JEIT200185
[4]	许宇光, 蒋飞, 朱恩强, 潘惊治, 谢惠扬. 基于个体稳定度博弈的动态社区发现算法研究, 电子与信息学报. doi: 10.11999/JEIT161077
[5]	李帆, 丁锦, 沈耿彪, 赵建辉. 基于复杂网络理论的编队电磁兼容网络优化, 电子与信息学报. doi: 10.11999/JEIT160494
[6]	孙昱, 姚佩阳, 张杰勇, 付凯. 基于优化理论的复杂网络节点攻击策略, 电子与信息学报. doi: 10.11999/JEIT160396
[7]	汪晓锋, 刘功申, 李建华. 基于模糊聚类的多分辨率社区发现方法, 电子与信息学报. doi: 10.11999/JEIT161116
[8]	张云雷, 吴斌, 刘宇. 一种新的基于粗糙集K-均值的社区发现方法, 电子与信息学报. doi: 10.11999/JEIT160516
[9]	刘宇, 吴斌, 曾雪琳, 张云雷, 王柏. 一种基于社交网络社区的组推荐框架, 电子与信息学报. doi: 10.11999/JEIT160544
[10]	刘树新, 季新生, 刘彩霞, 汤红波, 巩小锐. 局部拓扑信息耦合促进网络演化, 电子与信息学报. doi: 10.11999/JEIT151338
[11]	杜洪越, 李春双, 公利滨. 两个带有已知或未知参数的复杂网络的改进函数投影同步, 电子与信息学报. doi: 10.11999/JEIT150864
[12]	韩祺祎, 任梦吟, 文红. 基于拓扑势的P2P社区推荐信任模型, 电子与信息学报. doi: 10.11999/JEIT141303
[13]	汪涛, 刘阳, 席耀一. 基于图正则化非负矩阵分解的二分网络社区发现算法, 电子与信息学报. doi: 10.11999/JEIT141649
[14]	邓志宏, 老松杨, 白亮. 基于预测误差修正的时序链路预测方法, 电子与信息学报. doi: 10.3724/SP.J.1146.2013.00657
[15]	刘阳, 季新生, 刘彩霞. 一种基于边界节点识别的复杂网络局部社区发现算法, 电子与信息学报. doi: 10.3724/SP.J.1146.2013.01955
[16]	郭进时, 汤红波, 王晓雷. 基于社会网络增量的动态社区组织探测, 电子与信息学报. doi: 10.3724/SP.J.1146.2012.01590
[17]	刘阳, 季新生, 刘彩霞. 网络社区发现优化：基于随机游走的边权预处理方法, 电子与信息学报. doi: 10.3724/SP.J.1146.2012.01676
[18]	李春芳, 刘连忠, 刘振国. 数据库复杂网络构造算法及特征分析, 电子与信息学报. doi: 10.3724/SP.J.1146.2012.00491
[19]	肖觅, 孟祥武, 史艳翠. 一种基于移动用户行为的回路融合社区发现算法, 电子与信息学报. doi: 10.3724/SP.J.1146.2012.00331
[20]	史圣卿, 陈凯, 汪玉, 罗嵘. 基于FPGA的稀疏网络关键节点计算的硬件加速方法研究, 电子与信息学报. doi: 10.3724/SP.J.1146.2011.00363