Abstract
In temporal ordered clustering, given a single snapshot of a dynamic network in which nodes arrive at distinct time instants, we aim at partitioning its nodes into $K$ ordered clusters $\mathcal{C}_1 \prec \cdots \prec \mathcal{C}_K$ such that for $i < j$, nodes in cluster $\mathcal{C}_i$ arrived before nodes in cluster $\mathcal{C}_j$. This problem is significant for applications like tracking fake news or information spread. We formulate an integer programming framework to find optimal clustering as a strict partial order set, achieving high precision for a fixed density. We develop a sequential importance procedure and design unsupervised and semi-supervised algorithms to approximate the optimal solution. Our methods are validated on synthetic (vertex copying model) and real-world networks (ArXiv, Wikipedia), demonstrating superior performance over traditional heuristics.
Introduction
Inferring the arrival order of nodes from a single network snapshot—a "still photo" of a dynamic process—is a critical challenge in data science. Unlike scenarios where a full history is available, researchers often only have the final state. Determining node age is essential for identifying the source of rumors, tracking biological evolution, or understanding information cascades.
Traditional heuristics, such as the "older is bigger" rule (where degree correlates with age), often fail in complex growth models like the duplication-divergence (DD) model common in biological networks. Furthermore, structural symmetries in graphs often make a total 1-to-N ranking mathematically impossible. To address these issues, we propose Temporal Ordered Clustering: partitioning nodes into chronologically ordered groups where every node in an earlier cluster is older than those in subsequent clusters.
Methodology
The problem is framed as a constrained optimization task aimed at maximizing precision (correctly ordered pairs) for a given density (total pairs ordered).
Optimization and Relaxation
We initially formulate the problem as an Integer Program (IP). However, due to its high computational complexity ($O(n^{12})$), we introduce a Linear Programming (LP) relaxation ($O(n^7)$) that focuses on finding a partial order. This partial order represents the temporal dependencies between nodes as a directed acyclic graph (DAG).
Sequential Importance Sampling (SIS)
To estimate the probability $p_{u,v}$ that node $u$ is older than node $v$, we develop a Sequential Importance Sampling (SIS) procedure. This method "unwinds" the network by iteratively removing nodes from the final snapshot, effectively reverse-engineering the growth process.
Semi-Supervised Learning
We also introduce a semi-supervised approach that incorporates a small fraction of "perfect pairs" (known historical data). This additional information helps prune the search space and resolve structural symmetries that typically confound unsupervised methods.
Experimental Evaluation
The proposed algorithms were evaluated on several datasets:
- Synthetic (DD Model): Used as a stress test due to its high symmetry and non-monotonic degree-age relationship.
- ArXiv Citation Network: A real-world network where publication dates provide the ground truth.
- Simple English Wikipedia: A network of hyperlinks between articles.
- CollegeMsg: A private messaging network.
Key Results
- Performance: The LP-based partial order approach achieved precision nearly identical to the full IP while being significantly faster.
- Heuristic Comparison: On ArXiv and Wikipedia, our probabilistic sorting algorithm outperformed standard baselines like degree-based sorting.
- Impact of Supervision: Providing just 1% of the true arrival order led to a dramatic increase in precision, as these labels "break" the structural symmetries in the graph.
Conclusion
Temporal ordered clustering provides a statistically sound framework for reconstructing network history when total ordering is impossible. Our work demonstrates that even in models where degree is a poor proxy for age, probabilistic "unwinding" and partial order optimization can accurately recover chronological structure. Future work will focus on scaling these methods to massive graphs and accounting for network "churn," where nodes and edges are both added and deleted over time.
Summary updated