Leskovec www 2010
Contents
Citation
Leskovec, J., K. J Lang, and M. Mahoney. 2010. Empirical comparison of algorithms for network community detection. In Proceedings of the 19th international conference on World wide web, 631–640.
Online version
Summary
This paper presents an approach to Network Community Detection. 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
They use the Forest Fire method for graph generation. The goal of this method to construct a graph that has the properties of following densification power laws, long-tailed in and out degrees and shrinking diameter.
