Social Network Ad Allocation and Optimization: A Hyperbolic Embedding-Based Approach

With the increasing popularity of online social networks (SNS), many advertisers choose to post their advertisements (ads) within SNS. Advertising activity on social network sites (SNS) has grown rapidly and is now a billion-dollar business. For example, Facebook has reached more than 1 million active advertisers who contribute 90% of its revenue. In the SNS advertising model, advertisers participating in a SNS ad campaign benefit from the effects of viral marketing and network diffusion. Modern SNS serve as advertising agents, and take advantage of the network diffusion to attract advertisers and charge for the cascading impressions. The optimal ad allocation task is the problem of choosing the ad allocation plan that maximizes revenue for the SNS. Considering that users have diffusion abilities and limited daily impressions, and advertisers have various bidding prices and budget concerns, a feasible plan that obeys the constraints is difficult to find. The solution to this problem lies in the space of N ₀ ^{|Ads|×|User|}, which makes direct optimization unattractive. In this work, we study SNS advertising business models and formulate the SNS ad allocation problem. We show its connection with hyperbolic embedding and how the SNS ad allocation problem can be formulated as a linear program based on the hyperbolic embedding of a complex network. Accordingly, we develop a new embedding algorithm HyperCubeMap and an optimization framework that allow for dimension reduction in the optimization process. Our proposed method is able to reduce the dimensionality of the original problem significantly, run two to four orders of magnitude faster, and reach 95% of the optimal solution. We also discuss the possible extensions based on our current optimization framework, including shape design in allocation strategies for domain constraints like fairness and more comprehensive social influence models, in order to incorporate more real-world requirements.