1
|
Lin H, Xia Y, Liang Y. Efficient routing for spatial networks. CHAOS (WOODBURY, N.Y.) 2022; 32:053110. [PMID: 35649983 DOI: 10.1063/5.0091976] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 03/19/2022] [Accepted: 04/18/2022] [Indexed: 06/15/2023]
Abstract
In many complex networks, the main task is to transfer load from sources to destinations. Therefore, the network throughput is a very important indicator to measure the network performance. In order to improve the network throughput, researchers have proposed many effective routing strategies. Spatial networks, as a class of complex networks, exist widely in the real-world. However, the existing routing strategies in complex networks cannot achieve good results when applied in spatial networks. Therefore, in this paper, we propose a new degree-location ( D L) routing strategy to improve the throughput of spatial networks. In this routing strategy, the load transmitted from sources to destinations will bypass the nodes with high degrees and the nodes located close to the center of region. Simulations on homogeneous and heterogeneous spatial networks show that the D L routing strategy proposed in this paper can effectively improve the throughput of the network. The result of this paper can help the routing design of spatial networks and may find applications in many real-world spatial networks to improve the transmission performance.
Collapse
Affiliation(s)
- Hong Lin
- School of Communication Engineering, Hangzhou Dianzi University, Hangzhou 310018, China
| | - Yongxiang Xia
- School of Communication Engineering, Hangzhou Dianzi University, Hangzhou 310018, China
| | - Yuanyuan Liang
- School of Communication Engineering, Hangzhou Dianzi University, Hangzhou 310018, China
| |
Collapse
|
2
|
Chen B, Ding Z, Wu Y, Zhou J, Chen Y. An optimal global algorithm for route guidance in advanced traveler information systems. Inf Sci (N Y) 2021. [DOI: 10.1016/j.ins.2020.10.012] [Citation(s) in RCA: 6] [Impact Index Per Article: 2.0] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 12/01/2022]
|
3
|
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
|
4
|
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
|
5
|
Csoma A, Kőrösi A, Rétvári G, Heszberger Z, Bíró J, Slíz M, Avena-Koenigsberger A, Griffa A, Hagmann P, Gulyás A. Routes Obey Hierarchy in Complex Networks. Sci Rep 2017; 7:7243. [PMID: 28775278 PMCID: PMC5543142 DOI: 10.1038/s41598-017-07412-4] [Citation(s) in RCA: 9] [Impact Index Per Article: 1.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 03/28/2017] [Accepted: 06/23/2017] [Indexed: 12/21/2022] Open
Abstract
The last two decades of network science have discovered stunning similarities in the topological characteristics of real life networks (many biological, social, transportation and organizational networks) on a strong empirical basis. However our knowledge about the operational paths used in these networks is very limited, which prohibits the proper understanding of the principles of their functioning. Today, the most widely adopted hypothesis about the structure of the operational paths is the shortest path assumption. Here we present a striking result that the paths in various networks are significantly stretched compared to their shortest counterparts. Stretch distributions are also found to be extremely similar. This phenomenon is empirically confirmed on four networks from diverse areas of life. We also identify the high-level path selection rules nature seems to use when picking its paths.
Collapse
Affiliation(s)
- Attila Csoma
- Budapest University of Technology and Economics, Dept. of Telecommunications and Media Informatics, MTA-BME Information Systems Research Group, H-1117, Budapest, Magyar tudósok krt. 2, Hungary
| | - Attila Kőrösi
- Budapest University of Technology and Economics, Dept. of Telecommunications and Media Informatics, MTA-BME Information Systems Research Group, H-1117, Budapest, Magyar tudósok krt. 2, Hungary
| | - Gábor Rétvári
- Budapest University of Technology and Economics, Dept. of Telecommunications and Media Informatics, MTA-BME Information Systems Research Group, H-1117, Budapest, Magyar tudósok krt. 2, Hungary
| | - Zalán Heszberger
- Budapest University of Technology and Economics, Dept. of Telecommunications and Media Informatics, MTA-BME Information Systems Research Group, H-1117, Budapest, Magyar tudósok krt. 2, Hungary
| | - József Bíró
- Budapest University of Technology and Economics, Dept. of Telecommunications and Media Informatics, MTA-BME Information Systems Research Group, H-1117, Budapest, Magyar tudósok krt. 2, Hungary
| | - Mariann Slíz
- Eötvös Loránd University, Institute of Hungarian Linguistics and Finno-Ugric Studies, H-1088, Budapest, Múzeum krt. 4/A, Hungary
| | | | - Alessandra Griffa
- Department of Psychiatry, Brain Center Rudolf Magnus, University Medical Center Utrecht, Utrecht, Netherlands.,Signal Processing Laboratory 5 (LTS5), École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland
| | - Patric Hagmann
- Department of Radiology, Centre Hospitalier Universitaire Vaudois (CHUV) and University of Lausanne (UNIL), Lausanne, Switzerland.,Signal Processing Laboratory 5 (LTS5), École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland
| | - András Gulyás
- Budapest University of Technology and Economics, Dept. of Telecommunications and Media Informatics, MTA-BME Information Systems Research Group, H-1117, Budapest, Magyar tudósok krt. 2, Hungary.
| |
Collapse
|
6
|
Zhang X, Zhou Z, Cheng D. Efficient path routing strategy for flows with multiple priorities on scale-free networks. PLoS One 2017; 12:e0172035. [PMID: 28199382 PMCID: PMC5310893 DOI: 10.1371/journal.pone.0172035] [Citation(s) in RCA: 12] [Impact Index Per Article: 1.7] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 12/08/2016] [Accepted: 01/30/2017] [Indexed: 11/18/2022] Open
Abstract
In real networks, traffic flows are different in amount as well as their priorities. However, the latter priority has rarely been examined in routing strategy studies. In this paper, a novel routing algorithm, which is based on the efficient path routing strategy (EP), is proposed to overcome network congestion problem caused by large amount of traffic flows with different priorities. In this scheme, traffic flows with different priorities are transmitted through different routing paths, which are based on EP with different parameters. Simulation results show that the traffic capacity for flows with different priorities can be enhanced by 12% with this method, compared with EP. In addition, the new method contributes to more balanced network traffic load distribution and reduces average transmission jump and delay of packets.
Collapse
Affiliation(s)
- Xi Zhang
- School of Management, Xi’an Jiaotong University, No. 28, Xi’an, P. R. China
- * E-mail:
| | - Zhili Zhou
- School of Management, Xi’an Jiaotong University, No. 28, Xi’an, P. R. China
| | - Dong Cheng
- School of Management, Xi’an Jiaotong University, No. 28, Xi’an, P. R. China
| |
Collapse
|
7
|
Jiang ZY, Ma JF. Deployment of check-in nodes in complex networks. Sci Rep 2017; 7:40428. [PMID: 28074861 PMCID: PMC5225460 DOI: 10.1038/srep40428] [Citation(s) in RCA: 7] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 07/06/2016] [Accepted: 12/02/2016] [Indexed: 11/29/2022] Open
Abstract
In many real complex networks such as the city road networks and highway networks, vehicles often have to pass through some specially functioned nodes to receive check-in like services such as gas supplement at gas stations. Based on existing network structures, to guarantee every shortest path including at least a check-in node, the location selection of all check-in nodes is very essential and important to make vehicles to easily visit these check-in nodes, and it is still remains an open problem in complex network studies. In this work, we aim to find possible solutions for this problem. We first convert it into a set cover problem which is NP-complete and propose to employ the greedy algorithm to achieve an approximate result. Inspired by heuristic information of network structure, we discuss other four check-in node location deployment methods including high betweenness first (HBF), high degree first (HDF), random and low degree first (LDF). Finally, we compose extensive simulations in classical scale-free networks, random networks and real network models, and the results can well confirm the effectiveness of the greedy algorithm. This work has potential applications into many real networks.
Collapse
Affiliation(s)
- Zhong-Yuan Jiang
- School of Cyber Engineering, Xidian University, Xi'an, Shaanxi 710071, China
| | - Jian-Feng Ma
- School of Cyber Engineering, Xidian University, Xi'an, Shaanxi 710071, China.,School of Computer Science and Technology, Xidian University, Xi'an, Shaanxi 710071, China
| |
Collapse
|
8
|
Yang X, Li J, Pu C, Yan M, Sharafat RR, Yang J, Gakis K, Pardalos PM. Traffic congestion and the lifetime of networks with moving nodes. Phys Rev E 2017; 95:012322. [PMID: 28208369 DOI: 10.1103/physreve.95.012322] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.1] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 04/24/2016] [Indexed: 06/06/2023]
Abstract
For many power-limited networks, such as wireless sensor networks and mobile ad hoc networks, maximizing the network lifetime is the first concern in the related designing and maintaining activities. We study the network lifetime from the perspective of network science. In our model, nodes are initially assigned a fixed amount of energy moving in a square area and consume the energy when delivering packets. We obtain four different traffic regimes: no, slow, fast, and absolute congestion regimes, which are basically dependent on the packet generation rate. We derive the network lifetime by considering the specific regime of the traffic flow. We find that traffic congestion inversely affects network lifetime in the sense that high traffic congestion results in short network lifetime. We also discuss the impacts of factors such as communication radius, node moving speed, routing strategy, etc., on network lifetime and traffic congestion.
Collapse
Affiliation(s)
- Xianxia Yang
- Department of Computer Science and Engineering, Nanjing University of Science and Technology, Nanjing 210094, China
| | - Jie Li
- Department of Computer Science and Engineering, Nanjing University of Science and Technology, Nanjing 210094, China
| | - Cunlai Pu
- Department of Computer Science and Engineering, Nanjing University of Science and Technology, Nanjing 210094, China
- Industrial and Systems Engineering, University of Florida, Gainesville, Florida, USA
| | - Meichen Yan
- Department of Computer Science and Engineering, Nanjing University of Science and Technology, Nanjing 210094, China
| | - Rajput Ramiz Sharafat
- Department of Computer Science and Engineering, Nanjing University of Science and Technology, Nanjing 210094, China
| | - Jian Yang
- Department of Computer Science and Engineering, Nanjing University of Science and Technology, Nanjing 210094, China
| | - Konstantinos Gakis
- Industrial and Systems Engineering, University of Florida, Gainesville, Florida, USA
| | - Panos M Pardalos
- Industrial and Systems Engineering, University of Florida, Gainesville, Florida, USA
| |
Collapse
|
9
|
Li M, Hu MB, Wang BH. Transportation dynamics on coupled networks with limited bandwidth. Sci Rep 2016; 6:39175. [PMID: 27966624 PMCID: PMC5155292 DOI: 10.1038/srep39175] [Citation(s) in RCA: 16] [Impact Index Per Article: 2.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 07/26/2016] [Accepted: 11/18/2016] [Indexed: 11/25/2022] Open
Abstract
The communication networks in real world often couple with each other to save costs, which results in any network does not have a stand-alone function and efficiency. To investigate this, in this paper we propose a transportation model on two coupled networks with bandwidth sharing. We find that the free-flow state and the congestion state can coexist in the two coupled networks, and the free-flow path and congestion path can coexist in each network. Considering three bandwidth-sharing mechanisms, random, assortative and disassortative couplings, we also find that the transportation capacity of the network only depends on the coupling mechanism, and the fraction of coupled links only affects the performance of the system in the congestion state, such as the traveling time. In addition, with assortative coupling, the transportation capacity of the system will decrease significantly. However, the disassortative coupling has little influence on the transportation capacity of the system, which provides a good strategy to save bandwidth. Furthermore, a theoretical method is developed to obtain the bandwidth usage of each link, based on which we can obtain the congestion transition point exactly.
Collapse
Affiliation(s)
- Ming Li
- School of Engineering Science, University of Science and Technology of China, Hefei, 230026, P. R. China
| | - Mao-Bin Hu
- School of Engineering Science, University of Science and Technology of China, Hefei, 230026, P. R. China
| | - Bing-Hong Wang
- Department of Modern Physics, University of Science and Technology of China, Hefei, 230026, P. R. China
| |
Collapse
|
10
|
Lin B, Chen B, Gao Y, Tse CK, Dong C, Miao L, Wang B. Advanced Algorithms for Local Routing Strategy on Complex Networks. PLoS One 2016; 11:e0156756. [PMID: 27434502 PMCID: PMC4951044 DOI: 10.1371/journal.pone.0156756] [Citation(s) in RCA: 6] [Impact Index Per Article: 0.8] [Reference Citation Analysis] [Abstract] [MESH Headings] [Grants] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 09/26/2015] [Accepted: 05/19/2016] [Indexed: 11/21/2022] Open
Abstract
Despite the significant improvement on network performance provided by global routing strategies, their applications are still limited to small-scale networks, due to the need for acquiring global information of the network which grows and changes rapidly with time. Local routing strategies, however, need much less local information, though their transmission efficiency and network capacity are much lower than that of global routing strategies. In view of this, three algorithms are proposed and a thorough investigation is conducted in this paper. These algorithms include a node duplication avoidance algorithm, a next-nearest-neighbor algorithm and a restrictive queue length algorithm. After applying them to typical local routing strategies, the critical generation rate of information packets Rc increases by over ten-fold and the average transmission time 〈T〉 decreases by 70–90 percent, both of which are key physical quantities to assess the efficiency of routing strategies on complex networks. More importantly, in comparison with global routing strategies, the improved local routing strategies can yield better network performance under certain circumstances. This is a revolutionary leap for communication networks, because local routing strategy enjoys great superiority over global routing strategy not only in terms of the reduction of computational expense, but also in terms of the flexibility of implementation, especially for large-scale networks.
Collapse
Affiliation(s)
- Benchuan Lin
- Department of Modern Physics, University of Science and Technology of China, Hefei, China
| | - Bokui Chen
- School of Computing, National University of Singapore, Singapore, Singapore
- Faculty of Information Technology, Macau University of Science and Technology, Macau, China
- * E-mail:
| | - Yachun Gao
- School of Physical Electronics, University of Electronic Science and Technology of China, Chengdu, China, Chengdu, China
| | - Chi K. Tse
- Department of Electronic and Information Engineering, Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong
| | - Chuanfei Dong
- Department of Atmospheric, Oceanic and Space Science, University of Michigan, Ann Arbor, United States of America
| | - Lixin Miao
- Division of Logistics and Transportation, Graduate School at Shenzhen, Tsinghua University, Shenzhen, China
- Center of Environmental Science and New Energy Technology, Tsinghua-Berkeley Shenzhen Institute, Shenzhen, China
| | - Binghong Wang
- Department of Modern Physics, University of Science and Technology of China, Hefei, China
| |
Collapse
|
11
|
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
|
12
|
Tan F, Wu J, Xia Y, Tse CK. Traffic congestion in interconnected complex networks. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2014; 89:062813. [PMID: 25019839 DOI: 10.1103/physreve.89.062813] [Citation(s) in RCA: 8] [Impact Index Per Article: 0.8] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 01/23/2014] [Indexed: 06/03/2023]
Abstract
Traffic congestion in isolated complex networks has been investigated extensively over the last decade. Coupled network models have recently been developed to facilitate further understanding of real complex systems. Analysis of traffic congestion in coupled complex networks, however, is still relatively unexplored. In this paper, we try to explore the effect of interconnections on traffic congestion in interconnected Barabási-Albert scale-free networks. We find that assortative coupling can alleviate traffic congestion more readily than disassortative and random coupling when the node processing capacity is allocated based on node usage probability. Furthermore, the optimal coupling probability can be found for assortative coupling. However, three types of coupling preferences achieve similar traffic performance if all nodes share the same processing capacity. We analyze interconnected Internet autonomous-system-level graphs of South Korea and Japan and obtain similar results. Some practical suggestions are presented to optimize such real-world interconnected networks accordingly.
Collapse
Affiliation(s)
- Fei Tan
- Department of Information Science and Electronic Engineering, Zhejiang University, Hangzhou 310027, People's Republic of China and Department of Electronic and Information Engineering, The Hong Kong Polytechnic University, Kowloon, Hong Kong
| | - Jiajing Wu
- Department of Electronic and Information Engineering, The Hong Kong Polytechnic University, Kowloon, Hong Kong
| | - Yongxiang Xia
- Department of Information Science and Electronic Engineering, Zhejiang University, Hangzhou 310027, People's Republic of China
| | - Chi K Tse
- Department of Electronic and Information Engineering, The Hong Kong Polytechnic University, Kowloon, Hong Kong
| |
Collapse
|
13
|
Lee ZQ, Hsu WJ, Lin M. Estimating mean first passage time of biased random walks with short relaxation time on complex networks. PLoS One 2014; 9:e93348. [PMID: 24699325 PMCID: PMC3974760 DOI: 10.1371/journal.pone.0093348] [Citation(s) in RCA: 7] [Impact Index Per Article: 0.7] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/11/2013] [Accepted: 03/03/2014] [Indexed: 11/29/2022] Open
Abstract
Biased random walk has been studied extensively over the past decade especially in the transport and communication networks communities. The mean first passage time (MFPT) of a biased random walk is an important performance indicator in those domains. While the fundamental matrix approach gives precise solution to MFPT, the computation is expensive and the solution lacks interpretability. Other approaches based on the Mean Field Theory relate MFPT to the node degree alone. However, nodes with the same degree may have very different local weight distribution, which may result in vastly different MFPT. We derive an approximate bound to the MFPT of biased random walk with short relaxation time on complex network where the biases are controlled by arbitrarily assigned node weights. We show that the MFPT of a node in this general case is closely related to not only its node degree, but also its local weight distribution. The MFPTs obtained from computer simulations also agree with the new theoretical analysis. Our result enables fast estimation of MFPT, which is useful especially to differentiate between nodes that have very different local node weight distribution even though they share the same node degrees.
Collapse
Affiliation(s)
- Zhuo Qi Lee
- School of Computer Engineering, Nanyang Technological University, Singapore
| | - Wen-Jing Hsu
- School of Computer Engineering, Nanyang Technological University, Singapore
| | - Miao Lin
- School of Computer Engineering, Nanyang Technological University, Singapore
- * E-mail:
| |
Collapse
|
14
|
Dynamic source routing strategy for two-level flows on scale-free networks. PLoS One 2013; 8:e82162. [PMID: 24349207 PMCID: PMC3861365 DOI: 10.1371/journal.pone.0082162] [Citation(s) in RCA: 12] [Impact Index Per Article: 1.1] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 04/27/2013] [Accepted: 10/21/2013] [Indexed: 11/23/2022] Open
Abstract
Packets transmitting in real communication networks such as the Internet can be classified as time-sensitive or time-insensitive. To better support the real-time and time-insensitive applications, we propose a two-level flow traffic model in which packets are labeled as level-1 or level-2, and those with level-1 have higher priority to be transmitted. In order to enhance the traffic capacity of the two-level flow traffic model, we expand the global dynamic routing strategy and propose a new dynamic source routing which supports no routing-flaps, high traffic capacity, and diverse traffic flows. As shown in this paper, the proposed dynamic source routing can significantly enhance the traffic capacity and quality of time-sensitive applications compared with the global shortest path routing strategy.
Collapse
|
15
|
Bastas N, Maragakis M, Argyrakis P, ben-Avraham D, Havlin S, Carmi S. Random walk with priorities in communicationlike networks. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2013; 88:022803. [PMID: 24032879 DOI: 10.1103/physreve.88.022803] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 02/05/2013] [Revised: 06/20/2013] [Indexed: 06/02/2023]
Abstract
We study a model for a random walk of two classes of particles (A and B). Where both species are present in the same site, the motion of A's takes precedence over that of B's. The model was originally proposed and analyzed in Maragakis et al. [Phys. Rev. E 77, 020103(R) (2008)]; here we provide additional results. We solve analytically the diffusion coefficients of the two species in lattices for a number of protocols. In networks, we find that the probability of a B particle to be free decreases exponentially with the node degree. In scale-free networks, this leads to localization of the B's at the hubs and arrest of their motion. To remedy this, we investigate several strategies to avoid trapping of the B's, including moving an A instead of the hindered B, allowing a trapped B to hop with a small probability, biased walk toward non-hub nodes, and limiting the capacity of nodes. We obtain analytic results for lattices and networks, and we discuss the advantages and shortcomings of the possible strategies.
Collapse
Affiliation(s)
- Nikolaos Bastas
- Department of Physics, University of Thessaloniki, 54124 Thessaloniki, Greece
| | | | | | | | | | | |
Collapse
|
16
|
Rachadi A, Jedra M, Zahid N. Self avoiding paths routing algorithm in scale-free networks. CHAOS (WOODBURY, N.Y.) 2013; 23:013114. [PMID: 23556951 DOI: 10.1063/1.4790864] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.1] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 06/02/2023]
Abstract
In this paper, we present a new routing algorithm called "the self avoiding paths routing algorithm." Its application to traffic flow in scale-free networks shows a great improvement over the so called "efficient routing" protocol while at the same time maintaining a relatively low average packet travel time. It has the advantage of minimizing path overlapping throughout the network in a self consistent manner with a relatively small number of iterations by maintaining an equilibrated path distribution especially among the hubs. This results in a significant shifting of the critical packet generation rate over which traffic congestion occurs, thus permitting the network to sustain more information packets in the free flow state. The performance of the algorithm is discussed both on a Barábasi-Albert network and real autonomous system network data.
Collapse
Affiliation(s)
- Abdeljalil Rachadi
- Laboratoire Conception et Systèmes (Micoélectronique et Informatique), Faculté des Sciences, Université Mohammed V, Agdal, Avenue Ibn Batouta, B.P. 1014, Rabat 10000, Morocco.
| | | | | |
Collapse
|
17
|
Yang HX, Wang WX, Lai YC. Traffic-driven epidemic outbreak on complex networks: how long does it take? CHAOS (WOODBURY, N.Y.) 2012; 22:043146. [PMID: 23278081 PMCID: PMC7112479 DOI: 10.1063/1.4772967] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.1] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 08/13/2012] [Accepted: 12/04/2012] [Indexed: 05/31/2023]
Abstract
Recent studies have suggested the necessity to incorporate traffic dynamics into the process of epidemic spreading on complex networks, as the former provides support for the latter in many real-world situations. While there are results on the asymptotic scope of the spreading dynamics, the issue of how fast an epidemic outbreak can occur remains outstanding. We observe numerically that the density of the infected nodes exhibits an exponential increase with time initially, rendering definable a characteristic time for the outbreak. We then derive a formula for scale-free networks, which relates this time to parameters characterizing the traffic dynamics and the network structure such as packet-generation rate and betweenness distribution. The validity of the formula is tested numerically. Our study indicates that increasing the average degree and/or inducing traffic congestion can slow down the spreading process significantly.
Collapse
Affiliation(s)
- Han-Xin Yang
- Department of Physics, Fuzhou University, Fuzhou 350108, China
| | | | | |
Collapse
|
18
|
Barankai N, Fekete A, Vattay G. Effect of network structure on phase transitions in queuing networks. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2012; 86:066111. [PMID: 23368008 DOI: 10.1103/physreve.86.066111] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 09/13/2012] [Indexed: 06/01/2023]
Abstract
Recently, De Martino et al. [J. Stat. Mech. (2009) P08023; Phys. Rev. E 79, 015101 (2009)] have presented a general framework for the study of transportation phenomena on random networks with annealed disorder. One of their most significant achievements was a deeper understanding of the phase transition from the uncongested to the congested phase at a critical traffic load on uncorrelated networks. In this paper, we also study phase transition in transportation networks using a discrete time random walk model. Our aim is to establish a direct connection between the structure of an uncorrelated random graph with quenched disorder and the value of the critical traffic load. We show that if the network is dense, the quenched and annealed formulas for the critical loading probability coincide. For sparse graphs, higher-order corrections, related to the local structure of the network, appear.
Collapse
Affiliation(s)
- Norbert Barankai
- Department of the Physics of Complex Systems, Eötvös University, Pázmány Péter Sétány 1/A, H-1117 Budapest, Hungary
| | | | | |
Collapse
|
19
|
Gavalda A, Duch J, Gómez-Gardeñes J. Reciprocal interactions out of congestion-free adaptive networks. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2012; 85:026112. [PMID: 22463284 DOI: 10.1103/physreve.85.026112] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.1] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 11/01/2011] [Indexed: 05/31/2023]
Abstract
In this paper we study the jamming transition in complex adaptive networks. We introduce an adaptation mechanism that modifies the weight of the communication channels in order to delay the congestion onset. Adaptivity takes place locally as it is driven by each node of the network. Surprisingly, regardless of the structural properties of the backbone topology, e.g., its degree distribution, the adaptive network can reach optimal functioning provided it allows a reciprocal distribution of the weights. Under this condition, the optimal functioning is achieved through an extensive network reshaping ending up in a highly reciprocal weighted network whose critical onset of congestion is delayed up to its maximum possible value. We also show that, for a given network, the reciprocal weighting obtained from adaptation produce optimal static configurations.
Collapse
Affiliation(s)
- Arnau Gavalda
- Departament d'Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili, ES-43007 Tarragona, Spain
| | | | | |
Collapse
|
20
|
Tang M, Zhou T. Efficient routing strategies in scale-free networks with limited bandwidth. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2011; 84:026116. [PMID: 21929073 DOI: 10.1103/physreve.84.026116] [Citation(s) in RCA: 5] [Impact Index Per Article: 0.4] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 04/30/2010] [Revised: 03/10/2011] [Indexed: 05/31/2023]
Abstract
We study the traffic dynamics in complex networks where each link is assigned a limited and identical bandwidth. Although the first-in-first-out (FIFO) queuing rule is widely applied in the routing protocol of information packets, here we argue that if we drop this rule, the overall throughput of the network can be remarkably enhanced. We propose some efficient routing strategies that do not strictly obey the FIFO rule. Compared to the routine shortest-path strategy, throughput for both Barabási-Albert (BA) networks and the Internet can be improved by a factor of more than five. We calculate the theoretical limitation of the throughput. In BA networks, our proposed strategy can achieve 88% of the theoretical optimum, yet for the Internet, it is about 12%, implying that we still have a huge space to further improve the routing strategy for the Internet. Finally, we discuss possibly promising ways to design more efficient routing strategies for the Internet.
Collapse
Affiliation(s)
- Ming Tang
- Web Sciences Center, University of Electronic Science and Technology of China, Chengdu 610054, People's Republic of China.
| | | |
Collapse
|
21
|
Meloni S, Gómez-Gardeñes J. Local empathy provides global minimization of congestion in communication networks. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2010; 82:056105. [PMID: 21230543 DOI: 10.1103/physreve.82.056105] [Citation(s) in RCA: 2] [Impact Index Per Article: 0.1] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 08/06/2010] [Revised: 10/04/2010] [Indexed: 05/30/2023]
Abstract
We present a mechanism to avoid congestion in complex networks based on a local knowledge of traffic conditions and the ability of routers to self-coordinate their dynamical behavior. In particular, routers make use of local information about traffic conditions to either reject or accept information packets from their neighbors. We show that when nodes are only aware of their own congestion state they self-organize into a hierarchical configuration that delays remarkably the onset of congestion although leading to a sharp first-order-like congestion transition. We also consider the case when nodes are aware of the congestion state of their neighbors. In this case, we show that empathy between nodes is strongly beneficial to the overall performance of the system and it is possible to achieve larger values for the critical load together with a smooth, second-order-like, transition. Finally, we show how local empathy minimize the impact of congestion as much as global minimization. Therefore, here we present an outstanding example of how local dynamical rules can optimize the system's functioning up to the levels reached using global knowledge.
Collapse
Affiliation(s)
- Sandro Meloni
- Dipartimento di Informatica e Automazione, Universitá degli studi Roma Tre, Via della Vasca Navale, 79 00146 Roma, Italy
| | | |
Collapse
|