Abstract

Finding the k most in uential nodes in a social network is a well-known problem, which is shown to be NP-hard. There is a major dierence between what this problem tries to nd and what happens in real life. In practice, companies usually advertise to a set of groups rather than individuals. Here, each group is the set of people who can be targeted using a specic advertising medium such as billboards, TV com- mercials, and newspaper ads. Based on this observation, we study the problem of nding the most in uential groups rather than nodes in this paper. As the rst step to ad- dress this problem, we propose a model for the group-based diusion and present a greedy (1 - 1/e)-approximation al- gorithm. We also present a polynomial time algorithm for detection of in uential groups when the number of groups is extremely large. By conducting experiments on two large real datasets, we show that using groups as targets of adver- tisements can produce more revenue (more than 1:7 average improvement in our experiments) with faster speed (around 400 times speedup) compared to individual advertising case under reasonable assumptions.

 

Manuscript

 

Bibtex