Union acceptable profit maximization in social networks

Online social network has deeply changed our lives, such as the style of communication and business, and hence promotes a lot of researches in social influence. The prior works in social influence mainly consider the influence from the view of individuals. However, in many cases, influencing the most of members of an important group such as the board of directors in a company can bring bigger profit than directly influencing the individuals of the company. We call such high profit group which obeys the vote rule as an union, different from existed targeted influence model, we consider such scenarios to make union acceptable and propose the union acceptable profit problem (UAPM) to choose seeds to maximize the union-acceptable profit, i.e., maximize the probability of the union being acceptable. The objective of profit in UAPM is #P-hard, and not submodularity or supmodularity. To solve the problem, we propose an efficient estimation method for the objective and design a heuristic algorithm and further a data-driven beta(1 -1/is an element of)-approximation algorithm where beta is the data-driven parameter which is related to the input data. At last we evaluate the performance of the algorithms we proposed on effectiveness and efficiency by the experiments in real-world social network datasets. (c) 2022 Elsevier B.V. All rights reserved.

Automated summary

Online social networks have had a profound impact on our lives, leading to an increase in research on social influence. Previous studies on social influence have primarily focused on individual influence, but in many cases, influencing an important group can bring greater profits than directly influencing individuals. We propose a model called the Union Acceptable Profit Problem (UAPM) to maximize the probability of a union being acceptable and present efficient estimation methods and algorithms to solve the problem. We evaluate the performance of our algorithms using real-world social network datasets.