NFNikolaos Fountoulakis

Nikolaos Fountoulakis

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Nikolaos Fountoulakis has a total of 32 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Bootstrap percolation in inhomogeneous random graphs

    by Hamed Amini, Nikolaos Fountoulakis, Konstantinos Panagiotou

    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

    Percolation on random graphs with a fixed degree sequence

    by Nikolaos Fountoulakis, Felix Joos, Guillem Perarnau

    We consider bond percolation on random graphs with given degrees and bounded average degree. In particular, we consider the order of the largest component after the random deletion of the edges of such a random graph. We give a rough characterisation of those degree distributions for which bond percolation with high probability leaves a component of linear order, known usually as a giant component. We show that essentially the critical condition has to do with the tail of the degree distribution. Our proof makes use of recent technique introduced by Joos et al. [FOCS 2016, pp. 695--703], which is based on the switching method and avoids the use of the classic configuration model as well as the hypothesis of having a limiting object. Thus our results hold for sparse degree sequences without the usual restrictions that accompany the configuration model.

  • Open Access

    The modularity of random graphs on the hyperbolic plane

    by Jordan Chellig, Nikolaos Fountoulakis, Fiona Skerman

    Modularity is a quantity which has been introduced in the context of complex networks in order to quantify how close a network is to an ideal modular network in which the nodes form small interconnected communities that are joined together with relatively few edges. In this article, we consider this quantity on a probabilistic model of complex networks introduced by Krioukov et al. (2010, Phys. Rev. E, 82, 036106). This model views a complex network as an expression of hidden popularity hierarchies (i.e. nodes higher up in the hierarchies have more global reach), encapsulated by an underlying hyperbolic space. For certain parameters, this model was proved to have typical features that are observed in complex networks such as power law degree distribution, bounded average degree, clustering coefficient that is asymptotically bounded away from zero and ultra-small typical distances. In the present work, we investigate its modularity and we show that, in this regime, it converges to one in probability.


  • Best response dynamics on random graphs

    by Jordan Chellig, Calina Durbac, Nikolaos Fountoulakis


  • Open Access

    Algebraic and combinatorial expansion in random simplicial complexes

    by Nikolaos Fountoulakis, Michał Przykucki

    In this paper we consider the expansion properties and the spectrum of the combinatorial Laplace operator of a d‐dimensional Linial–Meshulam random simplicial complex, above the cohomological connectivity threshold. We consider the spectral gap of the Laplace operator and the Cheeger constant as this was introduced by Parzanchevski, Rosenthal, and Tessler. We show that with high probability the spectral gap of the random simplicial complex as well as the Cheeger constant are both concentrated around the minimum co‐degree of among all ‐faces. Furthermore, we consider a random walk on such a complex, which generalizes the standard random walk on a graph. We show that the associated conductance is with high probability bounded away from 0, resulting in a bound on the mixing time that is logarithmic in the number of vertices of the complex.


  • Open Access

    Limit theory of isolated and extreme points in hyperbolic random geometric graphs

    by Nikolaos Fountoulakis, Joseph Yukich

    Given $\alpha \in (0, \infty)$ and $r \in (0, \infty)$, let ${\cal D}_{r, \alpha}$ be the disc of radius $r$ in the hyperbolic plane having curvature $-\alpha^2$. Consider the Poisson point process having uniform intensity density on ${\cal D}_{R, \alpha}$, with $R = 2 \log(n/ \nu),$ $n \in \mathbb{N}$, and $\nu < n$ a fixed constant. The points are projected onto ${\cal D}_{R, 1}$, preserving polar coordinates, yielding a Poisson point process ${\cal P}_{\alpha, n}$ on ${\cal D}_{R, 1}$. The hyperbolic geometric graph ${\cal G}_{\alpha, n}$ on ${\cal P}_{\alpha, n}$ puts an edge between pairs of points of ${\cal P}_{\alpha, n}$ which are distant at most $R$. This model has been used to express fundamental features of complex networks in terms of an underlying hyperbolic geometry. For $\alpha \in (1/2, \infty)$ we establish expectation and variance asymptotics as well as asymptotic normality for the number of isolated and extreme points in ${\cal G}_{\alpha, n}$ as $n \to \infty$. The limit theory and renormalization for the number of isolated points are highly sensitive on the curvature parameter. In particular, for $\alpha \in (1/2, 1)$, the variance is super-linear, for $\alpha = 1$ the variance is linear with a logarithmic correction, whereas for $\alpha \in (1, \infty)$ the variance is linear. The central limit theorem fails for $\alpha \in (1/2, 1)$ but it holds for $\alpha \in (1, \infty)$.

  • Open Access

    Best response dynamics on random graphs

    by Jordan Chellig, Calina Durbac, Nikolaos Fountoulakis

    We consider evolutionary games on a population whose underlying topology of interactions is determined by a binomial random graph $G(n,p)$. Our focus is on 2-player symmetric games with 2 strategies played between the incident members of such a population. Players update their strategies synchronously. At each round, each player selects the strategy that is the best response to the current set of strategies its neighbours play. We show that such a system reduces to generalised majority and minority dynamics. We show rapid convergence to unanimity for $p$ in a range that depends on a certain characteristic of the payoff matrix. In the presence of a bias among the pure Nash equilibria of the game, we determine a sharp threshold on $p$ above which the largest connected component reaches unanimity with high probability. For $p$ below this critical value, where this does not happen, we identify those substructures inside the largest component that remain discordant throughout the evolution of the system.

  • Open Access

    Resolution of a conjecture on majority dynamics: rapid stabilisation in dense random graphs

    by Nikolaos Fountoulakis, Mihyun Kang, Tamás Makai

    We study majority dynamics on the binomial random graph $G(n,p)$ with $p = d/n$ and $d > \lambda n^{1/2}$, for some large $\lambda>0$. In this process, each vertex has a state in $\{-1,+1 \}$ and at each round every vertex adopts the state of the majority of its neighbours, retaining its state in the case of a tie. We show that with high probability the process reaches unanimity in at most four rounds. This confirms a conjecture of Benjamini, Chan, O' Donnel, Tamuz and Tan.

  • Open Access

    Resolution of a conjecture on majority dynamics: Rapid stabilization in dense random graphs

    by Nikolaos Fountoulakis, Mihyun Kang, Tamás Makai

    We study majority dynamics on the binomial random graph G(n, p) with p = d/n and , for some large . In this process, each vertex has a state in {− 1, + 1} and at each round every vertex adopts the state of the majority of its neighbors, retaining its state in the case of a tie. We show that with high probability the process reaches unanimity in at most four rounds. This confirms a conjecture of Benjamini et al.