Community-based Influence Maximization framework for Social Networks

Abstract: Maximizing Influence (IM) in social networks has a considerable role to play in the phenomenon of viral marketing, targeted advertisements and in promoting any campaigns. However, the Influence Maximization Problem is a very challenging research-problem due to it being NP-Hard and scaling with the social networks with millions of nodes and edges becomes very tough due to the computational complexities concerned with it. Recently, solving this problem through the use of community detection based methodology is becoming very popular since, it reduces the search space by dividing the network into smaller and more manageable groups called "communities." As part of the larger research work, we reiterate a framework which has been inspired by collection of different work done by Alfalahi et al. (2013) that we can implement to solve the IM problem and its limitation through community detection and fuzzy logic inspired approach. Since the work is still under development, for this project, we report on understanding the IM field through literature reviews and in communicating a design of IM framework as inspired by the previous works. We also present our version ofthe blueprint (Algorithm design) of the framework as a five step approach. For the purpose of this report, we implement and evaluated the step 1 and step 2 of the framework. Step 1 is about preprocessing the input network with a similarity measure, which according to previous study by Alfalahi et al. (2013a) aids the algorithms in detecting better community structure (clear and accurate distinction of the nodes into communities in networks). We test it to see if it holds true. Step 2 is about implementing the community detection in social network. We benchmarkthree candidate algorithms, chosen based on theirperformance, from the previous studies in community detection fieldand we report onwhich algorithm should we consider to use in the proposed framework through experimentationon the simulated data. We use Normalized Mutual Information (NMI) and Modularity (Q) as evaluation metrics to measure the accuracy of the community detected by the candidate algorithms. Our results show that similarity based preprocessing does not improve the community structure and thus may not be required in the framework. We also found out that Louvain should be the algorithm that use to detect communities in social networks since it outperforms both CNM and Infomap on Q and NMI