Research On Fairness-Aware Algorithms For Social Advertising

With the proliferation of online social networks in recent years,social elements have been highly integrated with various emerging applications.Various social applications have shown unprecedented growth in scale,and become an important information channel and decision-making basis for people.Users can spread their views and opinions through social networks and influence others potentially.Social advertising refers to advertisers’"viral marketing" for their products based on social network platforms and this potential information cascade effect:they will provide free samples for selected social network users,in exchange for those users promoting those products to their friends and create a cascade of influence to other users.This paradigm can make more people buy products and increase the revenue of advertisers.However,there is often no explicit social network data in the real scene.The structure and parameter information of the relevant social network are all unknown,which makes the previous social advertising algorithms invalid.Another onerous issue is that there are often multiple advertisers with comparable products over the same market in real social advertising paradigms.Prior studies only focus on maximizing the expected revenue and disregard the fairness criteria.Such an issue would cause polarized revenues or other unreasonable results among different advertisers.To solve the above problems,we propose a fairness-aware social advertising algorithm framework,which consists of two parts:a sample-based social network inference algorithm and a fairness-guaranteed seeds allocation algorithm.The social network inference algorithm will construct a social network based on sample cascade data,and then the seed allocation algorithm will select the seed nodes according to the constructed social network.To circumvent the existing issue of social advertising,we have carried out the following research:First,we propose an efficient social network inference algorithm,which can calculate explicit social networks based on sample cascade data.We consider that sample data could be missing in real scenarios and lay the foundation for the selection of seed nodes in subsequent social advertising.Specifically,We design a sampling rule for missing data based on the independent cascade model and show that it is effective to calculate the propagation probability with observable data and sampled missing data iteratively.We provide a theoretical analysis of the algorithm via Chernoff bounds and figure out the relationship between the number of cascades and the inference error.The evaluation on many real datasets indicates that our solution is effective and outperforms the existing algorithms in terms of the problem of social network inference with missing data.Next,according to the explicit social network structure and parameters,we further propose a seed allocation algorithm based on the maximin share,which can ensure that the final revenue of each advertiser is relatively fair and avoid the unfairness or unreasonable solution that may occur in traditional social advertising algorithms.We draw support from the multilinear extension and demonstrate that our approach achieves an approximation factor of((1-1/e)~2)/3·1/h~2 in polynomial time,where h is the number of different advertisers.Our result recovers the best-known proposed((1-1/e))~2/3-approximation ratio when h=1 and extends settings to a more general case.Sufficient experiments prove that our algorithm can effectively guarantee the fairness of seed allocation.