27 citations · 73 across the 20 of their papers we have counts for
24 papers
Note on edge expansion and modularity in preferential attachment graphs
Colin McDiarmid, Katarzyna Rybarczyk, Fiona Skerman +1
Edge expansion is a parameter indicating how well-connected a graph is. It is useful for designing robust networks, analysing random walks or information flow through a network and…
Modularity and random graphs
Colin McDiarmid, Fiona Skerman
This work will appear as a chapter in a forthcoming volume titled `Topics in Probabilistic Graph Theory'. For a given graph , each partition of the vertices has a modularity sco…
Modularity and Graph Expansion
Baptiste Louf, Colin McDiarmid, Fiona Skerman
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. M…
On graphs with modularity zero or near-zero
Colin McDiarmid, Fiona Skerman
It is known that complete graphs and complete multipartite graphs have modularity zero. We show that the least number of edges we may delete from the complete graph to obtain…
Universal lower bound for community structure of sparse graphs
Vilhelm Agdur, Nina Kamčev, Fiona Skerman
We prove new lower bounds on the modularity of graphs. Specifically, the modularity of a graph with average degree is , under some mild assumptions…
Logical limit laws for Mallows random permutations
Tobias Muller, Fiona Skerman, Teun W. Verstraaten
A random permutation of follows the $\DeclareMathOperator{\Mallows}{Mallows}\Mallows(n,q)$ distribution with parameter if is pro…
Is it easier to count communities than find them?
Cynthia Rush, Fiona Skerman, Alexander S. Wein +1
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…
From flip processes to dynamical systems on graphons
Frederik Garbe, Jan Hladký, Matas Šileikis +1
We introduce a class of random graph processes, which we call flip processes. Each such process is given by a rule which is a function $\mathcal{R}:\mathcal{H}_k\rightarrow \mathca…
Modularity and partially observed graphs
Colin McDiarmid, Fiona Skerman
Suppose that there is an unknown underlying graph on a large vertex set, and we can test only a proportion of the possible edges to check whether they are present in . If $G…
A branching process with deletions and mergers that matches the threshold for hypercube percolation
Laura Eslava, Sarah Penington, Fiona Skerman
We define a graph process based on a discrete branching process with deletions and mergers, which is inspired by the 4-cycle structure of both the hypercube $Q_d…
The modularity of random graphs on the hyperbolic plane
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 for…
Finding large expanders in graphs: from topological minors to induced subgraphs
Baptiste Louf, Fiona Skerman
In this paper, we consider a structural and geometric property of graphs, namely the presence of large expanders. The problem of finding such structures was first considered by Kri…
No additional tournaments are quasirandom-forcing
Robert Hancock, Adam Kabela, Daniel Kral +4
A tournament H is quasirandom-forcing if the following holds for every sequence (G_n) of tournaments of growing orders: if the density of H in G_n converges to the expected density…
Embedding small digraphs and permutations in binary trees and split trees
Michael Albert, Cecilia Holmgren, Tony Johansson +1
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…
Random tree recursions: which fixed points correspond to tangible sets of trees?
Tobias Johnson, Moumanti Podder, Fiona Skerman
Let be the set of rooted trees containing an infinite binary subtree starting at the root. This set satisfies the metaproperty that a tree belongs to it if and only i…
Modularity of Erdős-Rényi random graphs
Colin McDiarmid, Fiona Skerman
For a given graph , each partition of the vertices has a modularity score, with higher values indicating that the partition better captures community structure in . The modul…
The parameterised complexity of computing the maximum modularity of a graph
Kitty Meeks, Fiona Skerman
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…
K-cut on paths and some trees
Xing Shi Cai, Luc Devroye, Cecilia Holmgren +1
We define the (random) -cut number of a rooted graph to model the difficulty of the destruction of a resilient network. The process is as the cut model of Meir and Moon except n…
Assigning times to minimise reachability in temporal graphs
Jessica Enright, Kitty Meeks, Fiona Skerman
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 informa…
Inversions in split trees and conditional Galton--Watson trees
Xing Shi Cai, Cecilia Holmgren, Svante Janson +2
We study , the number of inversions in a tree with its vertices labeled uniformly at random, which is a generalization of inversions in permutations. We first show that t…
Modularity of regular and treelike graphs
Colin McDiarmid, Fiona Skerman
Clustering algorithms for large networks typically use modularity values to test which partitions of the vertex set better represent structure in the data. The modularity of a grap…
Guessing Numbers of Odd Cycles
Ross Atkins, Puck Rombach, Fiona Skerman
For a given number of colours, , the guessing number of a graph is the base logarithm of the size of the largest family of colourings of the vertex set of the graph such tha…
Avoider-Enforcer star games
Andrzej Grzesik, Mirjana Mikalački, Zoltán Lóránt Nagy +3
In this paper, we study Avoider-Enforcer games played on the edge set of the complete graph on vertices. For every constant we analyse the -star game, wh…
Degree sequences of random digraphs and bipartite graphs
Brendan D. McKay, Fiona Skerman
We investigate the joint distribution of the vertex degrees in three models of random bipartite graphs. Namely, we can choose each edge with a specified probability, choose a speci…