Targeting algorithms for online social advertising markets

Chaolun Xia, Saikat Guha, S. Muthukrishnan

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    Advertisers in online social networks (OSNs) like Facebook and LinkedIn have some preferred set of users they wish to reach by showing their ads. OSNs offer fine-grained sets of user characteristics - including their career, wealth, education information, etc - that advertisers can specify for targeting their audience, and each of these characteristics requires different amounts of money for targeting. The problem we address is what we call the targeting problem, that is, given a set ST characteristics of interest to an advertiser (that is, the advertiser wishes to reach users who have these characteristics, i.e. U(ST)) and a budget b0 he wishes to spend, how to split the budget among the user characteristics so that they can reach the most number of users in U(ST)? • OSN-perspective. OSNs have complete knowledge of each user and their characteristics. In this case, we propose a polynomial time algorithm for the targeting problem and prove that it is an 1-1/e approximation to the targeting that gets the optimal number of users. We define the marginal increment and iteratively maximize it. • Advertiser-perspective. No single advertiser has the mapping of users to their characteristics or the distribution of users over the characteristics, and hence they cannot use the algorithm from above. We show through empirical data analysis that the strategy of targeting subsets U(S) U(ST) is their only feasible approach (in other words, targeting U(S) U(ST) will be arbitrarily worse than the direct solution). For evaluation, we crawl and analyze more than one million suggested bids from Facebook and LinkedIn. Further, we propose a fast greedy algorithm for the targeting problem based on targeting subsets, that in empirical analysis, increases the number of reached preferred users by nearly 40% over directly targeting the characteristics of interest, and for a moderate budget, it increases the number of reached preferred users by nearly 20%.

    Original languageEnglish (US)
    Title of host publicationProceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016
    EditorsRavi Kumar, James Caverlee, Hanghang Tong
    PublisherInstitute of Electrical and Electronics Engineers Inc.
    Pages485-492
    Number of pages8
    ISBN (Electronic)9781509028467
    DOIs
    StatePublished - Nov 21 2016
    Event2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016 - San Francisco, United States
    Duration: Aug 18 2016Aug 21 2016

    Publication series

    NameProceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016

    Conference

    Conference2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016
    CountryUnited States
    CitySan Francisco
    Period8/18/168/21/16

    ASJC Scopus subject areas

    • Computer Networks and Communications
    • Sociology and Political Science
    • Communication

    Fingerprint Dive into the research topics of 'Targeting algorithms for online social advertising markets'. Together they form a unique fingerprint.

    Cite this