en-de
en-es
en-fr
en-sl
en
en-zh
0.25
0.5
0.75
1.25
1.5
1.75
2
Modeling real-world networks using Kronecker multiplication
Published on 2007-03-2011825 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
Presentation
Modeling networks using Kronecker multiplication00:03
Introduction00:37
New approach (1)02:40
New approach (2)04:26
Outline04:54
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
Graph Generators26:10
Kronecker graphs27:02
Recursive Graph Generation27:30
Kronecker Product – a Graph27:43
Kronecker Graphs – Formally:28:59
Kronecker Product – Definition29:27
Kronecker Graphs29:46
Kronecker Graphs – Intuition29:53
How to randomize a graph?30:15
Stochastic Kronecker Graphs30:27
Problem Definition31:20
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
Conclusion01:10:37