The independent set (IS) method is a widely used approach for identifying multiple influential spreaders in complex networks [2]. The method leverages the concept of independent sets , which are groups of nodes in which no two nodes are directly connected. The IS method consists of the following steps:


  1. Node ranking: all nodes in the network \(G\) are ranked according to a chosen centrality measure, typically the node degree.

  2. Network coloring: the network is colored using the Welsh-Powell algorithm. This algorithm assigns colors to nodes such that no two adjacent nodes share the same color. The computational complexity of this step is \(O(N^2)\).

  3. Independent set formation: Nodes with the same color form an independent set , guaranteeing that the selected nodes are not directly connected to one another.

  4. Spreader selection: within each independent set, the node with the highest centrality is chosen as an initial spreader. This strategy ensures that multiple spreaders are both influential and spatially well-distributed across the network.


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.