Pathlength scaling in graphs with incomplete navigational information
arXiv:1106.2610 · doi:10.1016/j.physa.2011.06.021
Abstract
The graph-navigability problem concerns how one can find as short paths as possible between a pair of vertices, given an incomplete picture of a graph. We study the navigability of graphs where the vertices are tagged by a number (between 1 and the total number of vertices) in a way to aid navigation. This information is too little to ensure errorfree navigation but enough, as we will show, for the agents to do significantly better than a random walk. In our setup, given a graph, we first assign information to the vertices that agents can utilize for their navigation. To evaluate the navigation, we calculate the average distance traveled over random pairs of source and target and different graph realizations. We show that this type of embedding can be made quite efficiently; the more information is embedded, the more efficient it gets. We also investigate the embedded navigational information in a standard graph layout algorithm and find that although this information does not make algorithms as efficient as the above-mentioned schemes, it is significantly helpful.
arXiv comment14 pages, 5 figures
References in corpus (17)
- Emergence of scaling in random networks
- Random graphs with arbitrary degree distributions and their applications
- Search in Power-Law Networks
- Growing Scale-Free Networks with Tunable Clustering
- Scale-Free Networks are Ultrasmall
- Navigability of Complex Networks
- Betweenness centrality correlation in social networks
- The Price of Anarchy in Transportation Networks: Efficiency and Optimality Control
- The entropy of network ensembles
- Traceroute sampling makes random graphs appear to have power law degree distributions
- Accuracy and Scaling Phenomena in Internet Mapping
- Searchability of Networks
- Hide and seek on complex networks
- Navigating Networks with Limited Information
- Navigating ultrasmall worlds in ultrashort time
- On the Tomography of Networks and Multicast Trees
- Random Walks on Complex Networks