Speaker
Description
The nodes in a network can be grouped into equivalence classes according to their connection patterns with other nodes, whether in the same group or different ones. This process, known as role extraction or block modelling, aims to produce a simplified, coarse-grained representation of a large, complex network. The first step in this task is to define a similarity criterion between pairs of nodes. This is achieved by constructing a similarity matrix, the entries of which quantify the similarity between all node pairs. Node groups are then identified by clustering the rows and columns of this matrix.
This work presents a novel node similarity measure designed specifically for directed networks. Our approach is based on random walks that proceed in both directions along the links to unveil network structures that are not apparent in the original data. The resulting similarity matrix is derived as the solution to a generalised Stein matrix equation, for which we present a provably convergent iterative method. To enhance scalability, we also develop a low-rank approximation of this iteration, which significantly reduces memory and computational demands. Theoretical analysis and experimental results on synthetic and real-world directed networks suggest that our similarity matrix achieves superior performance when solving block modelling tasks in directed networks where node degrees exhibit significant heterogeneity.
This work was supported by the Italian Ministry of University and Research through the PRIN Project 20227PCCKZ “Low Rank Structures and Numerical Methods in Matrix and Tensor Computations and their Applications”. The author is also affiliated with the INdAM-GNCS.
References
- D. Fasino, Role extraction by matrix equations and generalized random walks, arXiv:2502.12689, (2025)
