Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAverage Path Length in Complex Networks: Patterns and Predictions
124
0
0.0
(
0
)
Authors
Reginald D. Smith
Ask ChatGPT about the research
No Arabic abstract
A simple and accurate relationship is demonstrated that links the average shortest path, nodes, and edges in a complex network. This relationship takes advantage of the concept of link density and shows a large improvement in fitting networks of all scales over the typical random graph model. The relationships herein can allow researchers to better predict the shortest path of networks of almost any size.
rate research
Read More
Various real-life networks exhibit degree correlations and heterogeneous structure, with the latter being characterized by power-law degree distribution $P(k)sim k^{-gamma}$, where the degree exponent $gamma$ describes the extent of heterogeneity. In this paper, we study analytically the average path length (APL) of and random walks (RWs) on a family of deterministic networks, recursive scale-free trees (RSFTs), with negative degree correlations and various $gamma in (2,1+frac{ln 3}{ln 2}]$, with an aim to explore the impacts of structure heterogeneity on APL and RWs. We show that the degree exponent $gamma$ has no effect on APL $d$ of RSFTs: In the full range of $gamma$, $d$ behaves as a logarithmic scaling with the number of network nodes $N$ (i.e. $d sim ln N$), which is in sharp contrast to the well-known double logarithmic scaling ($d sim ln ln N$) previously obtained for uncorrelated scale-free networks with $2 leq gamma <3$. In addition, we present that some scaling efficiency exponents of random walks are reliant on degree exponent $gamma$.
The exact formula for the average path length of Apollonian networks is found. With the help of recursion relations derived from the self-similar structure, we obtain the exact solution of average path length, $bar{d}_t$, for Apollonian networks. In contrast to the well-known numerical result $bar{d}_t propto (ln N_t)^{3/4}$ [Phys. Rev. Lett. textbf{94}, 018702 (2005)], our rigorous solution shows that the average path length grows logarithmically as $bar{d}_t propto ln N_t$ in the infinite limit of network size $N_t$. The extensive numerical calculations completely agree with our closed-form solution.
A bridge in a graph is an edge whose removal disconnects the graph and increases the number of connected components. We calculate the fraction of bridges in a wide range of real-world networks and their randomized counterparts. We find that real networks typically have more bridges than their completely randomized counterparts, but very similar fraction of bridges as their degree-preserving randomizations. We define a new edge centrality measure, called bridgeness, to quantify the importance of a bridge in damaging a network. We find that certain real networks have very large average and variance of bridgeness compared to their degree-preserving randomizations and other real networks. Finally, we offer an analytical framework to calculate the bridge fraction , the average and variance of bridgeness for uncorrelated random networks with arbitrary degree distributions.
In network science complex systems are represented as a mathematical graphs consisting of a set of nodes representing the components and a set of edges representing their interactions. The framework of networks has led to significant advances in the understanding of the structure, formation and function of complex systems. Social and biological processes such as the dynamics of epidemics, the diffusion of information in social media, the interactions between species in ecosystems or the communication between neurons in our brains are all actively studied using dynamical models on complex networks. In all of these systems, the patterns of connections at the individual level play a fundamental role on the global dynamics and finding the most important nodes allows one to better understand and predict their behaviors. An important research effort in network science has therefore been dedicated to the development of methods allowing to find the most important nodes in networks. In this short entry, we describe network centrality measures based on the notions of network traversal they rely on. This entry aims at being an introduction to this extremely vast topic, with many contributions from several fields, and is by no means an exhaustive review of all the literature about network centralities.
Complex networks have acquired a great popularity in recent years, since the graph representation of many natural, social and technological systems is often very helpful to characterize and model their phenomenology. Additionally, the mathematical tools of statistical physics have proven to be particularly suitable for studying and understanding complex networks. Nevertheless, an important obstacle to this theoretical approach is still represented by the difficulties to draw parallelisms between network science and more traditional aspects of statistical physics. In this paper, we explore the relation between complex networks and a well known topic of statistical physics: renormalization. A general method to analyze renormalization flows of complex networks is introduced. The method can be applied to study any suitable renormalization transformation. Finite-size scaling can be performed on computer-generated networks in order to classify them in universality classes. We also present applications of the method on real networks.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
