An efficient spectral algorithm for network community discovery and its applications to biological and social networks

Jianhua Ruan, Weixiong Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

83 Scopus citations

Abstract

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/).

Original languageEnglish (US)
Title of host publicationProceedings of the 7th IEEE International Conference on Data Mining, ICDM 2007
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages643-648
Number of pages6
ISBN (Print)0769530184, 9780769530185
DOIs
StatePublished - Jan 1 2007
Externally publishedYes
Event7th IEEE International Conference on Data Mining, ICDM 2007 - Omaha, NE, United States
Duration: Oct 28 2007Oct 31 2007

Publication series

NameProceedings - IEEE International Conference on Data Mining, ICDM
ISSN (Print)1550-4786

Conference

Conference7th IEEE International Conference on Data Mining, ICDM 2007
CountryUnited States
CityOmaha, NE
Period10/28/0710/31/07

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'An efficient spectral algorithm for network community discovery and its applications to biological and social networks'. Together they form a unique fingerprint.

Cite this