The KED method is a local spreader ranking algorithm designed to identify influential nodes in large-scale social networks [2]. KED is based on the concept of path diversity , which quantifies the diversity of spreading paths originating from each node.
Let \(K_i\) denote the total degree of node \(i\)'s neighbors, i.e.,
\begin{equation*}
K_i = \sum_{j \in \mathcal{N}(i)} k_j,
\end{equation*}
where \(k_j\) is the degree of neighbor \(j\) and \(\mathcal{N}(i)\) is the set of neighbors of node \(i\). The centrality of node \(i\) is then defined as
\begin{equation*}
c_{\mathrm{KED}}(i) = k_i \, E_i^α \, D_i^β,
\end{equation*}
where:

  • \(k_i\) is the degree of node \(i\),
  • \(E_i = \frac{\sum_{j \in \mathcal{N}(i)} - p_j \log(p_j)}{\log(k_i)}\) is the local path diversity, with \(p_j = k_j / K_i\),
  • \(D_i = \exp\!\Big(\frac{K_i}{\max_l K_l}\Big)\) captures the contribution of the degrees of neighboring nodes,
  • \(α\) and \(β\) are tunable parameters that control the relative importance of path diversity \(E_i\) and neighbor influence \(D_i\).

Chen et al. [2] suggest using \(α = β = 1\), giving equal weight to path diversity and neighbor connectivity in the ranking.

References

[1] Shvydun, S. (2025). Zoo of Centralities: Encyclopedia of Node Metrics in Complex Networks. arXiv: 2511.05122 https://doi.org/10.48550/arXiv.2511.05122
[2] Chen, D. B., Xiao, R., Zeng, A., & Zhang, Y. C. (2014). Path diversity improves the identification of influential spreaders. Europhysics letters, 104(6), 68006. doi: 10.1209/0295-5075/104/68006.