Modularity and partially observed graphs
Preprint
Abstract
Suppose that there is an unknown underlying graph $G$ on a large vertex set, and we can test only a proportion of the possible edges to check whether they are present in $G$. If $G$ has high modularity, is the observed graph $G'$ likely to have high modularity? We see that this is indeed the case under a mild condition, in a natural model where we test edges at random. We find that $q^*(G') \geq q^*(G)-\varepsilon$ with probability at least $1-\varepsilon$, as long as the expected number edges in $G'$ is large enough. Similarly, $q^*(G') \leq q^*(G)+\varepsilon$ with probability at least $1-\varepsilon$, under the stronger condition that the expected average degree in $G'$ is large enough. Further, under this stronger condition, finding a good partition for $G'$ helps us to find a good partition for $G$. We also consider the vertex sampling model for partially observing the underlying graph: we find that for dense underlying graphs we may estimate the modularity by sampling constantly many vertices and observing the corresponding induced subgraph, but this does not hold for underlying graphs with a subquadratic number of edges. Finally we deduce some related results, for example showing that under-sampling tends to lead to overestimation of modularity.
Keywords
All Related Versions
This publication has 28 references indexed in Scilit:
- Expansion in supercritical random subgraphs of expanders and its consequencesRandom Structures & Algorithms, 2024
- Isoperimetric Inequalities and Supercritical Percolation on High-Dimensional GraphsCombinatorica, 2024
- Modularity in planted partition modelComputational Management Science, 2023
- Phase transition of degeneracy in minor-closed familiesAdvances in Applied Mathematics, 2023
- On the modularity of 3‐regular random graphs and random graphs with given degree sequencesRandom Structures & Algorithms, 2022
- Modularity of Erdős‐Rényi random graphsRandom Structures & Algorithms, 2020
- The Parameterised Complexity of Computing the Maximum Modularity of a GraphAlgorithmica, 2019
- Testability of minimum balanced multiway cut densitiesDiscrete Applied Mathematics, 2012
- Community detection in graphsPhysics Reports, 2010
- Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testingAdvances in Mathematics, 2008