CS Paper Radar

Vertex-subgraph eigenvector centrality for connected induced subgraphs

Qingying Zhang, Haotian Zeng, Changjiang Bu

cs.SI ·submitted 2026-11-04 14:03 UTC · v1
theory

Abstract

Eigenvector centrality evaluates the importance of vertices through adjacency relations, while higher-order subgraph structures provide additional information for centrality analysis. This motivates the simultaneous evaluation of vertices and subgraphs within a unified spectral framework. In this paper, we propose vertex-subgraph eigenvector centrality (VSC), which jointly determines the centralities of vertices and connected induced subgraphs of order three. The vertex centrality depends on the centralities of the subgraphs containing it and those of the other vertices in these subgraphs, whereas the subgraph centrality depends on the centralities of its constituent vertices. To distinguish induced paths P3 from triangles K3, the capacity of each subgraph is defined as its number of edges. The resulting coupled nonlinear eigenvalue equations are represented by a fourth-order symmetric nonnegative tensor. We prove that this tensor is weakly irreducible for every connected graph with at least three vertices, which guarantees the existence and uniqueness, up to scaling, of a positive Perron eigenvector. Numerical experiments on four real-world networks compare VSC with classical centrality measures and show that capacity weighting has a greater effect on subgraph rankings than on vertex rankings.

Comment
24 pages, 5 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Semi-Monotonicity for Spectral Centrality Measures

cs.SI ·2026-09-21 ·Paolo Boldi, Davide D'Ascenzo, Flavio Furia, Sebastiano Vigna
theory similarity 0.69
Abstract

Score monotonicity and rank monotonicity are properties describing the behavior of a centrality measure when an arc is added to a network: the former requires that the score of the target of the arc should increase, the latter that its importance with respect to the remaining nodes should not deteriorate. While in directed networks almost all classical centrality measures satisfy both properties, in undirected networks they fail for most measures: adding an edge can reduce the score or the rank of one of its endpoints. Semi-monotonicity is a recently introduced weaker property for undirected networks, requiring that at least one of the two endpoints of the new edge enjoys monotonicity, and it is known to hold for closeness, harmonic centrality, distance-decay centralities and betweenness. In this paper we study semi-monotonicity for three classical spectral centrality measures: eigenvector centrality, Katz's index, and PageRank. We prove that all of them are strictly rank semi-monotone on connected undirected graphs, and that all of them are also score semi-monotone, (the only exception being eigenvector centrality when scores are normalized by projecting the constant vector on the dominant eigenspace, for which we provide a counterexample). In particular, adding an edge can never decrease the PageRank of both its endpoints, which answers a question left open in previous work.

0.19

Spectral Efficiency Centrality: An Efficient Spectral Approach for Influential Node Identification in Temporal Networks

cs.SI ·2026-08-14 ·Aksa Urooj, Iqra Altaf Gillani
similarity 0.64
Abstract · 23 pages, 16 figures, 11 tables, journal paper

Centrality measures play a vital role in identifying influential nodes in evolving networks. While existing temporal centrality measures primarily rely on local structural properties or temporal paths, spectral node-removal approaches have been largely limited to static networks. To bridge this gap, we propose Spectral Efficiency Centrality (SEC), a temporal spectral centrality framework that quantifies node importance by evaluating the change in spectral radius caused by node removal across temporal snapshots. By capturing the global structural influence of nodes throughout network evolution, SEC identifies nodes that are critical for preserving the structural connectivity and efficiency of temporal networks. To improve computational scalability, we further develop an efficient approximation, ASEC, based on Perron-Frobenius theory and first-order eigenvalue perturbation. ASEC requires only the leading eigenpair and avoids repeated eigendecomposition, making it suitable for large temporal networks. Extensive experiments on multiple real-world temporal datasets demonstrate that SEC and ASEC outperform existing baseline centrality measures in identifying influential nodes under SI, SIS, and IC diffusion models. Statistical significance and robustness analyses further confirm their effectiveness, while ASEC offers a computationally efficient solution for large-scale temporal networks.

0.10

Structural Properties of DomiRank Centrality: Symmetry Axioms, an Entropy Bound, and Spectral Interpolation

cs.SI math.CO ·2026-09-09 ·Yingying Zhang, Chengye Zhao
theory similarity 0.63
Abstract · 63 pages, 15 figures, 3 tables, 38 references

DomiRank is a node-importance algorithm for unweighted networks, defined by a dynamical model governed by a competition-strength parameter, a dominance threshold, and a decay rate. We establish three structural results. First, on symmetry. Automorphism-related vertices share the same DomiRank value, and a graph whose values are pairwise distinct must be asymmetric. The orbit count bounds the number of distinct values, and regular and vertex-transitive graphs admit closed forms. Second, on entropy. The maximum of the DomiRank entropy over connected graphs, log_2 N, is attained if and only if the graph is regular. The initial entropy derivative is the degree-log-degree edge covariance, making the decrease rigorous near vanishing competition for structurally disassortative graphs, and an assortative counterexample shows it does not extend to all graphs; a sufficient-condition theorem and a refined conjecture cover the rest. Third, on spectrum. The normalized distribution is sigma-invariant if and only if the degree vector is an adjacency-matrix eigenvector. The parameter sigma interpolates continuously between degree and smallest-eigenvector centrality within the resolvent (Bonacich-type) family, its sensitivity being a second-order suppression operator on the degree vector. Graph transformations are also characterized, including the m-product. Experiments on four real networks and synthetic families up to 10^4 vertices confirm the interpolation and exhibit monotone entropy decrease, continuous ranking interpolation, decaying positive fraction and ranking reversals; where the positive fraction has decayed far from one, the limit describes the solution vector rather than the induced ranking. DomiRank is thus a tunable complement to principal-eigenvector centrality. A companion study quantifies how much of its task-level edge over a degree baseline survives degree correction.

0.59

A Cheeger Inequality for Hypergraphs and Its Applications

cs.DS math.CO ·2026-09-14 ·Raj Kamal, Amitabha Bagchi
similarity 0.62
Abstract

Hypergraphs provide a natural framework for modeling higher-order relationships, but the development of spectral techniques with provable guarantees for general non-uniform hypergraphs remains challenging. Building on Banerjee's normalized adjacency matrix and Spiro's averaging-based diffusion framework, we develop a spectral framework for non-uniform hypergraphs and establish Cheeger's inequality for their conductance. A fundamental result in the spectral theory of hypergraphs asserts that, for every non-covering hypergraph, the second-smallest eigenvalue of its normalized Laplacian is at most one. This spectral characterization yields an improved Cheeger's inequality for non-covering hypergraphs, and we show that the resulting inequality is tight on both sides using cycle and cube hypergraphs. Our framework further yields higher-order Cheeger inequalities and provides theoretical guarantees for Fiedler's spectral partitioning algorithm, all in the setting of hypergraphs. Finally and most notably, we construct a new family of optimal hypergraph expanders that is tight for the Alon-Boppana bound.

0.24

Spectral Fingerprints of Street-Network Morphology: A Size-Adjusted Graph-Laplacian Descriptor of Urban Fabric

cs.SI physics.soc-ph ·2026-08-17 ·Piotr C. Kaminski
similarity 0.55
Abstract · 18 pages, 7 figures. Under review at Journal of Complex Networks (Oxford University Press)

Decades of space-syntax research have established that the topology of the street network conditions movement, co-presence and urban activity. The standard vocabulary for this -- integration, choice and connectivity -- summarises each street's position as a scalar centrality, yet two streets with identical centrality can sit in radically different morphological fabric. We introduce a compact, comparable, machine-learning-ready encoding of that local fabric: the spectral fingerprint, a fixed-dimensional kernel-density representation of the graph-Laplacian eigenvalue distribution of each node's k-hop ego subgraph, computed on the COINS dual graph of the street network. From it we derive two interpretable scalar readouts: the Mesh Index (MI), a normalised spectral entropy, and the Connectivity Resilience Index (CRI), the algebraic connectivity (Fiedler value). Both are corrected for an ego-subgraph-size confound that dominates raw spectral statistics. Applied to the full street network of Poznan, Poland (1,908 continuity-based strokes), the descriptor is robust to its encoding hyperparameters (spectral resolution and kernel bandwidth; Spearman rho >= 0.98) while remaining scale-dependent in its neighbourhood radius. The size adjustment leaves the Mesh Index near-orthogonal to integration (r = 0.06), carrying information classical centrality does not. The fingerprint separates morphological tissue types without supervision, and the Mesh Index is associated with the functional diversity of street-adjacent activity at the neighbourhood scale (r ~ 0.19, on open OpenStreetMap data). We delineate the method's scope honestly: it characterises what kind of activity a street's position affords, not the price that activity commands. It offers an information-theoretic morphological descriptor that complements space syntax and is directly consumable by modern graph-learning pipelines.

0.25

Spectral Methods for the Complexity of Planar Graph Homomorphisms

cs.CC ·2026-09-28 ·Ashwin Maran, Jin-Yi Cai, Zhuxiao Tang
theory similarity 0.55
Abstract · 35 pages, 2 figures

We explore the frontier beyond the recently discovered barrier represented by the \emph{quantum automorphism group} $qut(M)$ in the classification theory of planar graph homomorphisms $PlGH(M)$. We show that analyzing the spectral relations of $M$ can prove \#P-hardness when traditional vertex separation and domain-reduction methods with planar edge gadgets provably fail due to the $\qut(M)$ barrier. We prove two criteria of \#P-hardness for $PlGH(M)$: a spectral criterion and a determinant criterion. It is known that the core problem for the classification of $PlGH(M)$ for nonnegative matrices $M$ is for positive definite entry-wise positive matrices. We use the spectral criterion to show that $PlGH(M)$ is \#P-hard for all circulant matrices of prime order $q \ge 3$, while for $q=2$ it is precisely the matchgate case and is P-time computable by the FKT algorithm (for planar perfect matching). We also prove a complexity dichotomy for $\PlGH$ problems defined by tensor products of 2 by 2 matrices. This gives a complete complexity classification for this class of matrices, and the FKT algorithm together with a holographic transformation is \emph{universal}---every $PlGH(M)$ is either (1) P-time computable over all graphs, or (2) \#P-hard in general but P-time computable over planar graphs, or (3) \#P-hard over planar graphs; furthermore, $PlGH(M)$ in (2) consists of precisely those computable by FKT with a holographic transformation.

0.30

Assortativity and the Distribution of Spectral Gaps in Directed Networks

cs.SI ·2026-10-30 ·Sreerag Puravankara, Vipin P. Veetil
theory similarity 0.55
Abstract

This paper studies how the distribution of spectral gaps of a weighted directed network varies with its assortativity. We prove that the sum of the distances of each of the eigenvalues from the Perron root along the real axis, which we call the `spectral depth', decreases as the network is rewired to be less assortative. The result is conditional on the network's Perron vectors ordering the rewired vertices in the same way as their strengths do. We also develop a method to determine whether a particular spectral gap contracts or expands under a rewiring that changes the network's assortativity. It turns out that the direction of any one gap depends on far more than the network's assortativity. In computational experiments on heavy-tailed networks, disassortative rewiring lowers the spectral depth by about two fifths, contracts most strongly the gaps in the middle of the spectrum, and collapses a growing part of the spectrum to zero. The experiments also show that a sequence of disassortative rewirings tends to narrow the first spectral gap, while a sequence of assortative rewirings widens it.

0.24

Provable Guarantees for Spectral Structured Prediction

cs.LG ·2026-09-16 ·Violet Zheng, Jean Honorio
similarity 0.54
Abstract

Structured prediction is the simultaneous prediction of multiple labels, and is widely used in various fields, such as natural language processing and computer vision. In this paper, we study binary node label recovery on signed graphs with edge-flip noise, a model introduced by (Globerson et al., 2015), via a simple spectral method that decodes node labels from the signs of the principal eigenvector of the noisy signed adjacency matrix. We develop graph structure-agnostic theoretical guarantees for approximate inference of node labels as well as guarantees for maximum angle deviation with respect to the ground truth node labels. By leveraging tools from matrix concentration theory and eigenvector perturbation analysis, we derive new concentration inequalities that explicitly quantify the effect of the spectral gap of the adjacency matrix, number of nodes, degree distribution, and noise level. As a corollary, we relate our general results to the Cheeger constant and provide results for different classes of graphs. We perform several synthetic experiments to validate our theory. To the best of our knowledge, we are the first to provide theoretical guarantees for the spectral-based approach. As a byproduct of our analysis, we derive technical results that might be of independent interest and useful for other machine learning problems.

0.31