基于广义意见动态模型的社交信任网络意见最大化问题

曾佳媛 张广

摘要：提出了一种广义意见动态模型（ GODM），此模型可以通过动态计算每个人的表达意见来解决社交信任网络中的意见最大化问题。在模型中提出了一个新的、合理的、可解释的自信指数ai，ai由个人的社会地位与其周围人的评价共同决定。并且利用对角占优理论，得到模型达到纳什均衡状态时的最优解析解。设计了一种具有，1形式的交替方向乘子法来最大化现有的总体意见。进行了一系列实验，实验结果表明，此方法在4个数据集上都有较好的结果。在4个数据集上，解决内部意见问题的平均效益分别提升了66.4%，88.7%，47.8%和34.1%。实验结果充分验证了所提模型的优越性。

关键词：意见最大化；社交信任网络；自信指数；有限预算

中图分类号：O 157

文献标志码：A

近年来，大规模社交媒体网络的日益普及极大地推动了社交网络分析的发展。人们如何通过与他人的社交互动形成自己的观点一直是社会科学领域的研究课题。在社交网络上，用户可以对产品或实时新闻表达自己的意见。通过量化这些意见，可以确定一个网络中的用户对产品或新闻的整体看法。人们可以定量研究用户意见间的相互作用，并通过有针对性的干预来提高总体意见值。

1 相关研究

社交信任网络是某些群体（人、企业和组织）之间关系相对稳定的网络。它可以表示为有向符号加权图，如图l所示。社交信任网络的研究在社区检测[1]、情感分析[2-4]、意见领袖检测[5]、产品推荐[6]、识别假新[7]、监控系统[8]及意见最大化[9-12]等方面有广泛应用。近年来，有许多基于社交互动的意见动态模型被提出[9-12]，Chen等[9]提出了一种算法来寻找对网络产生影响最大的K个节点。Liu等[11]考虑了意见最大化问题，其目标是在多轮活动中找到种子用户集，用来最大化目标产品的总体意见传播。除了考虑直接改变人们内部意见的干预，Abebe等[12]还考虑了改变人们对说服敏感性的干预。其目的是利用修改用户的敏感性来最大限度地提高纳什均衡下的总体意见。Xu等[10]提出了一种新的连续值意见动态模型，该模型更符合真实场景，取得了良好的效果。但是，文献[10]中仍有一些可以改进的地方，如它将每个用户的表达意见考虑为个人内部意见和周围人意见的加权平均值。然而，在现实生活中，每个人的性格都是不同的，也就是说，不同的人受别人影响的程度也不同。因此，本文在文献[10]的基础上进行了一些改进，建立了一个广义的社交信任网络意见动态模型来具体计算每个人的表达意见，并解决了意见最大化问题。提出了一种新的自信指数ai，这与文献[12]中随机选择的ai不同，它取决于一个人的社会地位和周围人的评价。对于不同的人类群体，ai的取值范围是不同的。利用对角占优理论和Friedkin-Johnsen模型给出了达到纳什均衡时的解析解，实现了文献[10]中模型的推广。引入了一种成熟的优化算法一一交替方向乘子法，并利用该算法所衍生的特殊形式——Z1正则化形式解决了意见最大化问题。

2 模型构建

2.1 模型中使用的定义和引理

定义1[13]对于矩阵A= （aij）nxn，若其对角元素的绝对值大于非对角元素的绝对值之和，即laiil>∑laijl，i=1，2，…，，z，则A=（aij）nxn严格对角占优。

引理1[13]若A= （aij）nxn是严格对角占优矩阵，则det A≠0。

2.2纳什均衡

定义2纳什均衡是博弈论中一种解的概念，它是指满足下面性质的策略组合：任何一位玩家在此策略组合下单方面改变自己的策略（其他玩家策略不变）都不会提高自身的收益。

在一个博弈过程中，无论对方的策略选择如何，当事人一方都会选择某个确定的策略，则该策略被称为支配性策略。如果任意一位参与者在其他所有参与者的策略确定的情况下，其选择的策略是最优的，那么，这个组合就被定义为纳什均衡。当每个博弈者的均衡策略都达到自己期望收益的最大值时，这个策略组合被称为纳什均衡。2.3 Friedkin-Johnsen模型

社交信任网络可以表示为有向符号加权图G=（VE），其中，V={1，2，…，n）为节点集，E为弧集（有向边集）。ωij为从i到j的有向边（i，j）的权重，

2.4社交信任网络的广义意见动态模型

从Friedkin-Johnsen模型可以看出，对于每个节点i，其表达的意见是其内部意见与周围节点意见的加权平均值。然而，在现实生活中，人们的性格是不同的，每个人受到他人影响的程度也是不同的。因此，建立了一个广义的社交信任网络意见动态模型。

首先写出社交游戏的共识成本函数

在社交网络中，ai越高，表明这个人在发表意见的时候更倾向于关注自己的想法，而不会轻易被他人的意见所影响。在此模型中，自信指数与一个人的社会地位和别人对他的评价，即与其在网络中的重要性以及周围人对他的评价有关。

2.4.2平均入评价

在社交网络中，每个节点都有2个身份：源节点（出节点）和目标节点（人节点）。作为一个目标节点，指向它的边的符号和权值代表它的人邻居对它的评价。在这里，对于节点i，使用平均人评价m（i）来表示它的人邻居对它的平均评价，即

2.4.3自信指数ai

网络中每个用户节点的自信程度与其在网络中的影响力大小和别人对其的評价密切相关。因此，这里的自信指数ai由PageRank值和平均人评价加权求得，其计算公式为式中：似f），r（i）分别表示节点i的平均人评价和PageRank值；q为常数，且满足0≤q≤1。

q越大，说明在定义自信指数时更注重周围人的评价；q越小，说明更注重PageRank值，即每个个体在社会网络中的重要性。这里取q= 0.5，也就是平均人评价和PageRank值同等重要。

在真實的社交信任网络中，一个用户对另一个用户的评价可能是负面的。由于PageRank值可能很小，所以，ai可能为负，这样是不符合实际意义的。因此，引入线性整流函数，将ai的值限制在（0，1）内，则式（2）变为

ai= RELU（q.n（i）+（1- q）r（i》

（3）这里RELU（x）= max {0.0001，x）。有必要提的一点是，为了使得ai>0，这里的RELU函数是在一般的RELU函数上作了一些调整。从式（3）中可以看出，如果一个人在网络中很重要或者周围人对他的评价较高，那么，这个人的自信指数就会比较大。

定义3总体意见p（z*）表示纳什均衡状态下所有用户表达意见的总和，p（z*）=∑z：= lr（A+（I—A）L）-1．As，这里的1是全1向量。

定义4在社交信任网络中，为了提高整个网络的总体意见，需要付出一定的费用来改变其中一些人的内部意见，这些费用的总和称为预算。

定义5在社交信任网络中通过预算改变了一部分人的内部意见，会使得总体意见增加。总体意见的增加量被称为效益。

3 社会信任网络中的意见最大化

定义6给定社交信任网络G、内部意见向量s和预算μ，内部意见问题的目标是找出每个用户节点的内部意见的修改情况A，以最大化总体意见p（z*）。

为了解决内部意见问题，使用一种传统的优化算法——交替方向乘子法（ADMM算法）来进行求解。3.1 利用ADMM算法解决内部意见问题

ADMM算法是Gabay和Mercier提出的一种混合了双上升法的可分解性和乘数法优越性的收敛算法[15]。当目标函数中有多个变量时，对于凸优化问题的求解是困难的。ADMM算法利用变量分离法将问题分解成几个简单的子问题，然后并行求解，这样可以得到原问题的最优解[16]。它是一种简单但强大的算法，非常适合于解决分布式凸优化，特别是应用统计和机器学习中出现的问题。

3.2 算法的步骤

要解决的优化问题为

算法1的第1行是将As初始化为全零向量。第2～5行是使用ADMM算法寻找最优解的过程。这里设置的停止条件为IIXk一Zkll<10-4。最后一行是更新△s。初始内部意见向量是用3种方法随机选择的。

4 实验研究

本文进行了一系列实验来评估所提出的方法。从以下2个方面进行实验：首先，将所提模型获得的结果与文献[10]中的模型进行比较；其次，为了进一步说明所提模型的优越性，将所提模型与其他启发式方法进行比较，所有的实验结果都表明了所提方法的优越性。

4.1 数据集

实验中使用到的数据集如下：a．Alpha。b．OTC。Alpha和OTC边上的权重为[-10，10]，将它归一化为[-1，1]。c．WikiElec。d．WikiRfa。这2个网络中的边的符号、权重与信任密切相关。关于这些网络的具体数据详见斯坦福实验数据集（ SNAP）。

4.2 内部意见的初始化

从表1可以看出，所提模型与文献[10]中的模型相比具有明显的优势。加入自信指数后，更加符合实际场景。每个人都有不同的个性，有些人更注重自己的意见，而有些人则更注重周围人的意见。例如，小孩很容易受到他人的影响，而老人或在社交网络中有较大影响力的人不容易受到他人的影响。由式（2）可知，ai越高，人越自信，表达意见的时候会越关注自己的观点，而不单纯是自己内部意见和周围人意见的加权均值。

4.3对比实验

为了更好地体现此模型的优势，仿照文献[10]，将其与其他3种启发式方法（Rand，Trust，IO）进行比较。a．Rand[17]：对节点随机排序。b．Ihist[9]：通过计算邻接矩阵相应列的和来表示节点的信任和。被大多数用户节点信任的用户节点在网络中可能会有较强的影响力，因此，按照节点信任总和降序对节点进行排序。c．I0[18]：如果能够说服那些具有消极内部意见的用户节点，让它们的内部意见变成积极的内部意见，那么，总体意见就会增加。因此，取节点的内部意见，对节点进行升序排序。实验结果如表2和图2所示。从实验结果可以看出，所提模型在所有数据集上都具有优势。

5 结束语

提出了一种广义的社交信任网络意见动态模型来解决社交信任网络中的意见最大化问题。与其他方法不同的是，所提模型引入了一个新的自信指数，并利用ADMM算法求解了内部意见问题。在4个数据集上的实验结果证明了该模型的性等来估计aj，以及用此模型解决部分点的表达意见使得总体意见最大化的问题 。

参考文献：

[1] LI F Z， WU J. XUE S. et al. Detecting the evolvingcommunity structure in dynamic social networks[J]. WorldWicle Web， 2020， 23（2）： 715-733.

[2] GARG S， PANWAR D S， GUPTA A， et al. A literature review on sentiment analysis techniques involving socialmedia platforms[C]//Proceedings of the Sixth IntemationalConference on Parallel. Distributed and Grid Computing.Waknaghat： IEEE， 2020： 254-259.

[3] BHATIA B. VERMA A， ANJUM， et al. Analysingcyberbullying using natural language processing byunderstanding jargon in social media[M]//AURELIA S，HIREMATH S S， SUBRAMANIAN K. et al. SustainableAdvanced Computing. Singapore： Springer， 2021： 397-recommender system using deep leaming based textanalysis modeI[J]. Multimedia Tools and Applications， 2020， 79（47）： 35927-35948.

[7] KATARYA R， MASSOUDI M. Recognizing fake news insocial media with deep leaming： a systematicreview[C]//Proceedings of the 4th Intemational Conferenceon Computer， Communication and Signal Processing.Chennai： IEEE. 2020： 1-4.

[8] GUPTA A. KATARYA R. Social media based surveillancesystems for healthcare using machine leaming： a systematicreview[J]. Journal of Biomedical Informatics， 2020， 108：103500.

[9] CHEN S， FAN J， LI G L， et al. Online topic-awareinfluence maximization[J]. Proceedings of the VLDBEndowment， 2015， 8（6）： 666-677.

[10] XU P H. HU W B. WU J， et al. Opinion maximization insocial trust networks[C]//Proceedings of the 29thIntemational Joint Conference on Artificial Intelligence.Huawei： Unknown Publishers. 2020： 1251-1257.

[11] LIU X Y， KONG X N. YU P S. Active opinionmaximization in social networks[C]//Proceedings of the24th ACM SIGKDD Intemational Conference onKnowledge Discovery & Data Mining. London： Associationfor Computing Machinery， 2018 ： 1840-1849.

[12] ABEBE R， KLErNBERG J， PARKES D. et al. Opiniondynamics with varying susceptibility to persuasion[C]//Proceedings of the 24th ACM SIGKDD IntemationalConference on Knowledge Discovery & Data Mining.London： Association for Computing Machinery， 2018：1089-1098.

[13] BERMAN A， PLEMMONS R J. Nonnegative matrices inthe mathematical sciences[J]. Society for Industrial andApplied Mathematics， 1994. 3 5（1）： 5-17.

[14] FRIEDKIN N E， JOffNSEN E C. Social influence andopinions[J]. The Journal of Mathematical Sociology. 1990，15（3/4）： 193-206.

[i5] GABAY D， MERCIER B. A dual algorithm for thesolution of nonlinear variational problems via fmiteelement approximation[J]. Computers & Mathematics withApplications， 1976， 2（1）： 17-40.

[16] BOYD S. PARIKH S. CHU E， et al. Distributedoptimization and statistical leaming via the alternatingdirection method of multipliers[J]. Foundations andTrends～ in Machine Leaming， 2010， 3（1）： 1-122.

[17] LI Y H， CHEN W， WANG Y J， et al. Influence diffusiondynamics and influence maximization in social networkswith friend and foe relationships[C]//Proceedings of the 6thACM Intemational Conference on Web Search and DataMining. Rome： Association for Computing Machinery，2013： 657-666.

[18] MUSCO C， MUSCO C， TSOURAKAKIS C E.Minimizing polarization and disagreement in socialnetworks[C]//Proceedings of the 2018 World Wide WebConference. Lyon： Intemational World Wide WebConferences Steering Committee， 2018 ： 369-3 78.