Identifying network communities with a high resolution
Jianhua Ruan
1, * and Weixiong Zhang 1,2,†
1 Department of Computer Science and Engineering, Washington University
in St. Louis, St. Louis, Missouri 63130, USA
2 Department of Genetics, Washington University in St. Louis, St.
Louis, Missouri 63130, USA
Community structure is an important property of complex networks.
The automatic discovery of such structure is a fundamental task
in many disciplines, including sociology, biology, engineering,
and computer science. Recently, several community discovery algorithms
have been proposed based on the optimization of a modularity function
(Q). However, the problem of modularity optimization is NP-hard
and the existing approaches often suffer from a prohibitively long
running time or poor quality. Furthermore, it has been recently
pointed out that algorithms based on optimizing Q will have a resolution
limit; i.e., communities below a certain scale may not be detected.
In this research, we first propose an efficient heuristic algorithm
QCUT, which combines spectral graph partitioning and local search
to optimize Q.
Using both synthetic and real networks, we show that QCUT can find
higher modularities and is more scalable than the existing algorithms.
Furthermore,
using QCUT as an essential component, we propose a recursive algorithm
HQCUT to solve the resolution limit problem. We show that HQCUT
can successfully detect communities at a much finer scale or with
a higher
accuracy than the existing algorithms. We also discuss two possible
reasons that can cause the resolution limit problem and provide
a method to distinguish them. Finally, we apply QCUT and HQCUT to
study a protein-protein interaction network and show that the combination
of the two algorithms can reveal interesting bio-logical results
that may be otherwise undetected.
continua >>>>>
