MIRACLE: A multiple independent random walks community parallel detection algorithm for big graphs

详细信息    查看全文

• 作者：Xiaoming Liu^a ; ^{xmliu@sei.xjtu.edu.cn" class="auth_mail" title="E-mail the corresponding author} ; Yadong Zhou^a ; ^{ydzhou@sei.xjtu.edu.cn" class="auth_mail" title="E-mail the corresponding author} ; Chengchen Hu^a ; ^{huc@ieee.org" class="auth_mail" title="E-mail the corresponding author} ; Xiaohong Guan^a ; ^b ; ^{xhguan@sei.xjtu.edu.cn" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Community detection ; Complex networks ; Social networks ; Random walking ; Parallel computing
• 刊名：Journal of Network and Computer Applications
• 出版年：2016
• 出版时间：July 2016
• 年：2016
• 卷：70
• 期：Complete
• 页码：89-101
• 全文大小：784 K

文摘

Community detection is a common problem in various types of complex networks. With the emerging of large scale real networks like social networks, community detection meets new technology challenges of extremely large computational cost and lack of prior information. Although several literatures recently try to solve these new challenges, they still have limitations of parallelism and running time. With the scale of data increases sharply, the parallelism is necessary but few codes exist. In this work, we analyze the process of random walking in graphs, and observe that the weight of an edge gotten by processing the vertices visited by the walker could be an indicator to measure the closeness of vertex connection. Based on this finding, we first propose a novel parallel computing community detection algorithm for big unweighted undirected graphs in the true sense. The algorithm consists of three steps, including random walking using multiple independent random walks, weight calculating for edges and community detecting. The time complexity of our algorithm is class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1084804516300947&_mathId=si0008.gif&_user=111111111&_pii=S1084804516300947&_rdoc=1&_issn=10848045&md5=37d2775fb15d210b0d310e24218e2295" title="Click to view the MathML source">O(nlogn)class="mathContainer hidden">class="mathCode">$O\left(n\log n\right)$ without prior information. In order to implement our parallel computing algorithm efficiently, we also propose a novelty graph partition model. Experimental results show that our algorithm is capable of detecting the community structure and the overlapping parts of communities in real-world effectively (reduce the running time by 400 times at least), and handling the challenges of community detection in big graph era.