Real-world Networks and Random Graph Models

• Applicant: Professor Dr. Konstantinos Panagiotou
• Subject Area: Theoretical Computer Science
• Term: from 2012 to 2015
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 226031825

• Final Report Year: 2016

Final Report Abstract

A significant proportion of the current literature is devoted to experimental studies of various proposed models for real-life networks, and there has been only partial and by far not exhaustive rigorous mathematical work in the field. Although the experiments contribute significantly to our understanding of the typical properties of the models, it also often happens that predictions cannot be made or are incorrect. A rigorous treatment may also unravel unknown types of network characteristics, thus supporting the development of new networks and algorithms, or supporting us at improving the quality of existing ones. The aim of this research project was, based on and extending previous work by the author and related work of the research community and by developing new methods, twofold. First, to develop adequate methods, tools, and models that are suitable for the (rigorous) study of large-scale real-world networks. Among other things, Hyperbolic Random Graphs were considered. Previous to the work that was performed within this project, there was no theoretical fundament to conduct research on this topic. We succeeded in developing the underlying theory significantly, and proving several structural results about these graphs, including the degree distribution, subgraph counts, and compressibility. Moreover, new models (as the directed inhomogeneous random graphs) were developed and models where global constraints (“subcritical graphs”) on the structure are imposed were studied. Second, several algorithmic questions on such graphs, as the problems information/infection spreading, and also vulnerability issues, like robustness to random or malicious damage, were considered. This revealed grobal characteristics of the networks that promote or hinder the dissemination of information; this is valuable information that may guide the design of future networks with respect to their resilience to contagion effects.

Publications

• Random Hyperbolic Graphs: Degree Sequence and Clustering. Proceedings of the 39th Int. Colloquium on Automata, Languages and Programming (ICALP ’12), 573–585, 2012
  L. Gugelmann, K. Panagiotou and U. Peter
  
• Randomized Rumor Spreading: the Effect of the Network Topology. Combinatorics, Probability and Computing, 24(2): 457– 479, 2015
  K. Panagiotou, X. Perez-Gimenez, T. Sauerwald and H. Sun
  
• Scaling Limits for Random Graphs from Subcritical Classes. 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC ’15), DMTCS proceedings, 745-756, 2015
  K. Panagiotou, B. Stufler and K. Weller
  
• Asynchronous Rumor Spreading on Random Graphs. Proceedings of the 24th International Symposium on Algorithms and Computation, 424–434, 2013 und Algorithmica, 2016
  K. Panagiotou and L. Speidel
  
• Efficient Sampling Methods for Discrete Distribution. Proceedings of the 39th Int. Colloquium on Automata, Languages and Programming (ICALP ’12), 133–144, 2012 und Algorithmica, 2016
  K. Bringmann and K. Panagiotou
  
• Bootstrap percolation in directed and inhomogeneous random graphs. 2017
  N. Detering, T. Meyer-Brandis and K. Panagiotou