Community detection in networks via nonlinear modularity eigenvectors

DOI10.1137/17M1144143zbMATH Open1397.90089arXiv1708.05569MaRDI QIDQ4683908FDOQ4683908

Authors: Francesco Tudisco, Pedro Mercado, Matthias Hein 

Publication date: 26 September 2018

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

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.

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

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

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)

Cites Work

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

Cited In (14)

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

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)