Union acceptable profit maximization in social networks
Union acceptable profit maximization in social networks
复制标题
DOI：
10.1016/j.tcs.2022.03.015
复制
发表时间：
2022-03
期刊：
影响因子：
--
通讯作者：
Guoyao Rao;Yongcai Wang;Wenping Chen;Deying Li;Weili Wu
中科院分区：
文献类型：
--
作者：
Guoyao Rao;Yongcai Wang;Wenping Chen;Deying Li;Weili Wu
在线社会网络深刻地改变了人们的生活方式，如交流方式和商务方式，从而推动了大量的社会影响研究。以往关于社会影响的研究主要是从个体的角度来考虑影响。然而，在许多情况下，影响一个重要群体（如公司董事会）的大多数成员，比直接影响公司的个人带来更大的利润。与已有的目标影响力模型不同，我们将服从投票规则的高利润群体称为联盟，考虑这种情况使联盟可接受，并提出了联盟可接受利润问题（UAPM）来选择种子以最大化联盟可接受利润，即最大化联盟被接受的概率。UAPM的利润目标是# P-hard，而不是子模块化或超模块化。为了解决这个问题，我们提出了一种有效的目标估计方法，设计了一种启发式算法，并进一步设计了一种数据驱动的β（1− 1）-近似算法，其中β是与输入数据相关的数据驱动参数。最后通过在真实社会网络数据集上的实验，从有效性和效率两个方面对本文提出的算法进行了性能评估。
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, ie, 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 β (1− 1 ϵ)-approximation algorithm where β 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.