Modularity and partially observed graphs

MaRDI QIDQ6504861arXivFDO

Authors Colin McDiarmid, Fiona Skerman

Published in arXiv

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^{\prime }$ 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^{\ast }(G^{\prime })geq{q}^{\ast }(G)-varepsilon$ with probability at least $1-varepsilon$, as long as the expected number edges in $G^{\prime }$ is large enough. Similarly, $q^{\ast }(G^{\prime })leq{q}^{\ast }(G)+varepsilon$ with probability at least $1-varepsilon$, under the stronger condition that the expected average degree in $G^{\prime }$ is large enough. Further, under this stronger condition, finding a good partition for $G^{\prime }$ helps us to find a good partition for $G$.

This page was built for publication: Modularity and partially observed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6504861)