Robust Local Community Detection: On Free Rider Effect and Its Elimination
Robust Local Community Detection: On Free Rider Effect and Its Elimination
复制标题
DOI：
10.14778/2752939.2752948
复制
发表时间：
2015-02
期刊：
影响因子：
--
通讯作者：
Yubao Wu;R. Jin;Jing Li;Xiang Zhang
中科院分区：
文献类型：
--
作者：
Yubao Wu;R. Jin;Jing Li;Xiang Zhang
给定一个大型网络，本地社区检测的目标是找到包含一组查询节点的社区，并最大化（最小化）一个良度度量。这个问题最近引起了强烈的研究兴趣。人们提出了各种优良度度量。然而，大多数现有指标倾向于在检测到的本地社区中包含不相关的子图。我们把这种不相关的子图称为搭便车者。我们系统地研究了现有的优度指标，并对它们可能导致搭便车效应的原因提供了理论解释。我们进一步开发了一种查询偏置节点加权方案，以减少搭便车效应。特别是，每个节点根据其与查询节点的接近程度进行加权。我们定义了一个查询偏置密度度量来整合边和节点的权重。节点加权后，查询偏差密度最大的子图将向查询节点的邻域偏移。然后，我们提出了查询偏置密集连通子图（QDC）问题，研究了它的复杂性，并提供了有效的算法来解决它。我们在各种真实和合成网络上进行了广泛的实验，以评估所提出方法的有效性和效率。
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.