Community-Based Efficient Algorithms for User-Driven Competitive Influence Maximization in Social Networks

Nowadays, people in the modern world communicate with their friends, relatives, and colleagues through the internet. Persons/nodes and communication/edges among them form a network. Social media networks are a type of network where people share their views with the community. There are several models that capture human behavior, such as a reaction to the information received from friends or relatives. The two fundamental models of information diffusion widely discussed in the social networks are the Independent Cascade Model and the Linear Threshold Model. Liu et al. [1] propose a variant of the linear threshold model in their paper title User-driven competitive influence Maximization(UDCIM) in social networks. Authors try to simulate human behavior where they do not make a decision immediately after being influenced, but take a pause for a while, and then they make a final decision. They propose the heuristic algorithms and prove the approximation factor under community constraints( The seed vertices belong to an identical community). Even finding the community is itself an NP-hard problem. In this article, we extend the existing work with algorithms and LP-formation of the problem. We also implement and test the LP-formulated equations on small datasets by using the Gurobi Solver [2]. We furthermore propose one heuristic and one genetic algorithm. The extensive experimentation is carried out on medium to large datasets, and the outcomes of both algorithms are plotted in the results and discussion section.