Inferring Temporal Information from a Snapshot of a Dynamic Network

Jithin K. Sreedharan, Abram Magner, Ananth Grama, Wojciech SzpankowskiScientific 2019 · DOI

Abstract

The problem of reverse-engineering the evolution of a dynamic network, known broadly as network archaeology, is one of profound importance in diverse application domains. In analysis of infection spread, it reveals the spatial and temporal processes underlying infection. In analysis of biomolecular interaction networks (e.g., protein interaction networks), it reveals early molecules that are known to be differentially implicated in diseases. In economic networks, it reveals flow of capital and associated actors. Beyond these recognized applications, it provides analytical substrates for novel studies - for instance, on the structural and functional evolution of the human brain connectome. In this paper, we model, formulate, and rigorously analyze the problem of inferring the arrival order of nodes in a dynamic network from a single snapshot. We derive limits on solutions to the problem, present methods that approach this limit, and demonstrate the methods on a range of applications, from inferring the evolution of the human brain connectome to conventional citation and social networks, where ground truth is known.

Introduction

Many real-world systems—ranging from social networks and disease outbreaks to the developing human brain—are inherently dynamic. However, researchers often only have access to a "snapshot": the current state of the network without the timestamps of when each node or edge appeared. This paper introduces a framework for "network archaeology," the art of reconstructing the historical growth of a dynamic network from such a static snapshot.

The challenge is to reverse-engineer this evolution to identify critical temporal milestones. For instance, determining the arrival order of nodes can help identify "patient zero" in an epidemic, find the original source of a viral misinformation campaign, or understand which regions of the brain developed first. The fundamental hurdle is that networks often contain symmetries and "equiprobable" structures that make it impossible to distinguish the exact arrival order of every single node with high probability.

Methodology: The Peeling Algorithm

The authors approach the problem by shifting the goal from finding a total order (a perfect 1-to-n list) to a partial order, which involves grouping nodes into "bins" based on their relative arrival times. This shift is necessitated by the mathematical impossibility of recovering a perfect chronological order due to network symmetries.

Graph symmetries and permutations illustrate the difficulty of distinguishing node arrival order based solely on topology.

The Peeling Heuristic

The core of the proposed solution is the Peeling algorithm. This heuristic works by identifying nodes with the lowest degree (specifically degree m, the number of edges a node brings when it joins). In many growth models, these are statistically likely to be the newest nodes. The algorithm "peels" these nodes away and then repeats the process on the remaining graph. Nodes removed in earlier steps are classified as "younger," while those remaining until the end are considered the "ancestors."

To refine this, the authors developed Peeling+, an extension that attempts to order nodes within the same bin by analyzing the average "age" (bin number) of their neighbors. Furthermore, they formulated the problem as a rational linear integer program to find the optimal tradeoff between Density (the number of node pairs the algorithm attempts to order) and Precision (the accuracy of those guesses).

Experimental Validation

The researchers validated their methods on a diverse set of synthetic and real-world data, including Barabási-Albert models, citation networks (ArXiv), co-authorship bibliographies (DBLP), and social interaction networks (Facebook).

A complex network snapshot G used to test the inference of node arrival order.

Key Results

  • High Precision: On real-world datasets like ArXiv and DBLP, the Peeling algorithm achieved precision scores between 0.70 and 0.78, meaning nearly 80% of the inferred temporal relations were correct.
  • Brain Evolution: When applied to the human brain connectome (using fMRI data from the Cambridge-Buckner and HCP datasets), the algorithm identified the primary visual cortex (V1) and primary auditory cortex (A1) as "early" arrivals. Conversely, the uncinate fasciculus was identified as a "late" arrival. These findings align with established biological understanding of brain development, despite the algorithm having no prior biological knowledge.
  • Efficiency: While optimal solvers are computationally expensive, the Peeling heuristics are highly efficient, running in $O(n \log n)$ time, making them scalable to large-scale networks.

Insights and Future Directions

The study reveals that the graph's topology acts as a physical record of its own creation. The "Peeling" method works because, in many growth models, older nodes naturally accumulate more edges over time—the "rich-get-richer" effect. Surprisingly, the algorithms performed well even on networks that didn't strictly follow theoretical growth models, suggesting that "peeling" logic is a universal property of many growing systems.

However, limitations remain. The methods assume the network grows primarily by adding nodes and edges; they may struggle with networks experiencing significant edge deletion. Future work aims to extend this archaeology beyond node arrival to infer the evolution of higher-order structures like triads, motifs, and community clusters, potentially providing new tools to identify malicious actors in social networks who work in collusion.

Summary updated

Abstract

The problem of reverse-engineering the evolution of a dynamic network, known broadly as network archaeology, is one of profound importance in diverse application domains. In analysis of infection spread, it reveals the spatial and temporal processes underlying infection. In analysis of biomolecular interaction networks (e.g., protein interaction networks), it reveals early molecules that are known to be differentially implicated in diseases. In economic networks, it reveals flow of capital and associated actors. Beyond these recognized applications, it provides analytical substrates for novel studies - for instance, on the structural and functional evolution of the human brain connectome. In this paper, we model, formulate, and rigorously analyze the problem of inferring the arrival order of nodes in a dynamic network from a single snapshot. We derive limits on solutions to the problem, present methods that approach this limit, and demonstrate the methods on a range of applications, from inferring the evolution of the human brain connectome to conventional citation and social networks, where ground truth is known.
BibTeX
@inproceedings{sreedharan2019inferring,
  author = {Jithin K. Sreedharan and Abram Magner and Ananth Grama and Wojciech Szpankowski},
  title = {{Inferring Temporal Information from a Snapshot of a Dynamic Network}},
  booktitle = {Scientific},
  year = {2019},
  doi = {10.1038/s41598-019-38912-0},
}
Figure