Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Friedrich, Tobias http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-65106
URL:

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

pdf-format:


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
Seminar: 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Issue date: 2016
Date of publication: 2016


DROPS-Home | Fulltext Search | Imprint Published by LZI