Community detection in networks via nonlinear modularity eigenvectors

DOI10.1137/17M1144143MaRDI QIDQ4683908zbMATHFDO

Authors Francesco Tudisco, Pedro Mercado, Matthias Hein

Publication date 26 September 2018

Published in SIAM Journal on Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.05569

zbMATH Keywords

community detectiongraph modularitynonlinear eigenvaluesCheeger inequalityspectral partitioning

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Deterministic network models in operations research (90B10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Particular nonlinear operators (superposition, Hammerstein, Nemytski?, Uryson, etc.) (47H30)

Abstract: Revealing a community structure in a network or dataset is a central problem arising in many scientific areas. The modularity function $Q$ is an established measure quantifying the quality of a community, being identified as a set of nodes having high modularity. In our terminology, a set of nodes with positive modularity is called a extit{module} and a set that maximizes $Q$ is thus called extit{leading module}. Finding a leading module in a network is an important task, however the dimension of real-world problems makes the maximization of $Q$ unfeasible. This poses the need of approximation techniques which are typically based on a linear relaxation of $Q$, induced by the spectrum of the modularity matrix $M$. In this work we propose a nonlinear relaxation which is instead based on the spectrum of a nonlinear modularity operator $mathcalM$. We show that extremal eigenvalues of $mathcalM$ provide an exact relaxation of the modularity measure $Q$, however at the price of being more challenging to be computed than those of $M$. Thus we extend the work made on nonlinear Laplacians, by proposing a computational scheme, named extit{generalized RatioDCA}, to address such extremal eigenvalues. We show monotonic ascent and convergence of the method. We finally apply the new method to several synthetic and real-world data sets, showing both effectiveness of the model and performance of the method.

Recommendations

• Total variation based community detection using a nonlinear optimization approach
• Revealing network communities with a nonlinear programming method
• A doubly nonnegative relaxation for modularity density maximization
• Community detection via an efficient nonconvex optimization approach based on modularity
• A DC Programming Approach for Finding Communities in Networks

Cites work

• scientific article; zbMATH DE number 5977361 (Why is no real title available?)
• scientific article; zbMATH DE number 46303 (Why is no real title available?)
• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• A first-order primal-dual algorithm for convex problems with applications to imaging
• A method based on total variation for network modularity optimization using the MBO scheme
• A nodal domain theorem and a higher-order Cheeger inequality for the graph \(p\)-Laplacian
• An Efficient Heuristic Procedure for Partitioning Graphs
• An algebraic analysis of the graph modularity
• An algorithm for drawing general undirected graphs
• Communities in Networks
• Complex graphs and networks
• Fast unfolding of communities in large networks
• First-principles multiway spectral partitioning of graphs
• Generalized modularity matrices
• Graph clustering
• Learning with submodular functions: a convex optimization perspective
• Modularity bounds for clusters located by leading eigenvectors of the normalized modularity matrix
• Networks. An introduction.
• On Finding Graph Clusterings with Maximum Modularity
• On the generalization of the Courant nodal domain theorem
• Predicting triadic closure in networks using communicability distance functions
• Spectrum of the 1-Laplacian and Cheeger's constant on graphs
• The University of Florida sparse matrix collection

Cited in

(14)

• Generalized \(K\)-core percolation in networks with community structure
• Eigenvector Computation and Community Detection in Asynchronous Gossip Models
• Semi-supervised Learning for Aggregated Multilayer Graphs Using Diffuse Interface Methods and Fast Matrix-Vector Products
• A doubly nonnegative relaxation for modularity density maximization
• Total variation based community detection using a nonlinear optimization approach
• Phase transitions in normalized cut of social networks
• Laplacian-based semi-supervised learning in multilayer hypergraphs by coordinate descent
• Stochastic block models are a discrete surface tension
• Simplified energy landscape for modularity using total variation
• A Nonlinear Spectral Method for Core--Periphery Detection in Networks
• An algebraic analysis of the graph modularity
• Nonlinear eigenproblems in data analysis: balanced graph cuts and the RatioDCA-Prox
• Revealing network communities with a nonlinear programming method
• Community discovery using nonnegative matrix factorization

Describes a project that uses

Uses Software

• SNAP
• SparseMatrix
• MNIST
• GenLouvain

This page was built for publication: Community detection in networks via nonlinear modularity eigenvectors

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