Difference between revisions of "Faloutsos KDD 2005"
From Cohen Courses
Jump to navigationJump to search (Created page with ' ==Citation== J. Leskovec, J. Kleinberg and C. Faloutsos. Graphs over Time: Densification Laws, Shrinking Diameters and Possible Explanations. ACM SIGKDD International Conferenc…') |
|||
| Line 1: | Line 1: | ||
| − | + | == Citation == | |
| − | + | J. Leskovec, J. Kleinberg and C. Faloutsos. Graphs over Time: Densification Laws, Shrinking Diameters | |
| + | and Possible Explanations. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2005. | ||
| + | |||
== Online version == | == Online version == | ||
| − | |||
[http://www.cs.cmu.edu/~jure/pubs/powergrowth-kdd05.pdf KDD 2005] | [http://www.cs.cmu.edu/~jure/pubs/powergrowth-kdd05.pdf KDD 2005] | ||
| + | == Summary == | ||
| + | This [[Category::paper]] presents an approach to [[AddressesProblem::Graph Generation]]. Here they try to answer the question of network evolution of over time. While static graph models have been studied, less is known about time-evolving graphs. They use the following [[UsesDataset::US_Patent_citation_dataset|Patent Citation Network]]. They study a number of real world graphs and observe some interesting phenomena. | ||
| − | + | * Most graphs densify over time with number of edges growing superlinearly with respect to the number of nodes | |
| − | + | * The average distance between nodes shrinks over time | |
| − | |||
| − | |||
| − | |||
| + | Since existing graph generation models do not model for such behaviors they propose a new graph generation model based on a '''forestfire''' approach. | ||
| − | + | == Method == | |
<math> | <math> | ||
\sum_{i=1}^{n} | \sum_{i=1}^{n} | ||
</math> | </math> | ||
Revision as of 17:52, 4 February 2011
Contents
Citation
J. Leskovec, J. Kleinberg and C. Faloutsos. Graphs over Time: Densification Laws, Shrinking Diameters and Possible Explanations. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2005.
Online version
Summary
This paper presents an approach to Graph Generation. Here they try to answer the question of network evolution of over time. While static graph models have been studied, less is known about time-evolving graphs. They use the following Patent Citation Network. They study a number of real world graphs and observe some interesting phenomena.
- Most graphs densify over time with number of edges growing superlinearly with respect to the number of nodes
- The average distance between nodes shrinks over time
Since existing graph generation models do not model for such behaviors they propose a new graph generation model based on a forestfire approach.
Method
