Social network ad allocation via hyperbolic embedding

With the increasing popularity and ubiquity of online social networks (SNS), many advertisers choose to post their advertisements (Ads) within SNS. As a central problem for Ad platforms, Ad allocation is to maximize its revenue without overcharging advertisers, and it has received increasing attention from both industry and academia. The offline approach is a high dimensional integer programming problem with constraints incorporating potential allocation requirements from advertisers. In this paper we investigate the SNS Ad allocation problem in a single target group setting, study the connection of SNS advertising and hyperbolic geometry, and propose an approximation using hyperbolic embedding, which not only reduces the dimensionality of SNS Ad allocation problem significantly, but also provides a general framework for designing allocation strategies incorporating business rules. We evaluate the optimality and efficiency of our approach.