A framework for second-order eigenvector centralities and clustering coefficients

DOI10.1098/RSPA.2019.0724MaRDI QIDQ5160897zbMATH OpenOpenAlexWikidataFDO

Authors Francesca Arrigo, Desmond J. Higham, Francesco Tudisco

Publication date 29 October 2021

Published in Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1910.12711

zbMATH Keywords

tensorclustering coefficienthypergraphlink predictionPerron-Frobenius theorystatistical physicsapplied mathematicscomputational mathematicshigher-order network analysis

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Multilinear algebra, tensor calculus (15A69) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Social networks; opinion dynamics (91D30)

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.

Recommendations

• Three hypergraph eigenvector centralities
• Local estimates for eigenvector-like centralities of complex networks
• Some New Results on the Eigenvector Centrality
• Centrality measures in networks
• Eigenvector centrality of nodes in multiplex networks

Cites work

• A Unifying Perron--Frobenius Theorem for Nonnegative Tensors via Multihomogeneous Maps
• Bistability through triadic closure
• Classes of preferential attachment and triangle preferential attachment models with power-law spectra
• Collective dynamics of `small-world' networks
• Community structure in social and biological networks
• Computational topology. An introduction
• Experimental and Efficient Algorithms
• Information diffusion in social networks: friendship paradox based models and statistical inference
• Motif and Hypergraph Correlation Clustering
• Networks. An introduction.
• Node and Layer Eigenvector Centralities for Multiplex Networks
• Nonlinear Perron-Frobenius theory
• PageRank beyond the web
• Predicting triadic closure in networks using communicability distance functions
• Seeded PageRank solution paths
• The Perron--Frobenius Theorem for Multihomogeneous Mappings
• The Perron-Frobenius theorem for homogeneous, monotone functions
• The structure of scientific collaboration networks
• Three hypergraph eigenvector centralities
• Topology and data
• When local and global clustering of networks diverge

Cited in

(7)

• The structure and dynamics of networks with higher order interactions
• Nonlinear Perron--Frobenius Theorems for Nonnegative Tensors
• Quantifying the structural stability of simplicial homology
• Core-Periphery Detection in Hypergraphs
• Ergodicity Coefficients for Higher-Order Stochastic Processes
• Nonlocal pagerank
• Hitting times for second-order random walks

This page was built for publication: A framework for second-order eigenvector centralities and clustering coefficients

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5160897)