基于受限非負張量分解的用戶社會影響力分析

魏晶晶，陳暢，廖祥文，陳國龍，程學旗

?

基于受限非負張量分解的用戶社會影響力分析

魏晶晶1,2，陳暢3,4，廖祥文3,4，陳國龍3,4，程學旗5

（1. 福州大學物理與信息工程學院，福建福州350116；2. 福建江夏學院電子信息科學學院，福建福州 350108；3. 福州大學數(shù)學與計算機科學學院，福建福州350116；4. 福州大學福建省網(wǎng)絡計算與智能信息處理重點實驗室，福建福州350116；5. 中國科學院計算技術研究所，北京100086）

針對傳統(tǒng)社會影響力分析方法未能充分考慮觀點和話題信息等問題，提出了一種基于受限非負張量分解的用戶社會影響力分析方法。首先把社交媒介用戶相互評論關系自然地表示成三階張量，然后通過拉普拉斯話題約束矩陣控制張量分解過程，最后根據(jù)分解得到的潛在因子度量用戶觀點社會影響力。該方法的優(yōu)點是能有效地從受限張量分解結果中檢索出給定話題下用戶的社會影響力，同時保持其社會影響力的極性分布。實驗結果表明，該方法的性能優(yōu)于OOLAM和TwitterRank等基準算法。

社會影響力；話題；觀點；張量分析

1 引言

社會影響力是指一個人的思想、情感或行為被他人所影響的現(xiàn)象[1,2]，其作為一種影響網(wǎng)絡結構和信息傳播的重要因素，受到了許多研究者的關注。社會影響力分析往往通過分析人們的社會交互行為來研究人們的社會影響，并在多個研究領域中起到關鍵作用，如推薦系統(tǒng)[3]、社交網(wǎng)絡信息傳播[4,5]、突發(fā)事件檢測[6]和廣告投放[7]等。

在線社交網(wǎng)絡出現(xiàn)和興起之前，針對社會影響力的研究工作主要集中在理論層面，包括二級傳播理論、弱連帶優(yōu)勢理論、強連帶優(yōu)勢理論和結構洞理論等[8]。隨著微博、Facebook等社交媒體廣泛使用，人們可以在社交媒介上隨時隨地發(fā)布信息，而不受時間和空間的限制。這些海量的用戶自創(chuàng)造數(shù)據(jù)(user generated data)蘊含非常豐富的用戶信息，如用戶觀點、用戶間交互關系等，為社會影響力分析理論的驗證與應用提供了理想的環(huán)境。從內容角度，社會影響力分析可分為3方面[9]：1) 社會影響力自身的識別，研究影響力和相關因素的聯(lián)系；2) 社會影響力的度量，希望能夠找到合適的度量社會影響力的方法；3) 社會影響力的動態(tài)傳播，即刻畫社會影響力的動態(tài)特性。社會影響力的度量方法主要有4個角度[9]：1）基于網(wǎng)絡拓撲結構的度量，通過衡量網(wǎng)絡圖中節(jié)點與連接的重要性來體現(xiàn)社會影響力的大?。?）基于用戶行為的度量，使用統(tǒng)計等方法分析用戶在社交網(wǎng)絡中留下的行為數(shù)據(jù)；3）基于用戶交互信息的度量，主要包括基于交互信息內容的度量和基于話題的度量；4）基于時間因素、轉移熵等其他度量。

從層次角度，社交影響力分析主要有以下3個層次。1）整體社交影響力分析，毛佳昕等[8]提出用戶關注、微博轉發(fā)這2種用戶行為與時間維度有關，以及轉發(fā)延遲的分布近似服從冪律分布2個假設，并通過假設檢驗驗證，最后使用全局閱讀期望的方法度量用戶影響力。2）話題級社交影響力分析，Weng等[10]提出了一種結合網(wǎng)絡結構與話題信息來計算話題級社會影響力的方法，驗證了話題相似的用戶間更容易互相產生影響。據(jù)此，在PageRank基礎上加入話題相似度的因素，提出了一種TwitterRank方法并取得了不錯的效果。3）信息條目級社交影響力分析：Cui等[1,2]提出了一種更細粒度的社交影響力度量思路，即信息條目級社會影響力度量。其使用受限非負矩陣分解的方法來預測用戶在某一話題下的社會影響力大小，矩陣約束的部分考慮了用戶朋友活躍度、用戶與朋友關系強度以及話題信息，該方法的實驗效果較好。

當前，細粒度的社會影響力分析更加引起了研究者的重視，用戶觀點已成為度量用戶社會影響力不可忽視的因素。另一方面，用戶社會影響力與話題密切相關。Cai等[11]曾提出利用帶有傾向性連接的網(wǎng)絡度量用戶的社會影響力，并提出了一種可并行化的PageRank改進方法來求解所提出的OOLAM模型，得到2個獨立的用戶正負面影響力評分，從而更加細致地刻畫了社會影響力。然而，該方法不能很好地融入用戶的話題信息，難以分析領域專家的社會影響力。Weng等[10]提出的TwitterRank方法將話題信息融入到用戶社會影響力分析中，能夠有效地檢索出給定話題下比較重要的用戶，但是卻不能反映出用戶社會影響力的正負面傾向。導致這一局限性的根本原因在于基于圖的方法主要是刻畫二維數(shù)據(jù)，難以同時將不同的信息加入到分析過程中。張量[12]是一種特別適合表達多維數(shù)據(jù)、融合不同信息的數(shù)據(jù)表達方式，廣泛應用于多模態(tài)特征融合相關研究。

因此，本文提出一種基于受限非負張量分解的用戶觀點社會影響力分析方法，度量特定話題下用戶的社會影響力及其影響力的極性分布。該方法首先使用張量表示用戶相互評論關系，然后通過Laplacian矩陣將話題信息融入到張量分解中，最后基于分解得到的潛在因子度量在特定話題下用戶觀點的社會影響力。通過實驗表明，本文方法不僅在效果上比OOLAM、TwitterRank等方法有一定的提升，而且能夠更加細致地刻畫用戶觀點的社會影響力。

2 用戶觀點社會影響力估計模型

2.1 問題描述

2.2 張量代數(shù)介紹

遵循Kolda和Bader的符號描述，簡要介紹與本文工作相關的張量代數(shù)基本知識[12]。

(2)

2.3 基于受限非負張量分解的用戶觀點社會影響力分析方法

在應用的驅動下，越來越多研究工作關注話題級或條目級等更加細致的用戶社會影響力分析。本文所關注的問題是分析特定話題下用戶觀點的社會影響力和極性分布。通過觀察，本文發(fā)現(xiàn)：1）與話題相關度高的用戶往往越容易獲得其他用戶的評論，其收到的評論總量一般會高出與話題無關的用戶；2）話題相關的用戶所發(fā)布的文檔往往采用分布類似的詞來描述話題。基于用戶話題相似性特征，本文提出了一種基于受限非負張量的方法。該方法首先利用張量自然地對用戶之間的評論關系建模，然后通過加入用戶話題相似矩陣控制張量分解過程，最后基于張量分解得到的潛在因子度量用戶觀點的社會影響力和觀點極性分布。

2.3.1 基于用戶評論關系的張量構建

用戶與用戶之間帶有觀點評論的三元關系，可以用一個三階張量刻畫用戶間的評論行為。其中，張量的1模式表示被評論用戶，2模式表示發(fā)表評論的用戶，3模式表示評論的觀點傾向性，傾向性分為正面、中性、負面3種情況。這里的模式對應張量的每一個維度。每個張量元素值為

需要說明的是，判定用戶u對用戶u的評價觀點，即觀點傾向性的極性，是通過基于情感詞典[13]的判定方法獲得的。若評價內容中正面情感詞數(shù)大于負面情感詞數(shù)，則記為一次正面觀點的評價，若評價內容中正面情感詞數(shù)等于負面情感詞數(shù)，則記為一次中性觀點的評價，否則記為一次負面觀點的評價。

2.3.2 用戶話題相似性計算

(6)

2.3.3 改進的受限非負張量分解方法

針對評論關系張量，根據(jù)用戶話題相似性假設，提出一種CP(CANDECOMP/PARAFAC)分解算法CP_ALS[14]的改進算法HF-CP-ALS，并通過該算法分解得到刻畫用戶觀點社會影響力的潛在因子矩陣。

為求解目標函數(shù)式(7)，先求解在CP_ALS算法中的1模式最優(yōu)化目標函數(shù)為

在CP_ALS算法1模式的最優(yōu)化目標函數(shù)中加入用戶話題相似性限制，從而獲得限定話題下的用戶觀點社會影響力。在該約束下，話題相關而且影響力小的那些用戶，其用戶觀點社會影響力將提升，對于那些話題無關而且影響力大的用戶，其用戶觀點社會影響力將減小。此外，為了保證潛在因子的可解釋性，引入的約束，得到

(9)

直接求解式（9）所描述的優(yōu)化問題時間復雜度過高，為簡化運算引入拉普拉斯矩陣[15]=?，。是一個對角矩陣，。由于近似為對角占優(yōu)矩陣，因此用近似，可以得到

(10)

引入拉普拉斯矩陣后，待優(yōu)化的目標函數(shù)可以寫成如下形式

(11)

張量分解中解決該類型的優(yōu)化問題常用交替最小二乘法（ALS）求解目標函數(shù)，即更新其中一個因子矩陣時固定另外2個因子矩陣。表示限制項的重要程度，因此先計算對的微分

(12)

(14)

至此已經(jīng)得到了3個潛在因子矩陣的更新規(guī)則，加入非負性約束后可以得到算法HF-CP-ALS，其偽代碼如圖3所示。

Procedure HF-CP-ALS(X,D,R) 初始化 Repeat單位化的每一列，將中小于0的值置零，更新λ單位化的每一列，將中小于0的值置零，更新λ單位化的每一列，將中小于0的值置零，更新λUntil收斂或達到最大迭代次數(shù)return λ，A(1)，A (2)，A (3)end procedure

在算法HF-CP-ALS中，值得注意的是在每一次更新因子矩陣完畢后，需要對矩陣做一次列向量單位化。特別地，潛在因子矩陣具有非負性約束，因此，在更新完(1)、(2)或(3)時還需將其中小于零的元素置為0，從而保持潛在因子矩陣非負，即保證潛在因子矩陣的可解釋性。最后同時更新向量。HF-CP-ALS算法最終可以求得各個模式的潛在因子矩陣和向量。

2.3.4 用戶觀點社會影響力度量

用戶觀點的社會影響力往往由一系列潛在因子決定，可通過分析潛在特征矩陣計算得到[16,17]。通過算法HF-CP-ALS容易得到話題約束下的用戶觀點潛在因子：、和。設表示向量的長度，那么分解結果可以看成個秩為一的張量之和，其計算式可以寫成

(17)

不難看出，式（17）就是利用張量分解結果估計原始張量，類似張量補全的工作。不同的是，加入了用戶話題相似性約束。在該約束下，對于那些社會影響力大且與話題無關的用戶，其影響力的量化數(shù)值將分享給大量話題無關且社會影響力小的用戶。反映在最終分解結果中的就是在給定話題下，話題無關但是社會影響力大的用戶的社會影響力得分將變得相對較小。同理，話題相關的用戶將受到那些話題無關用戶的影響很小，在張量分解過程中能夠很好地保持這些數(shù)值的大小。在分解結果中，比起那些話題無關的用戶，其用戶觀點社會影響力得分將變得相對較大，在最終用戶觀點社會影響力計算中取得較高的分值。因此，在用戶相似性的約束下，本文方法最終能夠從估計的張量中較好地選出那些話題相關且社會影響力大的用戶。

3 實驗結果及分析

3.1 數(shù)據(jù)描述

如表1所示，實驗數(shù)據(jù)來自新浪微博，包括籃球、經(jīng)濟、法律、健康4個話題，共66 754個用戶、282 748條微博。為了更加詳盡地描述數(shù)據(jù)構成，圖4統(tǒng)計了所有話題中擁有相同數(shù)量級粉絲數(shù)的目標用戶分布。不難看出，粉絲數(shù)量和目標用戶數(shù)量近似符合冪律分布（在對數(shù)—對數(shù)坐標下近似為一條直線）。因此該數(shù)據(jù)中的目標用戶具有一定的代表性。

表1 實驗數(shù)據(jù)描述

以籃球話題為例，數(shù)據(jù)內容包含2個部分：1) 用戶間交互關系；2) 用戶信息。其中，用戶間交互關系可以使用三元組表示，其中，表示被評論用戶，表示發(fā)表評論的用戶，用戶對用戶進行了評論并且評論內容是，、和分別表示正面、負面和中性的評論內容。根據(jù)預先設定的話題“籃球”，通過新浪微博提供的搜索相關用戶功能獲取目標用戶集合，剩余所需的數(shù)據(jù)則通過爬取新浪微博頁面得到。目標用戶將均與籃球相關，即曾發(fā)表過與籃球有關的微博，用戶間的交互關系是從每個被評論用戶各自發(fā)表的40條微博中獲取的。由于評論量可能非常龐大，只選取每條微博的前30條評論關系。用戶信息則包括用戶發(fā)表過的微博內容，包括每個被評論用戶最多200條的微博。

實驗的關鍵是如何確定給定話題下用戶觀點的社會影響力排序。實驗中確定該影響力排序列表的方法將結合用戶與話題的相關性，由5位均參加過COAE2013-COAE2015、SIGHAN2015標注工作的標注者進行標注。提供給這5位標注者的數(shù)據(jù)包括：1）用戶列表；2）用戶主頁地址，可以進入目標用戶主頁查看該用戶的詳細情況，包括粉絲數(shù)、評論量、職業(yè)、發(fā)表過的微博等。每位標注者根據(jù)這些數(shù)據(jù)，判斷用戶在給定話題下的社會影響力大小，然后選出、和的用戶。如表2所示，5位標注者的指標在0.62以上，因此對用戶觀點社會影響力標注在一定程度上是可接受的。

表2 數(shù)據(jù)標注的Kappa指標

3.2 實驗設計

實驗環(huán)境為Matlab 2010，Intel(R) Pentium(R) CPU G645 2.90 GHz，8 GB內存。將基準方法與本文的方法應用在相同的數(shù)據(jù)集上，計算得到各個用戶在給定話題下的社會影響力得分，即排序結果。最后，基于人工標注的社會影響力用戶列表，比較各個方法在不同評價指標的性能優(yōu)劣。參與實驗的基準方法包括以下幾方面。

1) CP：未添加本文約束的CP分解方法[14]，從分解結果計算用戶影響力的方法與本文相同。

2) CP+BM 25：將話題相關性BM 25結合CP分解方法，計算方法是在CP分解的結果上乘以BM 25話題相關性得分。

3) OOLAM[11]：OOLAM模型的計算結果是用戶正面影響力和負面影響力2個得分，本文對比實驗中取正負面影響力的均值作為用戶社會影響力得分。

4) OOLAM+BM 25：由于OOLAM未考慮話題信息，本文對比實驗中將用戶話題相關性BM 25得分乘以OOLAM方法的結果作為用戶社會影響力得分。

5) TwitterRank[10]：TwitterRank的計算結果是用戶在特定話題下的重要程度得分，本文實驗直接使用該得分作為用戶社會影響力得分。

6) TR+RA：由于TwitterRank未考慮用戶間評論的交互關系。因此在對比實驗中，將用戶受到評論的數(shù)量乘以TwitterRank的結果作為用戶影響力得分。

3.2.1 評價指標

本文所采用的評價指標有以下3個指標。

1) 排序精度指標

2) 張量分解精度指標

3) 相關性評價指標

使用Pearson相關系數(shù)來評價本文方法計算的用戶社會影響力極性分布與用戶真實的社會影響力極性分布的相關強度。計算式如下

其中，和表示需要度量相關性的2個向量，表示這2個向量的長度，和表示均值。實驗中，取每個被評價用戶收到的正面、中性、負面評價數(shù)量作為用戶真實的社會影響力極性分布，對這3個方面的評價數(shù)量做歸一化得到的取值。而的取值就是本文方法對用戶社會影響力極性分布的估計值。最后取所有用戶的，計算均值作為評價本文方法反映用戶社會影響力極性分布性能的指標。

3.2.2 實驗結果分析

1) 參數(shù)確定

2) 用戶社會影響力排序精度比較

表3 本文的方法與基準方法對比實驗結果

3) 用戶社會影響力極性特征

為了評價本文方法刻畫用戶社會影響力極性分布的性能，以用戶正面、負面和中性的評論分布作為用戶真實的社會影響力極性分布，分別計算每個用戶真實社會影響力極性分布與預測結果的Pearson相關性得到均值，結果如表4所示。籃球、經(jīng)濟、法律和健康這4個話題的Pearson 相關系數(shù)值均大于0.70，具有強相關性。因此本文的方法能夠較好地反映用戶社會影響力的極性分布。

表4 話題的Pearson相關系數(shù)值

根據(jù)實驗結果，選出一位具有代表性的用戶，將其傾向性分布繪圖，結果如圖6所示。該用戶的正面社會影響力占主導，可以理解為其他用戶對他的反映往往是積極的。不難發(fā)現(xiàn)，在本文提出的方法中，借助于用戶社會影響力極性分布，可以更加全面的分析用戶的社會影響，進而為推薦系統(tǒng)、社交網(wǎng)絡信息傳播、突發(fā)事件檢測和廣告投放等應用提供更為細致的參考數(shù)據(jù)。

4 結束語

本文提出了一種在給定查詢話題下融合用戶觀點的用戶社會影響力分析模型，提出了一種受限的CANDECOMP/PARAFAC(CP)分解方法并應用于社會影響力分析。首先，在CP分解中加入用戶相似性約束，為保證張量分解結果中因子矩陣的可解釋性又加入了潛在因子非負約束。其次，為解決受約束的CP分解，設計了一種CP_ALS的改進算法HF-CP-ALS求解本文的模型。最后，通過分析潛在因子評定用戶的社會影響力得分，并可以根據(jù)張量評論傾向性維度的潛在因子得到用戶社會影響力的極性分布，在用戶社會影響力的分析上提供了更加詳盡的刻畫。在與基準方法的對比實驗中，本文提出的方法表現(xiàn)出了較好的性能。

[1] CUI P, WANG F, YANG S, et al. Item-level social influence prediction with probabilistic hybrid factor matrix factorization[C]//AAAI. c2011: 331-336.

[2] CUI P, WANG F, LIU S, et al. Who should share what?: item-level social influence prediction for users and posts ranking[C]//The 34th International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM, c2011:185-194.

[3] RASHID A M, KARYPIS G, RIEDL J. Influence in ratings-based recommender systems: an algorithm- independent approach[C]//The SIAM International Conference on Data Mining. c2005:556-560.

[4] BAKSHY E, HOFMAN J M, MASON W A, et al. Everyone's an influencer: quantifying influence on Twitter[C]//The fourth ACM International Conference on Web Search and Data Mining. ACM, c2011: 65-74.

[5] YANG J, LESKOVEC J. Modeling information diffusion in implicit networks[C]//2010 IEEE 10th International Conference on Data Mining (ICDM). IEEE, c2010: 599-608.

[6] SAKAKI T, OKAZAKI M, MATSUO Y. Earthquake shakes Twitter users: real-time event detection by social sensors[C]//The 19th International Conference on World Wide Web. ACM, c2010: 851-860.

[7] BAKSHY E, ECKLES D, YAN R, et al. Social influence in social advertising: evidence from field experiments[C]//The 13th ACM Conference on Electronic Commerce. ACM, c2012: 146-161.

[8] 毛佳昕, 劉奕群, 張敏, 等. 基于用戶行為的微博用戶社會影響力分析[J]. 計算機學報, 2014, 37(4): 791-800.

MAO J X, LIU Y Q, ZHANF M, et al. Social influence analysis for micro-blog user based on user behavior[J]. Chinese Journal of Computers, 2014, 37(4): 791-800.

[9] 吳信東, 李毅, 李磊. 在線社交網(wǎng)絡影響力分析[J]. 計算機學報, 2014, 37(4):735-752. WU X D, LI Y, LI L. Influence analysis of online social networks[J]. Chinese Journal of Computers, 2014, 37(4):735-752.

[10] WENG J, LIM E P, JIANG J, et al. Twitterrank: finding topic-sensitive influential twitterers[C]//The Third ACM International Conference on Web Search and Data Mining. ACM, c2010: 261-270.

[11] CAI K, BAO S, YANG Z, et al. OOLAM: an opinion oriented link analysis model for influence persona discovery[C]//The fourth ACM International Conference on Web Search and Data Mining. ACM, c2011: 645-654.

[12] KOLDA T G, BADER B W. Tensor decompositions and applications[J]. SIAM Review, 2009, 51(3): 455-500.

[13] DONG Z D, DONG Q.“ZhiHu”[EB/OL]. http://www.keenAge.com.

[14] CICHOCKI A, ZDUNEK R, PHAN A H, et al. Nonnegative matrix and tensor factorizations: applications to exploratory multi-way data analysis and blind source separation[M]. John Wiley & Sons, 2009:42-46.

[15] HU X, TANG L, TANG J, et al. Exploiting social relations for sentiment analysis in microblogging[C]//The Sixth ACM International Conference on Web Search and Data Mining. ACM, c2013: 537-546.

[16] DAVIDSON I, GILPIN S, WALKER P B. Behavioral event data and their analysis[J]. Data Mining and Knowledge Discovery, 2012, 25(3): 635-653.

[17] KOLDA T G, BADER B W, KENNY J P. Higher-order Web link analysis using multilinear algebra[C]//Fifth IEEE International Conference on Data Mining. IEEE, c2005: 242-249.

User social influence analysis based on constrained nonnegative tensor factorization

WEI Jing-jing1,2, CHEN Chang3,4, LIAO Xiang-wen3,4, CHEN Guo-long3,4, CHENG Xue-qi5

(1. College of Physics and Information Engineering, Fuzhou University, Fuzhou 350116, China; 2. College of Electronics and Information Science, Fujian Jiangxia University, Fuzhou 350108, China; 3. College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350116, China; 4. Fujian Provincial Key Laboratory of Networking Computing and Intelligent Information Processing, Fuzhou University, Fuzhou 350116,China; 5. Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100086, China)

Existing models for measuring user social influence fail to integrate both opinion and topic information. Therefore, a new constrained nonnegative tensor factorization method combining user’s opinion and the topical relevance was proposed. The method represented user’s comment relations as 3-order tensor, factorized the comments tensor constrained by Laplacian topical matrix, and then measures user influence according to the latent factors resulting from the tensor factorization. Thus, the new method not only was capable to effectively calculate the strength of user social influence on given topic, but also kept the polarity allocation of social influence. The experimental result shows that the performance of the proposed method is better than that of the baseline methods such as OOLAM , TwitterRank, etc.

social influence, topic, opinion, tensor analysis

TP391

A

10.11959/j.issn.1000-436x.2016125

2015-05-22；

2016-01-30

廖祥文，liaoxw@fzu.edu.cn

國家自然科學基金資助項目（No.61300105）；教育部博士點聯(lián)合基金資助項目（No.2012351410010）；福建省科技重大專項基金資助項目（No.2013H6012）；福州市科技計劃基金資助項目（No.2012-G-113, No.2013-PT-45）

The National Natural Science Foundation of China (No.61300105), The Research Fund for Doctoral Program of Higher Education of China (No.2012351410010), The Key Project of Science and Technology of Fujian (No.2013H6012), The Project of Science and Technology of Fuzhou (No.2012-G-113, No.2013-PT-45)

魏晶晶（1984-），女，福建平潭人，福州大學博士生，主要研究方向為網(wǎng)絡文本觀點挖掘。

陳暢（1991-），男，浙江江山人，福州大學碩士生，主要研究方向為社交網(wǎng)絡、數(shù)據(jù)挖掘等。

廖祥文（1980-），男，福建泉州人，博士，福州大學副教授、碩士生導師，主要研究方向為Web信息檢索與觀點挖掘。

陳國龍（1965-），男，福建莆田人，博士，福州大學教授、博士生導師，主要研究方向為網(wǎng)絡計算、智能信息處理等。

程學旗（1971-），男，安徽安慶人，博士，中國科學院計算技術研究所研究員、博士生導師，主要研究方向為網(wǎng)絡科學與社會計算、互聯(lián)網(wǎng)搜索與挖掘等。