Entropy Rate of Diffusion Processes on Complex Networks

Add to your list(s) Download to your calendar using vCal

• Vito Latora (Universita' di Catania, Italy)
• Thursday 07 August 2008, 14:00-15:00
• FW26, Computer Laboratory, William Gates Builiding.

If you have a question about this talk, please contact Eiko Yoneki.

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

This talk is part of the Computer Laboratory Systems Research Group Seminar series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• CL's SRG seminar
• Cambridge Centre for Data-Driven Discovery (C2D3)
• Cambridge talks
• Chris Davis' list
• Computer Laboratory Systems Research Group Seminar
• Department of Computer Science and Technology talks and seminars
• FW26, Computer Laboratory, William Gates Builiding
• Interested Talks
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• ndk22's list
• ob366-ai4er
• rp587

Note that ex-directory lists are not shown.