Invited Talk at MFCS 2016
Tobias Friedrich is invited speaker at the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS) in Kraków/Poland. MFCS is one of the oldest conferences for original research in all branches of theoretical computer science. On the second day of the conference Professor Friedrich will talk about "Scale-Free Networks, Hyperbolic Geometry, and Efficient Algorithms".
Abstract: 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 several mathematical models of scale-free networks (e.g. preferential attachment graphs, Chung-Lu graphs, hyperbolic random graphs) and analyze some of their properties (e.g. diameter, average distance, clustering). We then present several algorithms and distributed processes on and for these network models (e.g. rumor spreading, load balancing, de-anonymization, embedding) and discuss a number of open problems. The talk assumes no prior knowledge about scale-free networks, distributed computing or hyperbolic geometry.