Konstantinos Panagiotou
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Konstantinos Panagiotou has a total of 32 co-authors. Here are the top co-authors by number of shared publications:
- Nils Detering
Department of Statistics and Applied Probability, University of California at Santa Barbara, Santa Barbara, USA
5 shared publications - Daniel Ritter
Department of Mathematics University of Munich Theresienstraße 39 80333 Munich Germany
4 shared publications - Thilo Meyer-Brandis
Department of Mathematics, LMU Munich, Munich, Germany
4 shared publications - Amin Coja-Oghlan
Goethe University Frankfurt
2 shared publications - Leon Ramzews
Department of Mathematics Ludwig-Maximilians-Universität München
2 shared publications - Nikolaos Fountoulakis
University of Birmingham
2 shared publications
Latest Publications
- 20 October 2023
- Published by Elsevier in Information Processing Letters
- Vol. 185
The effect of iterativity on adversarial opinion forming
- 20 October 2023
- Published by Elsevier in Information Processing Letters
- Vol. 185
The effect of iterativity on adversarial opinion forming
- 7 August 2023
- Published by Cambridge University Press (CUP) in Advances in Applied Probability
- Vol. 56 (1) , 156-204
Bootstrap percolation in inhomogeneous random graphs
A bootstrap percolation process on a graph with n vertices is an ‘infection’ process evolving in rounds. Let $r \ge 2$ be fixed. Initially, there is a subset of infected vertices. In each subsequent round, every uninfected vertex that has at least r infected neighbors becomes infected as well and remains so forever.We consider this process in the case where the underlying graph is an inhomogeneous random graph whose kernel is of rank one. Assuming that initially every vertex is infected independently with probability $p \in (0,1]$ , we provide a law of large numbers for the size of the set of vertices that are infected by the end of the process. Moreover, we investigate the case $p = p(n) = o(1)$ , and we focus on the important case of inhomogeneous random graphs exhibiting a power-law degree distribution with exponent $\beta \in (2,3)$ . The first two authors have shown in this setting the existence of a critical $p_c =o(1)$ such that, with high probability, if $p =o(p_c)$ , then the process does not evolve at all, whereas if $p = \omega(p_c)$ , then the final set of infected vertices has size $\Omega(n)$ . In this work we determine the asymptotic fraction of vertices that will eventually be infected and show that it also satisfies a law of large numbers.- 7 August 2023
- Published by Cambridge University Press (CUP) in Advances in Applied Probability
- Vol. 56 (1) , 156-204
Bootstrap percolation in inhomogeneous random graphs
A bootstrap percolation process on a graph with n vertices is an ‘infection’ process evolving in rounds. Let $r \ge 2$ be fixed. Initially, there is a subset of infected vertices. In each subsequent round, every uninfected vertex that has at least r infected neighbors becomes infected as well and remains so forever.We consider this process in the case where the underlying graph is an inhomogeneous random graph whose kernel is of rank one. Assuming that initially every vertex is infected independently with probability $p \in (0,1]$ , we provide a law of large numbers for the size of the set of vertices that are infected by the end of the process. Moreover, we investigate the case $p = p(n) = o(1)$ , and we focus on the important case of inhomogeneous random graphs exhibiting a power-law degree distribution with exponent $\beta \in (2,3)$ . The first two authors have shown in this setting the existence of a critical $p_c =o(1)$ such that, with high probability, if $p =o(p_c)$ , then the process does not evolve at all, whereas if $p = \omega(p_c)$ , then the final set of infected vertices has size $\Omega(n)$ . In this work we determine the asymptotic fraction of vertices that will eventually be infected and show that it also satisfies a law of large numbers.- Open Access
Satisfiability Thresholds for Regular Occupation Problems
In the last two decades the study of random instances of constraint satisfaction problems (CSPs) has flourished across several disciplines, including computer science, mathematics and physics. The diversity of the developed methods, on the rigorous and non-rigorous side, has led to major advances regarding both the theoretical as well as the applied viewpoints. Based on a ceteris paribus approach in terms of the density evolution equations known from statistical physics, we focus on a specific prominent class of regular CSPs, the so-called occupation problems. The regular $r$-in-$k$ occupation problems resemble a basis of this class. By now, out of these CSPs only the satisfiability threshold - the largest degree for which the problem admits asymptotically a solution - for the $1$-in-$k$ occupation problem has been rigorously established. Here we determine the satisfiability threshold of the $2$-in-$k$ occupation problem for all $k$. In the proof we exploit the connection of an associated optimization problem regarding the overlap of satisfying assignements to a fixed point problem inspired by belief propagation, a message passing algorithm developed for solving such CSPs.Open AccessSatisfiability Thresholds for Regular Occupation Problems
In the last two decades the study of random instances of constraint satisfaction problems (CSPs) has flourished across several disciplines, including computer science, mathematics and physics. The diversity of the developed methods, on the rigorous and non-rigorous side, has led to major advances regarding both the theoretical as well as the applied viewpoints. Based on a ceteris paribus approach in terms of the density evolution equations known from statistical physics, we focus on a specific prominent class of regular CSPs, the so-called occupation problems. The regular $r$-in-$k$ occupation problems resemble a basis of this class. By now, out of these CSPs only the satisfiability threshold - the largest degree for which the problem admits asymptotically a solution - for the $1$-in-$k$ occupation problem has been rigorously established. Here we determine the satisfiability threshold of the $2$-in-$k$ occupation problem for all $k$. In the proof we exploit the connection of an associated optimization problem regarding the overlap of satisfying assignements to a fixed point problem inspired by belief propagation, a message passing algorithm developed for solving such CSPs. - Open Access
Suffocating Fire Sales
Fire sales are among the major drivers of market instability in modern financial systems. Due to iterated distressed selling and the associated price impact, initial shocks to some institutions can be amplified dramatically through the network induced by portfolio overlaps. In this paper, we develop a mathematical framework that allows us to investigate central characteristics that drive or hinder the propagation of distress. We investigate single systems as well as ensembles of systems that are alike, where similarity is measured in terms of the empirical distribution of all defining properties of a system. This asymptotic approach ensures a great deal of robustness to statistical uncertainty and temporal fluctuations. A characterization of those systems that are resilient to small shocks emerges, and we provide criteria that regulators might exploit in order to assess the stability of a financial system. We illustrate the application of these criteria for some exemplary configurations in the context of capital requirements and test the applicability of our results for systems of moderate size by Monte Carlo simulations.
Open AccessSuffocating Fire Sales
Fire sales are among the major drivers of market instability in modern financial systems. Due to iterated distressed selling and the associated price impact, initial shocks to some institutions can be amplified dramatically through the network induced by portfolio overlaps. In this paper, we develop a mathematical framework that allows us to investigate central characteristics that drive or hinder the propagation of distress. We investigate single systems as well as ensembles of systems that are alike, where similarity is measured in terms of the empirical distribution of all defining properties of a system. This asymptotic approach ensures a great deal of robustness to statistical uncertainty and temporal fluctuations. A characterization of those systems that are resilient to small shocks emerges, and we provide criteria that regulators might exploit in order to assess the stability of a financial system. We illustrate the application of these criteria for some exemplary configurations in the context of capital requirements and test the applicability of our results for systems of moderate size by Monte Carlo simulations.
- Open Access
The Chromatic Number of Dense Random Block Graphs
The chromatic number $\chi(G)$ of a graph $G$, that is, the smallest number of colors required to color the vertices of $G$ so that no two adjacent vertices are assigned the same color, is a classic and extensively studied parameter. Here we consider the case where $G$ is a random block graph, also known as the stochastic block model. The vertex set is partitioned into $k\in\mathbb{N}$ parts $V_1, \dotsc, V_k$, and for each $1 \le i\le j\le k$, two vertices $u \in V_i, v\in V_j$ are connected by an edge with some probability $p_{ij} \in (0,1)$ independently. Our main result pins down the typical asymptotic value of $\chi(G)$ and establishes the distribution of the sizes of the color classes in optimal colorings. We discover that in contrast to the case of a binomial random graph $G(n,p)$, that corresponds to $k=1$ in our model, where the average size of a color class in an (almost) optimal coloring essentially coincides with the independence number, the block model reveals a more diverse picture: the "average" class in an optimal coloring is a convex combination of several types of independent sets that vary in total size as well as in the size of their intersection with each $V_i$, $1\le i \le k$.Open AccessThe Chromatic Number of Dense Random Block Graphs
The chromatic number $\chi(G)$ of a graph $G$, that is, the smallest number of colors required to color the vertices of $G$ so that no two adjacent vertices are assigned the same color, is a classic and extensively studied parameter. Here we consider the case where $G$ is a random block graph, also known as the stochastic block model. The vertex set is partitioned into $k\in\mathbb{N}$ parts $V_1, \dotsc, V_k$, and for each $1 \le i\le j\le k$, two vertices $u \in V_i, v\in V_j$ are connected by an edge with some probability $p_{ij} \in (0,1)$ independently. Our main result pins down the typical asymptotic value of $\chi(G)$ and establishes the distribution of the sizes of the color classes in optimal colorings. We discover that in contrast to the case of a binomial random graph $G(n,p)$, that corresponds to $k=1$ in our model, where the average size of a color class in an (almost) optimal coloring essentially coincides with the independence number, the block model reveals a more diverse picture: the "average" class in an optimal coloring is a convex combination of several types of independent sets that vary in total size as well as in the size of their intersection with each $V_i$, $1\le i \le k$. - Open Access
Asymptotic Enumeration and Limit Laws for Multisets: the Subexponential Case
For a given combinatorial class $\mathcal{C}$ we study the class $\mathcal{G} = \mathrm{MSET}(\mathcal{C})$ satisfying the multiset construction, that is, any object in $\mathcal{G}$ is uniquely determined by a set of $\mathcal{C}$-objects paired with their multiplicities. For example, $\mathrm{MSET}(\mathbb{N})$ is (isomorphic to) the class of number partitions of positive integers, a prominent and well-studied case. The multiset construction appears naturally in the study of unlabelled objects, for example graphs or various structures related to number partitions. Our main result establishes the asymptotic size of the set $\mathcal{G}_{n,N}$ that contains all multisets in $\mathcal{G}$ having size $n$ and being comprised of $N$ objects from $\mathcal{C}$, as $n$ \emph{and} $N$ tend to infinity and when the counting sequence of $\mathcal{C}$ is governed by subexponential growth; this is a particularly important setting in combinatorial applications. Moreover, we study the component distribution of random objects from $\mathcal{G}_{n,N}$ and we discover a phenomenon that we baptise \emph{extreme condensation}: taking away the largest component as well as all the components of the smallest possible size, we are left with an object which converges in distribution as $n,N\to\infty$. The distribution of the limiting object is also retrieved. Moreover and rather surprisingly, in stark contrast to analogous results for labelled objects, the results here hold uniformly in $N$.Open AccessAsymptotic Enumeration and Limit Laws for Multisets: the Subexponential Case
For a given combinatorial class $\mathcal{C}$ we study the class $\mathcal{G} = \mathrm{MSET}(\mathcal{C})$ satisfying the multiset construction, that is, any object in $\mathcal{G}$ is uniquely determined by a set of $\mathcal{C}$-objects paired with their multiplicities. For example, $\mathrm{MSET}(\mathbb{N})$ is (isomorphic to) the class of number partitions of positive integers, a prominent and well-studied case. The multiset construction appears naturally in the study of unlabelled objects, for example graphs or various structures related to number partitions. Our main result establishes the asymptotic size of the set $\mathcal{G}_{n,N}$ that contains all multisets in $\mathcal{G}$ having size $n$ and being comprised of $N$ objects from $\mathcal{C}$, as $n$ \emph{and} $N$ tend to infinity and when the counting sequence of $\mathcal{C}$ is governed by subexponential growth; this is a particularly important setting in combinatorial applications. Moreover, we study the component distribution of random objects from $\mathcal{G}_{n,N}$ and we discover a phenomenon that we baptise \emph{extreme condensation}: taking away the largest component as well as all the components of the smallest possible size, we are left with an object which converges in distribution as $n,N\to\infty$. The distribution of the limiting object is also retrieved. Moreover and rather surprisingly, in stark contrast to analogous results for labelled objects, the results here hold uniformly in $N$. - Open Access
Managing Default Contagion in Inhomogeneous Financial Networks
The aim of this paper is to quantify and manage systemic risk caused by default contagion in the interbank market. We model the market as a random directed network, where the vertices represent financial institutions and the weighted edges monetary exposures between them. Our model captures the strong degree of heterogeneity observed in empirical data and the parameters can easily be fitted to real data sets. One of our main results allows us to determine the impact of local shocks, where initially some banks default, to the entire system and the wider economy. Here the impact is measured by some index of total systemic importance of all eventually defaulted institutions. As a central application, we characterize resilient and non-resilient cases. In particular, for the prominent case where the network has a degree sequence without second moment, we show that a small number of initially defaulted banks can trigger a substantial default cascade. Our results complement and extend significantly earlier findings derived in the configuration model where the existence of a second moment of the degree distribution is assumed. As a second main contribution, paralleling regulatory discussions, we determine minimal capital requirements for financial institutions sufficient to make the network resilient to small shocks. An appealing feature of these capital requirements is that they can be determined locally by each institution without knowing the complete network structure as they basically only depend on the institution's exposures to its counterparties.
Open AccessManaging Default Contagion in Inhomogeneous Financial Networks
The aim of this paper is to quantify and manage systemic risk caused by default contagion in the interbank market. We model the market as a random directed network, where the vertices represent financial institutions and the weighted edges monetary exposures between them. Our model captures the strong degree of heterogeneity observed in empirical data and the parameters can easily be fitted to real data sets. One of our main results allows us to determine the impact of local shocks, where initially some banks default, to the entire system and the wider economy. Here the impact is measured by some index of total systemic importance of all eventually defaulted institutions. As a central application, we characterize resilient and non-resilient cases. In particular, for the prominent case where the network has a degree sequence without second moment, we show that a small number of initially defaulted banks can trigger a substantial default cascade. Our results complement and extend significantly earlier findings derived in the configuration model where the existence of a second moment of the degree distribution is assumed. As a second main contribution, paralleling regulatory discussions, we determine minimal capital requirements for financial institutions sufficient to make the network resilient to small shocks. An appealing feature of these capital requirements is that they can be determined locally by each institution without knowing the complete network structure as they basically only depend on the institution's exposures to its counterparties.
- Open Access
- 12 August 2020
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 30 (1) , 37-78
Robustness of randomized rumour spreading
In this work we consider three well-studied broadcast protocols: push, pull and push&pull. A key property of all these models, which is also an important reason for their popularity, is that they are presumed to be very robust, since they are simple, randomized and, crucially, do not utilize explicitly the global structure of the underlying graph. While sporadic results exist, there has been no systematic theoretical treatment quantifying the robustness of these models. Here we investigate this question with respect to two orthogonal aspects: (adversarial) modifications of the underlying graph and message transmission failures.We explore in particular the following notion of local resilience: beginning with a graph, we investigate up to which fraction of the edges an adversary may delete at each vertex, so that the protocols need significantly more rounds to broadcast the information. Our main findings establish a separation among the three models. On one hand, pull is robust with respect to all parameters that we consider. On the other hand, push may slow down significantly, even if the adversary may modify the degrees of the vertices by an arbitrarily small positive fraction only. Finally, push&pull is robust when no message transmission failures are considered, otherwise it may be slowed down.On the technical side, we develop two novel methods for the analysis of randomized rumour-spreading protocols. First, we exploit the notion of self-bounding functions to facilitate significantly the round-based analysis: we show that for any graph the variance of the growth of informed vertices is bounded by its expectation, so that concentration results follow immediately. Second, in order to control adversarial modifications of the graph we make use of a powerful tool from extremal graph theory, namely Szemerédi’s Regularity Lemma.
- 12 August 2020
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 30 (1) , 37-78
Open AccessRobustness of randomized rumour spreading
In this work we consider three well-studied broadcast protocols: push, pull and push&pull. A key property of all these models, which is also an important reason for their popularity, is that they are presumed to be very robust, since they are simple, randomized and, crucially, do not utilize explicitly the global structure of the underlying graph. While sporadic results exist, there has been no systematic theoretical treatment quantifying the robustness of these models. Here we investigate this question with respect to two orthogonal aspects: (adversarial) modifications of the underlying graph and message transmission failures.We explore in particular the following notion of local resilience: beginning with a graph, we investigate up to which fraction of the edges an adversary may delete at each vertex, so that the protocols need significantly more rounds to broadcast the information. Our main findings establish a separation among the three models. On one hand, pull is robust with respect to all parameters that we consider. On the other hand, push may slow down significantly, even if the adversary may modify the degrees of the vertices by an arbitrarily small positive fraction only. Finally, push&pull is robust when no message transmission failures are considered, otherwise it may be slowed down.On the technical side, we develop two novel methods for the analysis of randomized rumour-spreading protocols. First, we exploit the notion of self-bounding functions to facilitate significantly the round-based analysis: we show that for any graph the variance of the growth of informed vertices is bounded by its expectation, so that concentration results follow immediately. Second, in order to control adversarial modifications of the graph we make use of a powerful tool from extremal graph theory, namely Szemerédi’s Regularity Lemma.
- Open Access
- 27 June 2020
- Published by Springer Nature in Mathematics and Financial Economics
- Vol. 15 (1) , 59-101
An integrated model for fire sales and default contagion
Fire sales and default contagion are two of the main drivers of systemic risk in financial networks. While default contagion spreads via direct balance sheet exposures between institutions, fire sales describe iterated distressed selling of assets and their associated decline in price which impacts all institutions invested in these assets. That is, institutions are indirectly linked if they have overlapping asset portfolios. In this paper, we develop a model that helps us understand the joint effect of the two contagion channels and investigate structures of financial systems that promote or hinder the spread of an initial local shock. We first consider the contagion process for an explicitly given system and then derive our main results for random ensembles of systems whose macroscopic statistical characteristics of defining parameters are close to each other. In particular, we model direct exposures by means of a random graph. Our approach ensures robustness to local uncertainties and changes in the system. We characterize resilient and non-resilient system structures by criteria that can be used by regulators to assess system stability. Moreover, we provide explicit capital requirements that secure the financial system against the joint impact of fire sales and default contagion.
- 27 June 2020
- Published by Springer Nature in Mathematics and Financial Economics
- Vol. 15 (1) , 59-101
Open AccessAn integrated model for fire sales and default contagion
Fire sales and default contagion are two of the main drivers of systemic risk in financial networks. While default contagion spreads via direct balance sheet exposures between institutions, fire sales describe iterated distressed selling of assets and their associated decline in price which impacts all institutions invested in these assets. That is, institutions are indirectly linked if they have overlapping asset portfolios. In this paper, we develop a model that helps us understand the joint effect of the two contagion channels and investigate structures of financial systems that promote or hinder the spread of an initial local shock. We first consider the contagion process for an explicitly given system and then derive our main results for random ensembles of systems whose macroscopic statistical characteristics of defining parameters are close to each other. In particular, we model direct exposures by means of a random graph. Our approach ensures robustness to local uncertainties and changes in the system. We characterize resilient and non-resilient system structures by criteria that can be used by regulators to assess system stability. Moreover, we provide explicit capital requirements that secure the financial system against the joint impact of fire sales and default contagion.
- Open Access
Financial Contagion in a Generalized Stochastic Block Model
One of the most defining features of the global financial network is its inherent complex and intertwined structure. From the perspective of systemic risk it is important to understand the influence of this network structure on default contagion. Using sparse random graphs to model the financial network, asymptotic methods turned out powerful to analytically describe the contagion process and to make statements about resilience. So far, however, they have been limited to so-called {\em rank one} models in which informally the only network parameter is the degree sequence (see (Amini et. al. 2016) and (Detering et. al. 2019) for example) and the contagion process can be described by a one dimensional fix-point equation. These networks fail to account for a pronounced block structure such as core/periphery or a network composed of different connected blocks for different countries. We present a much more general model here, where we distinguish vertices (institutions) of different types and let edge probabilities and exposures depend on the types of both, the receiving and the sending vertex plus additional parameters. Our main result allows to compute explicitly the systemic damage caused by some initial local shock event, and we derive a complete characterisation of resilient respectively non-resilient financial systems. This is the first instance that default contagion is rigorously studied in a model outside the class of rank one models and several technical challenges arise. Moreover, in contrast to previous work, in which networks could be classified as resilient or non resilient, independent of the distribution of the shock, information about the shock becomes important in our model and a more refined resilience condition arises. Among other applications of our theory we derive resilience conditions for the global network based on subnetwork conditions only.
Open AccessFinancial Contagion in a Generalized Stochastic Block Model
One of the most defining features of the global financial network is its inherent complex and intertwined structure. From the perspective of systemic risk it is important to understand the influence of this network structure on default contagion. Using sparse random graphs to model the financial network, asymptotic methods turned out powerful to analytically describe the contagion process and to make statements about resilience. So far, however, they have been limited to so-called {\em rank one} models in which informally the only network parameter is the degree sequence (see (Amini et. al. 2016) and (Detering et. al. 2019) for example) and the contagion process can be described by a one dimensional fix-point equation. These networks fail to account for a pronounced block structure such as core/periphery or a network composed of different connected blocks for different countries. We present a much more general model here, where we distinguish vertices (institutions) of different types and let edge probabilities and exposures depend on the types of both, the receiving and the sending vertex plus additional parameters. Our main result allows to compute explicitly the systemic damage caused by some initial local shock event, and we derive a complete characterisation of resilient respectively non-resilient financial systems. This is the first instance that default contagion is rigorously studied in a model outside the class of rank one models and several technical challenges arise. Moreover, in contrast to previous work, in which networks could be classified as resilient or non resilient, independent of the distribution of the shock, information about the shock becomes important in our model and a more refined resilience condition arises. Among other applications of our theory we derive resilience conditions for the global network based on subnetwork conditions only.