A framework for second order eigenvector centralities and clustering coefficients

Tools

Arrigo, Francesca and Higham, Desmond and Tudisco, Francesco (2020) A framework for second order eigenvector centralities and clustering coefficients. Proceedings of the Royal Society A: Mathematical Physical and Engineering Sciences, 476 (2236). ISSN 1471-2962 (https://doi.org/10.1098/rspa.2019.0724)

[thumbnail of Arrigo-etal-PRSA-MPES-2020-A-framework-for-second-order-eigenvector-centralities]
Preview
 Text. Filename: Arrigo_etal_PRSA_MPES_2020_A_framework_for_second_order_eigenvector_centralities.pdf
Final Published Version
License: Creative Commons Attribution 4.0 logo
Download (1MB)| Preview

Abstract

We propose and analyse a general tensor-based framework for incorporating second-order features into network measures. This approach allows us to combine traditional pairwise links with information that records whether triples of nodes are involved in wedges or triangles. Our treatment covers classical spectral methods and recently proposed cases from the literature, but we also identify many interesting extensions. In particular, we define a mutually reinforcing (spectral) version of the classical clustering coefficient. The underlying object of study is a constrained nonlinear eigenvalue problem associated with a cubic tensor. Using recent results from nonlinear Perron–Frobenius theory, we establish existence and uniqueness under appropriate conditions, and show that the new spectral measures can be computed efficiently with a nonlinear power method. To illustrate the added value of the new formulation, we analyse the measures on a class of synthetic networks. We also give computational results on centrality and link prediction for real-world networks.

ORCID iDs

Arrigo, Francesca ORCID logoORCID: https://orcid.org/0000-0001-5473-7284, Higham, Desmond and Tudisco, Francesco;
CORE (COnnecting REpositories)