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

doi:10.11896/jsjkx.190700051

摘要/Abstract

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

尹欣红, 赵世燕, 陈晓云. 带偏置的信号传播的随机游走的社团检测算法[J]. 计算机科学, 2019, 46(12): 45-55.

YIN Xin-hong, ZHAO Shi-yan, CHEN Xiao-yun. Community Detection Algorithm Based on Random Walk of Signal Propagation with Bias[J]. Computer Science, 2019, 46(12): 45-55.

参考文献 58

[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.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed