27 citations · 73 across the 20 of their papers we have counts for
11 papers · 1 filter
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…
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…
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…
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…
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…
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…