Paper Info
Title
A general probabilistic framework for detecting community structure in networks
Abstract
Based on Newman's fast algorithm, in this paper we develop a general probabilistic framework for detecting community structure in a network. The key idea of our generalization is to characterize a network (graph) by a bivariate distribution that specifies the probability of the two vertices appearing at both ends of a randomly selected path in the graph. With such a bivariate distribution, we give a probabilistic definition of a community and a definition of a modularity index. To detect communities in a network, we propose a class of distribution-based clustering algorithms that have comparable computational complexity to that of Newman's fast algorithm. Our generalization provides the additional freedom to choose a bivariate distribution and a correlation measure. As such, we obtain significant performance improvement over the original Newman fast algorithm in the computer simulations of random graphs with known community structure.
Year
DOI
Venue
2011
10.1109/INFCOM.2011.5935256
INFOCOM
Keywords
Field
DocType
pattern clustering,correlation measure,general probabilistic framework,community structure,computational complexity,computer networks,random graphs,clustering algorithms,large complex networks,graph theory,graph partitioning,distribution-based clustering algorithm,newman fast algorithm,modularity index,bivariate distribution,random graph,community,complex network,indexation,networks,probabilistic,computer simulation
Random graph,Computer science,Theoretical computer science,Artificial intelligence,Probabilistic logic,Cluster analysis,Graph partition,Distributed computing,Graph theory,Joint probability distribution,Vertex (geometry),Machine learning,Computational complexity theory
Conference
ISSN
ISBN
Citations 
0743-166X
978-1-4244-9919-9
6
PageRank 
References 
Authors
0.51
6
4
Name
Order
Citations
PageRank
Cheng-Shang Chang12392246.97
Chin-Yi Hsu260.51
Jay Cheng315314.40
Duan-Shin Lee467071.00