DegreePunishment is a degree-based heuristic for identifying influential nodes in a network [2]. The central idea is that once a node \(i\) is selected as a seed, it should “punish” or restrict the selection of its neighbors in the subsequent steps. DegreePunishment iteratively performs the following steps:


  1. Compute the degree \(d_i\) of each node \(i\) and initialize \(dp_i = d_i\).

  2. Select the node \(i\) with the largest \(dp_i\) and add it to the seed set. The punishment that node \(i\) imposes on node \(j\) is calculated as \[ p_{ij} = d_i \sum_{h=1}^{r} (A^h)_{ij} \, ω^h, \] where \(r\) defines the radius of influence (maximum path length) and \(ω\) is a weakening factor. The value of \(dp_j\) is then updated for each node \(j\) as \[ dp_j = d_j - \sum_{i \neq j} p_{ij} \, σ_i, \] where \(σ_i\) is an indicator function such that \(σ_i = 1\) if node \(i\) has already been selected as a seed, and \(σ_i = 0\) otherwise.

  3. Repeat step 2 until \(k\) nodes have been selected for the seed set.


Due to computational complexity, Wang et al. [2] restrict the punishment to paths of length \(r \le 2\) and suggest using \(ω = β_c\), where \(β_c\) is the spreading threshold of the graph \(G\).

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] Wang, X., Su, Y., Zhao, C., & Yi, D. (2016). Effective identification of multiple influential spreaders by DegreePunishment. Physica A: Statistical Mechanics and its Applications, 461, 238-247. doi: 10.1016/j.physa.2016.05.020.