Structural sparseness and complex networks

Reidl, Felix; Rossmanith, Peter; Nešetril, Jarik

doi:34392

Structural sparseness and complex networks = Strukturelle Dünnheit und Komplexe Netzwerke

Reidl, Felix

2016

Verantwortlichkeitsangabevorgelegt von Felix Jon Reidl

ImpressumAachen : Publikationsserver der RWTH Aachen University 2016

Aachen, Techn. Hochsch., Diss., 2015

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University 2016

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Rossmanith, Peter (Thesis advisor) ; Nešetril, Jarik (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2015-12-04

Online
URN: urn:nbn:de:hbz:82-rwth-2015-075649
URL: https://publications.rwth-aachen.de/record/565064/files/565064.pdf
URL: https://publications.rwth-aachen.de/record/565064/files/565064.pdf?subformat=pdfa

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
Informatik (frei) ; structural sparseness (frei) ; complex networks (frei) ; bounded expansion (frei) ; nowhere dense (frei) ; shallow minor (frei) ; kernelisation (frei) ; meta kernelisation (frei) ; FTP (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
Durch die stetig wachsende Menge an relationalen Daten, die unser tägliches Leben im Informationszeitalter erzeugt, hat sich das Forschungsgebiet der komplexen Netzwerke im letzten Jahrzehnt enorm entwickelt. Obwohl viele strukturelle Gemeinsamkeiten solcher Netzwerke bekannt sind - etwa ihre geringe Dichte, die starke Rechtsschiefe ihrer Gradverteilung oder das small-world Phänomen -, kannte manbisher noch keine Eigenschaft, die auf breiter Front algorithmisch nutzbar ist.Parallel dazu hat das Graph-Minoren-Programm von Robertson undSeymour die Theorie der strukturell dünnen Graphen revolutioniert. Viele Werkzeuge und Techniken, die als ‚Nebenprodukt‘ im Rahmen dieses Programms entwickelt wurden, hatten tiefgreifende Auswirkungen auf die Erforschung von parametrisierten und approximativen Algorithmen. Insbesondere ergmöglichten sie die Entwicklungmehrerer algorithmischer Metatheoreme, also Algorithmen, die ein großes Spektrum von Problemen auf strukturell dünnen Eingaben lösen. Ziel dieser Arbeit ist es, das Forschungsgebiet der strukturell dünnen Graphen und das der komplexen Netzwerke näher zusammenzubringen. Zwei Varianten von struktureller Dünnheit, basierend aufder Dichte von seichten Minoren (shallow minors), stellen sich dabei alsSchlüsselkonzepte heraus: die von Nešetril und Ossona de Mendezin ihrer wegweisende Arbeit zu einer robusten Definition des Dünnheitsbegriffs eingeführten Graphklassen mit beschränkter Expansion (bounded expansion) und Klassen, die nirgends dicht (nowhere dense) sind. Im Folgenden wird zum einen dargelegt, dass diese Klassenstrukturell dünner Graphen es erlauben, effiziente Algorithmen für eine Vielzahl von Problemen zu entwerfen - darunter insbesondereProbleme, die in Teilgebieten der Netzwerkforschung Anwendung finden. Zum anderen wird bewiesen, dass fundamentale Netzwerkmodelle diese strukturellen Eigenschaften innehaben, und empirisch belegt, dass dieser Sachverhalt erfolgreich auf konkrete Netzwerke ausverschiedensten Domänen übertragbar ist. Somit ist die Theorie der strukturell dünnen Graphen - und damitinsbesondere die Vielzahl der von ihr bereitgestellten algorithmischen Werkzeuge - tatsächlich auf komplexe Netzwerke anwendbar. Sowohldie algorithmische Graphentheorie als auch die Netzwerkforschungerhält aus diesem Brückenschlag neuartige Ansätze, Einsichten und Fragestellungen.

The field of complex networks has seen a steady growth in the last decade, fuelled by an ever-growing collection of relational data that ourlife in the information age generates. While several structural commonalities of complex networks have been observed - e.g. low density,heavily skewed degree-distributions, or the small world property - sofar no property has been discovered that is algorithmically exploitableon a broad scale. Concurrently, the theory of structurally sparse graphs has been revolutionised by Robertson and Seymour’s graph minors programme. Many tools and techniques, developed as ‘by-products’ in the programme, have had a tremendous impact on the research of parametrised and approximation algorithms. They in particular enabled thedevelopment of several algorithmic meta-theorems, that is, algorithmsthat work for a large spectrum of problems on sparse inputs.In this thesis, we work towards bringing the field of structural sparsegraphs and the field of complex networks closer together. We identifytwo notions of structural sparseness based on the density of shallowminors as keys for this endeavour: classes of bounded expansion andnowhere dense classes as introduced by Nešetril and Ossona de Mendez in their seminal work on a robust theory of sparseness. In thefollowing, we demonstrate that these sparse classes admit efficient algorithms for a huge number of problems, some of which have applications in domain-specific areas of network science. We further provethat several fundamental network models exhibit these properties anddemonstrate empirically that this also holds true for a selection of real-world networks from various domains. As a result, we can state that the theory of structurally sparse graphsis applicable to complex networks and, as a corollary, so is the richalgorithmic toolkit it provides. This connection offers researchers fromboth the field of algorithmic graph theory and network science newapproaches, insights, and productive questions.

OpenAccess:
PDF PDF (PDFA)
(additional files)