Scaling phenomena have been intensively studied during the past decade in the context of complex networks. As part of these works, recently novel methods have appeared to measure the dimension of abstract and spatially embedded networks. In this paper we propose a new dimension measurement method for networks, which does not require global knowledge on the embedding of the nodes, instead it exploits link-wise information (link lengths, link delays or other physical quantities). Our method can be regarded as a generalization of the spectral dimension, that grasps the network’s large-scale structure through local observations made by a random walker while traversing the links. We apply the presented method to synthetic and real-world networks, including road maps, the Internet infrastructure and the Gowalla geosocial network. We analyze the theoretically and empirically designated case when the length distribution of the links has the form P(ρ)∼1 ρ. We show that while previous dimension concepts are not applicable in this case, the new dimension measure still exhibits scaling with two distinct scaling regimes. Our observations suggest that the link length distribution is not sufficient in itself to entirely control the dimensionality of complex networks, and we show that the proposed measure provides information that complements other known measures.
In the last several years, a number of methods have appeared in the literature that were successful in identifying scale-invariant properties in small-world complex networks. Probably, the earliest such concept is the @cite_11 which originates from random walks on the network (see sec_method ), and was applied to both theoretical models of networks @cite_1 and empirical datasets spectral2 . Additionally, the application of the box-counting dimension @cite_43 to networks was also proposed @cite_0 , and further generalized to reveal fractal properties of complex networks @cite_16 @cite_41 . The scaling exponents arising from these methods are usually interpreted as a special type of network dimension.
@cite_41 @cite_1 @cite_0 @cite_43 @cite_16 @cite_11
2140948827 2032332507 1504623951 1978345999
The fractal and the small-world properties of complex networks are systematically studied both in the box-covering (BC) and the cluster-growing (CG) measurements. We elucidate that complex networks possessing the fractal (small-world) nature in the BC measurement are always fractal (small world) even in the CG measurement and vice versa, while the fractal dimensions d B by the BC measurement and d C by the CG measurement are generally different. This implies that two structural properties of networks, fractality and small worldness, cannot coexist in the same length scale. These properties can, however, crossover from one to the other by varying the length scale. We show that the crossover behavior in a network near the percolation transition appears both in the BC and CG measurements and is scaled by a unique characteristic length ξ. In this paper we study the small-world network model of Watts and Strogatz, which mimics some aspects of the structure of networks of social interactions. We argue that there is one non-trivial length-scale in the model, analogous to the correlation length in other systems, which is well-defined in the limit of infinite system size and which diverges continuously as the randomness in the network tends to zero, giving a normal critical point in this limit. This length-scale governs the cross-over from large- to small-world behavior in the model, as well as the number of vertices in a neighborhood of given radius on the network. We derive the value of the single critical exponent controlling behavior in the critical region and the finite size scaling form for the average vertex-vertex distance on the network, and, using series expansion and Pade approximants, find an approximate analytic form for the scaling function. We calculate the effective dimension of small-world graphs and show that this dimension varies as a function of the length-scale on which it is measured, in a manner reminiscent of multifractals. We also study the problem of site percolation on small-world networks as a simple model of disease propagation, and derive an approximate expression for the percolation probability at which a giant component of connected vertices first forms (in epidemiological terms, the point at which an epidemic occurs). The typical cluster radius satisfies the expected finite size scaling form with a cluster size exponent close to that for a random graph. All our analytic results are confirmed by extensive numerical simulations of the model. Appears in Phys. Rev. E 60, 7332-7342 (1999). The spectral dimension has been widely used to understand transport properties on regular and fractal lattices. Nevertheless, it has been little studied for complex networks such as scale-free and small world networks. Here we study the spectral dimension and the return-to-origin probability of random walks on hierarchical scale-free networks, which can be either fractals or non-fractals depending on the weight of shortcuts. Applying the renormalization group (RG) approach to the Gaussian model, we obtain the spectral dimension exactly. While the spectral dimension varies between @math and @math for the fractal case, it remains at @math , independent of the variation of network structure for the non-fractal case. The crossover behavior between the two cases is studied through the RG flow analysis. The analytic results are confirmed by simulation results and their implications for the architecture of complex systems are discussed. The spectral densities of the weighted Laplacian, random walk, and weighted adjacency matrices associated with a random complex network are studied using the replica method. The link weights are parametrized by a weight exponent β. Explicit results are obtained for scale-free networks in the limit of large mean degree after the thermodynamic limit, for arbitrary degree exponent and β.