Analysis of influence and its applications in social advertising

• Main Author: Zhu, Yuqing
• Other Authors: Jian Ming
• Format: Thesis-Doctor of Philosophy
• Language: English
• Published: Nanyang Technological University 2022
• Subjects: Engineering::Computer science and engineering
• Online Access: https://hdl.handle.net/10356/155783
• Institution: Nanyang Technological University

Online Social Networks (OSNs), such as Facebook and Twitter, serve as important media where users gain information in the modern world. With the tremendous number of active users sharing information on social media, the rich social connections serve as fertile soil for advertising campaigns as information can be propagated efficiently and widely with the word-of-mouth effects. The influential users, who normally have large audiences over OSNs, are of great values to initiate marketing campaigns. In this thesis, we carry out an in-depth analysis on users' influence in social advertising. First, we study the problem of pricing the influential users to reflect the influence spread they can bring in an advertising campaign. Second, we analyze the influence contributions of the influential users given the advertising campaign result. Third, we propose a new sampling method to improve the efficiency and accuracy for estimating users' influence spread. In social advertising, the influential users, also called influencers or seeds, generate revenue from the seed purchase of the advertiser for initiating the marketing campaigns. The influence spread, on the other hand, is the reward gained by the advertiser in the campaigns. Thus, it is important to make sure that the influence spread is worth the cost of seed purchase. To match the price with the expected marketing value (reflected by the influence spread) of the seed set as closely as possible, we formulate an optimization problem to minimize the divergence between the price and the expected influence spread of the initiator sets. An optimal price profile is derived and an advanced algorithm is developed to estimate the price profile with accuracy guarantees. Given the result of an advertising campaign, we formulate the problem for OSN providers to measure the influence contributions of influential users to produce the campaign result, namely influence contribution allocation (ICA). We make a connection between ICA and the concept of Shapley value in cooperative game theory to reveal the rationale behind ICA. To address ICA effectively and efficiently, a linear time algorithm is developed to find the exact solution under the Linear Threshold model and an efficient approximation algorithm is devised to construct an approximate solution under the Independent Cascade model. Our solution consists of a scalable sampling method that significantly boosts the sampling efficiency with accuracy guarantees. To improve the efficiency in the sampling process of influence estimation, we propose a new sampling method, called 2-hop+. Our method generates only the samples spreading influence beyond the source with at least one 2-hop live path. The samples generated by our 2-hop+ method can yield the random variable to estimate with tighter ranges and better concentration bounds can be applied to obtain an approximation of the random variable with a theoretically tighter threshold requiring less samples. In addition, we speed-up the generation of each sample to enhance the sampling efficiency with a SkipEdge technique. Extensive experiments with real-world OSN datasets demonstrate the effectiveness of our algorithms and techniques.