Influence maximization based on bottom-up community merging

Influence maximization (IM) is a prominent topic in the complex network analysis domain, and its goal is to identify the fewest nodes to achieve the maximum influence in a network. There are numerous IM methods that have emerged, among which community-based methods are potentially advantageous due to their ability to utilize community structure information and reduce time complexity through reduced search space. However, the key to these methods is a deep understanding of community structures, and their accuracy depends heavily on filtering candidate nodes and identifying seed nodes. To address these challenges, this study proposes a novel community-based IM method, BUCIM, that selects both candidate and seed nodes in different but more reasonable ways. This study considers both bridge nodes and core nodes within communities as candidate nodes. Differing from the related efforts, BUCIM selects bridge nodes by considering their heterogeneity of external links and selects core nodes by combining different topology-based centrality metrics. To select seed nodes in large complex networks from a global perspective, potential candidate nodes are discovered by iteratively merging communities based on their spreading influence and attraction coefficient. Moreover, to reduce influence overlaps, seed nodes are selected by considering both the spreading influence of a candidate node and its minimum distance to other candidate nodes. Experimental results on nine real-world networks demonstrate that BUCIM not only outperforms state-of-the-art methods in both influence scale and coverage redundancy but also has reasonable time complexity.