The improved distance-based coloring (IIS) method builds upon the independent set (IS) approach in [2] by introducing a distance constraint to further enhance the spatial dispersiveness of the selected spreaders [3]. The IIS procedure can be summarized as follows:


  1. Node ranking: all nodes are ranked based on a selected centrality measure, such as degree, betweenness, closeness, or coreness centrality.

  2. Distance-based coloring: nodes are sequentially assigned colors with the rule that any two nodes sharing the same color must be separated by a network distance of at least \(r\). The parameter \(r\) can be set, for example, to the average shortest path length in the network. This step ensures that nodes with the same color are sufficiently dispersed.

  3. Independent set construction: after coloring, nodes with the same color form an independent set, similar to the IS method.

  4. Spreader selection: within each independent set, the node with the highest centrality is selected. Priority is often given to the set containing the node with the maximum centrality value in the network. This guarantees that the chosen spreaders are both highly influential and well-distributed.


By introducing the distance constraint, the IIS method improves upon the IS method by reducing overlap between the influence regions of multiple spreaders, which can enhance overall spreading efficiency.

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] Zhao, X. Y., Huang, B., Tang, M., Zhang, H. F., & Chen, D. B. (2015). Identifying effective multiple spreaders by coloring complex networks. Europhysics Letters, 108(6), 68005. doi: 10.1209/0295-5075/108/68005.
[3] Guo, L., Lin, J. H., Guo, Q., & Liu, J. G. (2016). Identifying multiple influential spreaders in term of the distance-based coloring. Physics Letters A, 380(7-8), 837-842. doi: 10.1016/j.physleta.2015.12.031.