### Social network ad allocation and optimization: a geometric mapping-based approachSocial network ad allocation and optimization: a geometric mapping-based approach

Access Restriction
Subscribed

 Author Gao, Peixin ♦ Miao, Hui ♦ Baras, John S. ♦ Hajiaghayi, MohammadTaghi Source SpringerLink Content type Text Publisher Springer Vienna File Format PDF Copyright Year ©2016 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Social network analysis ♦ Large-scale graph algorithms ♦ SNS ad allocation ♦ Geometric mapping ♦ Approximation and optimization ♦ Dimension reduction ♦ Maximum allocation problem ♦ Data Mining and Knowledge Discovery ♦ Applications of Graph Theory and Complex Networks ♦ Game Theory, Economics, Social and Behav. Sciences ♦ Statistics for Social Science, Behavorial Science, Education, Public Policy, and Law ♦ Methodology of the Social Sciences Abstract With the increasing popularity of online social networks (SNS), many advertisers choose to post their advertisements (ads) within SNS. Advertising activity on 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 ${\mathbb {N}}_0^{|Ads|\times |Users|}$ , which makes direct optimization unattractive. In this work, we study SNS advertising business models and formulate the SNS ad allocation problem. We show the problem is NP-hard and propose two dimension reduction schemes together with novel relaxation techniques. Our dimension reduction technique is formulated based on SNS user profile-based bidding scenario as well as social influence-based billing policies. We show the core ideas for dimension reduction are applicable to generalized assignment problems in bipartite graphs. We further draw connections between geometric mapping for complex network and the SNS ad allocation problem and map the SNS onto 2-D geometric space in order to relax the problem to geometric region allocation problems. We develop an optimization framework and solve the relaxed problem as a series of linear programs. 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. In addition, we discuss several extensions of our approach, including shape design in the geometric space for incorporating domain constraints in allocation strategies, more comprehensive real-world social influence models, as well as an alternative relaxation approach and its application in generalized assignment problems. ISSN 18695450 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2016-11-29 Publisher Place Vienna e-ISSN 18695469 Journal Social Network Analysis and Mining Volume Number 6 Issue Number 1 Page Count 23 Starting Page 1 Ending Page 23