The Power of Side-Information in Subgraph Detection
The Power of Side-Information in Subgraph Detection
复制标题
子图检测中辅助信息的力量
DOI：
10.1109/tsp.2017.2786266
复制
发表时间：
2016
影响因子：
5.4
通讯作者：
R. Sundaresan
中科院分区：
文献类型：
--
作者：
Arun Kadavankandy;Konstantin Avrachenkov;L. Cottatellucci;R. Sundaresan
在本文中，我们解决了隐藏社区检测的问题。我们考虑将置信传播 (BP) 应用于检测嵌入在较大且稀疏 ER 图中的隐藏 Erdős-Rényi (ER) 图的问题，并且存在辅助信息。我们推导了两种基于BP的相关算法，在存在两种边信息的情况下执行子图检测。辅助信息的第一个变体由一组称为线索的节点组成，已知来自子图。辅助信息的第二种变体由一组节点组成，这些节点是具有给定概率的线索。过去的工作表明，当所谓的有效信噪比参数低于阈值时，没有辅助信息的 BP 无法正确检测子图。相比之下，在存在重要辅助信息的情况下，我们表明 BP 算法对于适当定义的相变参数的任何值都可以实现渐近零误差。我们在合成数据集和一些现实世界网络上验证了我们的结果。
In this paper, we tackle the problem of hidden community detection. We consider belief propagation (BP) applied to the problem of detecting a hidden Erdős-Rényi (ER) graph embedded in a larger and sparser ER graph, in the presence of side-information. We derive two related algorithms based on BP to perform subgraph detection in the presence of two kinds of side-information. The first variant of side-information consists of a set of nodes, called cues, known to be from the subgraph. The second variant of side-information consists of a set of nodes that are cues with a given probability. It was shown in past works that BP without side-information fails to detect the subgraph correctly when a so-called effective signal-to-noise ratio parameter falls below a threshold. In contrast, in the presence of nontrivial side-information, we show that the BP algorithm achieves asymptotically zero error for any value of a suitably defined phase-transition parameter. We validate our results on synthetic datasets and a few real world networks.
在 O(|E|log*|V|) 时间内恢复超出 KestenâStigum 阈值的隐藏社区
影响因子：
1
作者：
Hajek, Bruce;Wu, Yihong;Xu, Jiaming
通讯作者：
Xu, Jiaming