Evaluating Structure of Complex Networks by Navigation Entropy

Complex networks are extensively studied in various areas such as social networks, biological networks, Internet and WWW. Those networks have many characters such as small-diameter, higher cluster and power-law degree distribution. Small-world is evolved for efficient information transformation and navigation. Thus, navigation is an important functional character of networks. Previous researches mostly focus on understanding the navigability of small-world networks by analyzing the diameter and the routing efficiency. In this paper, we use the navigability to model the basic structural complexity of a network. That is, given a network topology, we need a model to evaluate how complex the topology is. Some network complexity models have been proposed but none of them consider the navigability factor of the network systems. We believe that using the navigability factor to evaluate the network structural complexity is a feasible and reasonable way. We use the adjacent matrix to build a navigation transition matrix and evaluate the randomness of random walks on the transition matrix by defining navigation entropy on it. We use the iteration of the random walk matrix to evaluate the navigability of a network and the complexity of network. That is, the higher the navigation entropy, the higher the randomness of a network. The lower the navigation entropy, the higher the structure of a network. We apply the navigation entropy model on a set of structural and random network topologies to show how the model can show the different complexity of networks.