Average distance in a hierarchical scale-free network: an exact solution

Abstract

Various real systems simultaneously exhibit scale-free and hierarchical structure. In this paper, we study analytically average distance in a deterministic scale-free network with hierarchical organization. Using a recursive method based on the network construction, we determine explicitly the average distance, obtaining an exact expression for it, which is confirmed by extensive numerical calculations. The obtained rigorous solution shows that the average distance grows logarithmically with the network order (number of nodes in the network). We exhibit the similarity and dissimilarity in average distance between the network under consideration and some previously studied networks, including random networks and other deterministic networks. On the basis of the comparison, we argue that the logarithmic scaling of average distance with network order could be a generic feature of deterministic scale-free networks.

Definitive version published in Journal of Statistical Mechanics

References in corpus (37)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The structure and function of complex networks
• Hierarchical organization of modularity in metabolic networks
• Evolution of networks
• Hierarchical structure and the prediction of missing links in networks
• Hierarchical Organization in Complex Networks
• Growing Scale-Free Networks with Tunable Clustering
• Heterogeneity in oscillator networks: Are smaller worlds easier to synchronize?
• Scale-Free Networks are Ultrasmall
• First-passage times in complex scale-invariant media
• Origins of fractality in the growth of complex networks
• Pseudofractal Scale-free Web
• Deterministic Scale-Free Networks
• Average path length in random networks
• Average path length in uncorrelated random networks with hidden variables
• Fractal and Transfractal Recursive Scale-Free Nets
• A Geometric Fractal Growth Model for Scale Free Networks
• Inverted Berezinskii-Kosterlitz-Thouless Singularity and High-Temperature Algebraic Order in an Ising Model on a Scale-Free Hierarchical-Lattice Small-World Network
• Random Walks on deterministic Scale-Free networks: Exact results
• Maximal planar scale-free Sierpinski networks with small-world effect and power-law strength-degree correlation
• Metric structure of random networks
• Self-similarity, small-world, scale-free scaling, disassortativity, and robustness in hierarchical lattices
• Exact solution of mean geodesic distance for Vicsek fractals
• Universal scaling of distances in complex networks
• Exact scaling properties of a hierarchical network model
• Exact analytical solution of average path length for Apollonian networks
• Evolving small-world scale-free networks consist of cliques
• Griffiths singularities and algebraic order in the exact solution of an Ising model on a fractal modular network
• Exactly solvable scale-free network model
• Average distance in a hierarchical scale-free network: an exact solution
• Degree-dependent intervertex separation in complex networks
• Local-world evolving networks with tunable clustering
• Constrained spin dynamics description of random walks on hierarchical scale-free networks
• Transition from fractal to non-fractal scalings in growing scale-free networks
• Shortest path discovery of complex networks
• Contact graphs of disk packings as a model of spatial planar networks

Cited by in corpus (9)

• Exact calculations of first-passage quantities on recursive networks
• Analyses of Some Structural Properties on a Class of Hierarchical Scale-free Networks
• Mapping Koch curves into scale-free small-world networks
• Effective target arrangement in a deterministic scale-free graph
• Random walks in modular scale-free networks with multiple traps
• Average distance in a hierarchical scale-free network: an exact solution
• Random walks in unweighted and weighted modular scale-free networks with a perfect trap
• Optimal scale-free network with a minimum scaling of transport efficiency for random walks with a perfect trap
• An alternative approach to determining average distance in a class of scale-free modular networks