NDLI: Finding One Community in a Sparse Graph

Content Provider	Springer Nature Link
Author	Montanari, Andrea
Copyright Year	2015
Abstract	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 $$\deg _\mathrm{in} - \deg _\mathrm{out} > \sqrt{\deg _\mathrm{out}/e}$$ and fail for $$\deg _\mathrm{in} - \deg _\mathrm{out} < \sqrt{\deg _\mathrm{out}/e}$$ (with $$\deg _\mathrm{in}$$ , $$\deg _\mathrm{out}$$ 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 $$\deg _\mathrm{in} - \deg _\mathrm{out} < \sqrt{\deg _\mathrm{out}/e}$$ .
Starting Page	273
Ending Page	299
Page Count	27
File Format	PDF
ISSN	00224715
Journal	Journal of Statistical Physics
Volume Number	161
Issue Number	2
e-ISSN	15729613
Language	English
Publisher	Springer US
Publisher Date	2015-08-02
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Random graphs Cavity method Statistical inference Hidden clique Polynomial algorithms Phase Transitions Statistical Physics, Dynamical Systems and Complexity Theoretical, Mathematical and Computational Physics Physical Chemistry Quantum Physics
Content Type	Text
Resource Type	Article
Subject	Statistical and Nonlinear Physics Mathematical Physics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Phase Transitions for the Cavity Approach to the Clique Problem on Random Graphs

Phase Transitions in Dynamical Random Graphs

Critical Phenomena in Exponential Random Graphs

Inference of Kinetic Ising Model on Sparse Graphs

A Detailed Investigation into Near Degenerate Exponential Random Graphs

The Cut Metric, Random Graphs, and Branching Processes

Minimal Contagious Sets in Random Regular Graphs

Overlapping Modularity at the Critical Point of k-Clique Percolation

Singularities in the Entropy of Asymptotically Large Simple Graphs

Finding One Community in a Sparse Graph

Similar Documents

Phase Transitions for the Cavity Approach to the Clique Problem on Random Graphs

Phase Transitions in Dynamical Random Graphs

Critical Phenomena in Exponential Random Graphs

Inference of Kinetic Ising Model on Sparse Graphs

A Detailed Investigation into Near Degenerate Exponential Random Graphs

The Cut Metric, Random Graphs, and Branching Processes

Minimal Contagious Sets in Random Regular Graphs

Overlapping Modularity at the Critical Point of k-Clique Percolation

Singularities in the Entropy of Asymptotically Large Simple Graphs

Finding One Community in a Sparse Graph