基于廣義意見動(dòng)態(tài)模型的社交信任網(wǎng)絡(luò)意見最大化問(wèn)題

曾佳媛 張廣

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

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

中圖分類號(hào)：O 157

文獻(xiàn)標(biāo)志碼：A

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

1 相關(guān)研究

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

2 模型構(gòu)建

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

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

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

2.2納什均衡

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

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

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

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

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

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

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

2.4.2平均入評(píng)價(jià)

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

2.4.3自信指數(shù)ai

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

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

在真實(shí)的社交信任網(wǎng)絡(luò)中，一個(gè)用戶對(duì)另一個(gè)用戶的評(píng)價(jià)可能是負(fù)面的。由于PageRank值可能很小，所以，ai可能為負(fù)，這樣是不符合實(shí)際意義的。因此，引入線性整流函數(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）。有必要提的一點(diǎn)是，為了使得ai>0，這里的RELU函數(shù)是在一般的RELU函數(shù)上作了一些調(diào)整。從式（3）中可以看出，如果一個(gè)人在網(wǎng)絡(luò)中很重要或者周圍人對(duì)他的評(píng)價(jià)較高，那么，這個(gè)人的自信指數(shù)就會(huì)比較大。

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

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

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

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

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

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

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

3.2 算法的步驟

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

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

4 實(shí)驗(yàn)研究

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

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

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

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

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

4.3對(duì)比實(shí)驗(yàn)

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

5 結(jié)束語(yǔ)

提出了一種廣義的社交信任網(wǎng)絡(luò)意見動(dòng)態(tài)模型來(lái)解決社交信任網(wǎng)絡(luò)中的意見最大化問(wèn)題。與其他方法不同的是，所提模型引入了一個(gè)新的自信指數(shù)，并利用ADMM算法求解了內(nèi)部意見問(wèn)題。在4個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果證明了該模型的性等來(lái)估計(jì)aj，以及用此模型解決部分點(diǎn)的表達(dá)意見使得總體意見最大化的問(wèn)題 。

參考文獻(xiàn)：

[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.