TY - GEN
T1 - An efficient spectral algorithm for network community discovery and its applications to biological and social networks
AU - Ruan, Jianhua
AU - Zhang, Weixiong
PY - 2007
Y1 - 2007
N2 - Automatic discovery of community structures in complex networks is a fundamental task in many disciplines, including social science, engineering, and biology. Recently, a quantitative measure called modularity (Q) has been proposed to effectively assess the quality of community structures. Several community discovery algorithms have since been developed based on the optimization of Q. However, this optimization problem is NP-hard, and the existing algorithms have a low accuracy or are computationally expensive. In this paper, we present an efficient spectral algorithm for modularity optimization. When tested on a large number of synthetic or real-world networks, and compared to the existing algorithms, our method is efficient and and has a high accuracy. In addition, we have successfully applied our algorithm to detect interesting and meaningful community structures from real-world networks in different domains, including biology, medicine and social science. Due to space limitation, results of these applications are presented in a complete version of the paper available on our website (http://cse.wustl.edu/∼jruan/).
AB - Automatic discovery of community structures in complex networks is a fundamental task in many disciplines, including social science, engineering, and biology. Recently, a quantitative measure called modularity (Q) has been proposed to effectively assess the quality of community structures. Several community discovery algorithms have since been developed based on the optimization of Q. However, this optimization problem is NP-hard, and the existing algorithms have a low accuracy or are computationally expensive. In this paper, we present an efficient spectral algorithm for modularity optimization. When tested on a large number of synthetic or real-world networks, and compared to the existing algorithms, our method is efficient and and has a high accuracy. In addition, we have successfully applied our algorithm to detect interesting and meaningful community structures from real-world networks in different domains, including biology, medicine and social science. Due to space limitation, results of these applications are presented in a complete version of the paper available on our website (http://cse.wustl.edu/∼jruan/).
UR - http://www.scopus.com/inward/record.url?scp=38349102446&partnerID=8YFLogxK
U2 - 10.1109/ICDM.2007.72
DO - 10.1109/ICDM.2007.72
M3 - Conference contribution
AN - SCOPUS:38349102446
SN - 0769530184
SN - 9780769530185
T3 - Proceedings - IEEE International Conference on Data Mining, ICDM
SP - 643
EP - 648
BT - Proceedings of the 7th IEEE International Conference on Data Mining, ICDM 2007
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 7th IEEE International Conference on Data Mining, ICDM 2007
Y2 - 28 October 2007 through 31 October 2007
ER -