Total variation based community detection using a nonlinear optimization approach
SIAM Journal on Applied Mathematics, vol. 80, pp. 1392–1419, 2020
Maximizing the modularity of a network is a successful tool to identify an important community of nodes. However, this combinatorial optimization problem is known to be NP-hard. Inspired by recent nonlinear modularity eigenvector approaches, we introduce the modularity total variation $TV_Q$ and show that its …
The expected adjacency and modularity matrices in the degree corrected stochastic block model
Special Matrices, vol. 6, pp. 110–121, 2018
We provide explicit expressions for the eigenvalues and eigenvectors of matrices that can be written as the Hadamard product of a block partitioned matrix with constant blocks and a rank one matrix. Such matrices arise as the expected adjacency or modularity matrices in certain random graph models that are widely used …
Modularity bounds for clusters located by leading eigenvectors of the normalized modularity matrix
Journal of Mathematical Inequalities, vol. 11, pp. 701–714, 2017
Nodal theorems for generalized modularity matrices ensure that the cluster located by the positive entries of the leading eigenvector of various modularity matrices induces a connected subgraph. In this paper we obtain lower bounds for the modularity of that set of nodes showing that, under certain conditions, the …
A modularity based spectral method for simultaneous community and anti-community detection
Linear Algebra and its Applications, vol. 542, pp. 605–623, 2018
In a graph or complex network, communities and anti-communities are node sets whose modularity attains extremely large values, positive and negative, respectively. We consider the simultaneous detection of communities and anti-communities, by looking at spectral methods based on various matrix-based definitions of the …
Community detection in networks via nonlinear modularity eigenvectors
SIAM Journal on Applied Mathematics, vol. 78, pp. 2393–2419, 2018
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 …
Localization of dominant eigenpairs and planted communities by means of Frobenius inner products
Czechoslovak Mathematical Journal, vol. 66, pp. 881–893, 2016
We propose a new localization result for the leading eigenvalue and eigenvector of a symmetric matrix $A$. The result exploits the Frobenius inner product between $A$ and a given rank-one landmark matrix $X$. Different choices for $X$ may be used, depending on the problem under investigation. In particular, we show …
Generalized modularity matrices
Linear Algebra and its Applications, vol. 502, pp. 327–345, 2016
Various modularity matrices appeared in the recent literature on network analysis and algebraic graph theory. Their purpose is to allow writing as quadratic forms certain combinatorial functions appearing in the framework of graph clustering problems. In this paper we put in evidence certain common traits of various …
An algebraic analysis of the graph modularity
SIAM Journal on Matrix Analysis and Applications, vol. 35, pp. 997–1018, 2014
One of the most relevant tasks in network analysis is the detection of community structures, or clustering. Most popular techniques for community detection are based on the maximization of a quality function called modularity, which in turn is based upon particular quadratic forms associated to a real symmetric …