计算机科学 ›› 2019, Vol. 46 ›› Issue (12): 45-55.doi: 10.11896/jsjkx.190700051

• 大数据与数据科学 • 上一篇    下一篇

带偏置的信号传播的随机游走的社团检测算法

尹欣红, 赵世燕, 陈晓云   

  1. (兰州大学信息科学与工程学院 兰州730000)
  • 收稿日期:2019-05-05 出版日期:2019-12-15 发布日期:2019-12-17
  • 通讯作者: 陈晓云(1954-),女,硕士,教授,博士生导师,CCF高级会员,主要研究方向为数据挖掘、大数据分析、网络信息挖掘等,E-mail:chenxy@lzu.edu.cn。
  • 作者简介:尹欣红(1993-),女,硕士生,主要研究方向为复杂网络社团检测;赵世燕(1994-),女,硕士生,主要研究方向为复杂网络社团检测。

Community Detection Algorithm Based on Random Walk of Signal Propagation with Bias

YIN Xin-hong, ZHAO Shi-yan, CHEN Xiao-yun   

  1. (School of Information Science and Engineering,Lanzhou University,Lanzhou 730000,China)
  • Received:2019-05-05 Online:2019-12-15 Published:2019-12-17

摘要: 复杂网络是从大量现实存在的复杂系统中抽象得到的,网络的整体功能体现在网络中节点间的相互作用上,社团结构是其关键性结构特征。社团对应于系统的功能模块,提取网络的功能模块有助于深层探究复杂网络的内部规律,从复杂网络中检测社团结构具有重要的理论研究意义和实用价值。因此,很多研究者对社团检测进行了研究,进而提出了很多社团检测算法,如基于模块度优化的社团检测算法、基于标签传播的社团检测算法、基于随机游走的社团检测算法等。在对这些算法进行充分研究的基础上,通过模拟随机游走的过程,结合信号传播过程中随着传播距离的增大,信号量会缓慢衰减的思想,提出了一种带偏置的信号传播机制的随机游走的社团检测算法。该算法从网络中选取一个节点作为信号源,随机选择与其相邻的节点作为下一跳节点,将衰减后的信号量传递到该节点,依次迭代并传递信号。考虑到信号的衰减,为每条边设置偏置,对信号传播过程进行限定。通过模拟信号的传播,将网络的每个顶点作为信号源来重复这一过程,得到传播矩阵。然后,为每个顶点添加自环,并结合邻接矩阵以及顶点间的相似性,形成具有新属性的相似性矩阵。根据新属性矩阵和传播矩阵为每个顶点构造属性。最后,使用k-means算法进行聚类,得到高质量的社团结构。为了验证该方法的性能,在10个实际网络数据集以及不同规模的人工合成网络上进行实验。实验结果充分证明,所提算法能够从网络中提取出高质量的社团结构,从而有效地为社团检测领域提供依据。

关键词: 社团检测, 偏置, 随机游走, 信号传播, 社团结构

Abstract: Complex networks are abstracted from various complex systems.The overall function is reflected in the interaction among nodes,and community structure is one of the most significant structural properties presented in many networks.Generally,the community corresponds to the functional modules of the system.Therefore,extracting these communities of the network helps us to explore the internal rules,and it has important theoretical research significance and practical value for community detection of complex networks.As a result,it is paid attention widely by many resear-chers,and many community-detection algorithms are proposed,such as the algorithms based on modularity optimization,label propagation,and random walk.In the process of signal propagation,as the propagation distance increases,the signal quantity will decay slowly.On the basis of the full study of these algorithms,by simulating the process of random walk,a community detection algorithm with random walk based on the signal propagation mechanism with bias was proposed.The algorithm selects a node from the network as the signal source,chooses the neighbor node randomly as the next hop node,transmits the attenuated semaphore to the node,and iteratively selects the next hop node and transmits the signal randomly.Considering the attenuation of the signal,an attenuation factor is attached to each edge to constrain the signal propagation process.Through the propagation of the analog signal,each process of the network is repeated as a signal source to obtain a propagation matrix.Then,the self-loop is added for each vertex.By considering the similarity matrix with new attributes between the adjacency matrix and the similarity among vertices,attributes for each vertex are constructed based on the new attribute matrix and propagation matrix.Finally,k-means algorithm is used for clustering to obtain high-quality community structure.In the end,k-means algorithm is used for clustering to obtain high-quality community structure with the minimum cost.In order to verify the performance of this method,this paper conducted experiments on 10 actual network data sets and artificial synthetic networks of different sizes.The experimental results fully prove that this algorithm can extract high-quality community structure from the network,thus effectively providing a basis for community detection field.

Key words: Community detection, Bias, Random walk, Signal propagation, Community structure

中图分类号: 

  • TP311
[1] ZACHARY W W.An information flow model for conflict and fission in small groups [J].Journal of Anthropological Research,1977,33(4):452-473.
[2] LEI X J,WANG F,WU F X,et al.Protein complex identification through markov clustering with firefly algorithm on dynamicproteinprotein interaction networks[J].Information Sciences,2016,329(6):303-316.
[3] ATAY Y,KOC I,BABAOGLU I,et al.Community detection from biological and social networks:A comparative analysis of metaheuristic algorithms [J].Applied Soft Computing,2017,50:194-211.
[4] FORTUNATO S,HRIC D.Community detection in networks:a user guide [J].Physics Reports,2016,659:1-44.
[5] NEWMAN M E.The structure of scientific collaboration networks [J].Proceedings of the National Academy of Sciences of the United States of America,2001,98(2):404-409.
[6] MARK E J N,GIRVAN M.Finding and evaluating community structure in networks[J].Physical Review E,2004,69(2):026113.
[7] SINGH A,HUMPHRIES M D .Finding communities in sparse networks [J].Scientific Reports,2015,5(1):8828.
[8] LEWIS A C F,JONES N S,PORTER M A,et al.The function of communities in protein interaction networks at multiple scales [J].BMC Systems Biology,2010,4(1):100.
[9] BEDI P,SHARMA C.Community detection in social networks [J].Wiley Interdisciplinary Reviews:Data Mining and Know-ledge Discovery,2016,6(3):115-135.
[10] GIRVAN M,NEWMAN M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences,2002,99(12):7821-7826.
[11] KERNIGHAN B W,LIN S.An efficient heuristic procedure for partitioning graphs [J].The Bell System Technical Journal,1970,49(2):291-307.
[12] FIEDLER M.Laplacian of graphs and algebraic connectivity [J].Banach Center Publications,1989,25(1):57-70.
[13] URSCHEL J C,ZIKATANOV L T.Spectral bisection of graphs and connectedness [J].Linear Algebra and its Applications,2014,449:1-16.
[14] DONATH W E,HOFFMAN A J.Lower bounds for the partitioning of graphs [C]//Selected Papers of Alan J Hoffman:With Commentary.World Scientific,2003:437-442.
[15] XU Y,ZHUANG Z,LI W M,et al.Effective community division based on improved spectral clustering [J].Neurocomputing,2018,279:54-62.
[16] GUI C,ZHANG R S,HU R J.Guoming Huang,Jiaxuan Wei.Overlapping communities detection based on spectral analysis of line graphs [J].Physica A:Statistical Mechanics and its Applications,2018,498:50-65.
[17] NEWMAN M E J.Modularity and community structure in networks [J].Proceedings of the National Academy of Sciences,2006,103(23):8577-8582.
[18] DUCH J,ARENAS A.Community detection in complex net- works using extremal optimization [J].Physical Review E,2005,72(2):027104.
[19] GUIMERA R,AMARAL L A N.Functional cartography of complex metabolic networks [J].Nature,2005,433(7028):895.
[20] GUERRERO M,MONTOYA F G,BAÑOS R,et al.Adaptive community detection in complex networks using genetic algorithms [J].Neurocomputing,2017,266:101-113.
[21] SAID A,ABBASI R A,MAQBOOL O,et al.Cc-ga:a clustering coefficient based genetic algorithm for detecting communities in social networks[J].Applied Soft Computing,2018,63:59-70.
[22] DŽAMICD,ALOISE D,MLADENOVICN.Ascent-descent variable neighborhood decomposition search for community detection by modularity maximization [J].Annals of Operations Research,2019,272(1/2):273-287.
[23] NEWMAN M E.Fast algorithm for detecting community structure in networks [J].Phys Rev E Stat Nonlin Soft Matter Phys,2004,69(6 Pt 2):066133.
[24] 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,2008(10):P10008.
[25] TABRIZI S A,SHAKERY A,Asadpour M,et al.Personalized pagerank clustering:A graph clustering algorithm based on random walks [J].Physica A:Statistical Mechanics and its Applications,2013,392(22):5772-5785.
[26] AKTUNC R,TOROSLU I H,OZER M,et al.A dynamic modularity based community detection algorithm for large-scale networks:Dslm [C]//2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM).IEEE,2015:1177-1183.
[27] CLAUSET A,NEWMAN M E J,MOORE C.Finding community structure in very large networks [J].Physical Review E,2004,70(6):066111.
[28] DANON L,DÍAZ-GUILERA A,ARENAS A.The effect of size heterogeneity on community identification in complex networks [J].Journal of Statistical Mechanics:Theory and Experiment,2006,2006(11):P11010.
[29] WAKITA K,TSURUMI T.Finding community structure in mega-scale social networks[C]//Proceedings of the 16th International Conference on World Wide Web.ACM,2007:1275-1276.
[30] 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.
[31] DENG Z H,QIAO H H,SONG Q,et al.A complex network community detection algorithm based on label propagation and fuzzy c-means [J].Physica A:Statistical Mechanics and its Applications,2019,519:217-226.
[32] BARBER M J,CLARK J W.Detecting network communities by propagating labels under constraints [J].Physical Review E,2009,80(2):026129.
[33] HU X G,HE W,LI H Z,et al.Role-based label propagation algorithm for community detection [J].arXiv:1601.06307,2016.
[34] GUI C,ZHANG R S,ZHAO Z L,et al.Lpa-cbd an improved label propagation algorithm based on community belonging degree for community detection[J].International Journal of Modern Physics C,2018,29(02):1850011.
[35] THAKARE S B,KIWELEKAR A W.Skiplpa:an efficient label propagation algorithm for community detection in sparse network [C]//Proceedings of the 9th Annual ACM India Confe-rence.ACM,2016:97-106.
[36] CHIN J H,RATNAVELU K.A semi-synchronous label propagation algorithm with constraints for community detection in complex networks [J].Scientific Reports,2017,7:45836.
[37] SU Y S,WANG B J,ZHANG X Y.A seed-expanding method based on random walks for community detection in networks with ambiguous community structures [J].Scientific Reports,2017,7:41830.
[38] SUN H L,CHŸNG E,YONG X,et al.A fast community detection method in bipartite networks by distance dynamics [J].Physica A:Statistical Mechanics and its Applications,2018,96:108-120.
[39] ZHOU H J.Network landscape from a brownian particle’s perspective [J].Physical Review E,2003,67(4):041908.
[40] PONS P,LATAPY M.Computing communities in large net- works using random walks [C]//International Symposium on Computer and Information Sciences.Springer,2005:284-293.
[41] ROSVALL M,BERGSTROM C T.Maps of random walks on complex networks reveal community structure [J].Proceedings of the National Academy of Sciences,2008,105(4):1118-1123.
[42] ROSVALL M,BERGSTROM C T.Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems [J].PloS One,2011,6(4):e18209.
[43] HU Y Q,LI M H,ZHANG P,et al.Community detection by signaling on complex networks [J].Physical Review E,2008,78(1):016115.
[44] ESMAILIAN P,JALILI M.Community detection in signed networks:the role of negative ties in different scales [J].Scientific Reports,2015,5(1):14339.
[45] BAHADORI S,MORADI P.A local random walk method for identifying communities in social networks [C]//Artificial Intelligence and Robotics(IRANOPEN).IEEE,2017:177-181.
[46] HARTIGAN J A,WONG M A.Algorithm as 136:A k-means clustering algorithm [J].Journal of the Royal Statistical Society.Series C (Applied Statistics),1979,28(1):100-108.
[47] FORTUNATO S,BARTHELEMY M.Resolution limit in community detection [J].Proceedings of the National Academy of Sciences,2007,104(1):36-41.
[48] ANA L N F,JAIN A K.Robust data clustering [C]//IEEE Computer Society Conference onComputer Vision and Pattern Recognition.IEEE,2003.
[49] ZACHARY W W.An information flow model for conflict and fission in small groups [J].Journal of Anthropological Research,1977,33(4):452-473.
[50] LUSSEAU D,SCHNEIDER K,BOISSEAU O J,et al.The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations [J].Behavioral Ecology and Sociobiology,2003,54(4):396-405.
[51] STEINHAEUSER K,CHAWLA N V.Identifying and evaluating community structure in complex networks [J].Pattern Re-cognition Letters,2010,31(5):413-421.
[52] NEWMAN M E J.Scientific collaboration networks.i.network construction and fundamental results [J].Physical Review E,2001,64(1):016131.
[53] KNUTH D E.The Stanford GraphBase:a platform for combinatorial computing [M].New York:ACM,1993.
[54] GLEISER P M,DANON L.Community structure in jazz [J].Advances in Complex Systems,2003,6(4):565-573.
[55] MILO R,SHEN-ORR S,ITZKOVITZ S,et al.Network motifs:simple building blocks of complex networks [J].Science,2002,298(5594):824-827.
[56] 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.
[57] LANCICHINETTI A,FORTUNATO S,RADICCHI F.Benchmark graphs for testing community detection algorithms [J].Physical Review E,2008,78(4):046110.
[58] FAGNAN J,ABNAR A,RABBANY R,et al.Modular networks for validating community detection algorithms [J].arXiv:1801.01229,2018.
[1] 杨卓璇, 马源培, 严冠. 基于耦合强度的多项式时间社团探测算法[J]. 计算机科学, 2020, 47(6A): 102-107.
[2] 张虎, 周晶晶, 高海慧, 王鑫. 融合节点结构和内容的网络表示学习方法[J]. 计算机科学, 2020, 47(12): 119-124.
[3] 唐家琪, 吴璟莉, 廖元秀, 王金艳. 基于双加权投票的蛋白质功能预测[J]. 计算机科学, 2019, 46(4): 222-227.
[4] 赵倩倩,吕敏,许胤龙. 基于两种子结构感知的社交网络Graphlets采样估计算法[J]. 计算机科学, 2019, 46(3): 314-320.
[5] 宾晟, 孙更新. 基于多关系社交网络的协同过滤推荐算法[J]. 计算机科学, 2019, 46(12): 56-62.
[6] 刘庆烽, 刘哲, 宋余庆, 朱彦. 基于约束随机游走的肿瘤图像分割方法[J]. 计算机科学, 2018, 45(7): 243-247.
[7] 肖迎元,张红玉. 基于用户潜在特征的社交网络好友推荐方法[J]. 计算机科学, 2018, 45(3): 218-222.
[8] 付立东,聂靖靖. 基于进化谱分方法的动态社团检测[J]. 计算机科学, 2018, 45(2): 171-174.
[9] 陆亿红,张振宁,杨雄. 一种基于节点特征向量的复杂网络社团发现算法[J]. 计算机科学, 2017, 44(Z6): 419-423.
[10] 卿勇,刘梦娟,银盈,李杨曦. SMART:一种面向电商平台快速消费品的图推荐算法[J]. 计算机科学, 2017, 44(Z11): 464-469.
[11] 李鹏,李英乐,王凯,何赞园,李星,常振超. 基于交互行为和连接分析的社交网络社团检测[J]. 计算机科学, 2017, 44(7): 197-202.
[12] 刘林峰,严禹道,吴国新. 一种基于节点移动倾向检测的社会网络机会转发机制[J]. 计算机科学, 2017, 44(7): 74-78.
[13] 卞梦阳,杨青,张敬伟,张会兵,钱俊彦. 基于FP-Growth的图上随机游走推荐方法[J]. 计算机科学, 2017, 44(6): 232-236.
[14] 何明,刘伟世,魏铮. 基于信任网络随机游走模型的协同过滤推荐[J]. 计算机科学, 2016, 43(6): 257-262.
[15] 陈永祥,陈崚. 基于随机游走的带有属性网络的链接预测[J]. 计算机科学, 2016, 43(6): 199-203.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75 .
[2] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[3] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[4] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[5] 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法[J]. 计算机科学, 2018, 45(4): 94 -99 .
[6] 周燕萍,业巧林. 基于L1-范数距离的最小二乘对支持向量机[J]. 计算机科学, 2018, 45(4): 100 -105 .
[7] 刘博艺,唐湘滟,程杰仁. 基于多生长时期模板匹配的玉米螟识别方法[J]. 计算机科学, 2018, 45(4): 106 -111 .
[8] 耿海军,施新刚,王之梁,尹霞,尹少平. 基于有向无环图的互联网域内节能路由算法[J]. 计算机科学, 2018, 45(4): 112 -116 .
[9] 崔琼,李建华,王宏,南明莉. 基于节点修复的网络化指挥信息系统弹性分析模型[J]. 计算机科学, 2018, 45(4): 117 -121 .
[10] 王振朝,侯欢欢,连蕊. 抑制CMT中乱序程度的路径优化方案[J]. 计算机科学, 2018, 45(4): 122 -125 .