曾佳媛 張廣

摘要：提出了一種廣義意見動態(tài)模型（ GODM），此模型可以通過動態(tài)計算每個人的表達意見來解決社交信任網(wǎng)絡中的意見最大化問題。在模型中提出了一個新的、合理的、可解釋的自信指數(shù)ai，ai由個人的社會地位與其周圍人的評價共同決定。并且利用對角占優(yōu)理論，得到模型達到納什均衡狀態(tài)時的最優(yōu)解析解。設計了一種具有，1形式的交替方向乘子法來最大化現(xiàn)有的總體意見。進行了一系列實驗，實驗結(jié)果表明，此方法在4個數(shù)據(jù)集上都有較好的結(jié)果。在4個數(shù)據(jù)集上，解決內(nèi)部意見問題的平均效益分別提升了66.4%，88.7%，47.8%和34.1%。實驗結(jié)果充分驗證了所提模型的優(yōu)越性。

關(guān)鍵詞：意見最大化；社交信任網(wǎng)絡；自信指數(shù)；有限預算

中圖分類號：O 157

文獻標志碼：A

近年來，大規(guī)模社交媒體網(wǎng)絡的日益普及極大地推動了社交網(wǎng)絡分析的發(fā)展。人們?nèi)绾瓮ㄟ^與他人的社交互動形成自己的觀點一直是社會科學領域的研究課題。在社交網(wǎng)絡上，用戶可以對產(chǎn)品或?qū)崟r新聞表達自己的意見。通過量化這些意見，可以確定一個網(wǎng)絡中的用戶對產(chǎn)品或新聞的整體看法。人們可以定量研究用戶意見間的相互作用，并通過有針對性的干預來提高總體意見值。

1 相關(guān)研究

社交信任網(wǎng)絡是某些群體（人、企業(yè)和組織）之間關(guān)系相對穩(wěn)定的網(wǎng)絡。它可以表示為有向符號加權(quán)圖，如圖l所示。社交信任網(wǎng)絡的研究在社區(qū)檢測[1]、情感分析[2-4]、意見領袖檢測[5]、產(chǎn)品推薦[6]、識別假新[7]、監(jiān)控系統(tǒng)[8]及意見最大化[9-12]等方面有廣泛應用。近年來，有許多基于社交互動的意見動態(tài)模型被提出[9-12]，Chen等[9]提出了一種算法來尋找對網(wǎng)絡產(chǎn)生影響最大的K個節(jié)點。Liu等[11]考慮了意見最大化問題，其目標是在多輪活動中找到種子用戶集，用來最大化目標產(chǎn)品的總體意見傳播。除了考慮直接改變?nèi)藗儍?nèi)部意見的干預，Abebe等[12]還考慮了改變?nèi)藗儗φf服敏感性的干預。其目的是利用修改用戶的敏感性來最大限度地提高納什均衡下的總體意見。Xu等[10]提出了一種新的連續(xù)值意見動態(tài)模型，該模型更符合真實場景，取得了良好的效果。但是，文獻[10]中仍有一些可以改進的地方，如它將每個用戶的表達意見考慮為個人內(nèi)部意見和周圍人意見的加權(quán)平均值。然而，在現(xiàn)實生活中，每個人的性格都是不同的，也就是說，不同的人受別人影響的程度也不同。因此，本文在文獻[10]的基礎上進行了一些改進，建立了一個廣義的社交信任網(wǎng)絡意見動態(tài)模型來具體計算每個人的表達意見，并解決了意見最大化問題。提出了一種新的自信指數(shù)ai，這與文獻[12]中隨機選擇的ai不同，它取決于一個人的社會地位和周圍人的評價。對于不同的人類群體，ai的取值范圍是不同的。利用對角占優(yōu)理論和Friedkin-Johnsen模型給出了達到納什均衡時的解析解，實現(xiàn)了文獻[10]中模型的推廣。引入了一種成熟的優(yōu)化算法一一交替方向乘子法，并利用該算法所衍生的特殊形式——Z1正則化形式解決了意見最大化問題。

2 模型構(gòu)建

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

定義1[13]對于矩陣A= （aij）nxn，若其對角元素的絕對值大于非對角元素的絕對值之和，即laiil>∑laijl，i=1，2，…，，z，則A=（aij）nxn嚴格對角占優(yōu)。

引理1[13]若A= （aij）nxn是嚴格對角占優(yōu)矩陣，則det A≠0。

2.2納什均衡

定義2納什均衡是博弈論中一種解的概念，它是指滿足下面性質(zhì)的策略組合：任何一位玩家在此策略組合下單方面改變自己的策略（其他玩家策略不變）都不會提高自身的收益。

在一個博弈過程中，無論對方的策略選擇如何，當事人一方都會選擇某個確定的策略，則該策略被稱為支配性策略。如果任意一位參與者在其他所有參與者的策略確定的情況下，其選擇的策略是最優(yōu)的，那么，這個組合就被定義為納什均衡。當每個博弈者的均衡策略都達到自己期望收益的最大值時，這個策略組合被稱為納什均衡。2.3 Friedkin-Johnsen模型

社交信任網(wǎng)絡可以表示為有向符號加權(quán)圖G=（VE），其中，V={1，2，…，n）為節(jié)點集，E為弧集（有向邊集）。ωij為從i到j的有向邊（i，j）的權(quán)重，

2.4社交信任網(wǎng)絡的廣義意見動態(tài)模型

從Friedkin-Johnsen模型可以看出，對于每個節(jié)點i，其表達的意見是其內(nèi)部意見與周圍節(jié)點意見的加權(quán)平均值。然而，在現(xiàn)實生活中，人們的性格是不同的，每個人受到他人影響的程度也是不同的。因此，建立了一個廣義的社交信任網(wǎng)絡意見動態(tài)模型。

首先寫出社交游戲的共識成本函數(shù)

在社交網(wǎng)絡中，ai越高，表明這個人在發(fā)表意見的時候更傾向于關(guān)注自己的想法，而不會輕易被他人的意見所影響。在此模型中，自信指數(shù)與一個人的社會地位和別人對他的評價，即與其在網(wǎng)絡中的重要性以及周圍人對他的評價有關(guān)。

2.4.2平均入評價

在社交網(wǎng)絡中，每個節(jié)點都有2個身份：源節(jié)點（出節(jié)點）和目標節(jié)點（人節(jié)點）。作為一個目標節(jié)點，指向它的邊的符號和權(quán)值代表它的人鄰居對它的評價。在這里，對于節(jié)點i，使用平均人評價m（i）來表示它的人鄰居對它的平均評價，即

2.4.3自信指數(shù)ai

網(wǎng)絡中每個用戶節(jié)點的自信程度與其在網(wǎng)絡中的影響力大小和別人對其的評價密切相關(guān)。因此，這里的自信指數(shù)ai由PageRank值和平均人評價加權(quán)求得，其計算公式為式中：似f），r（i）分別表示節(jié)點i的平均人評價和PageRank值；q為常數(shù)，且滿足0≤q≤1。

q越大，說明在定義自信指數(shù)時更注重周圍人的評價；q越小，說明更注重PageRank值，即每個個體在社會網(wǎng)絡中的重要性。這里取q= 0.5，也就是平均人評價和PageRank值同等重要。

在真實的社交信任網(wǎng)絡中，一個用戶對另一個用戶的評價可能是負面的。由于PageRank值可能很小，所以，ai可能為負，這樣是不符合實際意義的。因此，引入線性整流函數(shù)，將ai的值限制在（0，1）內(nèi)，則式（2）變?yōu)?/p>

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

（3）這里RELU（x）= max {0.0001，x）。有必要提的一點是，為了使得ai>0，這里的RELU函數(shù)是在一般的RELU函數(shù)上作了一些調(diào)整。從式（3）中可以看出，如果一個人在網(wǎng)絡中很重要或者周圍人對他的評價較高，那么，這個人的自信指數(shù)就會比較大。

定義3總體意見p（z*）表示納什均衡狀態(tài)下所有用戶表達意見的總和，p（z*）=∑z：= lr（A+（I—A）L）-1．As，這里的1是全1向量。

定義4在社交信任網(wǎng)絡中，為了提高整個網(wǎng)絡的總體意見，需要付出一定的費用來改變其中一些人的內(nèi)部意見，這些費用的總和稱為預算。

定義5在社交信任網(wǎng)絡中通過預算改變了一部分人的內(nèi)部意見，會使得總體意見增加?？傮w意見的增加量被稱為效益。

3 社會信任網(wǎng)絡中的意見最大化

定義6給定社交信任網(wǎng)絡G、內(nèi)部意見向量s和預算μ，內(nèi)部意見問題的目標是找出每個用戶節(jié)點的內(nèi)部意見的修改情況A，以最大化總體意見p（z*）。

為了解決內(nèi)部意見問題，使用一種傳統(tǒng)的優(yōu)化算法——交替方向乘子法（ADMM算法）來進行求解。3.1 利用ADMM算法解決內(nèi)部意見問題

ADMM算法是Gabay和Mercier提出的一種混合了雙上升法的可分解性和乘數(shù)法優(yōu)越性的收斂算法[15]。當目標函數(shù)中有多個變量時，對于凸優(yōu)化問題的求解是困難的。ADMM算法利用變量分離法將問題分解成幾個簡單的子問題，然后并行求解，這樣可以得到原問題的最優(yōu)解[16]。它是一種簡單但強大的算法，非常適合于解決分布式凸優(yōu)化，特別是應用統(tǒng)計和機器學習中出現(xiàn)的問題。

3.2 算法的步驟

要解決的優(yōu)化問題為

算法1的第1行是將As初始化為全零向量。第2～5行是使用ADMM算法尋找最優(yōu)解的過程。這里設置的停止條件為IIXk一Zkll<10-4。最后一行是更新△s。初始內(nèi)部意見向量是用3種方法隨機選擇的。

4 實驗研究

本文進行了一系列實驗來評估所提出的方法。從以下2個方面進行實驗：首先，將所提模型獲得的結(jié)果與文獻[10]中的模型進行比較；其次，為了進一步說明所提模型的優(yōu)越性，將所提模型與其他啟發(fā)式方法進行比較，所有的實驗結(jié)果都表明了所提方法的優(yōu)越性。

4.1 數(shù)據(jù)集

實驗中使用到的數(shù)據(jù)集如下：a．Alpha。b．OTC。Alpha和OTC邊上的權(quán)重為[-10，10]，將它歸一化為[-1，1]。c．WikiElec。d．WikiRfa。這2個網(wǎng)絡中的邊的符號、權(quán)重與信任密切相關(guān)。關(guān)于這些網(wǎng)絡的具體數(shù)據(jù)詳見斯坦福實驗數(shù)據(jù)集（ SNAP）。

4.2 內(nèi)部意見的初始化

從表1可以看出，所提模型與文獻[10]中的模型相比具有明顯的優(yōu)勢。加入自信指數(shù)后，更加符合實際場景。每個人都有不同的個性，有些人更注重自己的意見，而有些人則更注重周圍人的意見。例如，小孩很容易受到他人的影響，而老人或在社交網(wǎng)絡中有較大影響力的人不容易受到他人的影響。由式（2）可知，ai越高，人越自信，表達意見的時候會越關(guān)注自己的觀點，而不單純是自己內(nèi)部意見和周圍人意見的加權(quán)均值。

4.3對比實驗

為了更好地體現(xiàn)此模型的優(yōu)勢，仿照文獻[10]，將其與其他3種啟發(fā)式方法（Rand，Trust，IO）進行比較。a．Rand[17]：對節(jié)點隨機排序。b．Ihist[9]：通過計算鄰接矩陣相應列的和來表示節(jié)點的信任和。被大多數(shù)用戶節(jié)點信任的用戶節(jié)點在網(wǎng)絡中可能會有較強的影響力，因此，按照節(jié)點信任總和降序?qū)?jié)點進行排序。c．I0[18]：如果能夠說服那些具有消極內(nèi)部意見的用戶節(jié)點，讓它們的內(nèi)部意見變成積極的內(nèi)部意見，那么，總體意見就會增加。因此，取節(jié)點的內(nèi)部意見，對節(jié)點進行升序排序。實驗結(jié)果如表2和圖2所示。從實驗結(jié)果可以看出，所提模型在所有數(shù)據(jù)集上都具有優(yōu)勢。

5 結(jié)束語

提出了一種廣義的社交信任網(wǎng)絡意見動態(tài)模型來解決社交信任網(wǎng)絡中的意見最大化問題。與其他方法不同的是，所提模型引入了一個新的自信指數(shù)，并利用ADMM算法求解了內(nèi)部意見問題。在4個數(shù)據(jù)集上的實驗結(jié)果證明了該模型的性等來估計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.