Computer Science ›› 2019, Vol. 46 ›› Issue (12): 45-55.doi: 10.11896/jsjkx.190700051

• Big Data & Data Science • Previous Articles     Next Articles

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

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: Bias, Community detection, Community structure, Random walk, Signal propagation

CLC Number: 

  • 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] ZHENG Wen-ping, LIU Mei-lin, YANG Gui. Community Detection Algorithm Based on Node Stability and Neighbor Similarity [J]. Computer Science, 2022, 49(9): 83-91.
[2] XU Guo-ning, CHEN Yi-peng, CHEN Yi-ming, CHEN Jin-yin, WEN Hao. Data Debiasing Method Based on Constrained Optimized Generative Adversarial Networks [J]. Computer Science, 2022, 49(6A): 184-190.
[3] HE Xi, HE Ke-tai, WANG Jin-shan, LIN Shen-wen, YANG Jing-lin, FENG Yu-chao. Analysis of Bitcoin Entity Transaction Patterns [J]. Computer Science, 2022, 49(6A): 502-507.
[4] ZHANG Yu-jiao, HUANG Rui, ZHANG Fu-quan, SUI Dong, ZHANG Hu. Study on Affinity Propagation Clustering Algorithm Based on Bacterial Flora Optimization [J]. Computer Science, 2022, 49(5): 165-169.
[5] WANG Ben-yu, GU Yi-jun, PENG Shu-fan, ZHENG Di-wen. Community Detection Algorithm Based on Dynamic Distance and Stochastic Competitive Learning [J]. Computer Science, 2022, 49(5): 170-178.
[6] YANG Xu-hua, WANG Lei, YE Lei, ZHANG Duan, ZHOU Yan-bo, LONG Hai-xia. Complex Network Community Detection Algorithm Based on Node Similarity and Network Embedding [J]. Computer Science, 2022, 49(3): 121-128.
[7] PU Shi, ZHAO Wei-dong. Community Detection Algorithm for Dynamic Academic Network [J]. Computer Science, 2022, 49(1): 89-94.
[8] CHEN Xiang-tao, ZHAO Mei-jie, YANG Mei. Overlapping Community Detection Algorithm Based on Subgraph Structure [J]. Computer Science, 2021, 48(9): 244-250.
[9] QIAN Meng-wei , GUO Yi. Biased Deep Distance Factorization Algorithm for Top-N Recommendation [J]. Computer Science, 2021, 48(9): 103-109.
[10] HE Bin, XU Dao-yun. Community Structure of Regular (3,4)-CNF Formula [J]. Computer Science, 2021, 48(4): 26-30.
[11] YANG Xu-hua, WANG Chen. Community Detection Algorithm in Complex Network Based on Network Embedding and Local Resultant Force [J]. Computer Science, 2021, 48(4): 229-236.
[12] MA Chuang, TIAN Qing, SUN He-yang, CAO Meng, MA Ting-huai. Unsupervised Domain Adaptation Based on Weighting Dual Biases [J]. Computer Science, 2021, 48(2): 217-223.
[13] XU Xin-li, XIAO Yun-yue, LONG Hai-xia, YANG Xu-hua, MAO Jian-fei. Attributed Network Embedding Based on Matrix Factorization and Community Detection [J]. Computer Science, 2021, 48(12): 204-211.
[14] NING Yi-xin, XIE Hui, JIANG Huo-wen. Survey of Graph Neural Network in Community Detection [J]. Computer Science, 2021, 48(11A): 11-16.
[15] PAN Yu, ZOU Jun-hua, WANG Shuai-hui, HU Gu-yu, PAN Zhi-song. Deep Community Detection Algorithm Based on Network Representation Learning [J]. Computer Science, 2021, 48(11A): 198-203.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!