Viewpoint

Strange Kinetics Shape Network Growth

    Ivan Bonamassa
    • Department of Network and Data Science, Central European University, Vienna, Austria
Physics 17, 96
A connection between time-varying networks and transport theory opens prospects for developing predictive equations of motion for networks.
I. Bonamassa/Central European University
Figure 1: Artistic illustration of the mapping proposed by Papadopoulos and collaborators recasting the discrete growth of networks into continuous, diffusive-like behaviors of particles on latent geometric spaces.

Many real-world networks change over time. Think, for example, of social interactions, gene activation in a cell, or strategy making in financial markets, where connections and disconnections occur all the time. Understanding and anticipating these microscopic kinetics is an overarching goal of network science, not least because it could enable the early detection and prevention of natural and human-made disasters. A team led by Fragkiskos Papadopoulos of Cyprus University of Technology has gained groundbreaking insights into this problem by recasting the discrete dynamics of a network as a continuous time series [1] (Fig. 1). In doing so, the researchers have discovered that if the breaking and forming of links are represented as a particle moving in a suitable geometric space, then its motion is subdiffusive—that is, slower than it would be if it diffused normally. What’s more, the particles’ motions are well described by fractional Brownian motion, a generalization of Einstein’s classic model. This feat establishes a profound connection between the kinetics of time-varying or “temporal” networks and anomalous transport theory, opening fresh prospects for developing predictive equations of motion for networks.

Networks, whether they represent a brain or an infrastructure, are dynamical systems in which a set of points, or nodes, are linked together according to basic wiring rules. Identifying these rules has been a major leitmotif in network science. Over the years, a consensus has coalesced around two equally important factors that shape connections: “popularity,” in which highly connected nodes attract the majority of new connections over time, and “similarity”—or homophily, as it is called in the context of sociology—which embodies the tendency of similar entities to link. In a seminal article from 2012, Papadopoulos and a different team of collaborators examined networks built using a wiring rule that optimized the product of these two factors: a new node would connect to the most connected and most similar among the existing nodes [2]. Such networks could accurately describe many fundamental features of real systems, including the small-world property, the high level of clustering and self-similarity.

Most importantly, those model networks also comprised a latent geometric representation lurking in their discrete structure. To reveal this geometric mapping, one projects the nodes of a growing network onto points on a two-dimensional disk. Nascent nodes are assigned a radial coordinate defined as the logarithm of their time since birth. Because older nodes have more chance to attract connections, time since birth is a measure of popularity. Meanwhile, angular coordinates are assigned such that the closer two nodes are to each other on the circle, the more similar they are. In this representation, the optimal wiring rule has a simple geometric interpretation: it connects nodes at a minimum distance in hyperbolic space. Characterized by its negative curvature, this space comes into play because the hyperbolic distance between two nodes is equivalent to minimizing the product of their popularity and similarity.

Mapping networks onto latent geometric spaces brings into action an arsenal of physics tools and ideas that usually apply only to continuous systems. Among these tools are geometric renormalization and the identification of spacetime symmetries, analogous to those characterizing cosmology or general relativity, which leave the large-scale structure of networks invariant. This is why the incorporation of geometric concepts is a game changer in network physics: it transcends the discrete topological nature of networks, enabling their study in continuous spaces [3].

In their latest work, Papadopoulos and his collaborators applied this powerful quality of network geometry to tackle a grand challenge in network science: Do fundamental equations of motion exist that characterize the temporal evolution of networked complex systems? To see why this question might be tricky, consider the history of network dynamics. It’s a well-researched area that has relied on a wealth of discrete models predicting the large-scale structure of networks from simple wiring rules [4]. On the one hand, the discrete nature of these models has helped to reveal profound phenomena accompanying network growth, such as Bose-Einstein condensation of edges in which a single node captures a macroscopic fraction of available links [5] and phase transitions akin to the Berezinskii-Kosterlitz-Thouless transition in two-dimensional spin models [6]. On the other hand, that same discreteness has forestalled the identification of common aspects of the stochastic processes that accompany network evolution, thereby hindering the formulation of a unified theoretical framework. The advance made by Papadopoulos and his team is rooted in the idea that the discrete growth of networks can be mapped onto a continuous single-particle trajectory in their corresponding geometric space. The kinetics can then be understood through classical transport theory, which has the potential to lead to more general equations of motion.

By leveraging the hyperbolic representation, Papadopoulos and his team showed that the trajectories of six different real-world temporal networks—among them, US air transportation, Bitcoin transactions, and arXiv collaborations—exhibit universal subdiffusive kinetics that are well described by a generalization of Brownian motion called fractional Brownian motion. Subdiffusive kinetics of this genre usually arise in crowded biological systems, where particles spread in environments characterized by impenetrable walls or energy barriers [7]. The observation by Papadopoulos and his team of a hidden fractional Brownian motion driving network growth suggests a similar interpretation. Clusters and modular structures, commonly found in real-world networks, confine the system’s growth by acting as topological traps for new nodes. Properties like clustering, which quantifies the prevalence of triangles in networks, are proxies for geometricity. This is because they reflect the existence of an underlying metric that increases the likelihood that nodes sharing a neighbor are also connected [8]. It is therefore reasonable to expect that the latent subdiffusive growth of networks has something to do with their underlying geometry. Indeed, Papadopoulos and his team provide results supporting this expectation. The researchers show that network models that lack a latent geometric space also lack any latent subdiffusive motion and instead have purely diffusive trajectories.

This finding has exciting implications. In general, kinetics whose variance grows slowly over time are more likely to be predictable. The latent trajectories analyzed by Papadopoulos and his team do indeed exhibit a notable degree of predictability with remarkably slow-growing variances—a property that makes them akin to so-called rough volatility financial models [9]. In the same vein, the strong resemblance to biological processes raises important questions. Specifically, why do temporal networks evolve through subdiffusive motion? Could this be because it leads to adaptive improvements [10] in a way akin to the evolution of living cells?

More generally, how helpful will latent kinetics turn out to be in forecasting tipping points or catastrophic shifts in, say, housing markets or epidemics? Also, Papadopoulos and his team observed subdiffusive trajectories, but what about superdiffusive motion? Does it have a geometric representation too? We don’t know yet whether answering questions of this kind will culminate in some fundamental equation of motion for networks. For the time being, Papadopoulos and his team’s feat nevertheless enables us to envision avenues of future research toward meeting this grand challenge.

References

  1. E. S. Papaefthymiou et al., “Fundamental dynamics of popularity-similarity trajectories in real networks,” Phys. Rev. Lett. 132, 257401 (2024).
  2. F. Papadopoulos et al., “Popularity versus similarity in growing networks,” Nature 489, 537 (2012).
  3. M. Boguñá et al., “Network geometry,” Nat. Rev. Phys. 3, 114 (2021).
  4. S. N. Dorogovtsev et al., “Critical phenomena in complex networks,” Rev. Mod. Phys. 80, 1275 (2008).
  5. G. Bianconi and A.-L. Barabási, “Bose-Einstein condensation in complex networks,” Phys. Rev. Lett. 86, 5632 (2001).
  6. D. S. Callaway et al., “Are randomly grown graphs really random?” Phys. Rev. E 64, 041902 (2001).
  7. E. Barkai et al., “Strange kinetics of single molecules in living cells,” Phys. Today 65, 29 (2012).
  8. D. Krioukov, “Clustering implies geometry in networks,” Phys. Rev. Lett. 116, 208302 (2016).
  9. J. Gatheral et al., “Volatility is rough,” in Commodities, edited by M. A. H. Dempster and K. Tang (Chapman and Hall/CRC, Boca Raton, 2022), p. 659.
  10. A. Li et al., “The fundamental advantages of temporal networks,” Science 358, 1042 (2017).

About the Author

Image of Ivan Bonamassa

Ivan Bonamassa is a postdoctoral researcher at the Central European University, Austria, and he is supported by Dynaset, a European Research Council Synergy Grant. He received his PhD in physics in 2021 at Bar-Ilan University, Israel, under the supervision of Shlomo Havlin. There, he explored and developed physical realizations of interdependent networks. His research encompasses the physics of complex systems, with particular interest in critical phenomena, phase transitions and, more recently, developing theoretical and computational tools for the study of physical networks.


Read PDF

Subject Areas

Statistical Physics

Related Articles

Network Science Applied to Urban Transportation
Computational Physics

Network Science Applied to Urban Transportation

A simple model based on network theory can reproduce the complex structures seen in urban transportation networks. Read More »

Improving Assessments of Climate Tipping Points
Complex Systems

Improving Assessments of Climate Tipping Points

Statistical properties of fluctuations of certain parameters describing a complex system can reveal when that system is approaching a tipping point. Read More »

Time-Symmetric Motion Maximizes Energy Efficiency in Fluid
Statistical Physics

Time-Symmetric Motion Maximizes Energy Efficiency in Fluid

Researchers discovered a trick for dragging an object in a fluid with minimal effort, suggesting an optimal strategy for nanorobots. Read More »

More Articles