ﻻ يوجد ملخص باللغة العربية
Random scale-free networks are ultrasmall worlds. The average length of the shortest paths in networks of size N scales as lnlnN. Here we show that these ultrasmall worlds can be navigated in ultrashort time. Greedy routing on scale-free networks embedded in metric spaces finds paths with the average length scaling also as lnlnN. Greedy routing uses only local information to navigate a network. Nevertheless, it finds asymptotically the shortest paths, a direct computation of which requires global topology knowledge. Our findings imply that the peculiar structure of complex networks ensures that the lack of global topological awareness has asymptotically no impact on the length of communication paths. These results have important consequences for communication systems such as the Internet, where maintaining knowledge of current topology is a major scalability bottleneck.
We demonstrate that the self-similarity of some scale-free networks with respect to a simple degree-thresholding renormalization scheme finds a natural interpretation in the assumption that network nodes exist in hidden metric spaces. Clustering, i.e
We study navigation with limited information in networks and demonstrate that many real-world networks have a structure which can be described as favoring communication at short distance at the cost of constraining communication at long distance. Thi
We establish a relationship between the Small-World behavior found in complex networks and a family of Random Walks trajectories using, as a linking bridge, a maze iconography. Simple methods to generate mazes using Random Walks are discussed along w
Random geometric graphs consist of randomly distributed nodes (points), with pairs of nodes within a given mutual distance linked. In the usual model the distribution of nodes is uniform on a square, and in the limit of infinitely many nodes and shri
We provide a simple proof that graphs in a general class of self-similar networks have zero percolation threshold. The considered self-similar networks include random scale-free graphs with given expected node degrees and zero clustering, scale-free