ADYN-Seminar

Show abstracts

Spreading Processes on Spatial Contact Networks (Lapinskas)

We study the spread of information (or an epidemic) through a random graph intended to model a real-world social network. A decade ago, it was a long-standing open problem to find any such random graph model which maintained enough independence between vertices and edges to be pleasant to work with. Now, a closely-related family of such models has been developed. We study two models in this family, geometric inhomogeneous random graphs (GIRGs) and scale-free percolation (SFP). GIRGs include as a sub-family arguably the most famous such model: hyperbolic random graphs. The talk will not assume any prior background in the area, and it will begin with an introduction to GIRGs and SFP and to the properties of social networks in general.

From prior work by Komjathy and Lodewijks, we know that if we consider a standard SI spreading model on any GIRG or SFP graph whose parameters give rise to a giant component, then for most reasonable choices of transmission parameters the process will “explode” with non-zero probability (covering a constant proportion of vertices in constant time). This is unrealistic in many situations, which suggests it may be the wrong model for those situations. We show that by adding a small transmission penalty to high-degree vertices, we can recover the expected behaviour of a phase transition to explosion, and we locate this phase transition. We will also discuss unpublished future work in which we determine many of the transitions between explosion, exponential spread, and even polynomial spread. The idea of polynomial spread is surprising, but true to life; some epidemics do spread at polynomial rates, such as ebola in west Africa, and understanding the cause of this phenomenon is an open problem.

Show abstracts

On codes decoding error on the BEC and BSC (Hazla)

I will talk about how to use a recent inequality on Boolean functions by Samorodnitsky to obtain a result in coding theory. Namely, assume that a linear code successfully corrects errors on the binary erasure channel (BEC) under optimal (maximum a posteriori, or MAP) decoding. Then, this code is also successful on a range of other channels with somewhat smaller capacities, including binary symmetric channel (BSC). One previously unknown consequence is that constant-rate Reed-Muller codes correct errors on BSC(p) for some constant p > 0.

Warning Propagation on Random Graphs (Ravelomanana)

Warning Propagation is a combinatorial message passing algorithm that unifies and generalises a wide variety of recursive combinatorial procedures. Special cases include the Unit Clause Propagation and Pure Literal algorithms for satisfiability as well as the peeling process for identifying the k-core of a random graph. Here we analyse Warning Propagation in full generality on the binomial random graph. We prove that under a mild stability assumption Warning Propagation converges rapidly. In effect, the analysis of the fixed point of the message passing process on a random graph reduces to analysing the process on a Galton-Watson tree. This result corroborates and generalises a heuristic first put forward by Pittel, Spencer and Wormald in their seminal k-core paper (JCTB 1996).

Show abstracts

Networked Contingent Convertible Obligations and Financial Stability (Feinstein)

In this talk we investigate whether a financial system can be made more stable if financial institutions share risk by exchanging contingent convertible (CoCo) debt obligations. The question is framed in a financial network with debt and equity interlinkages with the addition of CoCos that convert continuously when a bank's debt-equity ratio drops to a trigger level. We characterize the clearing problem for the interbank debt and equity at the maturity of the obligations. We then introduce stylized networks to study when introducing CoCo bonds improves financial stability, as well as specific networks for which CoCo bonds do not uniformly provide improved system performance. To return to the main question, we examine the EU financial network at the time of the 2011 EBA stress test to do comparative statics to study the implications of CoCo debt on financial stability.  It is found that by replacing all unsecured interbank debt by standardized CoCo interbank debt securities, systemic risk in the EU will decrease and bank shareholder value will increase. This is joint work with T.R. Hurd (McMaster University).

Stochastical Models for Bipartite Random Graph Models (Gerstorfer)

We study the embedding of bipartite random graph models using Bayesian stochastical models. Given a list of bipartite edges, we use Variational Inference algorithms to estimate the optimal parameters for a generative network model, so that the input network will be a typical outcome of the generative model. In this talk, I will present the methods we use for our models and explain the main concepts of our approach.

Show abstracts

Theoretical Algorithm Analysis meets Practical Data (Bläsius)

A theoretical running time analysis is a great tool for predicting the performance of algorithms, saving programmers from implementing and evaluating alternatives that are "obviously" worse. Though this works very well in many cases, there are situations where the predictions do not match practical observations. This often comes from the fact that practical problem instances have certain properties that make them well-behaved. In this talk, I formalize these properties using probabilistic models and discuss theoretical results based on these formalizations. In the course of this, I will discuss advantages and
limitations of this model-based approach.

Eventually Exponential Contagion via Local and Global Contacts (Fischbeck)

Bootstrap percolation is a classical model for the spread of information in a network. In the round-based version, nodes of an undirected graph become active once at least r neighbors were active in the previous round. We propose the perturbed percolation process, a superposition of two percolation processes on the same node set. One process acts on a base graph with activation threshold 1, while the other acts on a random graph with threshold r (representing local and global contacts, respectively). We consider a class of grid-like base graphs, in which the bootstrap percolation process only spreads polynomially fast. As random graph, we consider Erdős–Rényi graphs. For r=1, the perturbed percolation process percolates exponentially fast, as the diameter is known to be low. For r>=2 however, we prove that the process initially spreads polynomially fast, with no activations via the random graph, and eventually the activation rate becomes exponential, driven only by the random graph. We complement our theoretical results by empirical analyses of this process. In addition, we discuss future work on the inclusion of recovery into this process.

Show abstracts

The Next Economic Crisis? It's the Network! (Wattenhofer)

The world's financial system is a network, where financial institutions such as banks are connected via various kinds of financial contracts. If some financial institutions go bankrupt, then others might suffer as well; the financial network might experience a ripple effect. In other words, the next big financial crisis should be understood with the network in mind. In this talk I will present some analytical results on financial networks. For instance, can we build a financial network that is more robust to failures? How can we clean up after a crisis? Who should be bailed out?

Fire Sale Games (Wilhelmi)

We study a financial network consisting of n players, each write liabilities and hold unmarketable assets as well as a set of marketable assets called securities. Every player is obligated to fulfill a given leverage constraint and is forced to sell a share of its securities for discount prices whenever it violates the constraint. We study fire sales from a game-theoretical view where players sell securities strategically to minimize losses due to decreasing prices. We consider different combinations of price functions and their impact on sales revenue. For a wide range of games, we show monotonic sales of players. Furthermore, we prove existence of equilibria and convergence to the best equilibrium of the best-response dynamic.

Show abstracts

Self-Stabilizing Clock Synchronization with 1-Bit Messages (Giakkoupis)

I will talk about some recent results we showed for the problem of distributed clock synchronization. The model we consider is a synchronous fully-connected network of n agents, where each agent has a local clock, that is, a counter increasing by one modulo T in each round. The clocks have arbitrary values initially, and they must all indicate the same time eventually. We assume a gossip-based pull communication model, where in every round each agent receives an ℓ-bit message from a random agent. We devised several fast synchronization algorithms that use small messages and are self-stabilizing, that is, the complete initial state of each agent (not just its clock value) can be arbitrary. Our main contribution is an algorithm that synchronizes a general modulo T clock in polylogarithmic time (in n and T), using just 1-bit messages. This is a join work with Paul Bastide and Hayk Saribekyan.

Using an Oracle for Scheduling Unknown Independent Tasks (Rau)

We are studying a non-clairvoyant problem for scheduling independent tasks where the processing times of the tasks are unknown. However, the scheduler can use an external resource (oracle) that delivers an answer to a query on the processing time. This query for the processing time of a task takes some time and the schedule has to wait until it is answered. Aiming to minimize the total completion time of the given tasks, we study different strategies for which tasks the oracle should be questioned. If this strategy has to be fixed before the first task is queried or scheduled, we present the strategy that provably generates a schedule with the smallest expected total completion time. However, we prove that this strategy is not the best when aiming to minimize the worst case.

Show abstracts

Approximation of the Diagonal of a Laplacian's Pseudoinverse for Complex Network Analysis (Meyerhenke)

The ubiquity of massive graph data sets in numerous applications requires fast algorithms for extracting knowledge from these data. We are motivated here by three electrical measures for the analysis of large small-world graphs G = (V, E) - i. e., graphs with diameter in O(log |V|), which are abundant in complex network analysis. From a computational point of view, the three measures have in common that their crucial component is the diagonal of the graph Laplacian’s pseudoinverse, L^+. Computing diag(L^+) exactly by pseudoinversion, however, is as expensive as dense matrix multiplication - and the standard tools in practice even require cubic time. Moreover, the pseudoinverse requires quadratic space - hardly feasible for large graphs. Resorting to approximation by, e. g., using the Johnson-Lindenstrauss transform, requires the solution of O(log |V| /ε²) Laplacian linear systems to guarantee a relative error, which is still very expensive for large inputs. In this paper, we present a novel approximation algorithm that requires the solution of only one Laplacian linear system. The remaining parts are purely combinatorial - mainly sampling uniform spanning trees, which we relate to diag(L^+) via effective resistances. For small-world networks, our algorithm obtains a ± ε-approximation with high probability, in a time that is nearly-linear in |E| and quadratic in 1 / ε. Another positive aspect of our algorithm is its parallel nature due to independent sampling. We thus provide two parallel implementations of our algorithm: one using OpenMP, one MPI + OpenMP. In our experiments against the state of the art, our algorithm (i) yields more accurate approximation results for diag(L^+), (ii) is much faster and more memory-efficient, and (iii) obtains good parallel speedups, in particular in the distributed setting. Finally, we sketch some extensions of our techniques to related problems, in particular to (group) forest closeness centrality.

Simulating Population Protocols in Sub-Constant Time per Interaction (Penschuck)

We consider the efficient simulation of population protocols. In the population model, we are given a system of n agents modeled as identical finite-state machines. In each step, two agents are selected uniformly at random to interact by updating their states according to a common transition function. We empirically and analytically analyze two classes of simulators for this model. First, we consider sequential simulators executing one interaction after the other. Key to the
performance of these simulators is the data structure storing the agents' states. For our analysis, we consider plain arrays, binary search trees, and a novel Dynamic Alias Table data structure. Secondly, we consider batch processing to efficiently update the states of multiple independent agents in one step. For many protocols considered in literature, our simulator requires amortized sub-constant time per interaction and is fast in practice: given a fixed time budget, the
implementation of our batched simulator is able to simulate population protocols several orders of magnitude larger compared to the sequential competitors, and can carry out 2^50 interactions among the same number of agents in less than 400s.

Show abstracts

Beyond Sparsity: Compressive Sensing with (Deep) Generative Modeling Assumptions (Scarlett)

The problem of estimating an unknown vector from linear measurements has a long history in statistics, machine learning, and signal processing. Classical studies focus on the "n >> p" regime (#measurements >> #parameters), and more recent studies handle the "n << p" regime by exploiting low-dimensional structure such as sparsity or low-rankness.  Such variants are commonly known as compressive sensing.

In this talk, I will overview recent methods that move beyond these simple notions of structure, and instead assume that the underlying vector is well-modeled by a generative model (e.g., produced by deep learning methods such as GANs).  I will highlight algorithmic works that demonstrated up to 5-10x savings in the number of measurements over sparsity-based methods, and then move on to our theoretical work characterizing the order-optimal sample complexity in terms of quantities such as (i) the Lipschitz constant of the model, or (ii) the depth/width in a neural network model.  I will also briefly overview some recent results on non-linear observation models.

Inference under restrictions - sparsity constrained group testing (Hahn-Klimroth)

While non-adaptive group testing itself was recently fully understood to be easy in the sense that there is a polynomial time algorithm achieving inference at a universal information-theoretic lower bound, it comes with the flaw that within optimal designs each individual gets tested log(n) times and each test contains polynomially many individuals. Such testing schemes may not be applicable due to restrictions in laboratories.

In this talk, we will tackle the problem by analysing the sparsity-constrained group testing problem. Building up on first results by Gandikota et al. (2016), we provide a full understanding of the group testing problem if the test-size needs to be constant and achieve almost optimal results if the tests-per-individual are restricted to o(log n).