A framework for second-order eigenvector centralities and clustering coefficients

DOI10.1098/RSPA.2019.0724zbMATH Open1472.65043arXiv1910.12711OpenAlexW2982165638WikidataQ94601096 ScholiaQ94601096MaRDI QIDQ5160897FDOQ5160897

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)

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.

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

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

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)

Cites Work

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

Cited In (7)

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

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)