# Modularity maximisation for graphons

arXiv: https://arxiv.org/abs/2101.00503 · HTML: https://mlsanity.com/paper/2101.00503/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 80 references that are in the map.
- First posted on arXiv 2 Jan 2021.

## Builds on (most cited first, 30 of 30)

- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [From Louvain to Leiden: guaranteeing well-connected communities](https://mlsanity.com/paper/1810.08473/) (2018)
- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Cooperative Game Theory Approaches for Network Partitioning](https://mlsanity.com/paper/1707.03587/) (2017)
- [Community detection in networks: A user guide](https://mlsanity.com/paper/1608.00163/) (2016)
- [Statistical inference on random dot product graphs: a survey](https://mlsanity.com/paper/1709.05454/) (2017)
- [The ground truth about metadata and community detection in networks](https://mlsanity.com/paper/1608.05878/) (2016)
- [Stochastic blockmodel approximation of a graphon: Theory and consistent estimation](https://mlsanity.com/paper/1311.1731/) (2013)
- [A Consistent Histogram Estimator for Exchangeable Graph Models](https://mlsanity.com/paper/1402.1888/) (2014)
- [Estimating network edge probabilities by neighborhood smoothing](https://mlsanity.com/paper/1509.08588/) (2015)
- [Impact of regularization on Spectral Clustering](https://mlsanity.com/paper/1312.1733/) (2013)
- [Concentration and regularization of random graphs](https://mlsanity.com/paper/1506.00669/) (2015)
- [A Comparative Analysis of Community Detection Algorithms on Artificial Networks](https://mlsanity.com/paper/1608.00763/) (2016)
- [Bayesian Models of Graphs, Arrays and Other Exchangeable Random Structures](https://mlsanity.com/paper/1312.7857/) (2013)
- [Network histograms and universality of blockmodel approximation](https://mlsanity.com/paper/1312.5306/) (2013)
- [Sparse graphs using exchangeable random measures](https://mlsanity.com/paper/1401.1137/) (2014)
- [Private Graphon Estimation for Sparse Graphs](https://mlsanity.com/paper/1506.06162/) (2015)
- [Centrality measures for graphons: Accounting for uncertainty in networks](https://mlsanity.com/paper/1707.09350/) (2017)
- [Revealing Network Structure, Confidentially: Improved Rates for Node-Private Graphon Estimation](https://mlsanity.com/paper/1810.02183/) (2018)
- [Graphons: A Nonparametric Method to Model, Estimate, and Design Algorithms for Massive Networks](https://mlsanity.com/paper/1706.01143/) (2017)
- [The many facets of community detection in complex networks](https://mlsanity.com/paper/1611.07769/) (2016)
- [Cover time for random walks on arbitrary complex networks](https://mlsanity.com/paper/1706.02356/) (2017)
- [Generalized communities in networks](https://mlsanity.com/paper/1505.07478/) (2015)
- [Different approaches to community detection](https://mlsanity.com/paper/1712.06468/) (2017)
- [Graphon-based sensitivity analysis of SIS epidemics](https://mlsanity.com/paper/1912.10330/) (2019)
- [A unified view of generative models for networks: models, methods, opportunities, and challenges](https://mlsanity.com/paper/1411.4070/) (2014)
- [Relating modularity maximization and stochastic block models in multilayer networks](https://mlsanity.com/paper/1804.01964/) (2018)
- [Stochastic Block Models are a Discrete Surface Tension](https://mlsanity.com/paper/1806.02485/) (2018)
- [Resolving structural variability in network models and the brain](https://mlsanity.com/paper/1306.2893/) (2013)
- [Null Models for Community Detection in Spatially-Embedded, Temporal Networks](https://mlsanity.com/paper/1407.6297/) (2014)

## Built on by (most cited first, 1 of 1)

- [Joint Network Topology Inference via a Shared Graphon Model](https://mlsanity.com/paper/2209.08223/) (2022)

## Abstract (arXiv)

Networks are a widely-used tool to investigate the large-scale connectivity structure in complex systems and graphons have been proposed as an infinite size limit of dense networks. The detection of communities or other meso-scale structures is a prominent topic in network science as it allows the identification of functional building blocks in complex systems. When such building blocks may be present in graphons is an open question. In this paper, we define a graphon-modularity and demonstrate that it can be maximised to detect communities in graphons. We then investigate specific synthetic graphons and show that they may show a wide range of different community structures. We also reformulate the graphon-modularity maximisation as a continuous optimisation problem and so prove the optimal community structure or lack thereof for some graphons, something that is usually not possible for networks. Furthermore, we demonstrate that estimating a graphon from network data as an intermediate step can improve the detection of communities, in comparison with exclusively maximising the modularity of the network. While the choice of graphon-estimator may strongly influence the accord between the community structure of a network and its estimated graphon, we find that there is a substantial overlap if an appropriate estimator is used. Our study demonstrates that community detection for graphons is possible and may serve as a privacy-preserving way to cluster network data.