Laplacian-based Semi-Supervised Learning in Multilayer Hypergraphs by Coordinate Descent
EURO Journal on Computational Optimization, 2023
Graph Semi-Supervised learning is an important data analysis tool, where given a graph and a set of labeled nodes, the aim is to infer the labels to the remaining unlabeled nodes. In this paper, we start by considering an optimization-based formulation of the problem for an undirected graph, and then we extend this …
A Variance-aware Multiobjective Louvain-like Method for Community Detection in Multiplex Networks
Journal of Complex Networks, 2022
In this paper, we focus on the community detection problem in multiplex networks, i.e., networks with multiple layers having same node sets and no inter-layer connections. In particular, we look for groups of nodes that can be recognized as communities consistently across the layers. To this end, we propose a new …
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 …
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 …