Access Restriction

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

Open content in new tab

   Open content in new tab
Source: SpringerLink