A Framework for Facilitating Benchmarking Influence Maximization Algorithms

Hao, Xinxin
Major Professor
Samik Basu
Pavan Aduri
Committee Member
Journal Title
Journal ISSN
Volume Title
Research Projects
Organizational Units
Computer Science
Organizational Unit
Journal Issue
Computer Science

With the proliferation of social networks, viral marketing has become a viable and effective marketing strategy, one where a relatively small group of individuals can help shape public opinion about products. Central to this strategy is the existence of influencers, individuals whose influence or impact on the entire network is significant. In this context, the underlying challenge is to identify influencers or more precisely, the impact of the influencers. In general terms, given a network G representing the social connection/influence between entities and an integer k, the problem is to compute the set of k individuals who can maximally influence the network. The spread of influence is probabilistically modeled by the likelihood of one individual getting influenced by his/her neighbor(s), and the influencing a network corresponds to the number of the individuals impacted by the spread. The problem, in general, is NP-Hard and several approximation methods (and pure heuristics) have been proposed to address the problem. Due to the natural dependency on various probabilistic parameters, it is often difficult (if not impossible) to decide the relative strengths and weaknesses of these existing methods.

The objective of this creative component to develop a framework such that existing and new methods can be deployed and evaluated in terms of the quality and efficiency in a uniform fashion, with a clear presentation of the parameter-dependencies. Central to the framework are (a) easily translatable format for the input from a widely-used SNAP data repository, (b) clearly identifiable parameters in the form of a configuration file, and (c) a uniform format for output file for various influence maximization solutions.The framework is also modular in nature allowing for easy maintainability and extensibility.