centrality_ked: KED method centrality

In cograph: Analysis and Visualization of Complex Networks

KED method centrality

Description

The KED method of Chen, Xiao, Zeng and Zhang combines how many local paths leave a node with how diverse they are: KED(i)=k_i\,(1+H_i)\,\exp(K_i/N), where K_i=\sum_{j\in N(i)}k_j is the sum of the neighbors' degrees, H_i=\bigl(\sum_{j\in N(i)}-p_j\log p_j\bigr)/\log k_i with p_j=k_j/K_i is the normalized entropy of the neighbor-degree distribution, and N is the number of nodes in the whole graph. The source calls K_i the local path number and H_i the path diversity: two nodes of equal degree with equally many second neighbors are separated by how evenly their neighbors carry those paths.

Usage

centrality_ked(x, ...)

Arguments

x	Network input accepted by centrality.
...	Additional arguments to centrality.

Details

H_i is a ratio of two logarithms in the same base – equation (2) divides the entropy by the entropy of the uniform distribution on k_i outcomes – so the base cancels and no choice of base is being made. H_i lies in [0,1] and is exactly one when the neighbor degrees are all equal, which is the source's 1\le E_i\le 2.

The measure takes no parameters. Equation (6) is a bare product; the exponents \alpha and \beta the Centrality Zoo attributes to Chen et al. appear nowhere in the paper, and none is offered here.

Two degenerate cases are cograph decisions, not the source's. A node with one neighbor has p=1, so its entropy is zero, and its normalizer \log k_i is zero too: H_i is 0/0 and is written as zero, giving E_i=1. That is the value approached from k_i=2 as one neighbor's share vanishes, and the one that gives a node with a single path the least path diversity; the alternative reading of 0/0 as "the entropy equals its own maximum, so H=1" would double every leaf's score. An isolate has both sums empty; H_i is written as zero there as well, and the score is zero whatever finite E_i is chosen, because k_i multiplies the product. Empty graphs return no scores.

Raw scores are not comparable across graphs of different order. N in D_i is the vertex count of the whole network, as the source's own table 1 defines it, so adding a disconnected component – an isolate included – changes every score, and unlike a plain rescaling it can also change the ranking, because \exp(K_i/N) shrinks the large K_i more than the small.

The source's stated range 1\le D_i\le e is not general. It holds exactly when K_i\le N, which is true of the sparse toy networks of its figure 1 and false on dense graphs: every node of K_5 has K_i=16 against N=5, so D_i=e^{3.2}. cograph implements the formula, not the range claim. Scores can therefore be large; K_i/N\le (n-1)^2/n, so nothing overflows below about 710 vertices even on a complete graph, and an overflow beyond that raises an error rather than returning Inf.

This is not the Centrality Zoo's formula. Zoo section 2.215 writes c_{KED}(i)=k_i E_i^\alpha D_i^\beta with E_i=\bigl(\sum_{j}-p_j\log p_j\bigr)/\log k_i and D_i=\exp(K_i/\max_l K_l): it drops the 1+ from E_i and divides by the largest cluster degree instead of by N. On the source's own figure 1 that reading gives 13.5914 and 6.5672 where the paper prints 25.9187 and 19.2212, which cograph reproduces. The \max_l K_l denominator is a plausible misreading, since it makes the paper's stated 1\le D_i\le e hold, but it reproduces neither printed number. cograph implements the paper and offers no Zoo variant.

Uses the simple undirected unweighted skeleton, the source's undirected domain: either arc creates one edge, parallel edges count once and loops are removed. Edge weights, mode, cutoff and path-weight inversion are ignored. The source also defines a directed variant (its equation 3, replacing the neighborhood by the out-neighborhood and k_i by k_i^{out}); that variant is not implemented, so a directed input is symmetrized rather than being read as the paper's directed case. The source states no normalization; normalized = TRUE max-scales the finished vector as elsewhere in centrality. Cost is two sparse matrix-vector products, O(n + m).

Numerical verification establishes agreement with the two scores the source prints for its figure 1, not parity with author software, which does not exist, and not any claim about spreading performance.

Value

Named numeric vector in input node order.

References

Chen, D.-B., Xiao, R., Zeng, A. and Zhang, Y.-C. (2014). Path diversity improves the identification of influential spreaders. Europhysics Letters, 104(6), 68006. \Sexpr[results=rd]{tools:::Rd_expr_doi("10.1209/0295-5075/104/68006")}.

See Also

centrality_lnc and centrality_neighbor_distance for other neighbor-degree sums, centrality_entropy for a plain neighborhood entropy, and list_centralities for the catalogue.

Examples

# Every node of a ring has two neighbors of degree two, so the
# neighbor degrees are even, H is one and the score is 4 exp(4 / n)
centrality_ked(igraph::make_ring(8))

# A star: the center's neighbors are all leaves, so H is one again,
# and the center scores exactly 2 (n - 1) times a leaf, here 10
centrality_ked(igraph::make_star(6, mode = "undirected"))

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