Distribution-Free Models of Social and Information Networks
Talkat Optimization and Decision-Making Under Uncertainty (Simons Institute, September 2016) · 2016-09-19..09-23·
summary
Proposes two distribution-free graph classes motivated by triadic closure and proves concrete positive results. For triangle-dense graphs (global transitivity bounded away from 0) establishes a decomposition theorem that extracts disjoint, radius‑≤2 dense subgraphs covering a constant fraction of triangles using a practical Jaccard similarity cleaner plus a one‑hop/selected two‑hop extraction; implementation runs in time proportional to wedges (empirically ~N^1.5) and preserves 60–90% of triangles on real data. For C-closed graphs (pairs with ≥C common neighbors must be adjacent) proves at most N^2·3^{C/3} maximal cliques, so clique enumeration is polytime for fixed C via an inductive Moon–Moser based argument.
AI-written summary · about
chapters (21)
- 0:00Intro
- 2:45Social Networks Are Special
- 4:00Motivating Questions
- 4:43Inspiration: Hybrid Models
- 6:23Key Property: Triadic Closure
- 9:16On Power-Law Graphs
- 12:46Triange-Dense Graphs (Cartoon)
- 13:56Triangle-Dense Graphs
- 17:29What Do They Look Like?
- 18:22Model of Social Networks?
- 19:27A Decomposition Theorem
- 21:44Consequences
- 26:27Jaccard Similarity
- 28:57The Cleaner: Post-Conditions
- 31:13The Extractor
- 38:39C-Closed Graphs (Cartoon)
- 40:31C-Closed Graphs: Examples
- 42:27Enumerating Maximal Cliques
- 44:32Fixed-Parameter Tractability
- 47:48Proof by Picture
- 50:29Some Open Questions
related talks
41mGeneral Network Models with Transitive Structures
49mRecent Advances in Counting Sparse Graphs
35mLocal Statistics, Semidefinite Programming, and Community Detection II
56mTesting Thresholds for High-dimensional Sparse Random Geometric Graphs
01h 04mNonparametric Bayesian Methods: Models, Algorithms, and Applications IV
43mInformation-Theoretic Bounds and Phase Transitions in Community Detection and High-Dimensional Clust
31mSimple Models and Exact Algorithms for Computing Network Modules
35mDistributed Models for Private Analysis of Graph Data