Reconstructing the evolution history of networked complex systems

Complex networks are generic representations of diverse complex systems across biology, ecology, and social science, encoding interactions among system components. Evolution is a defining feature of these systems, yet the mechanisms governing the transformation from simple structures to complex forms, the emergence of patterns and functionalities, and future evolutionary directions remain open questions. Real-world networks exhibit hierarchical community structures, assortativity/disassortativity, local clustering, and motifs, making it difficult to capture their evolution with concise rules. Classical models, such as preferential attachment (PA), explain the scale-free degree distribution but not other features and may contradict them (e.g., zero clustering and lack of communities in PA-generated networks). This study aims to restore the temporal sequence of edge formation in an evolving network from its final structure to uncover underlying mechanisms and improve predictive tasks.

Prior work on network evolution has largely focused on specific features, notably PA and its variants that yield power-law degree distributions. However, these models often fail to simultaneously reproduce other ubiquitous properties such as community structure and clustering. Extensive studies have characterized network features (assortativity, clustering, motifs) and analyzed growth in social and biological networks, but a unified mechanism capturing co-evolution of multiple structural properties has been lacking. Methods for node and network embedding (e.g., Node2Vec, DeepWalk, LINE, Struct2Vec, SDNE) provide low-dimensional representations useful for learning tasks, and ranking measures (e.g., Borda count) and rank correlation (Kendall’s τ, Spearman’s ρ) assess ordering consistency. Transfer learning has been surveyed for cross-domain adaptation but remains challenging in real networks with differing generative processes.

The goal is to reconstruct the growing edge sequence from the final network structure using a two-step machine learning framework. Step 1 (supervised learning with partial history): For a network with partial evolution history (Network A), embed each edge into a low-dimensional vector. Edge vectors are obtained via node embeddings (Node2Vec, DeepWalk, SDNE, LINE, Struct2Vec) with edge representation as the Hadamard product of endpoint node vectors, and via a vector of eleven classical edge features. An ensemble of six comparative paradigm neural network (CPNN) models is trained on pairs of edges with known generation order to predict pairwise relative order. An additional output based on the single best-performing edge feature is included. The ensemble’s final output is a weighted average of seven probabilities, with weights selected via grid search. Predicted pairwise orders are aggregated using Borda’s method: for each edge i, the Borda count u_i sums votes u_ij indicating whether i is newer than j; edges are ranked ascending by u_i to form the restored temporal sequence. Performance is measured by pairwise accuracy x and overall sequence error ε, defined as normalized RMSE of position differences D_i = a_i − â_i across E edges. A theoretical relationship is derived: ε_theory = sqrt[x(1−x)] / (2x−1) * 1/sqrt(E), valid for x > 0.5 + 1/(4E), showing ε scales as 1/sqrt(E). Simulations and pseudo code illustrate obtaining distributions of D_i/E for fine- and coarse-grained ground truth. Step 2 (transfer learning for networks without history): For a target network (Network B) with only final structure, embed edges and align embeddings to Network A via a linear transformation. Nodes in both networks are sorted by degree quantiles; matrices H_A and H_B are formed from ordered node vectors. Find L minimizing ||H_B L − H_A|| by least squares: L = (H_B^T H_B)^{-1} H_B^T H_A. Apply the ensemble model trained on Network A to aligned embeddings of Network B and use the same ranking algorithm to infer Network B’s formation history.

Application to 17 real-world networks (protein-protein interaction (PPI), world trade web (WTW), collaboration, animal interactions, transportation) shows high restoration performance. Pairwise accuracy x rapidly exceeds 75% with small training data and saturates around using only 5% of edge pairs with time information. Theoretical and simulation results confirm that overall sequence error ε decreases with higher x and larger E, following ε_theory = sqrt[x(1−x)] / (2x−1) * 1/sqrt(E), implying that for large networks, models slightly better than random (x just above 0.5 + 1/(4E)) yield reliable trajectories. Distributions of D_i/E are bell-shaped and symmetric around zero in both simulations and real networks, consistent with theory. Transfer learning substantially outperforms direct validation on synthetic models. Across BA, PSO, and fitness networks (N=500, 1000), transfer accuracies x^b are ≈0.83–0.86, while direct validation x^d are ≈0.65–0.70, demonstrating effective restoration using only final structures. Mechanism interpretation: Restored sequences reproduce PA strength comparable to real networks (PPI Fungi, WTW, Collaboration), while additionally revealing community-preserving growth. In the fungi PPI meso-level protein function network, restored evolution shows edges preferentially added within functional communities, maintaining strong modularity, whereas pure PA simulation connects between communities and weakens modularity. Restored adjacency matrices and function networks closely match real snapshots, and modularity trajectories align with real data. Structural properties: Restored sequences closely match real trajectories for degree assortativity, local clustering, and shortest path lengths across PPI (Bacteria), WTW, and animal (Weaver) networks, while random sequences or pure PA diverge markedly. Link prediction: Using restored edge order in collapsed weighted tensor construction and TSVD dramatically improves prediction. Reported improvements (area under curve): PPI Fungi ↑21.1%, PPI Bacteria ↑67.6%, Collaboration (Chaos) ↑7.6%, WTW ↑25.1%, Animal (Weaver) ↑216.7%. Gains are consistent across other link prediction methods as well.

The study demonstrates that the evolution history of networked complex systems can be reliably reconstructed from the final structure using graph-based embeddings, pairwise comparative learning, and ranking aggregation. The theoretical scaling of error with 1/sqrt(E) explains strong performance on large networks and the feasibility of restoration when pairwise predictions slightly exceed random accuracy. Restored trajectories enable mechanistic insights beyond degree-based PA, uncovering co-evolution of preferential attachment with community-preserving dynamics, consistent with functional organization in biological networks. The method enhances practical tasks like link prediction, offering substantial accuracy gains where traditional algorithms have plateaued. Together, these results address the core problem of inferring temporal formation processes, providing a general tool to study structure-function relationships and dynamic evolution in diverse domains.

This work introduces a machine learning framework that reconstructs high-resolution edge formation histories of complex networks from their final structures. It provides theoretical guarantees linking pairwise prediction accuracy to overall sequence error, shows strong empirical performance across varied real networks, and reveals co-evolutionary mechanisms such as simultaneous preferential attachment and community reinforcement. The restored sequences significantly boost link prediction accuracy. Future research directions include handling edge and node deletions, improving credibility assessments under sparse or biased time-stamped data, and developing transfer learning methods applicable to heterogeneous real-world networks. The approach opens avenues for analyzing evolution and functionality in life sciences, brain science, ecology, information science, and beyond.

1. The model assumes edges persist once created, whereas many real systems feature edge/node deletions and divergence. 2) Real datasets often provide few time-stamped edge pairs, typically biased toward later snapshots, complicating credibility assessment of restorations. 3) Transfer learning was demonstrated mainly on synthetic networks with similar mechanisms; adapting transfer to heterogeneous real networks remains challenging and requires further exploration.