Heterogeneous Influence Maximization Through Community Detection in Social Networks

Heterogeneous Influence Maximization Through Community Detection in Social Networks

Jaya Krishna Raguru (Manipal University, Jaipur, India) and Devi Prasad Sharma (Manipal University, Jaipur, India)
Copyright: © 2021 |Pages: 14
DOI: 10.4018/IJACI.2021100107
OnDemand PDF Download:
No Current Special Offers


The problem of identifying a seed set composed of K nodes that increase influence spread over a social network is known as influence maximization (IM). Past works showed this problem to be NP-hard and an optimal solution to this problem using greedy algorithms achieved only 63% of spread. However, this approach is expensive and suffered from performance issues like high computational cost. Furthermore, in a network with communities, IM spread is not always certain. In this paper, heterogeneous influence maximization through community detection (HIMCD) algorithm is proposed. This approach addresses initial seed nodes selection in communities using various centrality measures, and these seed nodes act as sources for influence spread. A parallel influence maximization is applied with the aid of seed node set contained in each group. In this approach, graph is partitioned and IM computations are done in a distributed manner. Extensive experiments with two real-world datasets reveals that HCDIM achieves substantial performance improvement over state-of-the-art techniques.
Article Preview

Finding an influential node in social networks is the most of the researcher’s basic motivation. (Leskovec et al., 2007) have proposed an effective technique over the greedy algorithm called cost-effective lazy forward (CELF), which is many times better than greedy approach. In this approach marginal gain of vertex is calculated in every iteration of a greedy approach. The marginal gain of a vertex at time ts is smaller than the marginal gain of a node at time (ts+1). So they recommended not to calculate this marginal gain for other nodes at time (ts+1). This helped in the improvement of the algorithm efficiency by many times. (Chen et al., 2009) used a network centrality based approach to find the seed node in the network called Degree Discount (DD). The basic idea of this technique is to find a node with highest degree as a seed node. The selected seed node is taken out and added into a seed node set and the degrees of all of its neighbours are reduced by one. Recursively in each iteration a node with highest degree is chosen and its neighbouring nodes degrees are reduced which is identified as a discount step. But there is no expected improvement in this approach.

Complete Article List

Search this Journal:
Open Access Articles
Volume 13: 6 Issues (2022): Forthcoming, Available for Pre-Order
Volume 12: 4 Issues (2021)
Volume 11: 4 Issues (2020)
Volume 10: 4 Issues (2019)
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 2 Issues (2016)
Volume 6: 2 Issues (2014)
Volume 5: 4 Issues (2013)
Volume 4: 4 Issues (2012)
Volume 3: 4 Issues (2011)
Volume 2: 4 Issues (2010)
Volume 1: 4 Issues (2009)
View Complete Journal Contents Listing