The overlap gap property (OGP) is a statement about the geometry of near-optimal solutions. Exhibiting OGP implies failure of a class of local algorithms; and has been observed to coincide with conjectured algorithmic limits in problems with statistical computational gap. We consider the Stochastic Block Model (SBM), where the graph has a planted partition with k equal-size blocks which form the "communities", and where, for parameters p > q, vertices within the same community connect with probability p, while vertices in different communities connect with probability q, independently across pairs of vertices. Modularity-based clustering algorithms have become ubiquitous in applications. This article studies theoretical limits of local algorithms based on the modularity score on the SBM. We establish that modularity exhibits OGP on the SBM. This rules out a class of local algorithms based on modularity for recovery in the SBM, and shows slow mixing time for a related Markov Chain. Theoretically this is one of the few instances where OGP has been established for a "planted" model, as most such analyses to date consider the "null" model. As part of our analysis, we extend a result by Bickel and Chen 2009, who established that with high probability, the modularity optimal partition of SBM is o(n) local moves away from the planted partition, where n is the graph size. We show that, with high probability, any partition with modularity score sufficiently near the optimal value is close to the planted partition.

We relate two important notions in graph theory: expanders which are highly connected graphs, and modularity a parameter of a graph that is primarily used in community detection. More precisely, we show that a graph having modularity bounded below 1 is equivalent to it having a large subgraph which is an expander. We further show that a connected component H will be split in an optimal partition of the host graph G if and only if the relative size of H in G is greater than an expansion constant of H. This is a further exploration of the resolution limit known for modularity, and indeed recovers the bound that a connected component H in the host graph G will not be split if e(H) < √{2e(G)}.

Random graph models with community structure have been studied extensively in the literature. For both the problems of detecting and recovering community structure, an interesting landscape of statistical and computational phase transitions has emerged. A natural unanswered question is: might it be possible to infer properties of the community structure (for instance, the number and sizes of communities) even in situations where actually finding those communities is believed to be computationally hard? We show the answer is no. In particular, we consider certain hypothesis testing problems between models with different community structures, and we show (in the low-degree polynomial framework) that testing between two options is as hard as finding the communities. In addition, our methods give the first computational lower bounds for testing between two different "planted" distributions, whereas previous results have considered testing between a planted distribution and an i.i.d. "null" distribution.

We introduce a generalization of Galton-Watson trees where, individuals have independently a number of Poi(1 + p) offspring and, at each generation, pairs of cousins merge independently with probability q. If q = 0 we recover a usual Galton-Watson tree and the survival threshold for the process has p > 0. Our main thoerem gives sufficient conditions on p and q for extinction and survival of the Galton-Watson trees with cousin mergers. In the setting q > 0, the Markovian property of regular Galton-Watson trees is lost and so the analysis of the model becomes more involved. In particular, the main obstacle are the intergeneration dependencies since the genealogy of the individuals, having possibly more than one parent, is no longer represented by a tree but by a graph.

Temporal graphs (in which edges are active at specified times) are of particular relevance for spreading processes on graphs, e.g. the spread of disease or dissemination of information. Motivated by real-world applications, modification of static graphs to control this spread has proven a rich topic for previous research. Here, we introduce a new type of modification for temporal graphs: the number of active times for each edge is fixed, but we can change the relative order in which (sets of) edges are active. We investigate the problem of determining an ordering of edges that minimises the maximum number of vertices reachable from any single starting vertex; epidemiologically, this corresponds to the worst-case number of vertices infected in a single disease outbreak. We study two versions of this problem, both of which we show to be NP-hard, and identify cases in which the problem can be solved or approximated efficiently.

Abstract We investigate the number of permutations that occur in random labellings of trees. This is a generalisation of the number of subpermutations occurring in a random permutation. It also generalises some recent results on the number of inversions in randomly labelled trees (Cai et al. in Combin Probab Comput 28(3):335–364, 2019). We consider complete binary trees as well as random split trees a large class of random trees of logarithmic height introduced by Devroye (SIAM J Comput 28(2):409–432, 1998. 10.1137/s0097539795283954 ). Split trees consist of nodes (bags) which can contain balls and are generated by a random trickle down process of balls through the nodes. For complete binary trees we show that asymptotically the cumulants of the number of occurrences of a fixed permutation in the random node labelling have explicit formulas. Our other main theorem is to show that for a random split tree, with probability tending to one as the number of balls increases, the cumulants of the number of occurrences are asymptotically an explicit parameter of the split tree. For the proof of the second theorem we show some results on the number of embeddings of digraphs into split trees which may be of independent interest.

Abstract The maximum modularity of a graph is a parameter widely used to describe the level of clustering or community structure in a network. Determining the maximum modularity of a graph is known to be $$\textsf {NP}$$ NP -complete in general, and in practice a range of heuristics are used to construct partitions of the vertex-set which give lower bounds on the maximum modularity but without any guarantee on how close these bounds are to the true maximum. In this paper we investigate the parameterised complexity of determining the maximum modularity with respect to various standard structural parameterisations of the input graph G. We show that the problem belongs to $$\textsf {FPT}$$ FPT when parameterised by the size of a minimum vertex cover for G, and is solvable in polynomial time whenever the treewidth or max leaf number of G is bounded by some fixed constant; we also obtain an FPT algorithm, parameterised by treewidth, to compute any constant-factor approximation to the maximum modularity. On the other hand we show that the problem is W[1]-hard (and hence unlikely to admit an FPT algorithm) when parameterised simultaneously by pathwidth and the size of a minimum feedback vertex set.

We investigate the number of permutations that occur in random node labellings of trees. This is a generalisation of the number of subpermutations occuring in a random permutation. It also generalises some recent results on the number of inversions in randomly labelled trees [Cai et al., 2017]. We consider complete binary trees as well as random split trees a large class of random trees of logarithmic height introduced by Devroye [Devroye, 1998]. Split trees consist of nodes (bags) which can contain balls and are generated by a random trickle down process of balls through the nodes. For complete binary trees we show that asymptotically the cumulants of the number of occurrences of a fixed permutation in the random node labelling have explicit formulas. Our other main theorem is to show that for a random split tree with high probability the cumulants of the number of occurrences are asymptotically an explicit parameter of the split tree. For the proof of the second theorem we show some results on the number of embeddings of digraphs into split trees which may be of independent interest.

We study I(T), the number of inversions in a tree T with its vertices labeled uniformly at random. We first show that the cumulants of I(T) have explicit formulas. Then we consider X_n, the normalized version of I(T_n), for a sequence of trees T_n. For fixed T_n's, we prove a sufficient condition for X_n to converge in distribution. For T_n being split trees [Devroye, 1999], we show that X_n converges to the unique solution of a distributional equation. Finally, when T_n's are conditional Galton-Watson trees, we show that X_n converges to a random variable defined in terms of Brownian excursions. Our results generalize and extend previous work by Panholzer and Seitz [Panholzer and Seitz, 2012].

For a given graph G, modularity gives a score to each vertex partition, with higher values taken to indicate that the partition better captures community structure in G. The modularity q^*(G) (where 0 <= q^*(G)<= 1) of the graph G is defined to be the maximum over all vertex partitions of the modularity value. Given the prominence of modularity in community detection, it is an important graph parameter to understand mathematically. For the Erdös-Rényi random graph G_{n,p} with n vertices and edge-probability p, the likely modularity has three distinct phases. For np <= 1+o(1) the modularity is 1+o(1) with high probability (whp), and for np --> infty the modularity is o(1) whp. Between these regions the modularity is non-trivial: for constants 1 < c_0 <= c_1 there exists delta>0 such that when c_0 <= np <= c_1 we have delta<q^*(G)<1-delta whp. For this critical region, we show that whp q^*(G_{n,p}) has order (np)^{-1/2}, in accord with a conjecture by Reichardt and Bornholdt in 2006 (and disproving another conjecture from the physics literature).