0.25
0.5
0.75
1.25
1.5
1.75
2
Scalable Modeling of Real Graphs using Kronecker Multiplication
Published on Jun 23, 200710068 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? We propose to u
Related categories
Chapter list
Modeling Real Graphs using Kronecker Multiplication00:00
Modeling large networks00:24
The problem00:45
Why is this important?01:27
Statistical properties of networks02:23
The model: Kronecker graphs03:33
Idea: Recursive graph generation03:59
Kronecker product: Graph04:43
Kronecker product: Definition05:20
Kronecker graphs05:49
Kronecker product: Graph06:15
Stochastic Kronecker graphs06:43
Kronecker graphs: Intuition07:33
Properties of Kronecker graphs09:11
Model estimation: approach09:42
Fitting Kronecker graphs10:14
Challenge 1: Node correspondence11:06
Challenge 2: calculating P(G|T,s)11:59
Model estimation: solution12:28
Solution 1: Node correspondence 13:20
Sampling node correspondences13:55
Solution 2: Calculating P(G|T,s)15:20
Solution 2: Calculating P(G|T,s)0116:03
Experiments: synthetic data17:01
Experiments: real networks17:45
AS graph (N=6500, E=26500)18:31
AS: comparing graph properties19:07
AS: comparing graph properties0120:01
Epinions graph (N=76k, E=510k)20:27
Epinions graph (N=76k, E=510k)0121:15