RTG: A Recursive Realistic Graph Generator using Random Typing

author: Leman Akoglu, Carnegie Mellon University
published: Oct. 20, 2009,   recorded: September 2009,   views: 609
Categories
You might be experiencing some problems with Your Video player.

Slides

Slides
0:00 RTG: A Recursive Realistic Graph Generator using Random Typing
0:10 Outline, Motivation, Problem Definition
0:15 Motivation - 1
0:39 Motivation - 2
1:34 Problem Definition
2:10 Outline, Related Work
2:14 Related Work
2:22 Related Work 1: Graph Properties
2:30 Related Work 2: Graph Generators
2:50 Related Work 2: Graph Generators 1
3:02 Related Work 2: Graph Generators 2
3:27 Related Work 2: Graph Generators 3
3:45 Related Work 2: Graph Generators 4
3:48 Related Work 2: Graph Generators 5
3:51 Related Work 2: Graph Generators 4
3:57 Related Work 2: Graph Generators 5
4:06 Outline, A Little History
4:08 A Little History - 1
4:43 A Little History - 2, Mandelbrot
5:06 A Little History - 2, Miller
5:37 A Little History - 2 , Conrad and Mitzenmacher
5:57 Outline, Proposed Model
5:59 Preliminary Model 1 , Space
6:39 Preliminary Model 1 , Lemma 1
6:50 Graph Properties 1
6:53 Preliminary Model 1, Densification
7:25 Advantages of the Preliminary Model 1
8:05 Problems of the Preliminary Model 1, 1- Multinomial degree distributions
8:44 Problems of the Preliminary Model 1, 2- No homophily, no community structure
9:12 Preliminary Model 2 , Solution to Problem 1
9:33 Preliminary Model 2 , Solution to Problem 2
9:53 Proposed Model , Solution to Problem 2
10:17 Proposed Model , Solution to Problem 2, How do we choose the keys?
10:38 Proposed Model , Solution to Problem 2, (0<β<1: imbalance factor)
10:54 Proposed Model , Solution to Problem 2, homophily
11:13 Proposed Model , Parameters
11:39 Proposed Model. Generalizations
12:32 Outline, Experimental Results
12:34 Experimental Results, How does RTG model real graphs?
12:56 Experimental Results, Blognet RTG 1
13:33 Experimental Results, Blognet RTG 2
13:47 Experimental Results, Blognet RTG 3
14:04 Graph Properties 2
14:25 Experimental Results 1, Blognet RTG 3
14:54 Experimental Results, Blognet RTG 4
15:13 Experimental Results, Blognet RTG 5
15:40 Experimental Results, Blognet RTG 6
16:03 Experimental Results, Blognet RTG 7
16:29 Graph Properties 3
16:34 Experimental Results 2, Com2Cand - RTG 1
16:39 Experimental Results 2, Com2Cand - RTG 2
16:40 Experimental Results 2, Com2Cand - RTG 3
16:42 Experimental Results 2, Com2Cand - RTG 4
17:25 Experimental Results 2, Com2Cand - RTG 5
17:34 Graph Properties 4
17:40 Experimental Results, On “modularity”
18:27 Graph Properties 5
18:36 Experimental Results, On complexity
18:47 Outline, Conclusion
18:49 Conclusion 1
19:09 Conclusion 2
19:13 Conclusion 1
19:21 Conclusion 2
19:31 Contact

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.
 
    Delicious Bibliography

Description

We propose a new, recursive model to generate realistic graphs, evolving over time. Our model has the following properties: it is (a) flexible, capable of generating the cross product of weighted/unweighted, directed/undirected, uni/bipartite graphs; (b) realistic, giving graphs that obey eleven static and dynamic laws that real graphs follow (we formally prove that for several of the (power) laws and we estimate their exponents as a function of the model parameters); (c) parsimonious, requiring only four parameters. (d) fast, being linear on the number of edges; (e) simple, intuitively leading to the generation of macroscopic patterns. We empirically show that our model mimics two real-world graphs very well: Blognet (unipartite, undirected, unweighted) with 27K nodes and 125K edges; and Committee-to-Candidate campaign donations (bipartite, directed, weighted) with 23K nodes and 880K edges. We also show how to handle time so that edge/weight additions are bursty and self-similar.

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Write your own review or comment:

make sure you have javascript enabled or clear this field: