centrality_x_degree: X-degree centrality

In cograph: Analysis and Visualization of Complex Networks

X-degree centrality

Description

Computes Torres et al.'s X-degree (equation 3.15):

Xdeg(i) = (\sum_{j\in N(i)}(d_j-1))^2 - \sum_{j\in N(i)}(d_j-1)^2.

Degrees are measured in the original simple undirected graph. The score counts oriented nonbacktracking walks of four edges whose middle vertex is i. Walks can revisit a vertex provided they do not immediately reverse an edge. It is also the sum of entries of the paper's matrix DFE, where D, F and E are blocks of the nonbacktracking matrix around i.

Usage

centrality_x_degree(x, ...)

Arguments

x	Network input accepted by centrality.
...	Additional arguments to centrality. normalized = TRUE divides scores by their maximum; an all-zero result stays zero.

Details

Uses the simple undirected skeleton: direction, weights, mode, inversion and cutoff do not affect results. Loops are removed and parallel edges count once. This projection is a cograph convention extending the published simple, unweighted, undirected domain. Isolates and leaves score zero; every vertex of a star also scores zero. Empty graphs return no scores. Disconnected components are independent before maximum normalization. These cases follow directly from the local formula.

Native arithmetic accumulates nonnegative pair products instead of subtracting two squares. Aggregation takes O(n+m) time after neighbor construction; the current dense skeleton conversion uses O(n squared) time and memory. This is a score on the supplied graph, not the paper's iterative node-removal immunization algorithm. Agreement with the author function and matrix definition does not establish immunization efficacy, exact eigendrop prediction or an unconditional spectral upper bound.

Value

Named numeric vector in input node order.

References

Torres, L., Chan, K. S., Tong, H., & Eliassi-Rad, T. (2021). Nonbacktracking Eigenvalues under Node Removal: X-Centrality and Targeted Immunization. SIAM Journal on Mathematics of Data Science, 3(2), 656-675. \Sexpr[results=rd]{tools:::Rd_expr_doi("10.1137/20M1352132")}.

Examples

centrality_x_degree(igraph::make_graph("Zachary"))

cograph documentation built on Sept. 30, 2026, 5:08 p.m.