Three-level scoring based on community and decomposition structures to identify influential spreaders in a social network

Communication in any system is grounded in its interconnection pattern. This pattern allows the components of a system to communicate among themselves and work together to achieve the system-level goal. Information flow within a social system or any organizational setup plays a pivotal role in its growth. Availability of information across most parts of the network is often essential for advancing a social cause or organizational benefit. Selecting a seed set of influencers from where the information has to be initiated to maximize the diffusion is a crucial task. In this context, this paper proposes a three-level scoring framework: (i) inter-community edge-based score (global level), (ii) community-influence-oriented score (gateway level), and (iii) intra-community-oriented score (local level). Each node is assigned with certain importance values in all three levels, i.e., global level, gateway level, and local level. We utilize the core–periphery structure of the communities to calculate the gateway- and local-level scores of a node. Nodes with high overall scores (CKI_Score) from all the communities are combined to form a seed set, denoted as ‘S’. The simulation of the diffusion process is implemented using the independent cascade model. The performance of the proposed algorithm is assessed through the average influence capacity (in %) and Kendall’s tau coefficient of correlation (τ). The experiments demonstrate that the proposed community-based k-shell decomposition influence scoring method (CKI) outperforms the state-of-the-art algorithms.