Identification and evaluation of weak community structures in networks

Jianhua Ruan, Weixiong Zhang

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

18 Scopus citations

Abstract

Identifying intrinsic structures in large networks is a fundamental problem in many fields, such as engineering, social science and biology. In this paper, we are concerned with communities, which are densely connected sub-graphs in a network, and address two critical issues for finding community structures from large experimental data. First, most existing network clustering methods assume sparse networks and networks with strong community structures. In contrast, we consider sparse and dense networks with weak community structures. We introduce a set of simple operations that capture local neighborhood information of a node to identify weak communities. Second, we consider the issue of automatically determining the most appropriate number of communities, a crucial problem for all clustering methods. This requires to properly evaluate the quality of community structures. Built atop a function for network cluster evaluation by Newman and Girvan, we extend their work to weighted graphs. We have evaluated our methods on many networks of known structures, and applied them to analyze a collaboration network and a genetic network. The results showed that our methods can find superb community structures and correct numbers of communities. Comparing to the existing approaches, our methods performed significantly better on networks with weak community structures and equally well on networks with strong community structures.

Original languageEnglish (US)
Title of host publicationProceedings of the 21st National Conference on Artificial Intelligence and the 18th Innovative Applications of Artificial Intelligence Conference, AAAI-06/IAAI-06
Pages470-475
Number of pages6
StatePublished - Nov 13 2006
Externally publishedYes
Event21st National Conference on Artificial Intelligence and the 18th Innovative Applications of Artificial Intelligence Conference, AAAI-06/IAAI-06 - Boston, MA, United States
Duration: Jul 16 2006Jul 20 2006

Publication series

NameProceedings of the National Conference on Artificial Intelligence
Volume1

Conference

Conference21st National Conference on Artificial Intelligence and the 18th Innovative Applications of Artificial Intelligence Conference, AAAI-06/IAAI-06
CountryUnited States
CityBoston, MA
Period7/16/067/20/06

ASJC Scopus subject areas

  • Software
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Identification and evaluation of weak community structures in networks'. Together they form a unique fingerprint.

Cite this