### Abstract

Language | English |
---|---|

Place of Publication | Ithaca, N.Y. |

Number of pages | 23 |

Publication status | Published - 18 Aug 2017 |

### Fingerprint

### Keywords

- optimisation and control
- machine learning
- information networks

### Cite this

*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.

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 -