Dependence of the average to-node distance on the node degree for random graphs and growing networks

In a connected graph, nodes can be characterised locally (with their degree k) or globally (e.g. with their average length path to other nodes). Here we investigate how depends on k. The numerical algorithm based on the construction of the distance matrix is applied to random graphs and the growing networks: the scale-free ones and the exponential ones. The results are relevant for search strategies in different networks.Received: 15 June 2004, Published online: 21 October 2004PACS: 02.10.Ox Combinatorics; graph theory - 05.10.-a Computational methods in statistical physics and nonlinear dynamics