Robust local community detection
Open Access
- 1 February 2015
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 8 (7) , 798-809
Abstract
Given a large network, local community detection aims at finding the community that contains a set of query nodes and also maximizes (minimizes) a goodness metric. This problem has recently drawn intense research interest. Various goodness metrics have been proposed. However, most existing metrics tend to include irrelevant subgraphs in the detected local community. We refer to such irrelevant subgraphs as free riders. We systematically study the existing goodness metrics and provide theoretical explanations on why they may cause the free rider effect. We further develop a query biased node weighting scheme to reduce the free rider effect. In particular, each node is weighted by its proximity to the query node. We define a query biased density metric to integrate the edge and node weights. The query biased densest subgraph, which has the largest query biased density, will shift to the neighborhood of the query nodes after node weighting. We then formulate the query biased densest connected subgraph (QDC) problem, study its complexity, and provide efficient algorithms to solve it. We perform extensive experiments on a variety of real and synthetic networks to evaluate the effectiveness and efficiency of the proposed methods.Keywords
This publication has 35 references indexed in Scilit:
- Community detection in graphsPhysics Reports, 2010
- Benchmark graphs for testing community detection algorithmsPhysical Review E, 2008
- Modularity and community structure in networksProceedings of the National Academy of Sciences, 2006
- Proteome survey reveals modularity of the yeast cell machineryNature, 2006
- Finding local community structure in networksPhysical Review E, 2005
- On clusteringsJournal of the ACM, 2004
- A Fast and High Quality Multilevel Scheme for Partitioning Irregular GraphsSIAM Journal on Scientific Computing, 1998
- A Fast Parametric Maximum Flow Algorithm and ApplicationsSIAM Journal on Computing, 1989
- A faster approximation algorithm for the Steiner problem in graphsInformation Processing Letters, 1988
- Depth-First Search and Linear Graph AlgorithmsSIAM Journal on Computing, 1972