A framework for second order eigenvector centralities and clustering coefficients

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.

References in corpus (21)

• Community structure in social and biological networks
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• The structure of scientific collaboration networks
• Link Prediction in Complex Networks: A Survey
• Hierarchical structure and the prediction of missing links in networks
• Higher-order organization of complex networks
• Simplicial models of social contagion
• A roadmap for the computation of persistent homology
• Simplicial Closure and higher-order link prediction
• Fuzzy communities and the concept of bridgeness in complex networks
• Triadic closure as a basic generating mechanism of communities in complex networks
• Clustering and Synchronization of Oscillator Networks
• Higher-order clustering in networks
• Tensor Spectral Clustering for Partitioning Higher-order Network Structures
• Node and layer eigenvector centralities for multiplex networks
• Learning Role-based Graph Embeddings
• The Perron-Frobenius theorem for multi-homogeneous mappings
• A unifying Perron-Frobenius theorem for nonnegative tensors via multi-homogeneous maps
• Seeded PageRank Solution Paths
• Motif and Hypergraph Correlation Clustering

Cited by in corpus (4)

• Nonlocal PageRank
• Higher-order Network Analysis Takes Off, Fueled by Classical Ideas and New Data
• Quantifying the structural stability of simplicial homology
• A nonlinear diffusion method for semi-supervised learning on hypergraphs