Structural sparseness and complex networks

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