Finding One Community in a Sparse Graph
Finding One Community in a Sparse Graph
复制标题
在稀疏图中找到一个社区
DOI：
10.1007/s10955-015-1338-2
复制
发表时间：
2015
影响因子：
1.6
通讯作者：
A. Montanari
中科院分区：
文献类型：
--
作者：
A. Montanari
我们考虑一个平均度有界的随机稀疏图，其中一个顶点的子集具有比背景更高的连通度。具体地说，此顶点子集内部的平均阶数大于外部(但仍有界)。给出这类图的一个实现，我们的目标是识别隐藏的顶点子集。这可以被认为是在社交网络中找到紧密联系的社区或在关系数据集中找到集群的问题的模型。在本文中，我们提出了两组贡献：(I)我们使用自旋玻璃理论中的腔方法来推导出重建问题的精确相图。特别是，随着边概率差的增大，问题经历了两个相变，一个是静态相变，一个是动态相变。(Ii)建立了动态相变的严格界，证明了在一定阈值以上，局部算法(信任传播)能够正确识别大部分隐含集。在相同的阈值以下，没有任何局部算法能够实现这一目标。然而，在这种机制下，子集可以通过穷举搜索来识别。对于小的隐含集和大的平均程度，局部算法的相变具有有趣的简单形式。本地算法成功的概率很高，满足以下条件：degin-degout>；degout/e\documentclass[12pt]{minimal}\usepackage{amsath}\usepackage{wa ysym}\usepackage{amsfonts}\usepackage{amsbsy}\usepackage{amsbsy}\usepackage{mathsfs}\usepackage{upgreek}\setlong{\oddsidemargin}{-69pt}\Begin{Document}$\deg_\mathorm{in}-\deg_\mathorm{out}>；\Sqrt{\deg_\mathm{out}/e}$$\end{Document}失败，degin-degout<；degout/e\documentclass[12pt]{minimal}\usepackage{amsath}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{matrsfs}\usepackage{upgreek}\setlong{\oddsidemargin}{-69pt}\Begin{Document}$\deg_\mathm{in}-\deg_\mathm{out}<；\Sqrt{\deg_\mathm{out}/e}$\end{Document}(with des in\Documentclass[12pt]{Minimal}\usepackage{amsath}\usepackage{wa ysym}\usepackage{amsfonts}\usepackage{amsbsy}\usepackage{amsbsy}\usepackage{upgreek}\setlong{\oddsidemarin}{-69pt}\Begin{Document}$$\deg_\matrm{in}$\end{document}，Degout\Documentclass[12pt]{Minimal}\usepackage{amsath}\usepackage{wa ysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{matrsfs}\usepackage{upgreek}\setlong{\oddsidemargin}{-69pt}\Begin{Document}$$\deg_\mathm{out}$\end{Document}社区内外的平均学位)。我们认为，频谱算法在后一种情况下也是无效的。对于degin-degout<；degout/e\documentclass[12pt]{minimal}\usepackage{amsath}\usepackage{wa ysym}\usepackage{amsFonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{matrsfs}\usepackage{upgreek}\setlong{\oddsidemargin}{-69pt}\Begin{Document}$$\deg_\mathm{in}-\deg_\mathm{out}<，是否有任何多项式时间算法可能成功是一个悬而未决的问题；\sqrt{\deg_\mathm{out}/e}$$\end{文档}。
We consider a random sparse graph with bounded average degree, in which a subset of vertices has higher connectivity than the background. In particular, the average degree inside this subset of vertices is larger than outside (but still bounded). Given a realization of such graph, we aim at identifying the hidden subset of vertices. This can be regarded as a model for the problem of finding a tightly knitted community in a social network, or a cluster in a relational dataset. In this paper we present two sets of contributions: (i) We use the cavity method from spin glass theory to derive an exact phase diagram for the reconstruction problem. In particular, as the difference in edge probability increases, the problem undergoes two phase transitions, a static phase transition and a dynamic one. (ii) We establish rigorous bounds on the dynamic phase transition and prove that, above a certain threshold, a local algorithm (belief propagation) correctly identify most of the hidden set. Below the same threshold no local algorithm can achieve this goal. However, in this regime the subset can be identified by exhaustive search. For small hidden sets and large average degree, the phase transition for local algorithms takes an intriguingly simple form. Local algorithms succeed with high probability for degin-degout>degout/e\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\deg _\mathrm{in} - \deg _\mathrm{out} > \sqrt{\deg _\mathrm{out}/e}$$\end{document} and fail for degin-degout<degout/e\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\deg _\mathrm{in} - \deg _\mathrm{out} < \sqrt{\deg _\mathrm{out}/e}$$\end{document} (with degin\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\deg _\mathrm{in}$$\end{document}, degout\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\deg _\mathrm{out}$$\end{document} the average degrees inside and outside the community). We argue that spectral algorithms are also ineffective in the latter regime. It is an open problem whether any polynomial time algorithms might succeed for degin-degout<degout/e\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\deg _\mathrm{in} - \deg _\mathrm{out} < \sqrt{\deg _\mathrm{out}/e}$$\end{document}.