Randomizing growing networks with a time-respecting null model

Abstract

Complex networks are often used to represent systems that are not static but grow with time: people make new friendships, new papers are published and refer to the existing ones, and so forth. To assess the statistical significance of measurements made on such networks, we propose a randomization methodology---a time-respecting null model---that preserves both the network's degree sequence and the time evolution of individual nodes' degree values. By preserving the temporal linking patterns of the analyzed system, the proposed model is able to factor out the effect of the system's temporal patterns on its structure. We apply the model to the citation network of Physical Review scholarly papers and the citation network of US movies. The model reveals that the two datasets are strikingly different with respect to their degree-degree correlations, and we discuss the important implications of this finding on the information provided by paradigmatic node centrality metrics such as indegree and Google's PageRank. The randomization methodology proposed here can be used to assess the significance of any structural property in growing networks, which could bring new insights into the problems where null models play a critical role, such as the detection of communities and network motifs.

13 pages, 10 figures

References in corpus (11)

• Fast unfolding of communities in large networks
• Community detection in networks: A user guide
• Vital nodes identification in complex networks
• Activity driven modeling of time varying networks
• Finding Scientific Gems with Google
• Ranking Scientific Publications Using a Simple Model of Network Traffic
• Large-scale structure of time evolving citation networks
• Effective Distances for Epidemics Spreading on Complex Networks
• Experience versus Talent Shapes the Structure of the Web
• Identification of milestone papers through time-balanced network centrality
• Topological structure and the H-index in complex networks

Cited by in corpus (4)

• Unbiased evaluation of ranking metrics reveals consistent performance in science and technology citation data
• The long-term impact of ranking algorithms in growing networks
• Network-based ranking in social systems: three challenges
• Optimal timescale for community detection in growing networks