Generative graph models play an important role in network science. Unlike real-world networks, they are accessible for mathematical analysis and the number of available networks is not limited. The explanatory power of results on generative models, however, heavily depends on how realistic they are. We present a framework that allows for a systematic evaluation of generative network models. It is based on the question whether real-world networks can be distinguished from generated graphs with respect to certain graph parameters.

As a proof of concept, we apply our framework to four popular random graph models (Erdős-Rényi, Barabási-Albert, Chung-Lu, and hyperbolic random graphs). Our experiments for example show that all four models are bad representations for Facebook's social networks, while Chung-Lu and hyperbolic random graphs are good representations for other networks, with different strengths and weaknesses.

We investigate the complexity of hard counting problems that belong to the class #P but have easy decision version; several well-known problems such as #Perfect Matchings, #DNFSat share this property. We focus on classes of such problems which emerged through two disparate approaches: one taken by Hemaspaandra et al. who defined classes of functions that count the size of intervals of ordered strings, and one followed by Kiayias et al. who defined the class TotP, consisting of functions that count the total number of paths of NP computations. We provide inclusion and separation relations between TotP and interval size counting classes, by means of new classes that we define in this work. Our results imply that many known #P-complete problems with easy decision are contained in the classes defined in Hemaspaandra et al.—but are unlikely to be complete for these classes under certain types of reductions. We also define a new class of interval size functions which strictly contains FP and is strictly contained in TotP under reasonable complexity-theoretic assumptions. We show that this new class contains some hard counting problems.

This is joint work with Evangelos Bampas, Aris Pagourtzis, Aris Tentes.

In inductive inference various types of learning have emerged. This presentation aims to introduce a new type of learning, the confident iterative learning. Given a class to be learnt, the idea here is to merge the following two concepts. For confidence, we require the learner to converge on any set, however, it only needs to be correct on sets in the target class. To be iterative, we restrict the learner's memory on previous inputs and calculations to its last hypothesis. The main aim is to motivate and prove a classification theorem.

Additionally, we will introduce and compare different types of confidence, focusing on the learner's behaviour on sets outside of the class. Lastly, we will focus on the possible hypotheses. Introducing learning with respect to hypothesis spaces, we will explain why exact, class preserving and class comprising learning are different.

In this talk I will, first, summarize the problem of glucose-insulin interaction. Then I will briefly present some of my previous work for forecasting blood glucose levels using Grammatical Evolution and Estimation Distribution Algorithms. And finally, I will discuss about the ideas that I would like to develop and combine during my visit to HPI: Singular Spectrum Analysis, Grammatical Evolution, Estimation Distribution Algorithms, Fourier Analysis and Noisy Evolutionary Search.

Selfish Network Creation focuses on modeling real world networks from a game-theoretic point of view. One of the classic models by Fabrikant et al. [PODC'03] is the network creation game, where agents correspond to nodes in a network which buy incident edges for the price of alpha per edge to minimize their total distance to all other nodes. The model is well-studied but still has intriguing open problems. The most famous conjectures state that the price of anarchy is constant for all alpha>0 and that for alpha >= n all equilibrium networks are trees. Here n is the number of nodes in the network.

We introduce a novel technique for analyzing stable networks for high edge-price alpha and employ it to improve on the best known bounds for both conjectures. In particular we show that for alpha > 4n-13 all equilibrium networks must be trees, which implies a constant price of anarchy for this range of alpha. Moreover, we also improve the constant upper bound on the price of anarchy for equilibrium trees.

(The paper will be presented at STACS'18.)

Cedric will talk about the topic of his master thesis and his current progress.

Despite the success of CDCL SAT solvers solving industrial problems, there are still many open questions to explain such success. In this context, the generation of random SAT instances having computational properties more similar to real-world problems becomes crucial. Such generators are possibly the best tool to analyze families of instances and solvers behaviors on them.

In this talk, we present a random SAT instances generator based on the notion of "locality". We show that this is a decisive dimension of attractiveness among the variables of a formula, and show how CDCL SAT solvers take advantage of it. This random SAT model generates both scale-free structure and community structure at once.

Assignment problems are well-studied combinatorial optimization problems with numerous practical applications. In real-life optimization problems are modeled using data based on forecasts and estimates which leads to uncertain problem parameters. One way to take this fact into account is provided by the framework of robust optimization.

While most robust assignment problems considered in the literature address cost uncertainty, this talk deals with Robust Assignment Problem (RAP), which a new problem where the structure of the underlying bipartite graph is uncertain. In RAP, an additional part of the input is a list of failure scenarios described by a subset of resources (edges or nodes in the graph) that may fail simultaneously. If a scenario emerges, the corresponding resources are deleted from the graph. The goal is to find a minimum-cost set of resources defining a maximum matching in every scenario. As an example, consider production planning where orders are assigned to production lines. A change in product specifications can be encoded as an edge failure and production line maintenance corresponds to a node failure. We will discuss the computational complexity of two RAP variants and present asymptotically tight approximation algorithms. Additionally we address the following related question: Is it easier to harden an existent infrastructure rather than designing a new one from scratch?

Given a graph and a set of paths, we want to find a minimum set of vertices such that each path is covered by at least one chosen vertext. Although this problem is NP-hard in general, real-world instances can be solved almost completely by a set of simple reduction rules. We examine this behavior both from a theoretical as well as from an empirical perspective. We show that this problem is easy on forests, but becomes hard for any reasonable generalization of 'tree-likeness'. This indicates that the explanation for the effectiveness does not lie in the graph representation. We thus turn to a model-based analysis of the resulting geometric Hitting Set instances.

Mixture models are widely used in the context of generative classifiers. But they can also be applied as discriminative models for regression. This makes them very useful for modeling particular problems in economics. In the last five years a mixture of linear regression models (LRMs) has shown good properties to predict the dynamic of interest rates. The EM algorithm didn’t work very well as far as we considered a mixture of three or more LRMs. Adding random restarts to the EM algorithm helped to get over local maxima during the maximization of the auxiliary function.

Finding a community structure in a network is a fundamental problem with many applications in different research areas. There are different variants of it depending on how the quality of the community structure is measured. A common formulation asks for a non-overlapping partition that maximizes the modularity. Unfortunately, this problem is proven to be NP-hard. One among many heuristics is called Louvain Modularity Optimization (LMO) method and is commonly accepted to be fast while achieving good results in real-world complex networks. Despite the wide-spread practical use of this method, theoretical results neither about the quality of the solution nor about the runtime are known.

In this work, a lower bound of \(\Omega(n^2)\) for the worst-case runtime is presented. However, the LMO method is much faster in realistic graph models. An experimental examination of the runtime depending on different random graph models shows that for geometrical models the algorithm is considerably faster than for non-geometrical ones. The first are also known to have more realistic properties. This work analyses why the Louvain method is fast in real-world complex networks, although it is not fast in general. Finally, a faster variant of the method called k-Iterations-Louvain is presented.