TY - GEN
T1 - Detecting community structure for undirected big graphs based on random walks
AU - Liu, Xiaoming
AU - Zhou, Yadong
AU - Hu, Chengchen
AU - Guan, Xiaohong
AU - Leng, Junyuan
N1 - Publisher Copyright:
© Copyright 2014 by the International World Wide Web Conferences Steering Committee.
PY - 2014/4/7
Y1 - 2014/4/7
N2 - Community detection is a common problem in various types of big graphs. It is meaningful to understand the functions and dynamics of networks. The challenges of detecting community for big graphs include high computational cost, no prior information, etc.. In this work, we analyze the process of random walking in graphs, and find out 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 idea, we propose a community detection algorithm for undirected big graphs which consists of three steps, including random walking using a single walker, weight calculating for edges and community detecting. Our algorithm is running in O(n2) without prior information. Experimental results show that our algorithm is capable of detecting the community structure and the overlapping parts of graphs in real-world effectively, and handling the challenges of community detection in big graph era.
AB - Community detection is a common problem in various types of big graphs. It is meaningful to understand the functions and dynamics of networks. The challenges of detecting community for big graphs include high computational cost, no prior information, etc.. In this work, we analyze the process of random walking in graphs, and find out 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 idea, we propose a community detection algorithm for undirected big graphs which consists of three steps, including random walking using a single walker, weight calculating for edges and community detecting. Our algorithm is running in O(n2) without prior information. Experimental results show that our algorithm is capable of detecting the community structure and the overlapping parts of graphs in real-world effectively, and handling the challenges of community detection in big graph era.
KW - Big graphs
KW - Community detection
KW - Overlapping parts
KW - Random walking
UR - https://www.scopus.com/pages/publications/84990946744
U2 - 10.1145/2567948.2580060
DO - 10.1145/2567948.2580060
M3 - 会议稿件
AN - SCOPUS:84990946744
T3 - WWW 2014 Companion - Proceedings of the 23rd International Conference on World Wide Web
SP - 1151
EP - 1156
BT - WWW 2014 Companion - Proceedings of the 23rd International Conference on World Wide Web
PB - Association for Computing Machinery, Inc
T2 - 23rd International Conference on World Wide Web, WWW 2014
Y2 - 7 April 2014 through 11 April 2014
ER -