Exactly solvable scale-free network model

Abstract

We study a deterministic scale-free network recently proposed by Barabási, Ravasz and Vicsek. We find that there are two types of nodes: the hub and rim nodes, which form a bipartite structure of the network. We first derive the exact numbers $P(k)$ of nodes with degree $k$ for the hub and rim nodes in each generation of the network, respectively. Using this, we obtain the exact exponents of the distribution function $P(k)$ of nodes with $k$ degree in the asymptotic limit of $k\to \infty$. We show that the degree distribution for the hub nodes exhibits the scale-free nature, $P(k)\propto k^{-\gamma }$ with $\gamma =\ln 3/\ln 2=1.584962$, while the degree distribution for the rim nodes is given by $P(k)\propto e^{-{\gamma }^{\prime }k}$ with ${\gamma }^{\prime }=\ln (3/2)=0.405465$. Second, we numerically as well as analytically calculate the spectra of the adjacency matrix $A$ for representing topology of the network. We also analytically obtain the exact number of degeneracy at each eigenvalue in the network. The density of states (i.e., the distribution function of eigenvalues) exhibits the fractal nature with respect to the degeneracy. Third, we study the mathematical structure of the determinant of the eigenequation for the adjacency matrix. Fourth, we study hidden symmetry, zero modes and its index theorem in the deterministic scale-free network. Finally, we study the nature of the maximum eigenvalue in the spectrum of the deterministic scale-free network. We will prove several theorems for it, using some mathematical theorems. Thus, we show that most of all important quantities in the network theory can be analytically obtained in the deterministic scale-free network model of Barabási, Ravasz and Vicsek. Therefore, we may call this network model the exactly solvable scale-free network.

18 pages, 5 figures

References in corpus (25)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• Error and attack tolerance of complex networks
• The diameter of the world wide web
• Random graphs with arbitrary degree distributions and their applications
• Classes of behavior of small-world networks
• Network robustness and fragility: Percolation on random graphs
• Hierarchical Organization in Complex Networks
• Structure of Growing Networks: Exact Solution of the Barabasi--Albert's Model
• Topology of evolving networks: local events and universality
• Connectivity of Growing Random Networks
• Bose-Einstein condensation in complex networks
• Fast Response and Temporal Coding on Coherent Oscillations in Small-World Networks
• Spectra of "Real-World" Graphs: Beyond the Semi-Circle Law
• Deterministic Scale-Free Networks
• Mean-field solution of the small-world network model
• Degree Distributions of Growing Networks
• Small-world networks: Evidence for a crossover picture
• Spectra of complex networks
• Scaling Behaviour of Developing and Decaying Networks
• Spectra and eigenvectors of scale-free networks
• Statistical ensemble of scale-free random graphs
• World-Wide Web scaling exponent from Simon's 1955 model
• Erratum: Small-world networks: Evidence for a crossover picture
• Preferencial growth: exact solution of the time dependent distributions

Cited by in corpus (24)

• A deterministic small-world network created by edge iterations
• Multi-node basin stability in complex dynamical networks
• Coherence in scale-free networks of chaotic maps
• Random Walks on deterministic Scale-Free networks: Exact results
• Exact calculations of first-passage quantities on recursive networks
• High Dimensional Apollonian Networks
• Evolving Apollonian Networks with Small-world Scale-free topologies
• A general geometric growth model for pseudofractal scale-free web
• Analyses of Some Structural Properties on a Class of Hierarchical Scale-free Networks
• Effective target arrangement in a deterministic scale-free graph
• Evolving small-world networks with geographical attachment preference
• Random walks in modular scale-free networks with multiple traps
• Average distance in a hierarchical scale-free network: an exact solution
• Deterministic weighted scale-free small-world networks
• Recovery time after localized perturbations in complex dynamical networks
• 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
• Deterministic scale-free networks created in a recursive manner
• Spectral properties of disordered fully-connected graphs
• Analytical controllability of deterministic scale-free networks and Cayley trees
• Hierarchical deposition and scale-free networks: a visibility algorithm approach
• Minimum leader selection for Structural Controllability of Undirected Graphs with Leader-follower Framework
• Structure Properties of Koch Networks Based on Networks Dynamical Systems