0.25
0.5
0.75
1.25
1.5
1.75
2
Modeling real-world networks using Kronecker multiplication
Published on Mar 20, 200711817 Views
Given a large, real graph, how can we generate a synthetic graph that matches its properties, i.e., it has similar degree distribution, similar (small) diameter, similar spectrum, etc? First,
Related categories
Chapter list
Modeling networks using Kronecker multiplication00:03
Introduction00:37
New approach (1)02:40
New approach (2)04:26
Outline04:54
Outline04:58
Statistical properties of networks05:14
Small-world effect (1)06:11
Small-world effect (2)07:52
Degree distributions (1)08:51
Degree distributions (2)09:52
Degree distributions (3)10:31
Poisson vs. Scale-free network11:48
Spectral properties21:19
Temporal Graph Patterns22:14
Temporal Patterns – Densification22:26
Networks over time: Densification23:23
Densification & degree distribution24:07
Shrinking diameters24:10
Patterns hold in many graphs24:55
Outline25:51
Graph Generators26:10
Kronecker graphs27:02
Recursive Graph Generation27:30
Kronecker Product – a Graph27:43
Kronecker Product – a Graph28:52
Kronecker Graphs – Formally:28:59
Kronecker Product – a Graph29:16
Kronecker Graphs – Formally:29:20
Kronecker Product – Definition29:27
Kronecker Graphs29:46
Kronecker Graphs – Intuition29:53
How to randomize a graph?30:15
Kronecker Product – a Graph30:20
Stochastic Kronecker Graphs30:27
Outline31:12
Problem Definition31:20
Outline31:42
Why fitting generative models?32:02
Problem definition32:55
Fitting Kronecker to Real Data33:54
Challenge 1: Node labeling36:19
Challenge 2: calculating P(G|Θ,σ)37:49
Our solutions38:59
Sampling node labelings (1)41:39
Sampling node labelings (2)42:36
Calculating P(G|Θ,σ)47:33
Convergence of fitting50:11
AS graph (N=6500, E=26500)56:53
Epinions graph (N=76k, E=510k)58:13
Scalability01:02:16
Model selection01:03:41
Epinions graph (N=76k, E=510k)01:09:00
Conclusion01:10:37
AS graph (N=6500, E=26500)01:15:40
Epinions graph (N=76k, E=510k)01:16:10