1
|
Kundu P, MacLaren NG, Kori H, Masuda N. Mean-field theory for double-well systems on degree-heterogeneous networks. Proc Math Phys Eng Sci 2022. [DOI: 10.1098/rspa.2022.0350] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/12/2022] Open
Abstract
Many complex dynamical systems in the real world, including ecological, climate, financial and power-grid systems, often show critical transitions, or tipping points, in which the system’s dynamics suddenly transit into a qualitatively different state. In mathematical models, tipping points happen as a control parameter gradually changes and crosses a certain threshold. Tipping elements in such systems may interact with each other as a network, and understanding the behaviour of interacting tipping elements is a challenge because of the high dimensionality originating from the network. Here, we develop a degree-based mean-field theory for a prototypical double-well system coupled on a network with the aim of understanding coupled tipping dynamics with a low-dimensional description. The method approximates both the onset of the tipping point and the position of equilibria with a reasonable accuracy. Based on the developed theory and numerical simulations, we also provide evidence for multistage tipping point transitions in networks of double-well systems.
Collapse
Affiliation(s)
- Prosenjit Kundu
- Department of Mathematics, State University of New York at Buffalo, Buffalo, NY 14260-2900, USA
| | - Neil G. MacLaren
- Department of Mathematics, State University of New York at Buffalo, Buffalo, NY 14260-2900, USA
| | - Hiroshi Kori
- Department of Complexity Science and Engineering, The University of Tokyo, Chiba 277-8561, Japan
| | - Naoki Masuda
- Department of Mathematics, State University of New York at Buffalo, Buffalo, NY 14260-2900, USA
- Computational and Data-Enabled Science and Engineering Program, State University of New York at Buffalo, Buffalo, NY 14260-5030, USA
- Faculty of Science and Engineering, Waseda University, Tokyo 169-8555, Japan
| |
Collapse
|
2
|
Feng S, Jin Z. Infectious diseases spreading on a metapopulation network coupled with its second-neighbor network. APPLIED MATHEMATICS AND COMPUTATION 2019; 361:87-97. [PMID: 32287503 PMCID: PMC7112355 DOI: 10.1016/j.amc.2019.05.005] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.6] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Subscribe] [Scholar Register] [Received: 02/20/2019] [Revised: 04/19/2019] [Accepted: 05/06/2019] [Indexed: 05/27/2023]
Abstract
Traditional infectious diseases models on metapopulation networks focus on direct transportations (e.g., direct flights), ignoring the effect of indirect transportations. Based on global aviation network, we turn the problem of indirect flights into a question of second neighbors, and propose a susceptible-infectious-susceptible model to study disease transmission on a connected metapopulation network coupled with its second-neighbor network (SNN). We calculate the basic reproduction number, which is independent of human mobility, and we prove the global stability of disease-free and endemic equilibria of the model. Furthermore, the study shows that the behavior that all travelers travel along the SNN may hinder the spread of disease if the SNN is not connected. However, the behavior that individuals travel along the metapopulation network coupled with its SNN contributes to the spread of disease. Thus for an emerging infectious disease, if the real network and its SNN keep the same connectivity, indirect transportations may be a potential threat and need to be controlled. Our work can be generalized to high-speed train and rail networks, which may further promote other research on metapopulation networks.
Collapse
Affiliation(s)
- Shanshan Feng
- School of Data Science and Technology, North University of China, Taiyuan 030051, Shanxi, People’s Republic of China
- Complex Systems Research Center, Shanxi University, Taiyuan 030006, Shanxi, People’s Republic of China
| | - Zhen Jin
- Complex Systems Research Center, Shanxi University, Taiyuan 030006, Shanxi, People’s Republic of China
- Shanxi Key Laboratory of Mathematical Techniques and Big Data Analysis on Disease Control and Prevention, Shanxi University, Taiyuan 030006, Shanxi, People’s Republic of China
- Key Discipline of Computer Science and Technology of “Double-First-Class” Project of Shanxi Province, Shanxi University, Taiyuan 030006, Shanxi, People’s Republic of China
| |
Collapse
|
3
|
Dai M, Zong Y, He J, Sun Y, Shen C, Su W. The trapping problem of the weighted scale-free treelike networks for two kinds of biased walks. CHAOS (WOODBURY, N.Y.) 2018; 28:113115. [PMID: 30501217 DOI: 10.1063/1.5045829] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.2] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 06/25/2018] [Accepted: 10/26/2018] [Indexed: 06/09/2023]
Abstract
It has been recently reported that trapping problem can characterize various dynamical processes taking place on complex networks. However, most works focused on the case of binary networks, and dynamical processes on weighted networks are poorly understood. In this paper, we study two kinds of biased walks including standard weight-dependent walk and mixed weight-dependent walk on the weighted scale-free treelike networks with a trap at the central node. Mixed weight-dependent walk including non-nearest neighbor jump appears in many real situations, but related studies are much less. By the construction of studied networks in this paper, we determine all the eigenvalues of the fundamental matrix for two kinds of biased walks and show that the largest eigenvalue has an identical dominant scaling as that of the average trapping time (ATT). Thus, we can obtain the leading scaling of ATT by a more convenient method and avoid the tedious calculation. The obtained results show that the weight factor has a significant effect on the ATT, and the smaller the value of the weight factor, the more efficient the trapping process is. Comparing the standard weight-dependent walk with mixed weight-dependent walk, although next-nearest-neighbor jumps have no main effect on the trapping process, they can modify the coefficient of the dominant term for the ATT.
Collapse
Affiliation(s)
- Meifeng Dai
- Institute of Applied System Analysis, Jiangsu University, Zhenjiang, Jiangsu 212013, People's Republic of China
| | - Yue Zong
- Institute of Applied System Analysis, Jiangsu University, Zhenjiang, Jiangsu 212013, People's Republic of China
| | - Jiaojiao He
- Institute of Applied System Analysis, Jiangsu University, Zhenjiang, Jiangsu 212013, People's Republic of China
| | - Yu Sun
- Institute of Applied System Analysis, Jiangsu University, Zhenjiang, Jiangsu 212013, People's Republic of China
| | - Chunyu Shen
- Nonlinear Scientific Research Center, Jiangsu University, Zhenjiang, Jiangsu 212013, People's Republic of China
| | - Weiyi Su
- Department of Mathematics, Nanjing University, Nanjing 210093, People's Republic of China
| |
Collapse
|
4
|
Arola-Fernández L, Díaz-Guilera A, Arenas A. Synchronization invariance under network structural transformations. Phys Rev E 2018; 97:060301. [PMID: 30011485 DOI: 10.1103/physreve.97.060301] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.5] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 02/09/2018] [Indexed: 06/08/2023]
Abstract
Synchronization processes are ubiquitous despite the many connectivity patterns that complex systems can show. Usually, the emergence of synchrony is a macroscopic observable; however, the microscopic details of the system, as, e.g., the underlying network of interactions, is many times partially or totally unknown. We already know that different interaction structures can give rise to a common functionality, understood as a common macroscopic observable. Building upon this fact, here we propose network transformations that keep the collective behavior of a large system of Kuramoto oscillators invariant. We derive a method based on information theory principles, that allows us to adjust the weights of the structural interactions to map random homogeneous in-degree networks into random heterogeneous networks and vice versa, keeping synchronization values invariant. The results of the proposed transformations reveal an interesting principle; heterogeneous networks can be mapped to homogeneous ones with local information, but the reverse process needs to exploit higher-order information. The formalism provides analytical insight to tackle real complex scenarios when dealing with uncertainty in the measurements of the underlying connectivity structure.
Collapse
Affiliation(s)
- Lluís Arola-Fernández
- Departament d'Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili, 43007 Tarragona, Spain
| | - Albert Díaz-Guilera
- Departament de Física Fonamental, Universitat de Barcelona, Martí i Franquès 1, 08028 Barcelona, Spain
- Universitat de Barcelona Institute for Complex Systems (UBICS), Barcelona, Spain
| | - Alex Arenas
- Departament d'Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili, 43007 Tarragona, Spain
| |
Collapse
|
5
|
Tamura K, Takayasu H, Takayasu M. Diffusion-localization transition caused by nonlinear transport on complex networks. Sci Rep 2018; 8:5517. [PMID: 29615701 PMCID: PMC5882644 DOI: 10.1038/s41598-018-23675-x] [Citation(s) in RCA: 5] [Impact Index Per Article: 0.8] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 11/27/2017] [Accepted: 03/13/2018] [Indexed: 11/10/2022] Open
Abstract
We analyzed nonlinear transport as defined for directed complex networks, where the flux from one node to a neighboring node is given preferentially according to the scalar quantities at the neighbor nodes. This is known as the generalized gravity interaction. In our research, we discovered a novel phase transition type. In the diffusion phase, the scalar quantity is scattered over the whole system, whereas in the localization phase, the flow tends to form localized confluence patterns owing to nonlinearity, resulting in the appearance of special nodes that irreversibly attract huge amounts of flow. We analytically considered the transition for selected network configurations, demonstrating that the transition point depends on the network topology. We also demonstrated that the diffusion phase of this transport model fits well with data from business firms, implying that the whole network structure can be used to model money flow in the real world.
Collapse
Affiliation(s)
- Koutarou Tamura
- Institute of Innovative Research, Tokyo Institute of Technology, 4259-S1-3, Nagatsuta-cho, Midori-ku, Yokohama, 226-8503, Japan
| | - Hideki Takayasu
- Sony Computer Science Laboratories, 3-14-13, Higashigotanda, Shinagawa-ku, Tokyo, 141-0022, Japan
| | - Misako Takayasu
- Institute of Innovative Research, Tokyo Institute of Technology, 4259-S1-3, Nagatsuta-cho, Midori-ku, Yokohama, 226-8503, Japan.
| |
Collapse
|
6
|
Scaling of average receiving time on weighted polymer networks with some topological properties. Sci Rep 2017; 7:2128. [PMID: 28522831 PMCID: PMC5437065 DOI: 10.1038/s41598-017-02036-0] [Citation(s) in RCA: 6] [Impact Index Per Article: 0.9] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 01/10/2017] [Accepted: 04/06/2017] [Indexed: 11/08/2022] Open
Abstract
In this paper, a family of the weighted polymer networks is introduced depending on the number of copies f and a weight factor r. The topological properties of weighted polymer networks can be completely analytically characterized in terms of the involved parameters and/or of the fractal dimension. Moreover, assuming that the walker, at each step, starting from its current node, moves to any of its neighbors with probability proportional to the weight of edge linking them, namely weight-dependent walk. Then, we calculate the average receiving time (ART) with weighted-dependent walks, which is the sum of mean first-passage times (MFPTs) for all nodes absorpt at the trap located at the central node as a recursive relation. The obtained remarkable results display that when [Formula: see text], the ART grows sublinearly with the network size; when [Formula: see text], ART grows with increasing size N g as [Formula: see text]; when [Formula: see text], ART grows with increasing size N g as ln N g . In the treelike polymer networks, ART grows with linearly with the network size N g when r = 1. Thus, the weighted polymer networks are more efficient than treelike polymer networks in receiving information.
Collapse
|
7
|
Tamura K, Takayasu H, Takayasu M. Extraction of conjugate main-stream structures from a complex network flow. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2015; 91:042815. [PMID: 25974555 DOI: 10.1103/physreve.91.042815] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.1] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 01/13/2015] [Indexed: 06/04/2023]
Abstract
We introduce a method to extract main-stream structures for a given complex network flow by trimming less effective links. As the resulting main streams generally have an almost loopless treelike structure, we can define the stream basin size for each node, which characterizes the importance of the node with regard to the flow. As a real-world example, we apply this method to an interfirm trading network, both for the money flow and its conjugate-the material or service flow-confirming that both basin size distributions follow a similar power law that differs significantly from the basin size distributions of rivers in nature. We theoretically analyze the process of trimming and derive a consistent statistical formulation between the original link number and the basin size.
Collapse
Affiliation(s)
- Koutarou Tamura
- Department of Computational Intelligence and Systems Science, Interdisciplinary Graduate School of Science and Engineering, Tokyo Institute of Technology, 4259-G3-52 Nagatsuta-cho, Midori-ku, Yokohama 226-8503, Japan
| | - Hideki Takayasu
- Department of Computational Intelligence and Systems Science, Interdisciplinary Graduate School of Science and Engineering, Tokyo Institute of Technology, 4259-G3-52 Nagatsuta-cho, Midori-ku, Yokohama 226-8503, Japan
- Sony Computer Science Laboratories, 3-14-13 Higashigotanda, Shinagawa-ku, Tokyo 141-0022, Japan
- Meiji Institute for Advanced Study of Mathematical Sciences, Meiji University, 4-21-1 Nakano, Nakano-ku, Tokyo 164-8525, Japan
| | - Misako Takayasu
- Department of Computational Intelligence and Systems Science, Interdisciplinary Graduate School of Science and Engineering, Tokyo Institute of Technology, 4259-G3-52 Nagatsuta-cho, Midori-ku, Yokohama 226-8503, Japan
| |
Collapse
|
8
|
Ferreri L, Bajardi P, Giacobini M, Perazzo S, Venturino E. Interplay of network dynamics and heterogeneity of ties on spreading dynamics. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2014; 90:012812. [PMID: 25122347 DOI: 10.1103/physreve.90.012812] [Citation(s) in RCA: 5] [Impact Index Per Article: 0.5] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 09/10/2013] [Indexed: 05/16/2023]
Abstract
The structure of a network dramatically affects the spreading phenomena unfolding upon it. The contact distribution of the nodes has long been recognized as the key ingredient in influencing the outbreak events. However, limited knowledge is currently available on the role of the weight of the edges on the persistence of a pathogen. At the same time, recent works showed a strong influence of temporal network dynamics on disease spreading. In this work we provide an analytical understanding, corroborated by numerical simulations, about the conditions for infected stable state in weighted networks. In particular, we reveal the role of heterogeneity of edge weights and of the dynamic assignment of weights on the ties in the network in driving the spread of the epidemic. In this context we show that when weights are dynamically assigned to ties in the network, a heterogeneous distribution is able to hamper the diffusion of the disease, contrary to what happens when weights are fixed in time.
Collapse
Affiliation(s)
- Luca Ferreri
- GECO-Computational Epidemiology Group, Department of Veterinary Sciences, University of Torino, largo Braccini 2, IT-10095 Grugliasco (TO) and ARCS - Applied Research on Computational Complex Systems Group, Department of Computer Science, University of Torino, corso Svizzera 185, IT-10149 Torino
| | - Paolo Bajardi
- GECO-Computational Epidemiology Group, Department of Veterinary Sciences, University of Torino, largo Braccini 2, IT-10095 Grugliasco (TO) and ARCS - Applied Research on Computational Complex Systems Group, Department of Computer Science, University of Torino, corso Svizzera 185, IT-10149 Torino
| | - Mario Giacobini
- GECO-Computational Epidemiology Group, Department of Veterinary Sciences, University of Torino, largo Braccini 2, IT-10095 Grugliasco (TO) and ARCS - Applied Research on Computational Complex Systems Group, Department of Computer Science, University of Torino, corso Svizzera 185, IT-10149 Torino and CSU-Complex Systems Unit, Molecular Biotechnology Centre, University of Torino, via Nizza 52, IT-10126 Torino
| | - Silvia Perazzo
- Department of Mathematics "Giuseppe Peano", University of Torino, via Carlo Alberto 10, IT-10123 Torino
| | - Ezio Venturino
- Department of Mathematics "Giuseppe Peano", University of Torino, via Carlo Alberto 10, IT-10123 Torino
| |
Collapse
|
9
|
Lin Y, Zhang Z. Mean first-passage time for maximal-entropy random walks in complex networks. Sci Rep 2014; 4:5365. [PMID: 24947015 PMCID: PMC4064359 DOI: 10.1038/srep05365] [Citation(s) in RCA: 24] [Impact Index Per Article: 2.4] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 04/14/2014] [Accepted: 05/27/2014] [Indexed: 11/09/2022] Open
Abstract
We perform an in-depth study for mean first-passage time (MFPT)--a primary quantity for random walks with numerous applications--of maximal-entropy random walks (MERW) performed in complex networks. For MERW in a general network, we derive an explicit expression of MFPT in terms of the eigenvalues and eigenvectors of the adjacency matrix associated with the network. For MERW in uncorrelated networks, we also provide a theoretical formula of MFPT at the mean-field level, based on which we further evaluate the dominant scalings of MFPT to different targets for MERW in uncorrelated scale-free networks, and compare the results with those corresponding to traditional unbiased random walks (TURW). We show that the MFPT to a hub node is much lower for MERW than for TURW. However, when the destination is a node with the least degree or a uniformly chosen node, the MFPT is higher for MERW than for TURW. Since MFPT to a uniformly chosen node measures real efficiency of search in networks, our work provides insight into general searching process in complex networks.
Collapse
Affiliation(s)
- Yuan Lin
- School of Computer Science, Fudan University, Shanghai 200433, China
- Shanghai Key Lab of Intelligent Information Processing, Fudan University, Shanghai 200433, China
| | - Zhongzhi Zhang
- School of Computer Science, Fudan University, Shanghai 200433, China
- Shanghai Key Lab of Intelligent Information Processing, Fudan University, Shanghai 200433, China
| |
Collapse
|
10
|
Mean field approximation for biased diffusion on Japanese inter-firm trading network. PLoS One 2014; 9:e91704. [PMID: 24626149 PMCID: PMC3953512 DOI: 10.1371/journal.pone.0091704] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 12/04/2013] [Accepted: 02/14/2014] [Indexed: 11/19/2022] Open
Abstract
By analysing the financial data of firms across Japan, a nonlinear power law with an exponent of 1.3 was observed between the number of business partners (i.e. the degree of the inter-firm trading network) and sales. In a previous study using numerical simulations, we found that this scaling can be explained by both the money-transport model, where a firm (i.e. customer) distributes money to its out-edges (suppliers) in proportion to the in-degree of destinations, and by the correlations among the Japanese inter-firm trading network. However, in this previous study, we could not specifically identify what types of structure properties (or correlations) of the network determine the 1.3 exponent. In the present study, we more clearly elucidate the relationship between this nonlinear scaling and the network structure by applying mean-field approximation of the diffusion in a complex network to this money-transport model. Using theoretical analysis, we obtained the mean-field solution of the model and found that, in the case of the Japanese firms, the scaling exponent of 1.3 can be determined from the power law of the average degree of the nearest neighbours of the network with an exponent of −0.7.
Collapse
|
11
|
Bonaventura M, Nicosia V, Latora V. Characteristic times of biased random walks on complex networks. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2014; 89:012803. [PMID: 24580277 DOI: 10.1103/physreve.89.012803] [Citation(s) in RCA: 11] [Impact Index Per Article: 1.1] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 07/12/2013] [Indexed: 06/03/2023]
Abstract
We consider degree-biased random walkers whose probability to move from a node to one of its neighbors of degree k is proportional to k(α), where α is a tuning parameter. We study both numerically and analytically three types of characteristic times, namely (i) the time the walker needs to come back to the starting node, (ii) the time it takes to visit a given node for the first time, and (iii) the time it takes to visit all the nodes of the network. We consider a large data set of real-world networks and we show that the value of α which minimizes the three characteristic times differs from the value α(min)=-1 analytically found for uncorrelated networks in the mean-field approximation. In addition to this, we found that assortative networks have preferentially a value of α(min) in the range [-1,-0.5], while disassortative networks have α(min) in the range [-0.5,0]. We derive an analytical relation between the degree correlation exponent ν and the optimal bias value α(min), which works well for real-world assortative networks. When only local information is available, degree-biased random walks can guarantee smaller characteristic times than the classical unbiased random walks by means of an appropriate tuning of the motion bias.
Collapse
Affiliation(s)
- Moreno Bonaventura
- School of Mathematical Sciences, Queen Mary University of London, Mile End Road, London E1 4NS, United Kingdom and School of Business and Management, Queen Mary University of London, Mile End Road, London E1 4NS, United Kingdom
| | - Vincenzo Nicosia
- School of Mathematical Sciences, Queen Mary University of London, Mile End Road, London E1 4NS, United Kingdom
| | - Vito Latora
- School of Mathematical Sciences, Queen Mary University of London, Mile End Road, London E1 4NS, United Kingdom and Dipartimento di Fisica e Astronomia, Università di Catania and INFN, 95123 Catania, Italy
| |
Collapse
|
12
|
Baronchelli A, Ferrer-i-Cancho R, Pastor-Satorras R, Chater N, Christiansen MH. Networks in Cognitive Science. Trends Cogn Sci 2013; 17:348-60. [PMID: 23726319 DOI: 10.1016/j.tics.2013.04.010] [Citation(s) in RCA: 209] [Impact Index Per Article: 19.0] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 12/20/2012] [Revised: 04/16/2013] [Accepted: 04/17/2013] [Indexed: 01/14/2023]
|
13
|
Lin Y, Zhang Z. Random walks in weighted networks with a perfect trap: an application of Laplacian spectra. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2013; 87:062140. [PMID: 23848660 DOI: 10.1103/physreve.87.062140] [Citation(s) in RCA: 17] [Impact Index Per Article: 1.5] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 04/26/2013] [Indexed: 06/02/2023]
Abstract
Trapping processes constitute a primary problem of random walks, which characterize various other dynamical processes taking place on networks. Most previous works focused on the case of binary networks, while there is much less related research about weighted networks. In this paper, we propose a general framework for the trapping problem on a weighted network with a perfect trap fixed at an arbitrary node. By utilizing the spectral graph theory, we provide an exact formula for mean first-passage time (MFPT) from one node to another, based on which we deduce an explicit expression for average trapping time (ATT) in terms of the eigenvalues and eigenvectors of the Laplacian matrix associated with the weighted graph, where ATT is the average of MFPTs to the trap over all source nodes. We then further derive a sharp lower bound for the ATT in terms of only the local information of the trap node, which can be obtained in some graphs. Moreover, we deduce the ATT when the trap is distributed uniformly in the whole network. Our results show that network weights play a significant role in the trapping process. To apply our framework, we use the obtained formulas to study random walks on two specific networks: trapping in weighted uncorrelated networks with a deep trap, the weights of which are characterized by a parameter, and Lévy random walks in a connected binary network with a trap distributed uniformly, which can be looked on as random walks on a weighted network. For weighted uncorrelated networks we show that the ATT to any target node depends on the weight parameter, that is, the ATT to any node can change drastically by modifying the parameter, a phenomenon that is in contrast to that for trapping in binary networks. For Lévy random walks in any connected network, by using their equivalence to random walks on a weighted complete network, we obtain the optimal exponent characterizing Lévy random walks, which have the minimal average of ATTs taken over all target nodes.
Collapse
Affiliation(s)
- Yuan Lin
- School of Computer Science, Fudan University, Shanghai 200433, China
| | | |
Collapse
|
14
|
Noise enhances information transfer in hierarchical networks. Sci Rep 2013; 3:1223. [PMID: 23390574 PMCID: PMC3565226 DOI: 10.1038/srep01223] [Citation(s) in RCA: 41] [Impact Index Per Article: 3.7] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 08/09/2012] [Accepted: 01/11/2013] [Indexed: 11/21/2022] Open
Abstract
We study the influence of noise on information transmission in the form of packages shipped between nodes of hierarchical networks. Numerical simulations are performed for artificial tree networks, scale-free Ravasz-Barabási networks as well for a real network formed by email addresses of former Enron employees. Two types of noise are considered. One is related to packet dynamics and is responsible for a random part of packets paths. The second one originates from random changes in initial network topology. We find that the information transfer can be enhanced by the noise. The system possesses optimal performance when both kinds of noise are tuned to specific values, this corresponds to the Stochastic Resonance phenomenon. There is a non-trivial synergy present for both noisy components. We found also that hierarchical networks built of nodes of various degrees are more efficient in information transfer than trees with a fixed branching factor.
Collapse
|
15
|
Zhang Z, Shan T, Chen G. Random walks on weighted networks. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2013; 87:012112. [PMID: 23410288 DOI: 10.1103/physreve.87.012112] [Citation(s) in RCA: 23] [Impact Index Per Article: 2.1] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 05/07/2012] [Indexed: 06/01/2023]
Abstract
Random walks constitute a fundamental mechanism for a large set of dynamics taking place on networks. In this article, we study random walks on weighted networks with an arbitrary degree distribution, where the weight of an edge between two nodes has a tunable parameter. By using the spectral graph theory, we derive analytical expressions for the stationary distribution, mean first-passage time (MFPT), average trapping time (ATT), and lower bound of the ATT, which is defined as the average MFPT to a given node over every starting point chosen from the stationary distribution. All these results depend on the weight parameter, indicating a significant role of network weights on random walks. For the case of uncorrelated networks, we provide explicit formulas for the stationary distribution as well as ATT. Particularly, for uncorrelated scale-free networks, when the target is placed on a node with the highest degree, we show that ATT can display various scalings of network size, depending also on the same parameter. Our findings could pave a way to delicately controlling random-walk dynamics on complex networks.
Collapse
Affiliation(s)
- Zhongzhi Zhang
- School of Computer Science, Fudan University, Shanghai 200433,
| | | | | |
Collapse
|
16
|
Perra N, Baronchelli A, Mocanu D, Gonçalves B, Pastor-Satorras R, Vespignani A. Random walks and search in time-varying networks. PHYSICAL REVIEW LETTERS 2012; 109:238701. [PMID: 23368274 DOI: 10.1103/physrevlett.109.238701] [Citation(s) in RCA: 67] [Impact Index Per Article: 5.6] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 06/15/2012] [Indexed: 06/01/2023]
Abstract
The random walk process underlies the description of a large number of real-world phenomena. Here we provide the study of random walk processes in time-varying networks in the regime of time-scale mixing, i.e., when the network connectivity pattern and the random walk process dynamics are unfolding on the same time scale. We consider a model for time-varying networks created from the activity potential of the nodes and derive solutions of the asymptotic behavior of random walks and the mean first passage time in undirected and directed networks. Our findings show striking differences with respect to the well-known results obtained in quenched and annealed networks, emphasizing the effects of dynamical connectivity patterns in the definition of proper strategies for search, retrieval, and diffusion processes in time-varying networks.
Collapse
Affiliation(s)
- Nicola Perra
- Laboratory for the Modeling of Biological and Socio-technical Systems, Northeastern University, Boston, Massachusetts 02115, USA
| | | | | | | | | | | |
Collapse
|
17
|
Odor G, Pastor-Satorras R. Slow dynamics and rare-region effects in the contact process on weighted tree networks. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2012; 86:026117. [PMID: 23005835 DOI: 10.1103/physreve.86.026117] [Citation(s) in RCA: 8] [Impact Index Per Article: 0.7] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 06/07/2012] [Indexed: 06/01/2023]
Abstract
We show that generic, slow dynamics can occur in the contact process on complex networks with a tree-like structure and a superimposed weight pattern, in the absence of additional (nontopological) sources of quenched disorder. The slow dynamics is induced by rare-region effects occurring on correlated subspaces of vertices connected by large weight edges and manifests in the form of a smeared phase transition. We conjecture that more sophisticated network motifs could be able to induce Griffiths phases, as a consequence of purely topological disorder.
Collapse
Affiliation(s)
- Géza Odor
- Research Centre for Natural Sciences, Hungarian Academy of Sciences, MTA TTK MFA, Budapest, Hungary
| | | |
Collapse
|
18
|
Yang Z, Zhou T. Epidemic spreading in weighted networks: an edge-based mean-field solution. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2012; 85:056106. [PMID: 23004820 DOI: 10.1103/physreve.85.056106] [Citation(s) in RCA: 33] [Impact Index Per Article: 2.8] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 12/23/2011] [Revised: 04/20/2012] [Indexed: 06/01/2023]
Abstract
Weight distribution greatly impacts the epidemic spreading taking place on top of networks. This paper presents a study of a susceptible-infected-susceptible model on regular random networks with different kinds of weight distributions. Simulation results show that the more homogeneous weight distribution leads to higher epidemic prevalence, which, unfortunately, could not be captured by the traditional mean-field approximation. This paper gives an edge-based mean-field solution for general weight distribution, which can quantitatively reproduce the simulation results. This method could be applied to characterize the nonequilibrium steady states of dynamical processes on weighted networks.
Collapse
Affiliation(s)
- Zimo Yang
- Web Sciences Center, University of Electronic Science and Technology of China, Chengdu, People's Republic of China
| | | |
Collapse
|
19
|
Starnini M, Baronchelli A, Barrat A, Pastor-Satorras R. Random walks on temporal networks. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2012; 85:056115. [PMID: 23004829 DOI: 10.1103/physreve.85.056115] [Citation(s) in RCA: 44] [Impact Index Per Article: 3.7] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 03/12/2012] [Indexed: 06/01/2023]
Abstract
Many natural and artificial networks evolve in time. Nodes and connections appear and disappear at various time scales, and their dynamics has profound consequences for any processes in which they are involved. The first empirical analysis of the temporal patterns characterizing dynamic networks are still recent, so that many questions remain open. Here, we study how random walks, as a paradigm of dynamical processes, unfold on temporally evolving networks. To this aim, we use empirical dynamical networks of contacts between individuals, and characterize the fundamental quantities that impact any general process taking place upon them. Furthermore, we introduce different randomizing strategies that allow us to single out the role of the different properties of the empirical networks. We show that the random walk exploration is slower on temporal networks than it is on the aggregate projected network, even when the time is properly rescaled. In particular, we point out that a fundamental role is played by the temporal correlations between consecutive contacts present in the data. Finally, we address the consequences of the intrinsically limited duration of many real world dynamical networks. Considering the fundamental prototypical role of the random walk process, we believe that these results could help to shed light on the behavior of more complex dynamics on temporally evolving networks.
Collapse
Affiliation(s)
- Michele Starnini
- Departament de Física i Enginyeria Nuclear, Universitat Politècnica de Catalunya, Barcelona, Spain
| | | | | | | |
Collapse
|
20
|
Gleeson JP, Melnik S, Ward JA, Porter MA, Mucha PJ. Accuracy of mean-field theory for dynamics on real-world networks. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2012; 85:026106. [PMID: 22463278 DOI: 10.1103/physreve.85.026106] [Citation(s) in RCA: 60] [Impact Index Per Article: 5.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 11/16/2010] [Revised: 12/19/2011] [Indexed: 05/04/2023]
Abstract
Mean-field analysis is an important tool for understanding dynamics on complex networks. However, surprisingly little attention has been paid to the question of whether mean-field predictions are accurate, and this is particularly true for real-world networks with clustering and modular structure. In this paper, we compare mean-field predictions to numerical simulation results for dynamical processes running on 21 real-world networks and demonstrate that the accuracy of such theory depends not only on the mean degree of the networks but also on the mean first-neighbor degree. We show that mean-field theory can give (unexpectedly) accurate results for certain dynamics on disassortative real-world networks even when the mean degree is as low as 4.
Collapse
Affiliation(s)
- James P Gleeson
- MACSI, Department of Mathematics & Statistics, University of Limerick, Ireland
| | | | | | | | | |
Collapse
|
21
|
Xuan Q, Du F, Dong H, Yu L, Chen G. Structural control of reaction-diffusion networks. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2011; 84:036101. [PMID: 22060450 DOI: 10.1103/physreve.84.036101] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 05/21/2011] [Revised: 07/25/2011] [Indexed: 05/31/2023]
Abstract
Recent studies revealed that reaction-diffusion (RD) dynamics can be significantly influenced by the structure of the underlying network. In this paper, a framework is established to study a closely related problem, i.e., to control the proportion of active particles in an RD process by adjusting the structure of the underlying diffusion network. Both distributed and centralized rewiring and reweighting control schemes are proposed for unweighted and weighted networks, respectively. Simulations show that the proportion of active particles can indeed be controlled to a certain extent even when the distributed control mechanism is totally random, while quite high precision can be achieved by centralized control schemes. More interestingly, it is found that the reactants in heterogeneous networks have wider controllable ranges than those in homogeneous networks with similar numbers of nodes and links, if only the weights of links are changed with a fixed bound. Therefore, it is believed that heterogeneous networks fit the changeable environment better, which provides another explanation for some common observations on many heterogeneous real-world networks.
Collapse
Affiliation(s)
- Qi Xuan
- Department of Automation, Zhejiang University of Technology, Hangzhou 310023, People's Republic of China.
| | | | | | | | | |
Collapse
|
22
|
Baronchelli A, Castellano C, Pastor-Satorras R. Voter models on weighted networks. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2011; 83:066117. [PMID: 21797451 DOI: 10.1103/physreve.83.066117] [Citation(s) in RCA: 5] [Impact Index Per Article: 0.4] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 11/10/2010] [Indexed: 05/27/2023]
Abstract
We study the dynamics of the voter and Moran processes running on top of complex network substrates where each edge has a weight depending on the degree of the nodes it connects. For each elementary dynamical step the first node is chosen at random and the second is selected with probability proportional to the weight of the connecting edge. We present a heterogeneous mean-field approach allowing to identify conservation laws and to calculate exit probabilities along with consensus times. In the specific case when the weight is given by the product of nodes' degree raised to a power θ, we derive a rich phase diagram, with the consensus time exhibiting various scaling laws depending on θ and on the exponent of the degree distribution γ. Numerical simulations give very good agreement for small values of |θ|. An additional analytical treatment (heterogeneous pair approximation) improves the agreement with numerics, but the theoretical understanding of the behavior in the limit of large |θ| remains an open challenge.
Collapse
Affiliation(s)
- Andrea Baronchelli
- Departament de Física i Enginyeria Nuclear, Universitat Politècnica de Catalunya, Campus Nord B4, 08034 Barcelona, Spain
| | | | | |
Collapse
|
23
|
Tang M, Liu Z, Li B. Influence of zero range process interaction on diffusion. CHAOS (WOODBURY, N.Y.) 2010; 20:043135. [PMID: 21198105 DOI: 10.1063/1.3528101] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 05/30/2023]
Abstract
We study the aspects of diffusion for the case of zero range process interaction on scale-free networks, through statistical quantities such as the mean first passage time, coverage, mean square displacement etc., and pay attention to how the interaction, especially the resulted condensation, influences the diffusion. By mean-field theory we show that the statistical quantities of diffusion can be significantly reduced by the condensation and can be figured out by the waiting time of a particle staying at a node. Numerical simulations have confirmed the theoretical predictions.
Collapse
Affiliation(s)
- Ming Tang
- Department of Physics and Institute of Theoretical Physics, East China Normal University, Shanghai 200062, People's Republic of China.
| | | | | |
Collapse
|
24
|
Kwon S, Choi W, Kim Y. Bimolecular chemical reactions on weighted complex networks. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2010; 82:021108. [PMID: 20866776 DOI: 10.1103/physreve.82.021108] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.1] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 03/03/2010] [Revised: 06/09/2010] [Indexed: 05/29/2023]
Abstract
We investigate the kinetics of bimolecular chemical reactions A+A→0 and A+B→0 on weighted scale-free networks (WSFNs) with degree distribution P(k)∼k^{-γ} . On WSFNs, a weight w{ij} is assigned to the link between node i and j . We consider the symmetric weight given as w{ij}=(k{i}k{j})^{μ} , where k{i} and k{j} are the degree of node i and j . The hopping probability T{ij} of a particle from node i to j is then given as T{ij}∝(k{i}k{j})^{μ} . From a mean-field analysis, we analytically show in the thermodynamic limit that the kinetics of A+A→0 and A+B→0 are identical and there exist two crossover μ values, μ{1c}=γ-2 and μ{2c}=(γ-3)/2 . The density of particles ρ(t) algebraically decays in time t as t^{-α} with α=1 for μ<μ{2c} and α=(μ+1)/(γ-μ-2) for μ{2c}≤μ<μ{1c} . For μ≥μ{1c} , ρ decays exponentially. With the mean-field rate equation for ρ(t) , we also analytically show that the kinetics on the WSFNs is mapped onto that on unweighted SFNs with P(k)∼k^{-γ^{'}} with γ^{'}=(μ+γ)/(μ+1) .
Collapse
Affiliation(s)
- Sungchul Kwon
- Department of Physics and Research Institute of Basic Sciences, Kyung Hee University, Seoul, Korea
| | | | | |
Collapse
|