Scalable Approximate Algorithm for Group Influence Maximization in Online Social Network: An Experimental Evaluation
Existing strategies for solving multiobjective submodular optimizations are not scalable and cannot be applied to large networks, also these strategies work under the assumption that the exact value of the submodular function is known to us. In our work we relax the requirement of an exact oracle and show that by considering $\delta$-approximate oracle it is possible to ensure $(1-1/e)^2 - 3\delta$-approximate guarantee for the multi-objective submodular optimization problem. We show that group influence maximization in the context of online social networks is an instance of this optimization problem with cardinality constraint and $\delta$-oracle. We develop a new scalable strategy for solving multiobjective problems where the objective functions closely represent influence maximization objectives and create a prototype implementation of our solution strategy to solve the group influence maximization and experiment on networks of varying sizes. We empirically evaluate our new algorithm against various known existing strategies comparing runtime, individual influence spread, groups activated above threshold and various other metrics. Our algorithm being scalable to larger networks allows us to experiment with really large social networks and evaluate the effectiveness of the multi objective optimization strategy on some large real world social networks which had not been extensively experimentally evaluated previously. We run our algorithm on various real world networks like Facebook, DBLP etc and also experiment with a few group assignment strategies and show how different group assignment policies affect the effectiveness of the algorithm.
Committee: Pavan Aduri (major professor), Samik Basu (major professor), and Shawn Dorius
Meeting number: 2620 946 0298 Password: acBgXsDU924