8th December 2009 midnight Imperial College
Entropy Rate of Diffusion Processes on Complex Networks
Dr. Vito Latora
University of Catania, Italy
- Web page
- https://www8.imperial.ac.uk/content/dav/ad/workspaces/complexityscience/Abstract_Latora.pdf
- Submitter
- Hans Fangohr
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 sub ject 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 di?usion 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 di?usion process on a graph. 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 di?usion on the network. Therefore, a high entropy rate indicates a large randomness, or easiness of prop- agating from one node to another, and can be related to an e?cient spreading over the network. Di?erently from the network entropies previously de?ned, the entropy rate of a di?usion depends both on the dynamical process and on the graph topology. Hence we may use the entropy rate in two di?erent ways: i) to characterize with a single measure various structural properties of real- world networks, and ii) to design optimal di?usion processes which maximize the entropy. An example of the powerful possibilities of the introduced measure is the di?usion of random walkers whose motion is biased on the node degrees.