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 in-
vestigate 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 net-
work evolution, where nodes arrive at a prespecified rate and select
their lifetimes. Each node then independently initiates edges ac-
cording to a “gap” process, selecting a destination for each edge ac-
cording 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.
%0 Conference Paper
%1 Leskovec08microscopicEvolution
%A Leskovec, Jure
%A Backstrom, Lars
%A Kumar, Ravi
%A Tomkins, Andrew
%B KDD '08: Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining
%C New York, NY, USA
%D 2008
%I ACM
%K evolution master_thesis microscopic
%P 462--470
%R http://doi.acm.org/10.1145/1401890.1401948
%T Microscopic evolution of social networks
%U http://portal.acm.org/citation.cfm?id=1401890.1401948&coll=GUIDE&dl=GUIDE&CFID=6888978&CFTOKEN=39430661
%X 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 in-
vestigate 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 net-
work evolution, where nodes arrive at a prespecified rate and select
their lifetimes. Each node then independently initiates edges ac-
cording to a “gap” process, selecting a destination for each edge ac-
cording 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.
%@ 978-1-60558-193-4
@inproceedings{Leskovec08microscopicEvolution,
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 in-
vestigate 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 net-
work evolution, where nodes arrive at a prespecified rate and select
their lifetimes. Each node then independently initiates edges ac-
cording to a “gap” process, selecting a destination for each edge ac-
cording 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.},
added-at = {2014-10-04T16:23:00.000+0200},
address = {New York, NY, USA},
author = {Leskovec, Jure and Backstrom, Lars and Kumar, Ravi and Tomkins, Andrew},
biburl = {https://www.bibsonomy.org/bibtex/2e1743c9b9fde98839206a475bbed1bf0/subhashpujari},
booktitle = {KDD '08: Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining},
description = {Microscopic evolution of social networks},
doi = {http://doi.acm.org/10.1145/1401890.1401948},
interhash = {e6896bf5621609ddb653fffe38585cad},
intrahash = {e1743c9b9fde98839206a475bbed1bf0},
isbn = {978-1-60558-193-4},
keywords = {evolution master_thesis microscopic},
location = {Las Vegas, Nevada, USA},
pages = {462--470},
publisher = {ACM},
timestamp = {2014-10-04T16:23:00.000+0200},
title = {Microscopic evolution of social networks},
url = {http://portal.acm.org/citation.cfm?id=1401890.1401948&coll=GUIDE&dl=GUIDE&CFID=6888978&CFTOKEN=39430661},
year = 2008
}