License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2016.4
URN: urn:nbn:de:0030-drops-65106
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6510/
Go to the corresponding LIPIcs Volume Portal

Friedrich, Tobias

Scale-Free Networks, Hyperbolic Geometry, and Efficient Algorithms (Invited Talk)

pdf-format:
LIPIcs-MFCS-2016-4.pdf (0.2 MB)

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.

BibTeX - Entry

@InProceedings{friedrich:LIPIcs:2016:6510,
  author =	{Tobias Friedrich},
  title =	{{Scale-Free Networks, Hyperbolic Geometry, and Efficient Algorithms (Invited Talk)}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{4:1--4:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6510},
  URN =		{urn:nbn:de:0030-drops-65106},
  doi =		{10.4230/LIPIcs.MFCS.2016.4},
  annote =	{Keywords: power-law graphs, scale-free graphs, random graphs, distributed algorithms}
}

Keywords: power-law graphs, scale-free graphs, random graphs, distributed algorithms
Collection: 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Issue Date: 2016
Date of publication: 19.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI