Transport Efficiency for Networks Obtained by Vertex Merging Operation
Zhenhua Yuan, Junhao Peng, Long Gao · 2025
Read Transport Efficiency for Networks Obtained by Vertex Merging Operation by Zhenhua Yuan, Junhao Peng, Long Gao (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-20224.txt.
Introduction
Zhenhua Yuan, Junhao Peng, and Long Gao study how well merged networks move things from place to place, in a 2025 paper. Their networks form when several graphs are joined through a single shared node. Transport matters in many real systems, from data to travel. The authors ask how the joined shape affects search and spread.
They study random walks on the joined networks. Three measures track how long a walk takes to first reach a target. The authors derive exact formulas for all three. Each measure turns out to depend on the same traits of the parts that were joined. They also give a method to pick the joining node and tune links for faster transport.
Catalog record
| CREATOR | Zhenhua Yuan, Junhao Peng, Long Gao |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 58 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-20224
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Transport Efficiency for Networks Obtained by Vertex Merging Operation Zhenhua Yuan, Junhao Peng, Long Gao Abstract Transport is an important function of networks. Studying transport efficiency sheds light on the dynamic processes occurring within various underlying structures and offers a wide range of applications. To construct networks with different transport efficiencies, we focus on the networks obtained by vertex merging operation, which involves connecting multiple graphs through a single node. In this paper, we examine unbiased random walks on these networks and analyze their first-passage properties, including the mean first-passage time (MFPT), the mean trapping time (MTT), and the global-mean first-passage time (GFPT), which characterizes the transport (search) efficiency within the networks. We rigorously derive close-form solutions for these quantities. Results show that all these quantities are governed by the first-passage properties of the constituent components. Additionally, we propose a general method for optimizing the transport (search) efficiency by selecting a suitable node and adjusting the growth of the number of nodes in the subgraphs. We validate our findings using lollipop and barbell graphs. Our results indicate that for an arbitrary GFPT scaling exponent α ∈ [ 1 , 3 ] \alpha\in[1,3] , we can construct a network with GFPT scales with the network size N N as GFPT ∼ N α \text{GFPT}\sim N^{\alpha} through vertex merging operation. These conclusions provide valuable insights for designing and optimizing network structures. I Introduction Transport of information, energy, and mass is a vital function in many networked systems [ 1 , 2 , 3 , 4 ] . Studying transport problems across various networks helps to characterize and elucidate numerous dynamic processes within these systems and has a wide range of applications in disciplines such as biology, sociology, computer science, and physics [ 5 , 6 , 7 ] . Examples include information delivery in mobile ad-hoc networks [ 8 , 9 ] , disease transmission or rumor spreading in social networks [ 10 , 11 , 12 , 13 , 14 ] , intracellular transport of proteins and other molecular products [ 15 , 16 ] , energy transfer and animal foraging in food webs [ 17 , 18 ] , and data collection in sensor networks [ 19 , 20 ] . Global mean first-passage time (GFPT), also known as Kemeny’s constant [ 21 , 22 , 23 , 24 , 25 , 26 ] , is a crucial indicator of the information transport efficiency and the stochastic search efficiency of particles within the network. It is defined as the time required for a particle to move randomly to an absorbing node, with both the starting node of the particle and the location of the absorbing node being randomly selected. Previous studies have shown that the GFPT is closely linked to the underlying structure of the network [ 27 , 28 , 29 , 30 , 31 , 32 ] . To further explore the impact of network structure on the GFPT, considerable research has focused on analyzing the scaling behavior of the GFPT with network size N in classical symmetry random walks across different network structures. For instance, in extended pseudo-fractal scale-free networks, Apollonian networks, and complete graphs, the GFPT exhibits the smallest scaling behavior, i.e., \text{GFPT}\sim N [ 33 , 34 , 35 ] ; in recursive small-world trees and Cayley trees, the GFPT scaling is \text{GFPT}\sim N\log(N) [ 36 , 37 ] ; in comb graphs, \text{GFPT}\sim N^{\frac{3}{2}} [ 38 ] ; in tree-like fractals, GFPT grows superlinearly with network size as \text{GFPT}\sim N^{\alpha} , where 1<\alpha<2 [ 39 , 40 , 41 ] ; in linear chains, GFPT grows quadratically with network size, i.e., \text{GFPT}\sim N^{2} [ 30 ] ; and in barbell graphs, \text{GFPT}\sim N^{3} [ 42 , 30 , 43 ] . The exponent in the scaling of GFPT with network size reflects the transport (search) efficiency in a network. The smaller the GFPT scaling exponent, the more efficient the information transport (search) within the network. For a general network with \text{GFPT}\sim N^{\alpha} , its GFPT scaling exponent \alpha is bounded by 1\leq\alpha\leq 3 [ 34 , 44 ] . According to this measure of transport (search) efficiency, extended pseudo-fractal scale-free networks, Apollonian networks, and complete graphs exhibit the highest transport efficiency, whereas barbell graphs display the lowest transport efficiency. Additionally, several studies have focused on enhancing and optimizing transport (search) efficiency by modifying the random walk strategies of particles. Research has shown that incorporating a stochastic resetting strategy into the classical symmetric random walk, where the particles have a certain probability of returning to the starting node at each step, can effectively improve transport efficiency when the resetting rate is appropriately chosen [ 45 , 46 , 47 , 48 ] . Employing a biased random walk strategy by assigning weights to each edge in the network has also demonstrated improved transport efficiency [ 49 , 50 , 51 , 52 ] . Moreover, maximal-entropy random walks have proven effective in enhancing transport efficiency in certain network configurations [ 53 , 54 ] . However, few studies address how to construct networks with diverse transport efficiencies or arbitrary GFPT scaling exponents from existing structures. Developing such networks could help in designing not only efficient wireless networks and radar antennas but also polymers and noncrystalline solids with predetermined diffusion properties and transport efficiencies. In this paper, we explore the network obtained by vertex merging operation, which involves joining n graphs \mathcal{G}_{1},\mathcal{G}_{2},...,\mathcal{G}_{n} through a single node C . Our objective is to construct networks with distinct transport efficiencies and to enable control over the overall transport efficiency. We analyze the first-passage properties of unbiased random walk on this class of networks, focusing on key indicators such as mean first-passage time (MFPT), mean trapping time (MTT), and GFPT. By employing probabilistic methods, we derive analytic solutions for these quantities. Our results demonstrate that all these quantities are determined by the first-passage property of the individual graphs \mathcal{G}_{1},\mathcal{G}_{2},...,\mathcal{G}_{n} . Furthermore, we propose adjusting the position of node C and controlling the growth of the total number of nodes in graphs \mathcal{G}_{1},\mathcal{G}_{2},...,\mathcal{G}_{n} to optimize and enhance overall transport efficiency. Lollipop graphs and barbell graphs serve as examples to validate our findings. Finally, we introduce a method for constructing networks with arbitrary GFPT scaling exponent \alpha\in[1,3] . The conclusions obtained here contribute to the advancement of network construction and the optimization of network structures. The remainder of this paper is organized as follows. Sec. II introduces the vertex merging operation and discusses the quantities analyzed in the transport (search) problem, including the mean first-passage time (MFPT), the mean trapping time (MTT), and the GFPT. Sec. III analyzes the MFPT between any starting and absorbing nodes, where the starting and absorbing nodes differ. Furthermore, Sec. IV investigates the MTT for any given absorbing node. Sec. V presents the exact results for the GFPT of the overall structure. Sec. VI presents a general method for controlling transport (search) efficiency and provides two illustrative examples. Finally, Sec. VII summarizes the findings of this paper. II Preliminaries II-A Vertex Merging Operation To begin, we need to prepare n (n\geq 2) simple connected graphs \mathcal{G}_{1},\mathcal{G}_{2},...,\mathcal{G}_{n} . Let V_{\mathcal{G}_{i}} (i=1,2,...,n) be the set of nodes of