The colloquium of the DFG Research Training Group "Methods for Discrete Structures" takes place every Monday with lectures held by guests or faculty members. Usually, this lecture gives an introduction to a current research topic or new emerging developments related to the main research fields of the graduate programs. On May 11, 2015 Prof. Tobias Friedrich will talk about "Distributed Processes on Scale-Free Networks".
Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
Room MA 041
Monday, May 11, 2015
14:15 - 15:30
Distributed Processes on Scale-Free Networks
The node degrees of large real-world networks often follow a power-law distribution. Such scale-free networks can be social networks, internet topologies, the web graph, power grids, or many other networks from literally hundreds of domains. The talk will introduce three mathematical models of scale-free networks (preferential attachment graphs, Chung-Lu graphs, hyperbolic random graphs) and analyze some of their properties. We then study three distributed processes and algorithms on these network models (rumor spreading, load balancing, de-anonymization) and present several open problems. The talk assumes no prior knowledge about scale-free networks or distributed computing.