Overlapping community detection in complex networks based on multi kernel label propagation

Kun DENG; Wen-ping LI; Fa-hong YU; Jian-pei ZHANG

doi:10.11959/j.issn.1000-436x.2017028

您当前的位置：

首页 >

文章列表页 >

Overlapping community detection in complex networks based on multi kernel label propagation

Papers | 更新时间：2024-06-05

- Overlapping community detection in complex networks based on multi kernel label propagation
- Journal on Communications Vol. 38, Issue 2, Pages: 53-66(2017)
- 作者机构：
  
  1. 嘉兴学院数理与信息工程学院，浙江嘉兴 314001
  2. 哈尔滨工程大学计算机科学与技术学院，黑龙江哈尔滨 150001
- 作者简介：
- 基金信息：
  
  The National Natural Science Foundation of China(61672179);The National Natural Science Foundation of China(61370083);The National Natural Science Foundation of China(61402126);The Hu-manity and Social Science Youth Foundation of Ministry of Education of China(15YJCZH088);Zhejiang Provincial Natural Science Foundation of China(LY16F020027);Zhejiang Provincial Education Department Research Foundation of China(Y201636127);Zhejiang Provincial Education Department Research Foundation of China(Y201533771)
- DOI：10.11959/j.issn.1000-436x.2017028
  CLC： TP391
- Online First：2017-02，
  
  Published：25 February 2017
- 稿件说明：
移动端阅览
Kun DENG, Wen-ping LI, Fa-hong YU, et al. Overlapping community detection in complex networks based on multi kernel label propagation[J]. Journal on Communications, 2017, 38(2): 53-66.
DOI：

Kun DENG, Wen-ping LI, Fa-hong YU, et al. Overlapping community detection in complex networks based on multi kernel label propagation[J]. Journal on Communications, 2017, 38(2): 53-66. DOI： 10.11959/j.issn.1000-436x.2017028.

摘要

针对传统基于标签传播的重叠社区识别方法存在较强的随机性，以及需要预设相关阈值来辅助完成社区识别等缺陷，提出基于多核心标签传播的重叠社区识别方法(OMKLP)。在分析节点度以及节点与邻居节点的局部覆盖密度后提出核心节点评价模型，并在此基础上给出局部核心节点识别方法；基于局部核心节点，提出新的面向重叠社区的异步标签传播策略，该策略能够快速地识别出社区内部节点与边界节点，以获得重叠社区结构；提出重叠节点分析方法，进一步提高识别重叠节点准确度。OMKLP 算法无需掌握任何先验知识，仅在掌握网络基本信息(点、边)基础上，便能够准确识别出重叠社区结构，从而有效解决了传统标签传播算法所存在的缺陷。在基准网络和真实网络上进行测试，并与多个经典算法进行对比分析，实验结果验证了所提算法的有效性和可行性。

Abstract

In view of the strong randomness and pre-setting the related threshold of traditional overlapping community detection method based on label propagation

overlapping community detection in complex networks based on multi kernel label propagation (OMKLP) was proposed.Evaluation model of kernel nodes was proposed after analyzing the node's degree and local covering density of nodes and their neighbor nodes.And on this basis

the detection method of local kernel nodes was also presented.Based on local kernel nodes

a new asynchronous label propagation strategy ori-ented to overlapping community was proposed

which can rapidly distinguish inner nodes and outer nodes of communi-ties so as to obtain overlapping community structure.The analysis method of overlapping nodes was proposed to increase the accuracy of detecting overlapping nodes.Without any prior knowledge

only on the basis of the basic network infor-mation (nodes and links)

the algorithm can detect the structure of overlapping communities accurately.Therefore

it ef-fectively solved the defect of the traditional label propagation algorithm.The algorithm was tested over benchmark net-works and real-world networks and also compared with some classic algorithms.The experiment results verify the valid-ity and feasibility of OMKLP.

关键词

Keywords

references

WATTS D J , STROGATZ S H . Collective dynamics of “small-world”networks [J ] . Nature , 1998 , 393 ( 84 ): 440 - 442 .

BARABÁSI A L , ALBERT R . Emergence of scaling in random networks [J ] . Science , 1999 , 286 ( 5439 ): 509 - 512 .

金弟 , 刘大有 , 杨博 , 等 . 基于局部探测的快速复杂网络聚类算法 [J ] . 电子学报 , 2011 , 39 ( 11 ): 2540 - 2546 .

JIN D , LIU D Y , YANG B , et al . Fast complex network clustering algorithm using local detention [J ] . Acta Electronica Sinica , 2011 , 39 ( 11 ): 2540 - 2546 .

WANG Z , ZHANG J . In search of the biological significance of modular structures in protein networks [J ] . Plos Computational Biology , 2007 , 3 ( 6 ): 1011 - 1021 .

FARUTIN V , ROBISON K , LIGHTCAP E , et al . Edge-count probabilities for the identification of local protein communities and their organization [J ] . Proteins Structure Function and Bioinformatics , 2006 , 62 ( 3 ): 800 - 818 .

QIAN C , CAO J D , LU J Q , et al . Adaptive bridge control strategy for opinion evolution on social networks [J ] . Chaos:An Interdisciplinary Journal of Nonlinear Science , 2011 , 21 ( 2 ):025116

SIDIROPOULOS A , PALLIS G , KATSAROS D , et al . Prefetching in content distribution networks via web communities identification and outsourcing [J ] . World Wide Web , 2008 , 11 ( 1 ): 39 - 70 .

NEWMAN M E J , GIRVAN M . Finding and evaluating community structure in networks [J ] . Physical Review E , 2004 , 69 ( 2 ):026113.

NEWMAN M E J . Fast algorithm for detecting community structure in networks [J ] . Physical Review E , 2004 , 69 ( 6 ):066133.

BLONDEL V D , GUILLAUME J L , LAMBIOTTE R , et al . Fast unfolding of communities in large networks [J ] . Journal of Statistical Mechanics Theory and Experiment , 2008 , 10 :10008.

RAGHAVAN U N , ALBERT R , KUMARA S . Near linear time algorithm to detect community structures in large-scale networks [J ] . Physical Review E , 2007 , 76 ( 3 ):036106

PALLA G , DERÉNYI I , FARKAS I , et al . Uncovering the overlapping community structure of complex networks in nature and society [J ] . Nature , 2005 , 435 ( 7043 ): 814 - 818 .

SHEN H W , CHENG X Q , GUO J F . Quantifying and identifying the overlapping community structure in networks [J ] . Journal of Statistical Mechanics-Theory and Experiment , 2009 , 53 ( 7 ):07042.

ZHANG Z W , WANG Z Y . Mining overlapping and hierarchical communities in complex networks [J ] . Physica A:Statistical Mechanics and its Applications , 2015 , 421 : 25 - 33 .

AHN Y Y , BAGROW J P , LEHMANN S . Link communities reveal multiscale complexity in networks [J ] . Nature , 2010 , 466 ( 7307 ): 761 - 764 .

MENG F , ZHANG F , ZHU M , et al . Incremental density-based link clustering algorithm for community detection in dynamic networks [J ] . Mathematical Problems in Engineering , 2016 , 2016 ( 6 ): 1 - 11 .

KIM P , KIM S . Detecting overlapping and hierarchical communities in complex network using interaction-based edge clustering [J ] . Physica A:Statistical Mechanics and its Applications , 2015 , 417 : 46 - 56 .

LANCICHINETTI A , FORTUNATO S , KERTESZ J . Detecting the overlapping and hierarchical community structure in complex networks [J ] . New Journal of Physics , 2009 , 11 ( 3 ):033015.

WANG M , YANG S , WU L . Improved community mining method based on LFM and EAGLE [J ] . Computer Science and Information Systems , 2016 , 13 ( 2 ): 515 - 530 .

CAO X , WANG X , JIN D , et al . The (un)supervised detection of overlapping communities as well as hubs and outliers via (bayesian) NMF [C ] // International Conference on World Wide Web Companion . 2014 : 233 - 234 .

常振超 , 陈鸿昶 , 黄瑞阳 , 等 . 基于非负矩阵分解的半监督动态社团检测 [J ] . 通信学报 , 2016 , 37 ( 2 ): 132 - 142 .

CHANG Z C , CHEN H C , HUANG R Y , et al . Semi-supervised dynamic community detection bused on nonnegative matrix factoriza-tion [J ] . Journal on Communications , 2016 , 37 ( 2 ): 132 - 142 .

HE D , WANG H , JIN D , et al . A model framework for the enhancement of community detection in complex networks [J ] . Physica A Statistical Mechanics ＆ Its Applications , 2016 , 461 : 602 - 612 .

GREGORY S . Finding overlapping communities in networks by label propagation [J ] . New Journal of Physics , 2010 , 12 ( 10 ):103018.

XIE J R , SZYMANSKI B K , LIU X . Slpa:uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process [C ] // IEEE ICDM Workshop on DMCCI . IEEE,Vancouver,Canada , 2011 : 344 - 349 .

CHEN Q , WU T T . A method for local community detection by finding maximal-degree nodes [C ] // 9th International Conference on Machine Learning and Cybernetics . 2010 : 8 - 13 .

ZHANG T , WU B . A method for local community detection by finding core nodes [C ] // International Conference on Advances in Social Networks Analysis and Mining,IEEE . Istanbul,Turkey , 2012 : 1171 - 1176 .

LEUNG I X , HUI P LIÒ P , et al . Towards real-time community detection in large networks [J ] . Physical Review E , 2009 , 79 ( 2 ): 853 - 857 .

XIE J , KELLEY S , SZYMANSKI B K . Overlapping community detection in networks:the state of the art and comparative study [J ] . Acm Computing Surveys , 2011 , 45 ( 4 ): 115 - 123 .

LANCICHINETTI A , FORTUNATO S , RADICCHI F . Benchmark graphs for testing community detection algorithms [J ] . Physical Review E , 2008 , 78 ( 4 ):046110.

ZACHARY W W . An information flow model for conflict and fission in small groups [J ] . Journal of Anthropological Research , 1977 , 33 ( 4 ): 452 - 473 .

LUSSEAU D . The emergent properties of a dolphin social network [J ] . Proceedings of the Royal Society B:Biological Sciences , 2003 , 270 ( S2 ): 186 - 188 .

KNUTH D E . The Stanford graphbase:a platform for combinatorial computing [EB/OL ] . http://www-cs-faculty.stanford.edu/～uno/sgb.html http://www-cs-faculty.stanford.edu/～uno/sgb.html .

NEWMAN M E J . Modularity and community structure in networks [J ] . Proceedings of the National Academy of Science , 2006 , 103 ( 23 ): 8577 - 8582 .

GUIMERA R , DANON L DIAZ-GUILERA A , et al . Self-similar community structure in a network of human interactions [J ] . Physical Review E , 2003 , 68 ( 6 ):065103.

NEWMAN M E J . Network data from mark Newman's home page [EB/OL ] . http://www-personal.umich.edu/～mejn/netdata/ http://www-personal.umich.edu/～mejn/netdata/ .

NEWMAN M E J . Finding community structure in networks using the eigenvectors of matrices [J ] . Physical review E , 2006 , 74 ( 3 ):036104.

BOGUÑÁ M , PASTOR-SATORRAS R , DÍAZ-GUILERA A , et al . Models of social networks based on social distance attachment [J ] . Physical Review E , 2004 , 70 ( 5 ):056122. 056 - 122 .

Views

1469

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Community detection algorithm based on local affinity propagation and user profile

Analysis on IP-based density of Internet

Related Author

Kun GUO

Wen-zhong GUO

Qi-rong QIU

Qi-shan ZHANG

XU Ye

ZHAO Hai

SU Wei-ji

ZHANG Wen-bo

Related Institution

College of Mathematics and Computer Science, Fuzhou University

Management School,Fuzhou University

China First Node of CAIDA, Northeastern University

. of Embedded Technology, Northeastern University, Shenyang

Northeastern Networks Center of CERNET

AI问答

⁰