HyperCubeMap: Optimal Social Network Ad Allocation Using Hyperbolic Embedding

Advertising activity on SNS has grown rapidly and is now a billion dollar business. In the SNS advertising model, the SNS serves as the advertising agent, and takes the advantage of network diffusion to attract advertisers and charges for the cascading impressions. The optimal ad allocation task is to choose the ad allocation plan that maximizes the revenue. Each user has different diffusion ability, limited daily impressions and the advertisers have various bidding prices and budget concerns. A feasible plan that obeys the constraints is difficult to find. The solution of this problem lies in the space of N |Ads|×|User| 0 , which makes direct optimization unattractive. In this paper, we study SNS advertising business models, formulate the SNS ad allocation problem and show their connections with hyperbolic embedding. We develop a new embedding algorithm HYPERCUBEMAP that allows for dimension reduction. Our proposed method reduces the dimensionality of the original problem significantly, runs two to four orders of magnitude faster, and reaches 95% of the optimum