Scalable approximate algorithm for group influence maximization in online social network: An experimental evaluation
Date
2022-05
Authors
Bhatt, Rishabh Rajendra
Major Professor
Advisor
Basu, Samik
Aduri, Pavan
Dorius, Shawn
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Abstract
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 experimentally evaluate δ-approximate oracle 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 δ-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 net- works 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.
Series Number
Journal Issue
Is Version Of
Versions
Series
Academic or Administrative Unit
Type
thesis