Global Community Detection Using Individual-Centered Partial Information Networks

on YouTube ↗43m

" summary

Framework models an L=2 partial-view as a partial adjacency B = S A S and isolates a random signal term BE whose rank is 2K under SBM/DCSBM; eigenvalues and eigenvectors of BE are derived and drive new spectral algorithms that prove weak consistency when local edge density PN exceeds specified bounds. A proposed eigengap centrality (lambda_min) predicts which centers recover global communities; simulations show ~0.7 correlation with per-node accuracy versus standard centralities, and application to 39 Indian villages links leader centrality to program participation.

AI-written summary · about

" chapters (14)

1. 0:00Intro
2. 1:16Social network modeling
3. 3:30How much does a person understand about the connections in the full network?
4. 4:28A toy example of individual-centered partial information networks
5. 6:35Existing literature
6. 9:53A peak at the results
7. 12:20Preliminaries - low rank assumption
8. 14:02Theoretical properties of B
9. 23:04Main algorithm for SBM
10. 25:57Main algorithm for DCSBM
11. 26:43A conditional setting emphasizing individual differences
12. 31:54Simulation with DCSBM
13. 37:10Summary and future work
14. 38:48External impact of statistical theory and methodology papers

" related talks

• 35mLocal Statistics, Semidefinite Programming, and Community Detection IISidhanth Mohanty · Computational Phase Transitions (Simons Institute, 2020)
• 43mInformation-Theoretic Bounds and Phase Transitions in Community Detection and High-Dimensional ClustCris Moore · Random Instances and Phase Transitions (Simons Institute, 2016)
• 45mCommunity Detection with the Non-Backtracking OperatorMarc Lelarge · Random Instances and Phase Transitions (Simons Institute, 2016)
• 47mPhase Transitions in Semidefinite Relaxations (A Fast & Robust Algorithm for Community Detection)Fedrico Ricci-Tersenghi · Random Instances and Phase Transitions (Simons Institute, 2016)
• 32mLocal Statistics, Semidefinite Programming, and Community DetectionJess Banks · Computational Phase Transitions (Simons Institute, 2020)
• 47mLearning Probabilistic Models for Graph Partitioning in the Presence of NoiseAravindan Vijayaraghavan · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 25mFundamental Limit of Community Detection in Stochastic Block ModelsEmmanuel Abbe · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 24mIs it easier to count communities than find them?Cynthia Rush, Fiona Skerman, Alexander S Wein, Dana Yang · ITCS 2023