Efficient community-based influence maximization in large-scale social networks

• Published in: Multimedia tools and applications 2024-05, Vol.83 (15), p.44397-44424
• Main Authors: Venunath, M., Sujatha, Pothula, Koti, Prasad, Dharavath, Srinu
• Format: Article
• Language: English
• Subjects: Algorithms; Community; Computer Communication Networks; Computer Science; Data Structures and Information Theory; Maximization; Multimedia Information Systems; Nodes; Optimization; Performance evaluation; Run time (computers); Social networks; Special Purpose and Application-Based Systems
• ISSN: 1573-7721; 1380-7501; 1573-7721
• DOI: 10.1007/s11042-023-17025-x

The Influence Maximization problem (IMP) is a fundamental algorithmic challenge that involves selecting a set of k users, known as the seed set, from a social media network to maximize the expected number of influenced users or influence spread. In recent years, Influence maximization has been extensively studied due to its numerous applications in marketing and other domains. However, many existing algorithms neglect the impact of communities on influence maximization, and some other methods suffer from scalability issues and time-consuming computations. In this paper, we propose a fast, and scalable algorithm called Community based Influential maximization (CB-IM) to address these limitations. This method leverages the community structure of the network to select k users, thus maximizing the influence spread. The CB-IM algorithm comprises two main components for influence maximization: (1) seed selection and (2) local community spreading. In the seed selection phase, we extract seed nodes from communities identified through a community detection algorithm. To effectively reduce computational complexity and distribute seed nodes across communities, we carefully select meaningful communities. The second phase involves the propagation of influence within independent communities. In this step, the final seed nodes are strategically distributed to facilitate local spreading through simple paths within the communities. To evaluate the performance of proposed method, we conducted a series of experiments using real networks. The proposed CB-IM algorithm demonstrated superior performance over other algorithms in terms of influence spread and running time, highlighting its effectiveness.