2008 MicroscopicEvolutionofSocialNet

(Leskovec et al., 2008) ⇒ Jure Leskovec, Lars Backstrom, Ravi Kumar, and Andrew Tomkins. (2008). “Microscopic Evolution of Social Networks.” In: Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2008). doi:10.1145/1401890.1401948

Subject Headings:

Notes

Cited By

Quotes

Author Keywords

Abstract

We present a detailed study of network evolution by analyzing four large online social networks with full temporal information about node and edge arrivals. For the first time at such a large scale, we study individual node arrival and edge creation processes that collectively lead to macroscopic properties of networks. Using a methodology based on the maximum-likelihood principle, we investigate a wide variety of network formation strategies, and show that edge locality plays a critical role in evolution of networks. Our findings supplement earlier network models based on the inherently non-local preferential attachment.

Based on our observations, we develop a complete model of network evolution, where nodes arrive at a prespecified rate and select their lifetimes. Each node then independently initiates edges according to a "gap" process, selecting a destination for each edge according to a simple triangle-closing model free of any parameters. We show analytically that the combination of the gap distribution with the node lifetime leads to a power law out-degree distribution that accurately reflects the true network in all four cases. Finally, we give model parameter settings that allow automatic evolution and generation of realistic synthetic networks of arbitrary scale.

References

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2008 MicroscopicEvolutionofSocialNet	Jure Leskovec Andrew Tomkins Lars Backstrom Ravi Kumar			Microscopic Evolution of Social Networks				10.1145/1401890.1401948