2007 GraphEvolutionDensific...

• (Leskovec et al., 2007) ⇒ Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. (2007). “Graph Evolution: Densification and Shrinking Diameters.” In: Journal ACM Transactions on Knowledge Discovery from Data (TKDD), (1:1). doi:10.1145/1217299.1217301

Subject Headings: Graph Mining.

Cited By

• ~204 http://scholar.google.com/scholar?q=%22Graph+Evolution%3A+Densification+and+shrinking+diameters%22+2007

Quotes

Abstract

How do real graphs evolve over time? What are normal growth patterns in social, technological, and information networks? Many studies have discovered patterns in static graphs, identifying properties in a single snapshot of a large network or in a very small number of snapshots; these include heavy tails for in- and out-degree distributions, communities, small-world phenomena, and others. However, given the lack of information about network evolution over long periods, it has been hard to convert these findings into statements about trends over time.

Here we study a wide range of real graphs, and we observe some surprising phenomena. First, most of these graphs densify over time with the number of edges growing superlinearly in the number of nodes. Second, the average distance between nodes often shrinks over time in contrast to the conventional wisdom that such distance parameters should increase slowly as a function of the number of nodes (like O(log n) or O(log(log n)).

Existing graph generation models do not exhibit these types of behavior even at a qualitative level. We provide a new graph generator, based on a forest fire spreading process that has a simple, intuitive justification, requires very few parameters (like the flammability of nodes), and produces graphs exhibiting the full range of properties observed both in prior work and in the present study.

We also notice that the forest fire model exhibits a sharp transition between sparse graphs and graphs that are densifying. Graphs with decreasing distance between the nodes are generated around this transition point.

Last, we analyze the connection between the temporal evolution of the degree distribution and densification of a graph. We find that the two are fundamentally related. We also observe that real networks exhibit this type of relation between densification and the degree distribution.

References

• S. Boucheron, G. Lugosi, and P. Massart, A sharp concentration inequality with applications, Random Structures Algorithms 16 (2000), 277–292.
• E. J. Candes, and P. S. Loh, Image reconstruction with ridgelets, SURF Technical report, California Institute of Technology, 2002.
• S. S. Chen, D. L. Donoho, and M. A. Saunders, Atomic decomposition by basis pursuit, SIAM J. Scientific Computing 20 (1999), 33–61.
• A. H. Delaney, and Y. Bresler, A fast and accurate iterative reconstruction algorithm for parallel-beam tomography, IEEE Trans. Image Processing, 5 (1996), 740–753.
• D. C. Dobson, and F. Santosa, Recovery of blocky images from noisy and blurred data, SIAM J. Appl. Math. 56 (1996), 1181–1198.
• D.L. Donoho, P.B. Stark, Uncertainty principles and signal recovery, SIAM J. Appl. Math. 49 (1989), 906–931.
• D.L. Donoho and X. Huo, Uncertainty principles and ideal atomic decomposition, IEEE Transactions on Information Theory, 47 (2001), 2845–2862.
• D. L. Donoho and M. Elad, Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ1 minimization. Proceedings of Natl. Acad. Sci. USA 100 (2003), 2197–2202.
• M. Elad and A.M. Bruckstein, A generalized uncertainty principle and sparse representation in pairs of RN bases, IEEE Transactions on Information Theory, 48 (2002), 2558–2567.
• P. Feng, and Y. Bresler, Spectrum-blind minimum-rate sampling and reconstruction of multiband signals, in Proceedings of IEEE int. Conference Acoust. Speech and Sig. Proc., (Atlanta, GA), 3 (1996), 1689–1692.
• P. Feng, and Y. Bresler, A multicoset sampling approach to the missing cone problem in computer aided tomography, in Proceedings of IEEE International Symposium Circuits and Systems, (Atlanta, GA), 2 (1996), 734–737.
• A. Feuer and A. Nemirovsky, On sparse representations in pairs of bases, Accepted to the IEEE Transactions on Information Theory in November 2002. 38[13] J. J. Fuchs, On sparse representations in arbitrary redundant bases, IEEE Transactions on Information Theory, 50 (2004), 1341–1344.
• R. Gribonval and M. Nielsen, Sparse representations in unions of bases, Technical report, IRISA, November 2002.
• C. Mistretta, Personal communication (2004).
• F. Santosa, and W. W. Symes, Linear inversion of band-limited reflection seismograms, SIAM J. Sci. Statist. Comput. 7 (1986), 1307–1330.
• P. Stevenhagen, H.W. Lenstra Jr., Chebotar¨ev and his density theorem, Math. Intelligencer 18 (1996), no. 2, 26–37.
• T. Tao, An uncertainty principle for cyclic groups of prime order, preprint. math.CA/0308286
• J. A. Tropp, Greed is good: Algorithmic results for sparse approximation, Technical Report, The University of Texas at Austin, 2003.
• J. A. Tropp, Just relax: Convex programming methods for subset selection and sparse approximation, Technical Report, The University of Texas at Austin, 2004.
• M. Vetterli, P. Marziliano, and T. Blu, Sampling signals with finite rate of innovation, IEEE Transactions on Signal Processing, 50 (2002), 1417–1428.
• A. C. Gilbert, S. Guha, P. Indyk, S. Muthukrishnan, M. Strauss, Near-optimal sparse Fourier representations via sampling, 34th ACM Symposium on Theory of Computing, Montréal, May 2002.
• A. C. Gilbert, S. Muthukrishnan, and M. Strauss, Beating the B2 bottleneck in estimating B-term Fourier representations, unpublished manuscript, May 2004.

---

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2007 GraphEvolutionDensific...	Jon Kleinberg Jure Leskovec			Graph Evolution: Densification and Shrinking Diameters			http://www.maths.tcd.ie/~mnl/store/CandesRombergTao2004a.pdf