Heterogeneous Influence Maximization Through Community Detection in Social Networks

Related Work

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 t_s is smaller than the marginal gain of a node at time (t_s+1). So they recommended not to calculate this marginal gain for other nodes at time (t_s+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.