Efficient influence spread estimation for influence maximization
- PDF / 4,868,335 Bytes
- 21 Pages / 595.276 x 790.866 pts Page_size
- 87 Downloads / 217 Views
REVIEW ARTICLE
Efficient influence spread estimation for influence maximization Zahra Aghaee1 · Sahar Kianian1 Received: 24 December 2019 / Revised: 9 September 2020 / Accepted: 11 September 2020 © Springer-Verlag GmbH Austria, part of Springer Nature 2020
Abstract Word-of-Mouth promotion is among the effective methods of marketing and is highly regarded by many commercial companies. This type of marketing is mapped on the influence maximization problem (IMP) in the social networks, and its goal is finding a specific set of the individuals with the maximum influence on the network. Therefore, in this paper, a heuristicgreedy algorithm named the HEDVGreedy algorithm was proposed for the IMP in the social networks. In this algorithm, the expected diffusion value of the graph nodes was calculated using the heuristic method, and then, the effective nodes were selected using the greedy method. Experimental results showed that the proposed algorithm has a high performance than the baseline algorithms while, it significantly reduces the running time of the computations under both the Independent Cascade and Weighted Cascade models in the eight real-world data sets. Keywords Influence spread · Influence maximization problem · Social network · Viral marketing
1 Introduction Emergence of the new and different communication styles between the individuals in the society is due to the advances made in the Internet arena. Among these, social networks developed through the graph structure are consisted of the individuals and their communications. These networks are highly effective in the lives of the individuals in the society, due to easy access and their effects on the users’ behaviors. Consequently, the influence maximization problem (IMP) is an essential problem in the analysis of the social networks. This problem is related to the identity of the effective individuals in the social networks. In this context, the limited and specified number of influential individuals are selected in relation to the whole in the social network, where if these individuals are active, the cascade of the information is published. Therefore, this flow causes more number of the individuals to become active by the influential nodes in the network.
* Zahra Aghaee [email protected] Sahar Kianian [email protected] 1
Department of Computer Science, Shahid Rajaee Teacher Training University, Tehran, Iran
The IMP engulfs three major criteria: (1) the number of the effective individuals as the seed nodes where these individuals are the spreader of information in the beginning of the diffusion process, (2) the number of the activated individuals in the end of diffusion process namely, the influence spread defined as the expected number of the active nodes under a specified diffusion model by the seed nodes, and (3) the necessary time to activate most of the individuals in the network, namely, the running time (Wu 2015). The multi-purpose applications of the IMP are evidence in viral marketing, rumor diffusion, social healthcare, findin
Data Loading...
