DegreeDiscountIC is a degree-discount heuristic for identifying influential nodes in a network [2]. The main idea is that if a node \(i\) is selected as a seed, the edges connecting \(i\) to its neighbors should not be fully counted when evaluating the degrees of those neighbors for further seed selection. In other words, the degree of each neighbor of a selected seed is discounted to account for the presence of the seed node.
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. Select the node \(i\) with the largest \(dd_i\) and add it to the seed set. Then, for each 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, \] 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\), considering the presence of already selected neighbors.

  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] Chen, W., Wang, Y., & Yang, S. (2009). Efficient influence maximization in social networks. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 199-208). doi: 10.1145/1557019.1557047.