Robust local community detection: On free rider effect and its elimination

Yubao Wu, Ruoming Jin, Jing Li, Xiang Zhang

Research output: Contribution to journalConference articlepeer-review

134 Scopus citations


Given a large network, local community detection aims atfinding the community that contains a set of query nodes and also maximizes (minimizes) a goodness metric. This problem has recently drawn intense research interest. Var- ious goodness metrics have been proposed. However, most existing metrics tend to include irrelevant subgraphs in the detected local community. We refer to such irrelevant sub- graphs 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 de- velop 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 den- sity 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 bi- ased 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 syn- thetic networks to evaluate the effectiveness and efficiency of the proposed methods.

Original languageEnglish (US)
Pages (from-to)798-809
Number of pages12
JournalProceedings of the VLDB Endowment
Issue number7 7
StatePublished - 2015
Event41st International Conference on Very Large Data Bases, VLDB 2015 - Kohala Coast, United States
Duration: Aug 31 2015Sep 4 2015

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)
  • General Computer Science


Dive into the research topics of 'Robust local community detection: On free rider effect and its elimination'. Together they form a unique fingerprint.

Cite this