The Generalized Degree Discount (GDD) is a degree‐discount heuristic for identifying a set of influential spreaders in a network [2]. It builds on the earlier DegreeDiscount method by introducing for each node a “status” (probability of not being influenced yet) and computing a generalized discounted degree that accounts not only for the number of non‐seed neighbours, but also for how covered those neighbours already are by selected seeds. In each step a node with the highest generalized discounted degree is selected as a spreader, and thereafter the effective degrees of its neighbors (and their neighbors) are updated to reflect the diminished marginal influence. The algorithm proceeds iteratively as follows:

  1. Compute the degree \(d_i\) of each node \(i\), and initialize \(t_i = 0\) and \(dd_i = d_i\), where \(t_i\) is the number of selected neighbors of \(i\) and \(dd_i\) is the discounted degree.
  2. Selection and update: select the node \(i\) with the largest \(dd_i\) and add it to the seed set \(S\). Then, for each 1-hop and 2-hop neighbor \(j\) of node \(i\), update \[ t_j \gets t_j + 1, \quad dd_j = (d_j - 2 t_j - (d_j - t_j) t_j p) + \frac{t_j (t_j - 1) p}{2} - \sum_{k \in \mathcal{N}(j) \setminus S} t_k p, \] where \(p\) is the propagation probability (e.g., \(p=0.01\)). The value \(dd_j\) approximates the expected number of additional nodes influenced by selecting node \(j\), accounting for both 1-hop and 2-hop neighbor effects.
  3. Repeat step 2 until \(k\) nodes are selected for the seed set.

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., Zhang, X., Zhao, C., & Yi, D. (2016). Maximizing the spread of influence via generalized degree discount. PloS one, 11(10), e0164393. doi: 10.1371/journal.pone.0164393.