The partition-based spreaders identification (PBSI) method is a community-aware algorithm for identifying influential nodes in a network [2]. It assumes that the network \(G\) has a community structure consisting of \(K\) communities, denoted by \(C_1, \dots, C_K\). The PBSI procedure consists of two main steps:


  1. Community detection and node ranking: the network is partitioned into communities using a community detection algorithm, specifically the Louvain method. Within each community, nodes are ranked according to their gravity centrality [3].

  2. Spreader selection: a total of \(m\) spreaders are selected from different communities. If \(m \leq K\), one node with the highest gravity centrality is chosen from each of the \(m\) largest communities. If \(m > K\), a number of nodes \(n_i\) is selected from each community \(C_i\), proportional to its size, such that \(\sum_{i=1}^K n_i = m\). In all cases, the nodes with the highest gravity centrality within each community are selected.


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] Yanez-Sierra, J., Diaz-Perez, A., & Sosa-Sosa, V. (2021). An efficient partition-based approach to identify and scatter multiple relevant spreaders in complex networks. Entropy, 23(9), 1216. doi: 10.3390/e23091216.
[3] Ma, L. L., Ma, C., Zhang, H. F. & Wang, B. H. Identifying influential spreaders in complex networks based on gravity formula. Physica A 451, 205-212 (2015). doi: 10.1016/j.physa.2015.12.162.