Abstract

In the realm of complex networks the concept of entropy has been used as a measure to characterize properties of the topology, such as the degree distribution of a graph. Alternatively, various authors have studied the entropy associated with ensembles of graphs and provided, via the application of the maximum entropy principle, the best prediction of network properties subject to the constraints imposed by a given set of observations. The main theoretical and empirical interest in the study of complex networks is in understanding the relations between structure and function. Many of the interaction dynamics that takes place in social, biological and technological systems can be analyzed in terms of diffusion processes on top of complex networks, e.g. data search and routing, information and disease spreading. In this talk, we show how to associate an entropy rate to a diffusion process on a graph. In this context, the entropy rate is a quantity more similar to the Kolmogorov-Sinai entropy rate of a dynamical system, than to the entropy of a statistical ensemble, and measures what is, on average, the shortest per step description of the diffusion on the network. Therefore, a high entropy rate indicates a large randomness, or easiness of propagating from one node to another, and can be related to an efficient spreading over the network Differently from the network entropies previously defined, the entropy rate of a diffusion depends both on the dynamical process and on the graph topology. This allows us to use the entropy rate in two different ways: i) to characterize with a single measure various structural properties of real-world networks, and ii) to design optimal diffusion processes which maximize the entropy. As an example of the powerful possibilities of the introduced measure, we study the diffusion of random walkers whose motion is biased on the node degrees. J. Gomez-Gardenes, V. Latora, http://xxx.lanl.gov/abs/0712.0278

Vito Latora: Dipartimento di Fisica, Universita’ di Catania, and INFN Italy

http://www.ct.infn.it/~latora/bio.html