Modularity Maximization for Graphons
From MaRDI portal
Small world graphs, complex networks (graph-theoretic aspects) (05C82) Applications of graph theory (05C90) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Programming involving graphs or networks (90C35) Clustering in the social and behavioral sciences (91C20) Applications of graph theory to circuits and networks (94C15)
Abstract: 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.
Recommendations
Cites work
- A Simplex Method for Function Minimization
- An algorithm with guaranteed convergence for finding a zero of a function
- Co-clustering separately exchangeable network data
- Communities in Networks
- Community detection and stochastic block models: recent developments
- Community detection in temporal multilayer networks, with an application to correlation networks
- Concentration and regularization of random graphs
- Connected components in random graphs with given expected degree sequences
- Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
- Core-periphery structure in networks
- Estimating network edge probabilities by neighbourhood smoothing
- Fast unfolding of communities in large networks
- Finite state graphon games with applications to epidemics
- Hypergraphs for predicting essential genes using multiprotein complex data
- Impact of regularization on spectral clustering
- Information theoretic measures for clusterings comparison: variants, properties, normalization and correction for chance
- Large networks and graph limits
- Latent Space Approaches to Social Network Analysis
- Limits of dense graph sequences
- Limits of randomly grown graph sequences
- Local linear graphon estimation using covariates
- Matrix Completion From a Few Entries
- Matrix estimation by universal singular value thresholding
- Modularity of Erdős-Rényi random graphs
- Networks
- Poisson approximation of subgraph counts in stochastic block models and a graphon model
- Power network dynamics on graphons
- Random walks on dense graphs and graphons
- Rate-optimal graphon estimation
- Relating modularity maximization and stochastic block models in multilayer networks
- Representations for partially exchangeable arrays of random variables
- Sparse graphs using exchangeable random measures
- Statistical inference on random dot product graphs: a survey
- Statistical mechanics of complex networks
- Stochastic block models are a discrete surface tension
- Uncovering space-independent communities in spatial networks
- What is \dots a graphon?
- When are networks truly modular?
Cited in
(7)- A locally optimal hierarchical divisive heuristic for bipartite modularity maximization
- Generalized modularity matrices
- Improving heuristics for network modularity maximization using an exact algorithm
- scientific article; zbMATH DE number 7378595 (Why is no real title available?)
- scientific article; zbMATH DE number 6180551 (Why is no real title available?)
- On Inference for Modularity Statistics in Structured Networks
- The shortest-path distance on graphons
This page was built for publication: Modularity Maximization for Graphons
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6038778)
