Detecting community structure for undirected big graphs based on random walks
Lists
Only you see this
Abstract
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.
BibTeX
@inproceedings{liu2014detecting,
author = {Xiaoming Liu and Yadong Zhou and Chengchen Hu and Xiaohong Guan and Junyuan Leng},
title = {{Detecting community structure for undirected big graphs based on random walks}},
booktitle = {The Web Conference},
year = {2014},
doi = {10.1145/2567948.2580060},
}Loading related content...