Session B28: Network Theory and Applications to Complex Systems

Topological duality in complex networks

Duality enhances our understanding of complex systems by establishing symmetry properties and multiplicity with important consequences in theoretical studies and real-world applications. However, whether complex networks exhibit a duality is still largely unknown. That is because in the classical formalism, where the network interacting unit is the node, it is hard to define a dual dimension and its relation with the primal counterpart. The recently introduced multilayer network formalism offers a unique opportunity to overcome this limitation. In a multilayer network, nodes get connected within and between different layers, the latter representing different types of connectivity or scales. Here, the basic interacting unit is the node-layer duplet, which allows to naturally define a complex networks' duality. On one side, there is the standard primal nodewise dimension where connectivity is regarded from the nodes' perspective. On the other side, there is the dual layerwise dimension where connectivity is observed from the layers' viewpoint. Through rigorous analytical methods and extensive simulations, we demonstrated that nodewise and layerwise connectivity characterize different-but-related aspects of the same system. Critically, both are essential for fully describing the basic structural properties, but only one is in general better positioned to capture the underlying network (re)organization. Such duality enabled a better understanding and characterization of various real-world networks, spanning social, infrastructure, and biological systems. Notably, we discovered that neurodegeneration in Alzheimer's disease is mostly characterized by the disruption of information transfer between different frequencies of brain activity (dual dimension), rather than between spatially distributed brain areas (primal dimension). By shedding light on previously unappreciated hidden properties, we provide a foundation for future investigations into the structure and dynamics of interconnected systems, with broader implications in a wide range of disciplines, including network science, systems biology, and social network analysis.   

Neural embeddings unveil simplicity in complex systems

The cornerstone of any complex systems analysis, whether it is the Internet, social networks, or biological organisms, is the effectiveness of their representation. While traditional methods utilize discrete representations such as networks, recent neural network advancements provide continuous representations, or embeddings. Neural embeddings map entities into a vector space, enabling new operationalization of abstract inquiries.

Statistical physics of urban mobility

Predictive models for human mobility have important applications in many fields including traffic control, ubiquitous computing, and urban planning. The predictive performance of models in the literature varies quite broadly, from over 90% to under 40%. In the first part of my talk, I review the role of data and mobility metrics in the accuracy of mobility predictions. We discuss how a few mechanisms are important factors in our ability to predict human mobility. 

Then I combine two well-known approaches in network and transportation science: (i) The macroscopic fundamental diagram (MFD), which examines the characteristics of urban traffic flow at the network level, including the relationship between flow, density, and speed. (ii) Percolation theory, which investigates the topological and dynamical aspects of complex networks, including traffic networks. Combining these two approaches, we find that the maximum number of congested clusters and the maximum MFD flow occur at the same moment, precluding network percolation (i.e. traffic collapse). These insights describe the transition of the average network flow from the uncongested phase to the congested phase in parallel with the percolation transition from sporadic congested links to a large, congested cluster of links. 

Lastly, I use individual mobility metrics to measure the urban spatial structure. While it usually evolves slowly, it can change fast during large-scale emergency events, as well as due to urban renewal in rapidly developing countries. This work presents an approach to delineate such urban dynamics in quasi-real-time through a human mobility metric, the mobility centrality index. As a case study, we tracked the urban dynamics of eleven Spanish cities during the COVID-19 pandemic. Results revealed that their structures became more monocentric during the lockdown in the first wave, but kept their regular spatial structures during the second wave. To provide a more comprehensive understanding of mobility from home, we also introduce a dimensionless metric, which measures the extent of home-based travel and provides statistical insights into the transmission of COVID-19. By utilizing individual mobility data, our metrics enable the detection of changes in the urban spatial structure.   

Unlabeled Network Science

Even though the structure of a network is an unlabeled graph, a vast majority of network models in network science and random graphs are models of labeled graphs. The difference between labeled and unlabeled random graph models is typically negligible in dense graphs. In sparse graphs, however, this difference is quite significant.

We illustrate this difference in three examples. We first review what is currently known about unlabeled Erdos-Renyi (ER) graphs. Even though the leading term of their entropy is the same as in labeled ER graphs (a necessary but not sufficient condition for model equivalence), their degree distributions are very different. In the configuration model (random graphs with a given degree sequence), the leading entropy terms may have different prefactors in labeled and unlabeled graphs. Our main results are tight lower and upper bounds for the entropy of labeled and unlabeled sparse one-dimensional random geometric graphs. We prove that their entropies scale differently, indicating that the leading contribution to the "randomness" of the labeled graphs comes from their random labeling, versus their random structure.

These results suggest a need for "unlabeled network science," reexamining the adequacy of certain models of random labeled graphs in applications to the statistical analysis of the structure of real-world networks. The difference between labeled and unlabeled random structures is likely to be even more significant in higher-order network models (hypergraphs and simplicial complexes), and poses a collection of challenging open problems in the theory of sparse graph limits.   

Unified framework for hybrid percolation transitions based on microscopic dynamics

A hybrid percolation transition (HPT) exhibits both discontinuity of the order parameter and critical behavior at the transition point. Such dynamic transitions can occur in two ways: by cluster pruning with suppression of loop formation of cut links or by cluster merging with suppression of the creation of large clusters. While the microscopic mechanism of the former is understood in detail, a similar framework is missing for the latter. By studying two distinct cluster merging models, we uncover the universal mechanism of the features of HPT-s at a microscopic level. We find that these features occur in three steps: (i) medium-sized clusters accumulate due to the suppression rule hindering the growth of large clusters, (ii) those medium size clusters eventually merge and a giant cluster increases rapidly, and (iii) the suppression effect becomes obsolete and the kinetics is governed by the Erd˝os-R´enyi type of dynamics. We show that during the second and third period, the growth of the largest component must proceed in the form of a Devil's staircase. We characterize the critical behavior by two sets of exponents associated with the order parameter and cluster size distribution, which are related to each other by a scaling relation. Extensive numerical simulations are carried out to support the theory where a specific method is applied for finite-size scaling analysis to enable handling the large fluctuations of the transition point. Our results provide a unified theoretical framework for the HPT.