Influential Node Selection Using Positive Influential Dominating Set in Online Social Network

Online social networks (OSNs) have become a powerful medium of communicating, sharing and disseminating information. Because of popularity and availability of OSNs throughout the world, the connected users can spread information faster and thus propagate influence over each other constantly. Due to such impact, a lot of applications on OSNs focused on picking an initial set of users (seeds) to infuse their message in the OSN. Due to huge size of the network, the main challenge in picking the initial set is to maximize the resultant influence over the users in the network. The optimization problem of finding out the most influential set of members in an OSN for maximization of influence is an NP-hard problem. In this paper, we propose using the Positive Influential Dominating Set (PIDS) algorithm for the initial seed. PIDS is a well-known algorithm which determines the influential backbone nodes in the networks. We implemented PIDS-based influence maximization by using different propagation models. We compared PIDS performance to that of the existing approaches based on greedy and random heuristics. The experimental results from extensive simulation on real-world network data sets show that PIDS gives better influence spread than greedy and random for both Independent Cascade Model and Linear Threshold Model of influence propagation. PIDS is also scalable to large networks and in all size ranges, it performs well in influence maximization