Physics-Inspired Algorithms and Phase Transitions in Community Detection - 2014 Symposium

Explore a physics-inspired approach to community detection in this 48-minute lecture from the Santa Fe Institute's Annual Science Board Symposium. Delve into the stochastic block model, statistical inference, and belief propagation techniques. Examine phase transitions in community detection, from detectable to undetectable, and investigate hierarchical clustering methods. Learn about the non-backtracking operator and its applications in trust and centrality analysis. Gain insights into the intersection of physics culture and machine learning, and discover the challenges and opportunities in this field.

Intro
What is structure?
Statistical inference
The stochastic block model
Assortative and disassortative
Likelihood and energy
Statistical significance
What's the best labeling?
Belief propagation (a.k.a. the cavity method)
The Karate Club: leaders vs. followers
The Karate Club: two factions
Two local optima in free energy
Active learning: update the model as we learn more
The double life of Belief Propagation
A phase transition: detectable to undetectable communities
Phase transitions in semisupervised learning
Hierarchical clustering
Clustering nodes with eigenvalues
When does this work?
The non-backtracking operator
Comparing with standard spectral methods
Non-backtracking for trust and centrality: avoid the echo chamber
Morals
Physics culture meets machine learning
Challenges
Shameless Plug