Community detection in networks via nonlinear modularity eigenvectors

F. Tudisco, P. Mercado, M. Hein

Research output: Working paper

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 \textit{module} and a set that maximizes Q is thus called \textit{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 M. We show that extremal eigenvalues of M 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 \textit{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.
LanguageEnglish
Place of PublicationIthaca, N.Y.
Number of pages23
Publication statusPublished - 18 Aug 2017

Fingerprint

Community Detection
Modularity
Eigenvector
Module
Eigenvalue
Linear Relaxation
Q-function
Ascent
Community Structure
M-matrix
Vertex of a graph
Monotonic
Maximise
Approximation
Operator

Keywords

  • optimisation and control
  • machine learning
  • information networks

Cite this

Tudisco, F., Mercado, P., & Hein, M. (2017). Community detection in networks via nonlinear modularity eigenvectors. Ithaca, N.Y.
Tudisco, F. ; Mercado, P. ; Hein, M. / Community detection in networks via nonlinear modularity eigenvectors. Ithaca, N.Y., 2017.
@techreport{430ad260db3c402a837e41a66afe8829,
title = "Community detection in networks via nonlinear modularity eigenvectors",
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 \textit{module} and a set that maximizes Q is thus called \textit{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 M. We show that extremal eigenvalues of M 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 \textit{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.",
keywords = "optimisation and control, machine learning, information networks",
author = "F. Tudisco and P. Mercado and M. Hein",
year = "2017",
month = "8",
day = "18",
language = "English",
type = "WorkingPaper",

}

Tudisco, F, Mercado, P & Hein, M 2017 'Community detection in networks via nonlinear modularity eigenvectors' Ithaca, N.Y.

Community detection in networks via nonlinear modularity eigenvectors. / Tudisco, F.; Mercado, P.; Hein, M.

Ithaca, N.Y., 2017.

Research output: Working paper

TY - UNPB

T1 - Community detection in networks via nonlinear modularity eigenvectors

AU - Tudisco, F.

AU - Mercado, P.

AU - Hein, M.

PY - 2017/8/18

Y1 - 2017/8/18

N2 - 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 \textit{module} and a set that maximizes Q is thus called \textit{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 M. We show that extremal eigenvalues of M 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 \textit{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.

AB - 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 \textit{module} and a set that maximizes Q is thus called \textit{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 M. We show that extremal eigenvalues of M 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 \textit{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.

KW - optimisation and control

KW - machine learning

KW - information networks

UR - https://arxiv.org/abs/1708.05569

M3 - Working paper

BT - Community detection in networks via nonlinear modularity eigenvectors

CY - Ithaca, N.Y.

ER -

Tudisco F, Mercado P, Hein M. Community detection in networks via nonlinear modularity eigenvectors. Ithaca, N.Y. 2017 Aug 18.