1
|
Zhang D, Kabuka MR. MARML: Motif-Aware Deep Representation Learning in Multilayer Networks. IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS 2024; 35:11649-11660. [PMID: 38113155 DOI: 10.1109/tnnls.2023.3341347] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 12/21/2023]
Abstract
The rapid increase in high-throughput, complex, and heterogeneous data has led to the adoption of network-structured models and analyses for interpretation. However, these data are inherently complex and challenging to understand, prompting researchers to turn to graph embedding methods to facilitate analysis. While general network embedding techniques have shown promise in improving downstream prediction and classification tasks, real-world data are complicated due to cross-domain interactions between different types of entities. Multilayered networks have been successful in integrating biological data to represent biological systems' hierarchy, but embedding nodes based on different types of interactions remains an unsolved problem. To address this challenge, we propose the Motif-aware deep representation learning in multilayer (MARML) networks for learning network representations. Our method considers recurring motif patterns, topological information, and attributive information from other sources as node features. We validated the MARML method using various multilayer network datasets. In addition, by incorporating motif information, MARML considers higher order connections across different hierarchies. The learned features exhibited excellent accuracy in tasks related to link prediction and link differentiation, enabling us to distinguish between existing and disconnected triplets. Through the integration of both intrinsic node attributes and topological network structures, we enhance our understanding of complex biological systems.
Collapse
|
2
|
Ibrahim AA, Muehlebach M, De Bacco C. Optimal Transport with Constraints: From Mirror Descent to Classical Mechanics. PHYSICAL REVIEW LETTERS 2024; 133:057401. [PMID: 39159100 DOI: 10.1103/physrevlett.133.057401] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 08/22/2023] [Accepted: 07/01/2024] [Indexed: 08/21/2024]
Abstract
Finding optimal trajectories for multiple traffic demands in a congested network is a challenging task. Optimal transport theory is a principled approach that has been used successfully to study various transportation problems. Its usage is limited by the lack of principled and flexible ways to incorporate realistic constraints. We propose a principled physics-based approach to impose constraints flexibly in optimal transport problems. Constraints are included in mirror descent dynamics using the D'Alembert-Lagrange principle from classical mechanics. This results in a sparse, local and linear approximation of the feasible set leading in many cases to closed-form updates.
Collapse
|
3
|
Patwardhan S, Barthelemy M, Erkol Ş, Fortunato S, Radicchi F. Symmetry breaking in optimal transport networks. Nat Commun 2024; 15:3758. [PMID: 38704371 PMCID: PMC11069546 DOI: 10.1038/s41467-024-48068-9] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 11/27/2023] [Accepted: 04/17/2024] [Indexed: 05/06/2024] Open
Abstract
Engineering multilayer networks that efficiently connect sets of points in space is a crucial task in all practical applications that concern the transport of people or the delivery of goods. Unfortunately, our current theoretical understanding of the shape of such optimal transport networks is quite limited. Not much is known about how the topology of the optimal network changes as a function of its size, the relative efficiency of its layers, and the cost of switching between layers. Here, we show that optimal networks undergo sharp transitions from symmetric to asymmetric shapes, indicating that it is sometimes better to avoid serving a whole area to save on switching costs. Also, we analyze the real transportation networks of the cities of Atlanta, Boston, and Toronto using our theoretical framework and find that they are farther away from their optimal shapes as traffic congestion increases.
Collapse
Affiliation(s)
- Siddharth Patwardhan
- Center for Complex Networks and Systems Research, Luddy School of Informatics, Computing, and Engineering, Indiana University, Bloomington, IN, 47408, USA
| | - Marc Barthelemy
- Université Paris-Saclay, CNRS, CEA, Institut de Physique Théorique, 91191, Gif-sur-Yvette, France.
- Centre d'Analyse et de Mathématique Sociales (CNRS/EHESS) 54 Avenue de Raspail, 75006, Paris, France.
| | - Şirag Erkol
- Center for Science of Science and Innovation, Kellogg School of Management, Northwestern University, Evanston, IL, 60208, USA
| | - Santo Fortunato
- Center for Complex Networks and Systems Research, Luddy School of Informatics, Computing, and Engineering, Indiana University, Bloomington, IN, 47408, USA.
| | - Filippo Radicchi
- Center for Complex Networks and Systems Research, Luddy School of Informatics, Computing, and Engineering, Indiana University, Bloomington, IN, 47408, USA.
| |
Collapse
|
4
|
Cheng Z, Ouyang M, Du C, Zhang H, Wang N, Hong L. Boundary effects on topological characteristics of urban road networks. CHAOS (WOODBURY, N.Y.) 2023; 33:073123. [PMID: 37433653 DOI: 10.1063/5.0145079] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 02/02/2023] [Accepted: 06/16/2023] [Indexed: 07/13/2023]
Abstract
Urban road networks (URNs), as simplified views and important components of cities, have different structures, resulting in varying levels of transport efficiency, accessibility, resilience, and many socio-economic indicators. Thus, topological characteristics of URNs have received great attention in the literature, while existing studies have used various boundaries to extract URNs for analysis. This naturally leads to the question of whether topological patterns concluded using small-size boundaries keep consistent with those uncovered using commonly adopted administrative boundaries or daily travel range-based boundaries. This paper conducts a large-scale empirical analysis to reveal the boundary effects on 22 topological metrics of URNs across 363 cities in mainland China. Statistical results show that boundaries have negligible effects on the average node degree, edge density, orientation entropy of road segments, and the eccentricity for the shortest or fastest routes, while other metrics including the clustering coefficient, proportion of high-level road segments, and average edge length together with route-related metrics such as average angular deviation show significant differences between road networks extracted using different boundaries. In addition, the high-centrality components identified using varied boundaries show significant differences in terms of their locations, with only 21%-28% of high-centrality nodes overlapping between the road networks extracted using administrative and daily travel range-based boundaries. These findings provide useful insights to assist urban planning and better predict the influence of a road network structure on the movement of people and the flow of socio-economic activities, particularly in the context of rapid urbanization and the ever-increasing sprawl of road networks.
Collapse
Affiliation(s)
- Zekai Cheng
- School of Artificial Intelligence and Automation, Huazhong University of Science and Technology, Wuhan 430074, China
| | - Min Ouyang
- School of Artificial Intelligence and Automation, Huazhong University of Science and Technology, Wuhan 430074, China
- Key Laboratory for Image Processing and Intelligent Control, Huazhong University of Science and Technology, Ministry of Education, Wuhan 430074, China
| | - Chongyang Du
- School of Artificial Intelligence and Automation, Huazhong University of Science and Technology, Wuhan 430074, China
| | - Hui Zhang
- School of Artificial Intelligence and Automation, Huazhong University of Science and Technology, Wuhan 430074, China
| | - Naiyu Wang
- College of Civil Engineering and Architecture, Zhejiang University, Hangzhou 310058, China
| | - Liu Hong
- School of Artificial Intelligence and Automation, Huazhong University of Science and Technology, Wuhan 430074, China
- Key Laboratory for Image Processing and Intelligent Control, Huazhong University of Science and Technology, Ministry of Education, Wuhan 430074, China
| |
Collapse
|
5
|
Nag Chowdhury S, Rakshit S, Hens C, Ghosh D. Interlayer antisynchronization in degree-biased duplex networks. Phys Rev E 2023; 107:034313. [PMID: 37073037 DOI: 10.1103/physreve.107.034313] [Citation(s) in RCA: 3] [Impact Index Per Article: 3.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 09/16/2022] [Accepted: 03/09/2023] [Indexed: 04/20/2023]
Abstract
With synchronization being one of nature's most ubiquitous collective behaviors, the field of network synchronization has experienced tremendous growth, leading to significant theoretical developments. However, most previous studies consider uniform connection weights and undirected networks with positive coupling. In the present article, we incorporate the asymmetry in a two-layer multiplex network by assigning the ratio of the adjacent nodes' degrees as the weights to the intralayer edges. Despite the presence of degree-biased weighting mechanism and attractive-repulsive coupling strengths, we are able to find the necessary conditions for intralayer synchronization and interlayer antisynchronization and test whether these two macroscopic states can withstand demultiplexing in a network. During the occurrence of these two states, we analytically calculate the oscillator's amplitude. In addition to deriving the local stability conditions for interlayer antisynchronization via the master stability function approach, we also construct a suitable Lyapunov function to determine a sufficient condition for global stability. We provide numerical evidence to show the necessity of negative interlayer coupling strength for the occurrence of antisynchronization, and such repulsive interlayer coupling coefficients cannot destroy intralayer synchronization.
Collapse
Affiliation(s)
- Sayantan Nag Chowdhury
- Department of Environmental Science and Policy, University of California, Davis, California 95616, USA
- Technology Innovation Hub (TIH), IDEAS (Institute of Data Engineering Analytics and Science Foundation), Indian Statistical Institute, 203 B. T. Road, Kolkata 700108, India
| | - Sarbendu Rakshit
- Department of Mechanical Engineering, University of California, Riverside, California 92521, USA
| | - Chittaranjan Hens
- Center for Computational Natural Sciences and Bioinformatics, International Institute of Information Technology, Gachibowli, Hyderabad 500032, India
| | - Dibakar Ghosh
- Physics and Applied Mathematics Unit, Indian Statistical Institute, 203 B. T. Road, Kolkata 700108, India
| |
Collapse
|
6
|
Ibrahim AA, Leite D, De Bacco C. Sustainable optimal transport in multilayer networks. Phys Rev E 2022; 105:064302. [PMID: 35854570 DOI: 10.1103/physreve.105.064302] [Citation(s) in RCA: 2] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 02/15/2022] [Accepted: 05/18/2022] [Indexed: 11/07/2022]
Abstract
Traffic congestion is one of the major challenges faced by the transportation industry. While this problem carries a high economic and environmental cost, the need for an efficient design of optimal paths for passengers in multilayer network infrastructures is imperative. We consider an approach based on optimal transport theory to route passengers preferably along layers that are more carbon-efficient than the road, e.g., rails. By analyzing the impact of this choice on performance, we find that this approach reduces carbon emissions considerably compared to shortest-path minimization. Similarly, we find that this approach distributes traffic more homogeneously, thus alleviating the risk of traffic congestion. Our results shed light on the impact of distributing traffic flexibly across layers guided by optimal transport theory.
Collapse
Affiliation(s)
| | - Daniela Leite
- Max Planck Institute for Intelligent Systems, Cyber Valley, Tübingen 72076, Germany
| | - Caterina De Bacco
- Max Planck Institute for Intelligent Systems, Cyber Valley, Tübingen 72076, Germany
| |
Collapse
|
7
|
Park SJ, Lee KM, Yang JS. Navigating optimal treaty-shopping routes using a multiplex network model. PLoS One 2021; 16:e0256764. [PMID: 34449830 PMCID: PMC8396775 DOI: 10.1371/journal.pone.0256764] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 04/05/2021] [Accepted: 08/13/2021] [Indexed: 11/24/2022] Open
Abstract
The international tax treaty system is a highly integrated and complex network. In this system, many multinational enterprises (MNEs) explore ways of reducing taxes by choosing optimal detour routes. Treaty abuse by these MNEs causes significant loss of tax revenues for many countries, but there is no systematic way of regulating their actions. However, it may be helpful to find a way of detecting the optimal routes by which MNEs avoid taxes and observe the effects of this behavior. In this paper, we investigate the international tax treaty network system of foreign investment channels based on real data and introduce a novel measure of tax-routing centrality and other centralities via network analysis. Our analysis of tax routing in a multiplex network reveals not only various tax-minimizing routes and their rates, but also new paths which cannot be found by navigating a single network layer. In addition, we identify strongly connected components of the multiplex tax treaty system with minimal tax shopping routes; more than 80 countries are included in this system. This means that there are far more pathways to be observed than can be detected on any given individual single layer. We provide a unified framework for analyzing the international tax treaty system and observing the effects of tax avoidance by MNEs.
Collapse
Affiliation(s)
- Sung Jae Park
- Graduate School of Future Strategy, Korea Advanced Institute of Science and Technology, Daejeon, Republic of Korea
- Johns Hopkins Carey Business School, Baltimore, MD, United States of America
| | - Kyu-Min Lee
- College of Business, Korea Advanced Institute of Science and Technology, Seoul, Republic of Korea
| | - Jae-Suk Yang
- Graduate School of Future Strategy, Korea Advanced Institute of Science and Technology, Daejeon, Republic of Korea
- * E-mail:
| |
Collapse
|
8
|
Abstract
Modeling traffic distribution and extracting optimal flows in multilayer networks is of the utmost importance to design efficient, multi-modal network infrastructures. Recent results based on optimal transport theory provide powerful and computationally efficient methods to address this problem, but they are mainly focused on modeling single-layer networks. Here, we adapt these results to study how optimal flows distribute on multilayer networks. We propose a model where optimal flows on different layers contribute differently to the total cost to be minimized. This is done by means of a parameter that varies with layers, which allows to flexibly tune the sensitivity to the traffic congestion of the various layers. As an application, we consider transportation networks, where each layer is associated to a different transportation system, and show how the traffic distribution varies as we tune this parameter across layers. We show an example of this result on the real, 2-layer network of the city of Bordeaux with a bus and tram, where we find that in certain regimes, the presence of the tram network significantly unburdens the traffic on the road network. Our model paves the way for further analysis of optimal flows and navigability strategies in real, multilayer networks.
Collapse
|
9
|
Chowdhury SN, Rakshit S, Buldú JM, Ghosh D, Hens C. Antiphase synchronization in multiplex networks with attractive and repulsive interactions. Phys Rev E 2021; 103:032310. [PMID: 33862752 DOI: 10.1103/physreve.103.032310] [Citation(s) in RCA: 18] [Impact Index Per Article: 6.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 08/26/2020] [Accepted: 02/16/2021] [Indexed: 06/12/2023]
Abstract
A series of recent publications, within the framework of network science, have focused on the coexistence of mixed attractive and repulsive (excitatory and inhibitory) interactions among the units within the same system, motivated by the analogies with spin glasses as well as to neural networks, or ecological systems. However, most of these investigations have been restricted to single layer networks, requiring further analysis of the complex dynamics and particular equilibrium states that emerge in multilayer configurations. This article investigates the synchronization properties of dynamical systems connected through multiplex architectures in the presence of attractive intralayer and repulsive interlayer connections. This setting enables the emergence of antisynchronization, i.e., intralayer synchronization coexisting with antiphase dynamics between coupled systems of different layers. We demonstrate the existence of a transition from interlayer antisynchronization to antiphase synchrony in any connected bipartite multiplex architecture when the repulsive coupling is introduced through any spanning tree of a single layer. We identify, analytically, the required graph topologies for interlayer antisynchronization and its interplay with intralayer and antiphase synchronization. Next, we analytically derive the invariance of intralayer synchronization manifold and calculate the attractor size of each oscillator exhibiting interlayer antisynchronization together with intralayer synchronization. The necessary conditions for the existence of interlayer antisynchronization along with intralayer synchronization are given and numerically validated by considering Stuart-Landau oscillators. Finally, we also analytically derive the local stability condition of the interlayer antisynchronization state using the master stability function approach.
Collapse
Affiliation(s)
- Sayantan Nag Chowdhury
- Physics and Applied Mathematics Unit, Indian Statistical Institute, 203 B. T. Road, Kolkata-700108, India
| | - Sarbendu Rakshit
- Physics and Applied Mathematics Unit, Indian Statistical Institute, 203 B. T. Road, Kolkata-700108, India
| | - Javier M Buldú
- Laboratory of Biological Networks, Center for Biomedical Technology-UPM, Madrid 28223, Spain
- Complex Systems Group and GISC, Universidad Rey Juan Carlos, Móstoles 28933, Spain
- Unmanned Systems Research Institute, Northwestern Polytechnical University, Xi'an 710072, China
| | - Dibakar Ghosh
- Physics and Applied Mathematics Unit, Indian Statistical Institute, 203 B. T. Road, Kolkata-700108, India
| | - Chittaranjan Hens
- Physics and Applied Mathematics Unit, Indian Statistical Institute, 203 B. T. Road, Kolkata-700108, India
| |
Collapse
|
10
|
Natera Orozco LG, Battiston F, Iñiguez G, Szell M. Data-driven strategies for optimal bicycle network growth. ROYAL SOCIETY OPEN SCIENCE 2020; 7:201130. [PMID: 33489269 PMCID: PMC7813224 DOI: 10.1098/rsos.201130] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.8] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Figures] [Subscribe] [Scholar Register] [Received: 06/30/2020] [Accepted: 11/16/2020] [Indexed: 06/12/2023]
Abstract
Urban transportation networks, from pavements and bicycle paths to streets and railways, provide the backbone for movement and socioeconomic life in cities. To make urban transport sustainable, cities are increasingly investing to develop their bicycle networks. However, it is yet unclear how to extend them comprehensively and effectively given a limited budget. Here we investigate the structure of bicycle networks in cities around the world, and find that they consist of hundreds of disconnected patches, even in cycling-friendly cities like Copenhagen. To connect these patches, we develop and apply data-driven, algorithmic network growth strategies, showing that small but focused investments allow to significantly increase the connectedness and directness of urban bicycle networks. We introduce two greedy algorithms to add the most critical missing links in the bicycle network focusing on connectedness, and show that they outmatch both a random approach and a baseline minimum investment strategy. Our computational approach outlines novel pathways from car-centric towards sustainable cities by taking advantage of urban data available on a city-wide scale. It is a first step towards a quantitative consolidation of bicycle infrastructure development that can become valuable for urban planners and stakeholders.
Collapse
Affiliation(s)
| | - Federico Battiston
- Department of Network and Data Science, Central European University, 1100 Vienna, Austria
| | - Gerardo Iñiguez
- Department of Network and Data Science, Central European University, 1100 Vienna, Austria
- Department of Computer Science, Aalto University School of Science, 00076 Aalto, Finland
- Centro de Ciencias de la Complejidad, Universidad Nacional Autonóma de México, 04510 CDMX, Mexico
| | - Michael Szell
- NEtwoRks, Data, and Society (NERDS), IT University of Copenhagen, 2300 Copenhagen, Denmark
- ISI Foundation, 10126 Turin, Italy
- Complexity Science Hub Vienna, 1080 Vienna, Austria
| |
Collapse
|
11
|
Li M, Lü L, Deng Y, Hu MB, Wang H, Medo M, Stanley HE. History-dependent percolation on multiplex networks. Natl Sci Rev 2020; 7:1296-1305. [PMID: 34692158 PMCID: PMC8288926 DOI: 10.1093/nsr/nwaa029] [Citation(s) in RCA: 11] [Impact Index Per Article: 2.8] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 12/13/2019] [Revised: 02/12/2020] [Accepted: 02/18/2020] [Indexed: 12/01/2022] Open
Abstract
The structure of interconnected systems and its impact on the system dynamics is a much-studied cross-disciplinary topic. Although various critical phenomena have been found in different models, study of the connections between different percolation transitions is still lacking. Here we propose a unified framework to study the origins of the discontinuous transitions of the percolation process on interacting networks. The model evolves in generations with the result of the present percolation depending on the previous state, and thus is history-dependent. Both theoretical analysis and Monte Carlo simulations reveal that the nature of the transition remains the same at finite generations but exhibits an abrupt change for the infinite generation. We use brain functional correlation and morphological similarity data to show that our model also provides a general method to explore the network structure and can contribute to many practical applications, such as detecting the abnormal structures of human brain networks.
Collapse
Affiliation(s)
- Ming Li
- Department of Thermal Science and Energy Engineering, University of Science and Technology of China, Hefei 230026, China
| | - Linyuan Lü
- Institute of Fundamental and Frontier Sciences, University of Electronic Science and Technology of China, Chengdu 610054, China
| | - Youjin Deng
- Hefei National Laboratory for Physical Sciences at Microscale, Department of Modern Physics, and CAS Center for Excellence and Synergetic Innovation Center in Quantum Information and Quantum Physics, University of Science and Technology of China, Hefei 230026, China
| | - Mao-Bin Hu
- Department of Thermal Science and Energy Engineering, University of Science and Technology of China, Hefei 230026, China
| | - Hao Wang
- Institute of Fundamental and Frontier Sciences, University of Electronic Science and Technology of China, Chengdu 610054, China
| | - Matúš Medo
- Institute of Fundamental and Frontier Sciences, University of Electronic Science and Technology of China, Chengdu 610054, China
| | - H Eugene Stanley
- Alibaba Research Center for Complexity Sciences, Hangzhou Normal University, Hangzhou 310036, China
| |
Collapse
|
12
|
Rakshit S, Bera BK, Ghosh D. Invariance and stability conditions of interlayer synchronization manifold. Phys Rev E 2020; 101:012308. [PMID: 32069525 DOI: 10.1103/physreve.101.012308] [Citation(s) in RCA: 5] [Impact Index Per Article: 1.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 04/02/2019] [Indexed: 11/07/2022]
Abstract
We investigate interlayer synchronization in a stochastic multiplex hypernetwork which is defined by the two types of connections, one is the intralayer connection in each layer with hypernetwork structure and the other is the interlayer connection between the layers. Here all types of interactions within and between the layers are allowed to vary with a certain rewiring probability. We address the question about the invariance and stability of the interlayer synchronization state in this stochastic multiplex hypernetwork. For the invariance of interlayer synchronization manifold, the adjacency matrices corresponding to each tier in each layer should be equal and the interlayer connection should be either bidirectional or the interlayer coupling function should vanish after achieving the interlayer synchronization state. We analytically derive a necessary-sufficient condition for local stability of the interlayer synchronization state using master stability function approach and a sufficient condition for global stability by constructing a suitable Lyapunov function. Moreover, we analytically derive that intralayer synchronization is unattainable for this network architecture due to stochastic interlayer connections. Remarkably, our derived invariance and stability conditions (both local and global) are valid for any rewiring probabilities, whereas most of the previous stability conditions are only based on a fast switching approximation.
Collapse
Affiliation(s)
- Sarbendu Rakshit
- Physics and Applied Mathematics Unit, Indian Statistical Institute, Kolkata 700108, India
| | - Bidesh K Bera
- Department of Mathematics, Indian Institute of Technology Ropar, Punjab 140001, India.,Department of Solar Energy and Environmental Physics, BIDR, Ben-Gurion University of the Negev, Sede Boqer Campus, Midreshet Ben-Gurion, 8499000, Israel
| | - Dibakar Ghosh
- Physics and Applied Mathematics Unit, Indian Statistical Institute, Kolkata 700108, India
| |
Collapse
|
13
|
Kosmidis K, Jablonski KP, Muskhelishvili G, Hütt MT. Chromosomal origin of replication coordinates logically distinct types of bacterial genetic regulation. NPJ Syst Biol Appl 2020; 6:5. [PMID: 32066730 PMCID: PMC7026169 DOI: 10.1038/s41540-020-0124-1] [Citation(s) in RCA: 12] [Impact Index Per Article: 3.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 08/30/2019] [Accepted: 01/21/2020] [Indexed: 01/16/2023] Open
Abstract
For a long time it has been hypothesized that bacterial gene regulation involves an intricate interplay of the transcriptional regulatory network (TRN) and the spatial organization of genes in the chromosome. Here we explore this hypothesis both on a structural and on a functional level. On the structural level, we study the TRN as a spatially embedded network. On the functional level, we analyze gene expression patterns from a network perspective (“digital control”), as well as from the perspective of the spatial organization of the chromosome (“analog control”). Our structural analysis reveals the outstanding relevance of the symmetry axis defined by the origin (Ori) and terminus (Ter) of replication for the network embedding and, thus, suggests the co-evolution of two regulatory infrastructures, namely the transcriptional regulatory network and the spatial arrangement of genes on the chromosome, to optimize the cross-talk between two fundamental biological processes: genomic expression and replication. This observation is confirmed by the functional analysis based on the differential gene expression patterns of more than 4000 pairs of microarray and RNA-Seq datasets for E. coli from the Colombos Database using complex network and machine learning methods. This large-scale analysis supports the notion that two logically distinct types of genetic control are cooperating to regulate gene expression in a complementary manner. Moreover, we find that the position of the gene relative to the Ori is a feature of very high predictive value for gene expression, indicating that the Ori–Ter symmetry axis coordinates the action of distinct genetic control mechanisms.
Collapse
Affiliation(s)
- Kosmas Kosmidis
- Division of Theoretical Physics, Physics Department, Aristotle University of Thessaloniki, 54124, Thessaloniki, Greece.,PharmaInformatics Unit, Research Center ATHENA, Athens, Greece
| | - Kim Philipp Jablonski
- Department of Life Sciences and Chemistry, Jacobs University, Bremen, Germany.,Department of Biosystems Science and Engineering, ETH Zürich, Zürich, Switzerland
| | | | - Marc-Thorsten Hütt
- Department of Life Sciences and Chemistry, Jacobs University, Bremen, Germany.
| |
Collapse
|
14
|
Abstract
We develop graphlet analysis for multiplex networks and discuss how this analysis can be extended to multilayer and multilevel networks as well as to graphs with node and/or link categorical attributes. The analysis has been adapted for two typical examples of multiplexes: economic trade data represented as a 957-plex network and 75 social networks each represented as a 12-plex network. We show that wedges (open triads) occur more often in economic trade networks than in social networks, indicating the tendency of a country to produce/trade of a product in local structure of triads which are not closed. Moreover, our analysis provides evidence that the countries with small diversity tend to form correlated triangles. Wedges also appear in the social networks, however the dominant graphlets in social networks are triangles (closed triads). If a multiplex structure indicates a strong tie, the graphlet analysis provides another evidence for the concepts of strong/weak ties and structural holes. In contrast to Granovetter’s seminal work on the strength of weak ties, in which it has been documented that the wedges with only strong ties are absent, here we show that for the analyzed 75 social networks, the wedges with only strong ties are not only present but also significantly correlated.
Collapse
|
15
|
Chen J, Hu MB, Li M. Traffic-driven epidemic spreading in multiplex networks. Phys Rev E 2020; 101:012301. [PMID: 32069539 PMCID: PMC7217497 DOI: 10.1103/physreve.101.012301] [Citation(s) in RCA: 12] [Impact Index Per Article: 3.0] [Reference Citation Analysis] [Abstract] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 08/31/2019] [Indexed: 04/12/2023]
Abstract
Recent progress on multiplex networks has provided a powerful way to abstract the diverse interaction of a network system with multiple layers. In this paper, we show that a multiplex structure can greatly affect the spread of an epidemic driven by traffic dynamics. One of the interesting findings is that the multiplex structure could suppress the outbreak of an epidemic, which is different from the typical finding of spread dynamics in multiplex networks. In particular, one layer with dense connections can attract more traffic flow and eventually suppress the epidemic outbreak in other layers. Therefore, the epidemic threshold will be larger than the minimal threshold of the layers. With a mean-field approximation, we provide explicit expressions for the epidemic threshold and for the onset of suppressing epidemic spreading in multiplex networks. We also provide the probability of obtaining a multiplex configuration that suppresses the epidemic spreading when the multiplex is composed of: (i) two Erdős-Rényi layers and (ii) two scale-free layers. Therefore, compared to the situation of an isolated network in which a disease may be able to propagate, a larger epidemic threshold can be found in multiplex structures.
Collapse
Affiliation(s)
- Jie Chen
- School of Engineering Science, University of Science and Technology of China, Hefei 230026, People's Republic of China
| | - Mao-Bin Hu
- School of Engineering Science, University of Science and Technology of China, Hefei 230026, People's Republic of China
| | - Ming Li
- School of Engineering Science, University of Science and Technology of China, Hefei 230026, People's Republic of China
| |
Collapse
|
16
|
Gao L, Shu P, Tang M, Wang W, Gao H. Effective traffic-flow assignment strategy on multilayer networks. Phys Rev E 2019; 100:012310. [PMID: 31499882 DOI: 10.1103/physreve.100.012310] [Citation(s) in RCA: 21] [Impact Index Per Article: 4.2] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 08/16/2017] [Indexed: 11/07/2022]
Abstract
An efficient flow assignment strategy is of great importance to alleviate traffic congestion on multilayer networks. In this work, by considering the roles of nodes' local structures on the microlevel, and the different transporting speeds of layers in the macrolevel, an effective traffic-flow assignment strategy on multilayer networks is proposed. Both numerical and semianalytical results indicate that our proposed flow assignment strategy can reasonably redistribute the traffic flow of the low-speed layer to the high-speed layer. In particular, preferentially transporting the packets through small-degree nodes on the high-speed layer can enhance the traffic capacity of multilayer networks. We also find that the traffic capacity of multilayer networks can be improved by increasing the network size and the average degree of the high-speed layer. For a given multilayer network, there is a combination of optimal macrolevel parameter and optimal microlevel parameter with which the traffic capacity can be maximized. It is verified that real-world network topology does not invalidate the results. The semianalytical predictions agree with the numerical simulations.
Collapse
Affiliation(s)
- Lei Gao
- College of Information Science and Engineering, Shandong Agricultural University, Taian 271018, China.,Web Sciences Center, University of Electronic Science and Technology of China, Chengdu 610054, China
| | - Panpan Shu
- School of Sciences, Xi'an University of Technology, Xi'an 710054, China
| | - Ming Tang
- School of Mathematical Sciences, Shanghai Key Laboratory of PMMP, East China Normal University, Shanghai 200241, China.,Shanghai Key Laboratory of Multidimensional Information Processing, East China Normal University, Shanghai 200241, China
| | - Wei Wang
- Cybersecurity Research Institute, Sichuan University, Chengdu 610065, China
| | - Hui Gao
- Web Sciences Center, University of Electronic Science and Technology of China, Chengdu 610054, China
| |
Collapse
|
17
|
Abstract
Network analysis has driven key developments in research on animal behaviour by providing quantitative methods to study the social structures of animal groups and populations. A recent formalism, known as multilayer network analysis, has advanced the study of multifaceted networked systems in many disciplines. It offers novel ways to study and quantify animal behaviour through connected 'layers' of interactions. In this article, we review common questions in animal behaviour that can be studied using a multilayer approach, and we link these questions to specific analyses. We outline the types of behavioural data and questions that may be suitable to study using multilayer network analysis. We detail several multilayer methods, which can provide new insights into questions about animal sociality at individual, group, population and evolutionary levels of organization. We give examples for how to implement multilayer methods to demonstrate how taking a multilayer approach can alter inferences about social structure and the positions of individuals within such a structure. Finally, we discuss caveats to undertaking multilayer network analysis in the study of animal social networks, and we call attention to methodological challenges for the application of these approaches. Our aim is to instigate the study of new questions about animal sociality using the new toolbox of multilayer network analysis.
Collapse
Affiliation(s)
- Kelly R. Finn
- Animal Behavior Graduate Group, University of California, Davis, U.S.A
| | - Matthew J. Silk
- Environment and Sustainability Institute, University of Exeter, U.K
| | - Mason A. Porter
- Department of Mathematics, University of California, Los Angeles, U.S.A
| | - Noa Pinter-Wollman
- Department of Ecology and Evolutionary Biology, University of California, Los Angeles, U.S.A
| |
Collapse
|
18
|
Shu P, Liu QH, Wang S, Wang W. Social contagions on interconnected networks of heterogeneous populations. CHAOS (WOODBURY, N.Y.) 2018; 28:113114. [PMID: 30501222 DOI: 10.1063/1.5042677] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 06/03/2018] [Accepted: 10/26/2018] [Indexed: 06/09/2023]
Abstract
Recently, the dynamics of social contagions ranging from the adoption of a new product to the diffusion of a rumor have attracted more and more attention from researchers. However, the combined effects of individual's heterogenous adoption behavior and the interconnected structure on the social contagions processes have yet to be understood deeply. In this paper, we study theoretically and numerically the social contagions with heterogeneous adoption threshold in interconnected networks. We first develop a generalized edge-based compartmental approach to predict the evolution of social contagion dynamics on interconnected networks. Both the theoretical predictions and numerical results show that the growth of the final recovered fraction with the intralayer propagation rate displays double transitions. When increasing the initial adopted proportion or the adopted threshold, the first transition remains continuous within different dynamic parameters, but the second transition gradually vanishes. When decreasing the interlayer propagation rate, the change in the double transitions mentioned above is also observed. The heterogeneity of degree distribution does not affect the type of first transition, but increasing the heterogeneity of degree distribution results in the type change of the second transition from discontinuous to continuous. The consistency between the theoretical predictions and numerical results confirms the validity of our proposed analytical approach.
Collapse
Affiliation(s)
- Panpan Shu
- Xi'an University of Technology, Xi'an 710054, China
| | - Quan-Hui Liu
- Big Data Research Center,University of Electronic Science and Technology of China, Chengdu 610054, China
| | | | - Wei Wang
- Cybersecurity Research Institute, Sichuan University, Chengdu 610065, China
| |
Collapse
|
19
|
Ulusan A, Ergun O. Restoration of services in disrupted infrastructure systems: A network science approach. PLoS One 2018; 13:e0192272. [PMID: 29444191 PMCID: PMC5812613 DOI: 10.1371/journal.pone.0192272] [Citation(s) in RCA: 16] [Impact Index Per Article: 2.7] [Reference Citation Analysis] [Abstract] [MESH Headings] [Grants] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 07/14/2017] [Accepted: 11/16/2017] [Indexed: 11/18/2022] Open
Abstract
Due to the ubiquitous nature of disruptive extreme events, functionality of the critical infrastructure systems (CIS) is constantly at risk. In case of a disruption, in order to minimize the negative impact to the society, service networks operating on the CIS should be restored as quickly as possible. In this paper, we introduce a novel network science inspired measure to quantify the criticality of components within a disrupted service network and develop a restoration heuristic (Cent-Restore) that prioritizes restoration efforts based on this measure. As an illustrative case study, we consider a road network blocked by debris in the aftermath of a natural disaster. The debris obstructs the flow of relief aid and search-and-rescue teams between critical facilities and disaster sites, debilitating the emergency service network. In this context, the problem is defined as finding a schedule to clear the roads with the limited resources. First, we develop a mixed-integer programming model for the problem. Then we validate the efficiency and accuracy of the Cent-Restore heuristic on randomly generated instances by comparing it to the model. Furthermore, we use Cent-Restore to recommend real-time restoration plans for disrupted road networks of Boston and Manhattan and analyze the performance of the plans over time through resilience curves. We compare Cent-Restore to the current restoration guidelines proposed by FEMA and other strategies that prioritize the restoration efforts based on different measures. As a result we confirm the importance of including specific post-disruption attributes of the networks to create effective restoration strategies. Moreover, we explore the relationship between a service network’s resilience and its topological and operational characteristics under different disruption scenarios. The methods and insights provided in this work can be extended to other disrupted large-scale critical infrastructure systems in which the ultimate goal is to enable the functions of the overlaying service networks.
Collapse
Affiliation(s)
- Aybike Ulusan
- Mechanical and Industrial Engineering Department, Northeastern University, Boston, Massachusetts, United States of America
- * E-mail:
| | - Ozlem Ergun
- Mechanical and Industrial Engineering Department, Northeastern University, Boston, Massachusetts, United States of America
| |
Collapse
|
20
|
Manfredi S, Di Tucci E, Latora V. Mobility and Congestion in Dynamical Multilayer Networks with Finite Storage Capacity. PHYSICAL REVIEW LETTERS 2018; 120:068301. [PMID: 29481212 DOI: 10.1103/physrevlett.120.068301] [Citation(s) in RCA: 6] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 05/16/2017] [Revised: 12/11/2017] [Indexed: 06/08/2023]
Abstract
Multilayer networks describe well many real interconnected communication and transportation systems, ranging from computer networks to multimodal mobility infrastructures. Here, we introduce a model in which the nodes have a limited capacity of storing and processing the agents moving over a multilayer network, and their congestions trigger temporary faults which, in turn, dynamically affect the routing of agents seeking for uncongested paths. The study of the network performance under different layer velocities and node maximum capacities reveals the existence of delicate trade-offs between the number of served agents and their time to travel to destination. We provide analytical estimates of the optimal buffer size at which the travel time is minimum and of its dependence on the velocity and number of links at the different layers. Phenomena reminiscent of the slower is faster effect and of the Braess' paradox are observed in our dynamical multilayer setup.
Collapse
Affiliation(s)
- S Manfredi
- Department of Electrical Engineering and Information Technology, University of Naples Federico II, Naples I-80125, Italy
| | - E Di Tucci
- Department of Electrical Engineering and Information Technology, University of Naples Federico II, Naples I-80125, Italy
| | - V Latora
- School of Mathematical Sciences, Queen Mary University of London, London E1 4NS, United Kingdom
- Dipartimento di Fisica ed Astronomia, Università di Catania and INFN, I-95123 Catania, Italy
| |
Collapse
|
21
|
Lee M, Barbosa H, Youn H, Holme P, Ghoshal G. Morphology of travel routes and the organization of cities. Nat Commun 2017; 8:2229. [PMID: 29263392 PMCID: PMC5738436 DOI: 10.1038/s41467-017-02374-7] [Citation(s) in RCA: 20] [Impact Index Per Article: 2.9] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 03/08/2017] [Accepted: 11/24/2017] [Indexed: 11/09/2022] Open
Abstract
The city is a complex system that evolves through its inherent social and economic interactions. Mediating the movements of people and resources, urban street networks offer a spatial footprint of these activities. Of particular interest is the interplay between street structure and its functional usage. Here, we study the shape of 472,040 spatiotemporally optimized travel routes in the 92 most populated cities in the world, finding that their collective morphology exhibits a directional bias influenced by the attractive (or repulsive) forces resulting from congestion, accessibility, and travel demand. To capture this, we develop a simple geometric measure, inness, that maps this force field. In particular, cities with common inness patterns cluster together in groups that are correlated with their putative stage of urban development as measured by a series of socio-economic and infrastructural indicators, suggesting a strong connection between urban development, increasing physical connectivity, and diversity of road hierarchies. Complex networks are a useful tool to investigate the structure of cities and their street networks. Here the authors investigate the shape of travel routes in 92 cities and define a metric called inness which reveals connections between common urban features in cities with similar inness profiles.
Collapse
Affiliation(s)
- Minjin Lee
- Department of Energy Science, Sungkyunkwan University, Suwon, 16419, Korea
| | - Hugo Barbosa
- Department of Physics and Astronomy, University of Rochester, Rochester, NY, 14627, USA
| | - Hyejin Youn
- Kellogg School of Management at Northwestern University, Evanston, IL, 60208, USA.,Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, NM, 87501, USA.,London Mathematical Lab, London, WC2N 6DF, UK.,Northwestern Institute on Complex Systems, Northwestern University, Evanston, IL, 60208, USA
| | - Petter Holme
- Institute of Innovative Research, Tokyo Institute of Technology, Nagatsuta-cho 4259, Midori-ku, Yokohama, Kanagawa, 226-8503, Japan
| | - Gourab Ghoshal
- Department of Physics and Astronomy, University of Rochester, Rochester, NY, 14627, USA. .,Goergen Institute for Data Science, University of Rochester, Rochester, NY, 14627, USA.
| |
Collapse
|
22
|
Rakshit S, Majhi S, Bera BK, Sinha S, Ghosh D. Time-varying multiplex network: Intralayer and interlayer synchronization. Phys Rev E 2017; 96:062308. [PMID: 29347295 DOI: 10.1103/physreve.96.062308] [Citation(s) in RCA: 8] [Impact Index Per Article: 1.1] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 07/06/2017] [Indexed: 06/07/2023]
Abstract
A large class of engineered and natural systems, ranging from transportation networks to neuronal networks, are best represented by multiplex network architectures, namely a network composed of two or more different layers where the mutual interaction in each layer may differ from other layers. Here we consider a multiplex network where the intralayer coupling interactions are switched stochastically with a characteristic frequency. We explore the intralayer and interlayer synchronization of such a time-varying multiplex network. We find that the analytically derived necessary condition for intralayer and interlayer synchronization, obtained by the master stability function approach, is in excellent agreement with our numerical results. Interestingly, we clearly find that the higher frequency of switching links in the layers enhances both intralayer and interlayer synchrony, yielding larger windows of synchronization. Further, we quantify the resilience of synchronous states against random perturbations, using a global stability measure based on the concept of basin stability, and this reveals that intralayer coupling strength is most crucial for determining both intralayer and interlayer synchrony. Lastly, we investigate the robustness of interlayer synchronization against a progressive demultiplexing of the multiplex structure, and we find that for rapid switching of intralayer links, the interlayer synchronization persists even when a large number of interlayer nodes are disconnected.
Collapse
Affiliation(s)
- Sarbendu Rakshit
- Physics and Applied Mathematics Unit, Indian Statistical Institute, 203 B. T. Road, Kolkata-700108, India
| | - Soumen Majhi
- Physics and Applied Mathematics Unit, Indian Statistical Institute, 203 B. T. Road, Kolkata-700108, India
| | - Bidesh K Bera
- Physics and Applied Mathematics Unit, Indian Statistical Institute, 203 B. T. Road, Kolkata-700108, India
| | - Sudeshna Sinha
- Indian Institute of Science Education and Research Mohali, Manauli P.O. 140 306, Punjab, India
| | - Dibakar Ghosh
- Physics and Applied Mathematics Unit, Indian Statistical Institute, 203 B. T. Road, Kolkata-700108, India
| |
Collapse
|
23
|
Yubero P, Manrubia S, Aguirre J. The space of genotypes is a network of networks: implications for evolutionary and extinction dynamics. Sci Rep 2017; 7:13813. [PMID: 29062002 PMCID: PMC5653773 DOI: 10.1038/s41598-017-14048-x] [Citation(s) in RCA: 10] [Impact Index Per Article: 1.4] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 07/31/2017] [Accepted: 10/04/2017] [Indexed: 11/09/2022] Open
Abstract
The forcing that environmental variation exerts on populations causes continuous changes with only two possible evolutionary outcomes: adaptation or extinction. Here we address this topic by studying the transient dynamics of populations on complex fitness landscapes. There are three important features of realistic landscapes of relevance in the evolutionary process: fitness landscapes are rough but correlated, their fitness values depend on the current environment, and many (often most) genotypes do not yield viable phenotypes. We capture these properties by defining time-varying, holey, NK fitness landscapes. We show that the structure of the space of genotypes so generated is that of a network of networks: in a sufficiently holey landscape, populations are temporarily stuck in local networks of genotypes. Sudden jumps to neighbouring networks through narrow adaptive pathways (connector links) are possible, though strong enough local trapping may also cause decays in population growth and eventual extinction. A combination of analytical and numerical techniques to characterize complex networks and population dynamics on such networks permits to derive several quantitative relationships between the topology of the space of genotypes and the fate of evolving populations.
Collapse
Affiliation(s)
- Pablo Yubero
- Centro Nacional de Biotecnología, CSIC, c/Darwin 3, 28049, Madrid, Spain
| | - Susanna Manrubia
- Centro Nacional de Biotecnología, CSIC, c/Darwin 3, 28049, Madrid, Spain
- Grupo Interdisciplinar de Sistemas Complejos (GISC), Madrid, Spain
| | - Jacobo Aguirre
- Centro Nacional de Biotecnología, CSIC, c/Darwin 3, 28049, Madrid, Spain.
- Grupo Interdisciplinar de Sistemas Complejos (GISC), Madrid, Spain.
| |
Collapse
|
24
|
Ghariblou S, Salehi M, Magnani M, Jalili M. Shortest Paths in Multiplex Networks. Sci Rep 2017; 7:2142. [PMID: 28526822 PMCID: PMC5438413 DOI: 10.1038/s41598-017-01655-x] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.4] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 01/12/2017] [Accepted: 03/28/2017] [Indexed: 12/02/2022] Open
Abstract
The shortest path problem is one of the most fundamental networks optimization problems. Nowadays, individuals interact in extraordinarily numerous ways through their offline and online life (e.g., co-authorship, co-workership, or retweet relation in Twitter). These interactions have two key features. First, they have a heterogeneous nature, and second, they have different strengths that are weighted based on their degree of intimacy, trustworthiness, service exchange or influence among individuals. These networks are known as multiplex networks. To our knowledge, none of the previous shortest path definitions on social interactions have properly reflected these features. In this work, we introduce a new distance measure in multiplex networks based on the concept of Pareto efficiency taking both heterogeneity and weighted nature of relations into account. We then model the problem of finding the whole set of paths as a form of multiple objective decision making and propose an exact algorithm for that. The method is evaluated on five real-world datasets to test the impact of considering weights and multiplexity in the resulting shortest paths. As an application to find the most influential nodes, we redefine the concept of betweenness centrality based on the proposed shortest paths and evaluate it on a real-world dataset from two-layer trade relation among countries between years 2000 and 2015.
Collapse
Affiliation(s)
- Saeed Ghariblou
- Faculty of New Sciences and Technologies, University of Tehran, Tehran, Iran
- School of Computer Science, Institute for Research in Fundamental Science (IPM), Tehran, Iran
| | - Mostafa Salehi
- Faculty of New Sciences and Technologies, University of Tehran, Tehran, Iran.
- School of Computer Science, Institute for Research in Fundamental Science (IPM), Tehran, Iran.
| | - Matteo Magnani
- Department of Information Technology, Division of Computing Science, Uppsala University, Uppsala, Sweden
| | - Mahdi Jalili
- School of Engineering, RMIT University, Melbourne, Australia
| |
Collapse
|
25
|
Shu P, Gao L, Zhao P, Wang W, Stanley HE. Social contagions on interdependent lattice networks. Sci Rep 2017; 7:44669. [PMID: 28300198 PMCID: PMC5353708 DOI: 10.1038/srep44669] [Citation(s) in RCA: 18] [Impact Index Per Article: 2.6] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 11/09/2016] [Accepted: 02/13/2017] [Indexed: 11/15/2022] Open
Abstract
Although an increasing amount of research is being done on the dynamical processes on interdependent spatial networks, knowledge of how interdependent spatial networks influence the dynamics of social contagion in them is sparse. Here we present a novel non-Markovian social contagion model on interdependent spatial networks composed of two identical two-dimensional lattices. We compare the dynamics of social contagion on networks with different fractions of dependency links and find that the density of final recovered nodes increases as the number of dependency links is increased. We use a finite-size analysis method to identify the type of phase transition in the giant connected components (GCC) of the final adopted nodes and find that as we increase the fraction of dependency links, the phase transition switches from second-order to first-order. In strong interdependent spatial networks with abundant dependency links, increasing the fraction of initial adopted nodes can induce the switch from a first-order to second-order phase transition associated with social contagion dynamics. In networks with a small number of dependency links, the phase transition remains second-order. In addition, both the second-order and first-order phase transition points can be decreased by increasing the fraction of dependency links or the number of initially-adopted nodes.
Collapse
Affiliation(s)
- Panpan Shu
- School of Sciences, Xi’an University of Technology, Xi’an, 710054, China
| | - Lei Gao
- Web Sciences Center, University of Electronic Science and Technology of China, Chengdu, 610054, China
| | - Pengcheng Zhao
- School of Physics and Optoelectronic Engineering, Xidian University, Xi’an, 710071, China
| | - Wei Wang
- Web Sciences Center, University of Electronic Science and Technology of China, Chengdu, 610054, China
- Big data research center, University of Electronic Science and Technology of China, Chengdu 610054, China
- Center for Polymer Studies and Department of Physics, Boston University, Boston, Massachusetts, 02215, USA
| | - H. Eugene Stanley
- Center for Polymer Studies and Department of Physics, Boston University, Boston, Massachusetts, 02215, USA
| |
Collapse
|
26
|
Lotero L, Hurtado RG, Floría LM, Gómez-Gardeñes J. Rich do not rise early: spatio-temporal patterns in the mobility networks of different socio-economic classes. ROYAL SOCIETY OPEN SCIENCE 2016; 3:150654. [PMID: 27853531 PMCID: PMC5098956 DOI: 10.1098/rsos.150654] [Citation(s) in RCA: 11] [Impact Index Per Article: 1.4] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Subscribe] [Scholar Register] [Received: 12/01/2015] [Accepted: 09/09/2016] [Indexed: 05/20/2023]
Abstract
We analyse the urban mobility in the cities of Medellín and Manizales (Colombia). Each city is represented by six mobility networks, each one encoding the origin-destination trips performed by a subset of the population corresponding to a particular socio-economic status. The nodes of each network are the different urban locations whereas links account for the existence of a trip between two different areas of the city. We study the main structural properties of these mobility networks by focusing on their spatio-temporal patterns. Our goal is to relate these patterns with the partition into six socio-economic compartments of these two societies. Our results show that spatial and temporal patterns vary across these socio-economic groups. In particular, the two datasets show that as wealth increases the early-morning activity is delayed, the midday peak becomes smoother and the spatial distribution of trips becomes more localized.
Collapse
Affiliation(s)
- Laura Lotero
- Facultad de Ingeniería Industrial, Universidad Pontificia Bolivariana, Medellín, Colombia
- Departamento de Ciencias de la Computación y de la Decisión, Universidad Nacional de Colombia, Medellín, Colombia
| | - Rafael G. Hurtado
- Departamento de Física, Universidad Nacional de Colombia, Bogotá, Colombia
| | - Luis Mario Floría
- Departamento de Física de la Materia Condensada, Universidad de Zaragoza, Zaragoza 50009, Spain
- Instituto de Biocomputación y Física de Sistemas Complejos, Universidad de Zaragoza, Zaragoza 50018, Spain
| | - Jesús Gómez-Gardeñes
- Departamento de Física de la Materia Condensada, Universidad de Zaragoza, Zaragoza 50009, Spain
- Instituto de Biocomputación y Física de Sistemas Complejos, Universidad de Zaragoza, Zaragoza 50018, Spain
| |
Collapse
|
27
|
Chodrow PS, al-Awwad Z, Jiang S, González MC. Demand and Congestion in Multiplex Transportation Networks. PLoS One 2016; 11:e0161738. [PMID: 27657738 PMCID: PMC5033591 DOI: 10.1371/journal.pone.0161738] [Citation(s) in RCA: 21] [Impact Index Per Article: 2.6] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 05/24/2016] [Accepted: 08/10/2016] [Indexed: 12/01/2022] Open
Abstract
Urban transportation systems are multimodal, sociotechnical systems; however, while their multimodal aspect has received extensive attention in recent literature on multiplex networks, their sociotechnical aspect has been largely neglected. We present the first study of an urban transportation system using multiplex network analysis and validated Origin-Destination travel demand, with Riyadh's planned metro as a case study. We develop methods for analyzing the impact of additional transportation layers on existing dynamics, and show that demand structure plays key quantitative and qualitative roles. There exist fundamental geometrical limits to the metro's impact on traffic dynamics, and the bulk of environmental accrue at metro speeds only slightly faster than those planned. We develop a simple model for informing the use of additional, "feeder" layers to maximize reductions in global congestion. Our techniques are computationally practical, easily extensible to arbitrary transportation layers with complex transfer logic, and implementable in open-source software.
Collapse
Affiliation(s)
- Philip S. Chodrow
- Operations Research Center, Massachussetts Institute of Technology, Cambridge, MA 02139, United States of America
| | - Zeyad al-Awwad
- Center for Complex Engineering Systems, King Abdulaziz City for Science and Technology, Riyadh 11442, Saudi Arabia
| | - Shan Jiang
- Department of Civil and Environmental Engineering, Massachussetts Institute of Technology, Cambridge, MA 02139, United States of America
| | - Marta C. González
- Department of Civil and Environmental Engineering, Massachussetts Institute of Technology, Cambridge, MA 02139, United States of America
| |
Collapse
|
28
|
Galiceanu M, Strunz WT. Continuous-time quantum walks on multilayer dendrimer networks. Phys Rev E 2016; 94:022307. [PMID: 27627317 DOI: 10.1103/physreve.94.022307] [Citation(s) in RCA: 7] [Impact Index Per Article: 0.9] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 05/18/2016] [Indexed: 11/07/2022]
Abstract
We consider continuous-time quantum walks (CTQWs) on multilayer dendrimer networks (MDs) and their application to quantum transport. A detailed study of properties of CTQWs is presented and transport efficiency is determined in terms of the exact and average return probabilities. The latter depends only on the eigenvalues of the connectivity matrix, which even for very large structures allows a complete analytical solution for this particular choice of network. In the case of MDs we observe an interplay between strong localization effects, due to the dendrimer topology, and good efficiency from the linear segments. We show that quantum transport is enhanced by interconnecting more layers of dendrimers.
Collapse
Affiliation(s)
- Mircea Galiceanu
- Departamento de Física, Universidade Federal do Amazonas, 69077-000 Manaus, Brazil.,Institut für Theoretische Physik, Technische Universität Dresden, 01062 Dresden, Germany
| | - Walter T Strunz
- Institut für Theoretische Physik, Technische Universität Dresden, 01062 Dresden, Germany
| |
Collapse
|
29
|
Galiceanu M, Jurjiu A. Relaxation dynamics of multilayer triangular Husimi cacti. J Chem Phys 2016; 145:104901. [DOI: 10.1063/1.4962196] [Citation(s) in RCA: 9] [Impact Index Per Article: 1.1] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/14/2022] Open
|
30
|
Watanabe S, Kabashima Y. Resilience of antagonistic networks with regard to the effects of initial failures and degree-degree correlations. Phys Rev E 2016; 94:032308. [PMID: 27739839 DOI: 10.1103/physreve.94.032308] [Citation(s) in RCA: 2] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 05/18/2016] [Indexed: 06/06/2023]
Abstract
In this study we investigate the resilience of duplex networked layers α and β coupled with antagonistic interlinks, each layer of which inhibits its counterpart at the microscopic level, changing the following factors: whether the influence of the initial failures in α remains [quenched (case Q)] or not [free (case F)]; the effect of intralayer degree-degree correlations in each layer and interlayer degree-degree correlations; and the type of the initial failures, such as random failures or targeted attacks (TAs). We illustrate that the percolation processes repeat in both cases Q and F, although only in case F are nodes that initially failed reactivated. To analytically evaluate the resilience of each layer, we develop a methodology based on the cavity method for deriving the size of a giant component (GC). Strong hysteresis, which is ignored in the standard cavity analysis, is observed in the repetition of the percolation processes particularly in case F. To handle this, we heuristically modify interlayer messages for macroscopic analysis, the utility of which is verified by numerical experiments. The percolation transition in each layer is continuous in both cases Q and F. We also analyze the influences of degree-degree correlations on the robustness of layer α, in particular for the case of TAs. The analysis indicates that the critical fraction of initial failures that makes the GC size in layer α vanish depends only on its intralayer degree-degree correlations. Although our model is defined in a somewhat abstract manner, it may have relevance to ecological systems that are composed of endangered species (layer α) and invaders (layer β), the former of which are damaged by the latter whereas the latter are exterminated in the areas where the former are active.
Collapse
Affiliation(s)
- Shunsuke Watanabe
- Department of Computational Intelligence and Systems Science, Tokyo Institute of Technology, Yokohama 2268502, Japan
| | - Yoshiyuki Kabashima
- Department of Mathematical Intelligence and Systems Science, Tokyo Institute of Technology, Yokohama 2268502, Japan
| |
Collapse
|
31
|
Thiel F, Sokolov IM. Effective-medium approximation for lattice random walks with long-range jumps. Phys Rev E 2016; 94:012135. [PMID: 27575104 DOI: 10.1103/physreve.94.012135] [Citation(s) in RCA: 7] [Impact Index Per Article: 0.9] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 04/22/2016] [Indexed: 11/07/2022]
Abstract
We consider the random walk on a lattice with random transition rates and arbitrarily long-range jumps. We employ Bruggeman's effective-medium approximation (EMA) to find the disorder-averaged (coarse-grained) dynamics. The EMA procedure replaces the disordered system with a cleverly guessed reference system in a self-consistent manner. We give necessary conditions on the reference system and discuss possible physical mechanisms of anomalous diffusion. In the case of a power-law scaling between transition rates and distance, lattice variants of Lévy-flights emerge as the effective medium, and the problem is solved analytically, bearing the effective anomalous diffusivity. Finally, we discuss several example distributions and demonstrate very good agreement with numerical simulations.
Collapse
Affiliation(s)
- Felix Thiel
- Institut für Physik, Humboldt-Universität zu Berlin, Newtonstrasse 15, 12489 Berlin, Germany
| | - Igor M Sokolov
- Institut für Physik, Humboldt-Universität zu Berlin, Newtonstrasse 15, 12489 Berlin, Germany
| |
Collapse
|
32
|
Solé-Ribalta A, Gómez S, Arenas A. Congestion Induced by the Structure of Multiplex Networks. PHYSICAL REVIEW LETTERS 2016; 116:108701. [PMID: 27015514 DOI: 10.1103/physrevlett.116.108701] [Citation(s) in RCA: 19] [Impact Index Per Article: 2.4] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 12/16/2015] [Indexed: 06/05/2023]
Abstract
Multiplex networks are representations of multilayer interconnected complex networks where the nodes are the same at every layer. They turn out to be good abstractions of the intricate connectivity of multimodal transportation networks, among other types of complex systems. One of the most important critical phenomena arising in such networks is the emergence of congestion in transportation flows. Here, we prove analytically that the structure of multiplex networks can induce congestion for flows that otherwise would be decongested if the individual layers were not interconnected. We provide explicit equations for the onset of congestion and approximations that allow us to compute this onset from individual descriptors of the individual layers. The observed cooperative phenomenon is reminiscent of Braess' paradox in which adding extra capacity to a network when the moving entities selfishly choose their route can in some cases reduce overall performance. Similarly, in the multiplex structure, the efficiency in transportation can unbalance the transportation loads resulting in unexpected congestion.
Collapse
Affiliation(s)
- Albert Solé-Ribalta
- Departament d'Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili, 43007 Tarragona, Spain
| | - Sergio Gómez
- Departament d'Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili, 43007 Tarragona, Spain
| | - Alex Arenas
- Departament d'Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili, 43007 Tarragona, Spain
| |
Collapse
|
33
|
Gallotti R, Porter MA, Barthelemy M. Lost in transportation: Information measures and cognitive limits in multilayer navigation. SCIENCE ADVANCES 2016; 2:e1500445. [PMID: 26989769 PMCID: PMC4788487 DOI: 10.1126/sciadv.1500445] [Citation(s) in RCA: 16] [Impact Index Per Article: 2.0] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Grants] [Track Full Text] [Subscribe] [Scholar Register] [Received: 04/08/2015] [Accepted: 08/07/2015] [Indexed: 05/04/2023]
Abstract
Cities and their transportation systems become increasingly complex and multimodal as they grow, and it is natural to wonder whether it is possible to quantitatively characterize our difficulty navigating in them and whether such navigation exceeds our cognitive limits. A transition between different search strategies for navigating in metropolitan maps has been observed for large, complex metropolitan networks. This evidence suggests the existence of a limit associated with cognitive overload and caused by a large amount of information that needs to be processed. In this light, we analyzed the world's 15 largest metropolitan networks and estimated the information limit for determining a trip in a transportation system to be on the order of 8 bits. Similar to the "Dunbar number," which represents a limit to the size of an individual's friendship circle, our cognitive limit suggests that maps should not consist of more than 250 connection points to be easily readable. We also show that including connections with other transportation modes dramatically increases the information needed to navigate in multilayer transportation networks. In large cities such as New York, Paris, and Tokyo, more than 80% of the trips are above the 8-bit limit. Multimodal transportation systems in large cities have thus already exceeded human cognitive limits and, consequently, the traditional view of navigation in cities has to be revised substantially.
Collapse
Affiliation(s)
- Riccardo Gallotti
- Institut de Physique Théorique, CEA-Saclay, Gif-sur-Yvette F-91191, France
| | - Mason A. Porter
- Oxford Centre for Industrial and Applied Mathematics, Mathematical Institute, University of Oxford, Oxford OX2 6GG, UK
- CABDyN Complexity Centre, University of Oxford, Oxford OX1 1HP, UK
| | - Marc Barthelemy
- Institut de Physique Théorique, CEA-Saclay, Gif-sur-Yvette F-91191, France
- Centre d’Analyse et de Mathématique Sociales, École des Hautes Études en Sciences Sociales, 190-198, Avenue de France, 75244 Paris Cedex 13, France
| |
Collapse
|
34
|
Du WB, Zhou XL, Jusup M, Wang Z. Physics of transportation: Towards optimal capacity using the multilayer network framework. Sci Rep 2016; 6:19059. [PMID: 26791580 PMCID: PMC4726168 DOI: 10.1038/srep19059] [Citation(s) in RCA: 30] [Impact Index Per Article: 3.8] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/08/2015] [Accepted: 12/02/2015] [Indexed: 11/09/2022] Open
Abstract
Because of the critical role of transportation in modern times, one of the most successful application areas of statistical physics of complex networks is the study of traffic dynamics. However, the vast majority of works treat transportation networks as an isolated system, which is inconsistent with the fact that many complex networks are interrelated in a nontrivial way. To mimic a realistic scenario, we use the framework of multilayer networks to construct a two-layered traffic model, whereby the upper layer provides higher transport speed than the lower layer. Moreover, passengers are guided to travel along the path of minimal travelling time and with the additional cost they can transfer from one layer to another to avoid congestion and/or reach the final destination faster. By means of numerical simulations, we show that a degree distribution-based strategy, although facilitating the cooperation between both layers, can be further improved by enhancing the critical generating rate of passengers using a particle swarm optimisation (PSO) algorithm. If initialised with the prior knowledge from the degree distribution-based strategy, the PSO algorithm converges considerably faster. Our work exemplifies how statistical physics of complex networks can positively affect daily life.
Collapse
Affiliation(s)
- Wen-Bo Du
- School of Electronic and Information Engineering, Beihang University, Beijing 100191, P.R.China
| | - Xing-Lian Zhou
- School of Electronic and Information Engineering, Beihang University, Beijing 100191, P.R.China
| | - Marko Jusup
- Faculty of Sciences, Kyushu University, Fukuoka 819-0395, Japan
| | - Zhen Wang
- Interdisciplinary Graduate School of Engineering Sciences, Kyushu University, Fukuoka 816-8580, Japan
| |
Collapse
|
35
|
Vulnerability of Interdependent Networks and Networks of Networks. UNDERSTANDING COMPLEX SYSTEMS 2016. [DOI: 10.1007/978-3-319-23947-7_5] [Citation(s) in RCA: 22] [Impact Index Per Article: 2.8] [Reference Citation Analysis] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 12/23/2022]
|
36
|
Extreme events in multilayer, interdependent complex networks and control. Sci Rep 2015; 5:17277. [PMID: 26612009 PMCID: PMC4661526 DOI: 10.1038/srep17277] [Citation(s) in RCA: 25] [Impact Index Per Article: 2.8] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 09/08/2015] [Accepted: 10/28/2015] [Indexed: 11/30/2022] Open
Abstract
We investigate the emergence of extreme events in interdependent networks. We introduce an inter-layer traffic resource competing mechanism to account for the limited capacity associated with distinct network layers. A striking finding is that, when the number of network layers and/or the overlap among the layers are increased, extreme events can emerge in a cascading manner on a global scale. Asymptotically, there are two stable absorption states: a state free of extreme events and a state of full of extreme events, and the transition between them is abrupt. Our results indicate that internal interactions in the multiplex system can yield qualitatively distinct phenomena associated with extreme events that do not occur for independent network layers. An implication is that, e.g., public resource competitions among different service providers can lead to a higher resource requirement than naively expected. We derive an analytical theory to understand the emergence of global-scale extreme events based on the concept of effective betweenness. We also articulate a cost-effective control scheme through increasing the capacity of very few hubs to suppress the cascading process of extreme events so as to protect the entire multi-layer infrastructure against global-scale breakdown.
Collapse
|
37
|
|
38
|
Strano E, Shai S, Dobson S, Barthelemy M. Multiplex networks in metropolitan areas: generic features and local effects. J R Soc Interface 2015; 12:20150651. [PMID: 26400198 PMCID: PMC4614501 DOI: 10.1098/rsif.2015.0651] [Citation(s) in RCA: 18] [Impact Index Per Article: 2.0] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 07/21/2015] [Accepted: 08/28/2015] [Indexed: 11/12/2022] Open
Abstract
Most large cities are spanned by more than one transportation system. These different modes of transport have usually been studied separately: it is however important to understand the impact on urban systems of coupling different modes and we report in this paper an empirical analysis of the coupling between the street network and the subway for the two large metropolitan areas of London and New York. We observe a similar behaviour for network quantities related to quickest paths suggesting the existence of generic mechanisms operating beyond the local peculiarities of the specific cities studied. An analysis of the betweenness centrality distribution shows that the introduction of underground networks operate as a decentralizing force creating congestion in places located at the end of underground lines. Also, we find that increasing the speed of subways is not always beneficial and may lead to unwanted uneven spatial distributions of accessibility. In fact, for London—but not for New York—there is an optimal subway speed in terms of global congestion. These results show that it is crucial to consider the full, multimodal, multilayer network aspects of transportation systems in order to understand the behaviour of cities and to avoid possible negative side-effects of urban planning decisions.
Collapse
Affiliation(s)
- Emanuele Strano
- Laboratory of Geography Information Systems (LaSig), Polytechnic School of Lausanne (EPFL), Lausanne, CH, Switzerland
| | - Saray Shai
- School of Computer Science, University of St Andrews, St Andrews, Scotland, UK Department of Mathematics, University of North Carolina, Chapel Hill, NC, USA
| | - Simon Dobson
- School of Computer Science, University of St Andrews, St Andrews, Scotland, UK
| | - Marc Barthelemy
- CEA, Institut de Physique Theorique, Gif-sur-Yvette, France EHESS, Centre d'Analyse et de Mathématique Sociales, Paris, France
| |
Collapse
|
39
|
Asllani M, Busiello DM, Carletti T, Fanelli D, Planchon G. Turing instabilities on Cartesian product networks. Sci Rep 2015; 5:12927. [PMID: 26245138 PMCID: PMC4526855 DOI: 10.1038/srep12927] [Citation(s) in RCA: 14] [Impact Index Per Article: 1.6] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 01/26/2015] [Accepted: 07/10/2015] [Indexed: 12/04/2022] Open
Abstract
The problem of Turing instabilities for a reaction-diffusion system defined on a complex Cartesian product network is considered. To this end we operate in the linear regime and expand the time dependent perturbation on a basis formed by the tensor product of the eigenvectors of the discrete Laplacian operators, associated to each of the individual networks that build the Cartesian product. The dispersion relation which controls the onset of the instability depends on a set of discrete wavelengths, the eigenvalues of the aforementioned Laplacians. Patterns can develop on the Cartesian network, if they are supported on at least one of its constitutive sub-graphs. Multiplex networks are also obtained under specific prescriptions. In this case, the criteria for the instability reduce to compact explicit formulae. Numerical simulations carried out for the Mimura-Murray reaction kinetics confirm the adequacy of the proposed theory.
Collapse
Affiliation(s)
- Malbor Asllani
- Dipartimento di Scienza e Alta Tecnologia, University of Insubria, via Valleggio 11, 22100 Como, Italy
| | - Daniel M. Busiello
- Department of Physics and Astronomy G. Galilei, University of Padova, via Marzolo 8, 35131 Padova, Italy
| | - Timoteo Carletti
- Department of mathematics and Namur Center for Complex Systems - naXys, University of Namur, rempart de la Vierge 8, B 5000 Namur, Belgium
| | - Duccio Fanelli
- Dipartimento di Fisica e Astronomia, University of Florence and INFN, Via Sansone 1, 50019 Sesto Fiorentino, Florence, Italy
| | - Gwendoline Planchon
- Department of Physics and Astronomy G. Galilei, University of Padova, via Marzolo 8, 35131 Padova, Italy
- Dipartimento di Fisica e Astronomia, University of Florence and INFN, Via Sansone 1, 50019 Sesto Fiorentino, Florence, Italy
| |
Collapse
|
40
|
Ruan Z, Wang C, Ming Hui P, Liu Z. Integrated travel network model for studying epidemics: Interplay between journeys and epidemic. Sci Rep 2015; 5:11401. [PMID: 26073191 PMCID: PMC4466778 DOI: 10.1038/srep11401] [Citation(s) in RCA: 18] [Impact Index Per Article: 2.0] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 01/20/2015] [Accepted: 05/13/2015] [Indexed: 01/13/2023] Open
Abstract
The ease of travelling between cities has contributed much to globalization. Yet, it poses a threat on epidemic outbreaks. It is of great importance for network science and health control to understand the impact of frequent journeys on epidemics. We stress that a new framework of modelling that takes a traveller's viewpoint is needed. Such integrated travel network (ITN) model should incorporate the diversity among links as dictated by the distances between cities and different speeds of different modes of transportation, diversity among nodes as dictated by the population and the ease of travelling due to infrastructures and economic development of a city, and round-trip journeys to targeted destinations via the paths of shortest travel times typical of human journeys. An example is constructed for 116 cities in China with populations over one million that are connected by high-speed train services and highways. Epidemic spread on the constructed network is studied. It is revealed both numerically and theoretically that the traveling speed and frequency are important factors of epidemic spreading. Depending on the infection rate, increasing the traveling speed would result in either an enhanced or suppressed epidemic, while increasing the traveling frequency enhances the epidemic spreading.
Collapse
Affiliation(s)
- Zhongyuan Ruan
- Department of Physics, East China Normal University, Shanghai, 200062, China
- Center for Network Science, Central European University
| | - Chaoqing Wang
- Department of Physics, East China Normal University, Shanghai, 200062, China
| | - Pak Ming Hui
- Department of Physics, The Chinese University of Hong Kong, Shatin, New Territories, Hong Kong
| | - Zonghua Liu
- Department of Physics, East China Normal University, Shanghai, 200062, China
| |
Collapse
|
41
|
Yang HX, Tang M, Lai YC. Traffic-driven epidemic spreading in correlated networks. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2015; 91:062817. [PMID: 26172764 DOI: 10.1103/physreve.91.062817] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 04/04/2015] [Indexed: 05/26/2023]
Abstract
In spite of the extensive previous efforts on traffic dynamics and epidemic spreading in complex networks, the problem of traffic-driven epidemic spreading on correlated networks has not been addressed. Interestingly, we find that the epidemic threshold, a fundamental quantity underlying the spreading dynamics, exhibits a nonmonotonic behavior in that it can be minimized for some critical value of the assortativity coefficient, a parameter characterizing the network correlation. To understand this phenomenon, we use the degree-based mean-field theory to calculate the traffic-driven epidemic threshold for correlated networks. The theory predicts that the threshold is inversely proportional to the packet-generation rate and the largest eigenvalue of the betweenness matrix. We obtain consistency between theory and numerics. Our results may provide insights into the important problem of controlling and/or harnessing real-world epidemic spreading dynamics driven by traffic flows.
Collapse
Affiliation(s)
- Han-Xin Yang
- Department of Physics, Fuzhou University, Fuzhou 350108, China
| | - Ming Tang
- Web Sciences Center, University of Electronic Science and Technology of China, Chengdu 610051, China
| | - Ying-Cheng Lai
- School of Electrical, Computer and Energy Engineering, Arizona State University, Arizona 85287, USA
| |
Collapse
|
42
|
Gemmetto V, Garlaschelli D. Multiplexity versus correlation: the role of local constraints in real multiplexes. Sci Rep 2015; 5:9120. [PMID: 25767040 PMCID: PMC4357874 DOI: 10.1038/srep09120] [Citation(s) in RCA: 23] [Impact Index Per Article: 2.6] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 11/19/2014] [Accepted: 02/19/2015] [Indexed: 11/15/2022] Open
Abstract
Several systems can be represented as multiplex networks, i.e. in terms of a superposition of various graphs, each related to a different mode of connection between nodes. Hence, the definition of proper mathematical quantities aiming at capturing the added level of complexity of those systems is required. Various steps in this direction have been made. In the simplest case, dependencies between layers are measured via correlation-based metrics, a procedure that we show to be equivalent to the use of completely homogeneous benchmarks specifying only global constraints. However, this approach does not take into account the heterogeneity in the degree and strength distributions, which is instead a fundamental feature of real-world multiplexes. In this work, we compare the observed dependencies between layers with the expected values obtained from maximum-entropy reference models that appropriately control for the observed heterogeneity in the degree and strength distributions. This information-theoretic approach results in the introduction of novel and improved multiplexity measures that we test on different datasets, i.e. the International Trade Network and the European Airport Network. Our findings confirm that the use of homogeneous benchmarks can lead to misleading results, and highlight the important role played by the distribution of hubs across layers.
Collapse
Affiliation(s)
- V. Gemmetto
- Instituut-Lorentz for Theoretical Physics, Leiden Institute of Physics, University of Leiden, Niels Bohrweg 2, 2333 CA Leiden, The Netherlands
| | - D. Garlaschelli
- Instituut-Lorentz for Theoretical Physics, Leiden Institute of Physics, University of Leiden, Niels Bohrweg 2, 2333 CA Leiden, The Netherlands
| |
Collapse
|
43
|
Gong M, Ma L, Cai Q, Jiao L. Enhancing robustness of coupled networks under targeted recoveries. Sci Rep 2015; 5:8439. [PMID: 25675980 PMCID: PMC4327128 DOI: 10.1038/srep08439] [Citation(s) in RCA: 54] [Impact Index Per Article: 6.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/12/2014] [Accepted: 01/19/2015] [Indexed: 11/12/2022] Open
Abstract
Coupled networks are extremely fragile because a node failure of a network would trigger a cascade of failures on the entire system. Existing studies mainly focused on the cascading failures and the robustness of coupled networks when the networks suffer from attacks. In reality, it is necessary to recover the damaged networks, and there are cascading failures in recovery processes. In this study, firstly, we analyze the cascading failures of coupled networks during recoveries. Then, a recovery robustness index is presented for evaluating the resilience of coupled networks to cascading failures in the recovery processes. Finally, we propose a technique aiming at protecting several influential nodes for enhancing robustness of coupled networks under the recoveries, and adopt six strategies based on the potential knowledge of network centrality to find the influential nodes. Experiments on three coupling networks demonstrate that with a small number of influential nodes protected, the robustness of coupled networks under the recoveries can be greatly enhanced.
Collapse
Affiliation(s)
- Maoguo Gong
- Key Lab of Intelligent Perception and Image Understanding of Ministry of Education, International Research Center for Intelligent Perception and Computation, Xidian University, Xi'an, Shaanxi Province 710071, China
| | - Lijia Ma
- Key Lab of Intelligent Perception and Image Understanding of Ministry of Education, International Research Center for Intelligent Perception and Computation, Xidian University, Xi'an, Shaanxi Province 710071, China
| | - Qing Cai
- Key Lab of Intelligent Perception and Image Understanding of Ministry of Education, International Research Center for Intelligent Perception and Computation, Xidian University, Xi'an, Shaanxi Province 710071, China
| | - Licheng Jiao
- Key Lab of Intelligent Perception and Image Understanding of Ministry of Education, International Research Center for Intelligent Perception and Computation, Xidian University, Xi'an, Shaanxi Province 710071, China
| |
Collapse
|
44
|
Gallotti R, Barthelemy M. Anatomy and efficiency of urban multimodal mobility. Sci Rep 2014; 4:6911. [PMID: 25371238 PMCID: PMC4220282 DOI: 10.1038/srep06911] [Citation(s) in RCA: 62] [Impact Index Per Article: 6.2] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/09/2014] [Accepted: 10/15/2014] [Indexed: 11/14/2022] Open
Abstract
The growth of transportation networks and their increasing interconnections, although positive, has the downside effect of an increasing complexity which make them difficult to use, to assess, and limits their efficiency. On average in the UK, 23% of travel time is lost in connections for trips with more than one mode, and the lack of synchronization decreases very slowly with population size. This lack of synchronization between modes induces differences between the theoretical quickest trip and the 'time-respecting' path, which takes into account waiting times at interconnection nodes. We analyse here the statistics of these paths on the multilayer, temporal network of the entire, multimodal british public transportation system. We propose a statistical decomposition - the 'anatomy' - of trips in urban areas, in terms of riding, waiting and walking times, and which shows how the temporal structure of trips varies with distance and allows us to compare different cities. Weaknesses in systems can be either insufficient transportation speed or service frequency, but the key parameter controlling their global efficiency is the total number of stop events per hour for all modes. This analysis suggests the need for better optimization strategies, adapted to short, long unimodal or multimodal trips.
Collapse
Affiliation(s)
- Riccardo Gallotti
- Institut de Physique Théorique, CEA, CNRS-URA 2306, F-91191, Gif-sur-Yvette, France
| | - Marc Barthelemy
- Institut de Physique Théorique, CEA, CNRS-URA 2306, F-91191, Gif-sur-Yvette, France
| |
Collapse
|
45
|
Boccaletti S, Bianconi G, Criado R, del Genio C, Gómez-Gardeñes J, Romance M, Sendiña-Nadal I, Wang Z, Zanin M. The structure and dynamics of multilayer networks. PHYSICS REPORTS 2014; 544:1-122. [PMID: 32834429 PMCID: PMC7332224 DOI: 10.1016/j.physrep.2014.07.001] [Citation(s) in RCA: 874] [Impact Index Per Article: 87.4] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Accepted: 07/03/2014] [Indexed: 05/05/2023]
Abstract
In the past years, network theory has successfully characterized the interaction among the constituents of a variety of complex systems, ranging from biological to technological, and social systems. However, up until recently, attention was almost exclusively given to networks in which all components were treated on equivalent footing, while neglecting all the extra information about the temporal- or context-related properties of the interactions under study. Only in the last years, taking advantage of the enhanced resolution in real data sets, network scientists have directed their interest to the multiplex character of real-world systems, and explicitly considered the time-varying and multilayer nature of networks. We offer here a comprehensive review on both structural and dynamical organization of graphs made of diverse relationships (layers) between its constituents, and cover several relevant issues, from a full redefinition of the basic structural measures, to understanding how the multilayer nature of the network affects processes and dynamics.
Collapse
Affiliation(s)
- S. Boccaletti
- CNR - Institute of Complex Systems, Via Madonna del Piano, 10, 50019 Sesto Fiorentino, Florence, Italy
- The Italian Embassy in Israel, 25 Hamered st., 68125 Tel Aviv, Israel
| | - G. Bianconi
- School of Mathematical Sciences, Queen Mary University of London, London, United Kingdom
| | - R. Criado
- Departamento de Matemática Aplicada, Universidad Rey Juan Carlos, 28933 Móstoles, Madrid, Spain
- Center for Biomedical Technology, Universidad Politécnica de Madrid, 28223 Pozuelo de Alarcón, Madrid, Spain
| | - C.I. del Genio
- Warwick Mathematics Institute, University of Warwick, Gibbet Hill Road, Coventry CV4 7AL, United Kingdom
- Centre for Complexity Science, University of Warwick, Gibbet Hill Road, Coventry CV4 7AL, United Kingdom
- Warwick Infectious Disease Epidemiology Research (WIDER) Centre, University of Warwick, Gibbet Hill Road, Coventry CV4 7AL, United Kingdom
| | - J. Gómez-Gardeñes
- Institute for Biocomputation and Physics of Complex Systems, University of Zaragoza, Zaragoza, Spain
| | - M. Romance
- Departamento de Matemática Aplicada, Universidad Rey Juan Carlos, 28933 Móstoles, Madrid, Spain
- Center for Biomedical Technology, Universidad Politécnica de Madrid, 28223 Pozuelo de Alarcón, Madrid, Spain
| | - I. Sendiña-Nadal
- Center for Biomedical Technology, Universidad Politécnica de Madrid, 28223 Pozuelo de Alarcón, Madrid, Spain
- Complex Systems Group, Universidad Rey Juan Carlos, 28933 Móstoles, Madrid, Spain
| | - Z. Wang
- Department of Physics, Hong Kong Baptist University, Kowloon Tong, Hong Kong Special Administrative Region
- Center for Nonlinear Studies, Beijing–Hong Kong–Singapore Joint Center for Nonlinear and Complex Systems (Hong Kong) and Institute of Computational and Theoretical Studies, Hong Kong Baptist University, Kowloon Tong, Hong Kong Special Administrative Region
| | - M. Zanin
- Innaxis Foundation & Research Institute, José Ortega y Gasset 20, 28006 Madrid, Spain
- Faculdade de Ciências e Tecnologia, Departamento de Engenharia Electrotécnica, Universidade Nova de Lisboa, 2829-516 Caparica, Portugal
| |
Collapse
|
46
|
Asllani M, Busiello DM, Carletti T, Fanelli D, Planchon G. Turing patterns in multiplex networks. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2014; 90:042814. [PMID: 25375556 DOI: 10.1103/physreve.90.042814] [Citation(s) in RCA: 42] [Impact Index Per Article: 4.2] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 06/24/2014] [Indexed: 05/03/2023]
Abstract
The theory of patterns formation for a reaction-diffusion system defined on a multiplex is developed by means of a perturbative approach. The interlayer diffusion constants act as a small parameter in the expansion and the unperturbed state coincides with the limiting setting where the multiplex layers are decoupled. The interaction between adjacent layers can seed the instability of a homogeneous fixed point, yielding self-organized patterns which are instead impeded in the limit of decoupled layers. Patterns on individual layers can also fade away due to cross-talking between layers. Analytical results are compared to direct simulations.
Collapse
Affiliation(s)
- Malbor Asllani
- Dipartimento di Scienza e Alta Tecnologia, Università degli Studi dell'Insubria, via Valleggio 11, 22100 Como, Italy and Dipartimento di Fisica e Astronomia, University of Florence, INFN and CSDC, Via Sansone 1, 50019 Sesto Fiorentino, Florence, Italy
| | - Daniel M Busiello
- Dipartimento di Fisica e Astronomia, University of Florence, INFN and CSDC, Via Sansone 1, 50019 Sesto Fiorentino, Florence, Italy
| | - Timoteo Carletti
- Department of Mathematics and Namur Center for Complex Systems - naXys, University of Namur, rempart de la Vierge 8, B 5000 Namur, Belgium
| | - Duccio Fanelli
- Dipartimento di Fisica e Astronomia, University of Florence, INFN and CSDC, Via Sansone 1, 50019 Sesto Fiorentino, Florence, Italy
| | - Gwendoline Planchon
- Dipartimento di Fisica e Astronomia, University of Florence, INFN and CSDC, Via Sansone 1, 50019 Sesto Fiorentino, Florence, Italy and Department of Mathematics and Namur Center for Complex Systems - naXys, University of Namur, rempart de la Vierge 8, B 5000 Namur, Belgium
| |
Collapse
|
47
|
Nicosia V, Bianconi G, Latora V, Barthelemy M. Nonlinear growth and condensation in multiplex networks. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2014; 90:042807. [PMID: 25375549 DOI: 10.1103/physreve.90.042807] [Citation(s) in RCA: 7] [Impact Index Per Article: 0.7] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 12/12/2013] [Indexed: 06/04/2023]
Abstract
Different types of interactions coexist and coevolve to shape the structure and function of a multiplex network. We propose here a general class of growth models in which the various layers of a multiplex network coevolve through a set of nonlinear preferential attachment rules. We show, both numerically and analytically, that by tuning the level of nonlinearity these models allow us to reproduce either homogeneous or heterogeneous degree distributions, together with positive or negative degree correlations across layers. In particular, we derive the condition for the appearance of a condensed state in which one node in each layer attracts an extensive fraction of all the edges.
Collapse
Affiliation(s)
- V Nicosia
- School of Mathematical Sciences, Queen Mary University of London, Mile End Road, E1 4NS, London, United Kingdom
| | - G Bianconi
- School of Mathematical Sciences, Queen Mary University of London, Mile End Road, E1 4NS, London, United Kingdom
| | - V Latora
- School of Mathematical Sciences, Queen Mary University of London, Mile End Road, E1 4NS, London, United Kingdom
| | - M Barthelemy
- Institut de Physique Théorique, CEA, CNRS-URA 2306, F-91191, Gif-sur-Yvette, France
| |
Collapse
|
48
|
Abstract
Abstract
Network science has attracted much attention in recent years due to its interdisciplinary applications. We witnessed the revolution of network science in 1998 and 1999 started with small-world and scale-free networks having now thousands of high-profile publications, and it seems that since 2010 studies of ‘network of networks’ (NON), sometimes called multilayer networks or multiplex, have attracted more and more attention. The analytic framework for NON yields a novel percolation law for n interdependent networks that shows that percolation theory of single networks studied extensively in physics and mathematics in the last 50 years is a specific limit of the rich and very different general case of n coupled networks. Since then, properties and dynamics of interdependent and interconnected networks have been studied extensively, and scientists are finding many interesting results and discovering many surprising phenomena. Because most natural and engineered systems are composed of multiple subsystems and layers of connectivity, it is important to consider these features in order to improve our understanding of such complex systems. Now the study of NON has become one of the important directions in network science. In this paper, we review recent studies on the new emerging area—NON. Due to the fast growth of this field, there are many definitions of different types of NON, such as interdependent networks, interconnected networks, multilayered networks, multiplex networks and many others. There exist many datasets that can be represented as NON, such as network of different transportation networks including flight networks, railway networks and road networks, network of ecological networks including species interacting networks and food webs, network of biological networks including gene regulation network, metabolic network and protein–protein interacting network, network of social networks and so on. Among them, many interdependent networks including critical infrastructures are embedded in space, introducing spatial constraints. Thus, we also review the progress on study of spatially embedded networks. As a result of spatial constraints, such interdependent networks exhibit extreme vulnerabilities compared with their non-embedded counterparts. Such studies help us to understand, realize and hopefully mitigate the increasing risk in NON.
Collapse
Affiliation(s)
- Jianxi Gao
- Department of Automation, Shanghai Jiao Tong University, Shanghai 200240, China
- Center for Complex Network Research and Department of Physics, Northeastern University, Boston, MA 02115, USA
| | - Daqing Li
- School of Reliability and Systems Engineering, Beihang University, Beijing 100191, China
- Science and Technology on Reliability and Environmental Engineering Laboratory, Beijing 100191, China
| | - Shlomo Havlin
- Department of Physics, Bar-Ilan University, Ramat-Gan 52900, Israel
| |
Collapse
|
49
|
Zhou D, Bashan A, Cohen R, Berezin Y, Shnerb N, Havlin S. Simultaneous first- and second-order percolation transitions in interdependent networks. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2014; 90:012803. [PMID: 25122338 DOI: 10.1103/physreve.90.012803] [Citation(s) in RCA: 37] [Impact Index Per Article: 3.7] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 10/04/2013] [Indexed: 06/03/2023]
Abstract
In a system of interdependent networks, an initial failure of nodes invokes a cascade of iterative failures that may lead to a total collapse of the whole system in the form of an abrupt first-order transition. When the fraction of initial failed nodes 1-p reaches criticality p = p(c), the abrupt collapse occurs by spontaneous cascading failures. At this stage, the giant component decreases slowly in a plateau form and the number of iterations in the cascade τ diverges. The origin of this plateau and its increasing with the size of the system have been unclear. Here we find that, simultaneously with the abrupt first-order transition, a spontaneous second-order percolation occurs during the cascade of iterative failures. This sheds light on the origin of the plateau and how its length scales with the size of the system. Understanding the critical nature of the dynamical process of cascading failures may be useful for designing strategies for preventing and mitigating catastrophic collapses.
Collapse
Affiliation(s)
- Dong Zhou
- Department of Physics, Bar-Ilan University, Ramat Gan 52900, Israel
| | - Amir Bashan
- Department of Physics, Bar-Ilan University, Ramat Gan 52900, Israel
| | - Reuven Cohen
- Department of Mathematics, Bar-Ilan University, Ramat Gan 52900, Israel
| | - Yehiel Berezin
- Department of Physics, Bar-Ilan University, Ramat Gan 52900, Israel
| | - Nadav Shnerb
- Department of Physics, Bar-Ilan University, Ramat Gan 52900, Israel
| | - Shlomo Havlin
- Department of Physics, Bar-Ilan University, Ramat Gan 52900, Israel
| |
Collapse
|
50
|
Shekhtman LM, Berezin Y, Danziger MM, Havlin S. Robustness of a network formed of spatially embedded networks. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2014; 90:012809. [PMID: 25122344 DOI: 10.1103/physreve.90.012809] [Citation(s) in RCA: 10] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 03/20/2014] [Indexed: 06/03/2023]
Abstract
We present analytic and numeric results for percolation in a network formed of interdependent spatially embedded networks. We show results for a treelike and a random regular network of networks each with (i) unconstrained dependency links and (ii) dependency links restricted to a maximum Euclidean length r. Analytic results are given for each network of networks with spatially unconstrained dependency links and compared to simulations. For the case of two fully interdependent spatially embedded networks it was found [Li et al., Phys. Rev. Lett. 108, 228702 (2012)] that the system undergoes a first-order phase transition only for r>r(c) ≈ 8. We find here that for treelike networks of networks (composed of n networks) r(c) significantly decreases as n increases and rapidly (n ≥ 11) reaches its limiting value of 1. For cases where the dependencies form loops, such as in random regular networks, we show analytically and confirm through simulations that there is a certain fraction of dependent nodes, q(max), above which the entire network structure collapses even if a single node is removed. The value of q(max) decreases quickly with m, the degree of the random regular network of networks. Our results show the extreme sensitivity of coupled spatial networks and emphasize the susceptibility of these networks to sudden collapse. The theory proposed here requires only numerical knowledge about the percolation behavior of a single network and therefore can be used to find the robustness of any network of networks where the profile of percolation of a singe network is known numerically.
Collapse
Affiliation(s)
| | - Yehiel Berezin
- Department of Physics, Bar-Ilan University, Ramat Gan 52900, Israel
| | | | - Shlomo Havlin
- Department of Physics, Bar-Ilan University, Ramat Gan 52900, Israel
| |
Collapse
|