陳 暢，魏晶晶，廖祥文，林柏鋼，陳國龍

(福州大學 數(shù)學與計算機科學學院，福建 福州 350116)

融合用戶觀點的社會影響力分析

陳 暢，魏晶晶，廖祥文，林柏鋼，陳國龍

(福州大學 數(shù)學與計算機科學學院，福建 福州 350116)

社交媒介已經(jīng)成為了一種分享交換信息的重要平臺，識別出其中影響力高的用戶已經(jīng)廣泛地應(yīng)用于推薦系統(tǒng)、專家識別、廣告投放等應(yīng)用。該文提出了一種受限張量分解方法，其能識別出給定主題下影響力高的用戶，同時保持其影響力的極性分布(例如正面、中性、負面)。該方法通過拉普拉斯矩陣引入用戶主題相似性約束，控制張量分解過程，使用分解結(jié)果計算用戶影響力得分。實驗結(jié)果表明，該方法在社會影響力分析中的性能優(yōu)于OOLAM、TwitterRank等基準算法，并具有良好的可擴展性。

張量分解；觀點；拉普拉斯矩陣；社會影響力分析

Abstract: Social media has become an popular platform for sharing and exchanging information. The identification of users of social influence has already been applied into many applications including recommendation systems, experts finding, social advertising et al. This paper proposes a constrained tensor factorization method to identify users with high social influence. In the factorization result, the polairy allocation of influence is preserved (i.e. positive, neutral and negative influence). This method fuses topical similarity of users by Laplacian matrix, which would control tensor factorization to approximate the user influence. Experimental results demonstrate that the method outperformes the OOLAM, TwitterRank etc. in terms of ranking accuracy.

Key words: tensor factorization; opinion; Laplacian matrix; social influence analysis

收稿日期： 2015-09-18 定稿日期： 2016-03-20

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

1 引言

隨著社交網(wǎng)絡(luò)的飛速發(fā)展(例如微博、Facebook、Twitter等)，包括文本、評論、關(guān)注、轉(zhuǎn)發(fā)等由用戶生成的數(shù)據(jù)正在飛速增長。這些數(shù)據(jù)給我們提供了機會去分析和度量社交網(wǎng)絡(luò)中用戶的影響力。根據(jù)Wikipedia的解釋，社會影響力(social influence)是指一個人的思想、情感或行為被他人所影響的現(xiàn)象。因此，社會影響力分析具有很高的應(yīng)用價值，其應(yīng)用包括專家識別[1]、廣告投放[2]、推薦系統(tǒng)[3]等。

然而，社會影響力是一種控制人與人之間關(guān)系的復(fù)雜因素，其分析和度量是一件困難的任務(wù)。近幾年，該問題吸引了許多數(shù)據(jù)挖掘相關(guān)的學者、團體。Domingos等人[4]對用戶影響力在營銷網(wǎng)絡(luò)中的傳播規(guī)律展開了探索，他們發(fā)現(xiàn)具有廣泛影響力的用戶在營銷傳播中起到重要作用。Liu等人[5]提出了挖掘話題級社會影響力這一問題，并設(shè)計了一種產(chǎn)生式模型，結(jié)合連接關(guān)系和內(nèi)容信息挖掘混合網(wǎng)絡(luò)中的社會影響力。Iwata等人[6]提出了一種概率模型用于發(fā)現(xiàn)社區(qū)中用戶間潛在的影響力，該模型能夠找到社區(qū)中影響力高的用戶、用戶間關(guān)系及預(yù)測事件熱門程度。Mehmood等人[7]提出了一種用于分析社區(qū)級影響力大小的模型。借助于層次策略，給定社區(qū)間信息傳播模式，該模型能夠識別出社區(qū)及它們相互之間的影響力大小。張玥等人[8]針對PageRank算法按照度分布進行數(shù)據(jù)結(jié)構(gòu)優(yōu)化，提出了一種基于集合劃分的快速排序算法SD-Rank。在天涯論壇上的用戶排序?qū)嶒炛?，算法時空復(fù)雜性大大降低。郭巖等人[9]利用層次分析法結(jié)合專家打分，構(gòu)建了一種網(wǎng)絡(luò)信息源影響力的評估模型，通過信息源表現(xiàn)力、網(wǎng)民關(guān)注度和媒體關(guān)注度等指標對影響力進行評估。除此之外，基于圖的挖掘算法也被應(yīng)用于社會影響力分析中，這些算法將用戶看成圖中的一個節(jié)點，從不同的角度定義邊的含義[10-11]。一些更細粒度的社會影響力分析方法也被提出，它們基于受限非負矩陣分解[12]，通過分解(用戶—帖子)矩陣來預(yù)測用戶將會收到的點擊量。但是，在社交媒介的環(huán)境下，用戶間的關(guān)系往往存在描述性的信息，這使得這些由用戶產(chǎn)生的信息變成多維數(shù)據(jù)。比起矩陣或圖的表示方法，張量提供了一種更加自然、簡潔的數(shù)據(jù)框架，用于這類多維數(shù)據(jù)的表示。本文提出一種受限非負張量分解方法用于社會影響力分析，使用三階張量表示用戶間評論關(guān)系，關(guān)于主題的輔助信息則以限制項的形式加入到張量分解中，控制張量分解過程。使用該方法，話題相關(guān)的用戶將比話題無關(guān)的用戶更具影響力。通過實驗比較，在用戶影響力排序精度上，本文提出的方法要比TwitterRank[10]、OOLAM[11]等基準方法有更優(yōu)的性能。

近些年來，張量分解被大量地應(yīng)用于數(shù)據(jù)挖掘任務(wù)中,例如，鏈接預(yù)測[13]、標簽推薦[14]等。但是這些張量分解方法無法引入輔助信息控制張量分解過程。因此，許多受限張量分解方法被提出以利用額外的知識，控制張量分解。兩種應(yīng)用廣泛的張量分解模型是CANDECOMP/PARAFAC(CP)和Tucker分解[15]。基于這兩種分解方法衍生出一系列受限張量分解方法。在文獻[16]中，一種使用拉普拉斯矩陣限制張量分解的方法被應(yīng)用于圖像表示，在圖像聚類中取得了優(yōu)于基準方法的性能。在文獻[17]中，通過控制張量分解中潛在因子的性質(zhì)，在事件預(yù)測中取得了更好的效果。本文提出的張量分解方法主要有兩方面不同于以往的工作，一方面是受限張量分解的目標函數(shù)，另一方面是求解該目標函數(shù)的迭代算法。

接下來文章的結(jié)構(gòu)安排如下： 第二節(jié)將介紹本文提出的受限張量分解方法，第三節(jié)說明如何將本文的張量分解方法應(yīng)用于社會影響力分析，第四節(jié)為實驗與結(jié)果分析。

2 基于拉普拉斯限制項的非負張量分解

CANDECOMP/PARAFAC(CP)是一種被廣泛使用的張量分解方法，CP分解是將張量分解為一系列秩為1的張量[15]。為了檢索出給定主題下社會影響力高的用戶，本文提出一種基于CP模型的受限張量分解方法，其更新迭代規(guī)則是矩陣運算，形式更加簡潔高效。

2.1 加入拉普拉斯限制項的目標函數(shù)

通過分析本文的實驗數(shù)據(jù)我們發(fā)現(xiàn)，相關(guān)度前100名用戶所接收到的評論總量平均高出后100名用戶133.7%，這意味著主題相關(guān)的用戶將比無關(guān)用戶更有可能得到更多的評論。為了利用這一數(shù)據(jù)特性，我們引入拉普拉斯限制項，目標函數(shù)如式(1)所示。

其中，Xk∈I×J表示張量X∈I×J×K的第k片正面切片。k∈I×J表示Xk的估計。k是Ak∈I×R與VT∈R×J的乘積。H∈{0,1}I×I表示用戶相似性矩陣，若Hij=1表示用戶i與用戶j相似，否則不相似。接下來α設(shè)為1，即擬合原始張量和限制項同等重要。

其中，C是一個對角矩陣，Cii=Lii。這里Ak和V的元素都是需要求解的變量。

2.2 求解目標函數(shù)

我們使用交替最小二乘法，交替更新變量矩陣，當更新其中一個變量矩陣時固定其他變量矩陣。使用KKT條件找到一個局部最優(yōu)解。拉格朗日函數(shù)如式(3)所示。

其中，λ、σ和θ表示對應(yīng)三個限制條件的拉格朗日乘子。將矩陣V看成變量，將Ak看成常量?？梢缘玫絁(V)的梯度。

根據(jù)V的補充條件，對于任意a、b，有σabVab=0。使用該條件，我們有：

先給出V的更新規(guī)則，詳細的求解步驟在2.3節(jié)給出。同樣的方法，我們可以得到Ak的更新規(guī)則。形式如式(6)。

定理 1 拉格朗日函數(shù)J在更新規(guī)則(6)下是非增的。證明將在2.3節(jié)中給出。

矩陣運算能夠方便地用MapReduce編程框架實現(xiàn)，從而適應(yīng)大規(guī)模數(shù)據(jù)。不難發(fā)現(xiàn),式(6)可以寫成緊湊的矩陣運算形式：

圖1 拉普拉斯受限張量分解算法偽代碼

2.3 收斂性證明

先給出證明所需條件，證明方法類似文獻[18]。

定義2.1 對于任意M,M′，若函數(shù)Z(M,M′)滿足：

那么我們稱Z(M,M′)是一個J(M)的輔助函數(shù)。

將矩陣V視為函數(shù)J的變量，那么拉格朗日函數(shù)J可以寫成：

定理 2 函數(shù)Z(V,V′)是拉格朗日函數(shù)J(V)的輔助函數(shù)。Z(V,V′)形式如下：

式(11)關(guān)于Vab是凸的，這里令輔助函數(shù)Z(V,V′)關(guān)于Vab的梯度為0，求其極小值點，可以得到式(12)。

計算式(12)可以得到：

根據(jù)式(5)可得Vab的更新規(guī)則公式。同理，可以得到Akab的更新規(guī)則。這樣就可以得到式(6)。綜上，拉格朗日函數(shù)J在更新規(guī)則(6)下是非增的。定理1證畢。

3 社會影響力分析

為分析用戶的社會影響力，本文首先使用張量表示用戶間的交互關(guān)系，即用戶間的評論關(guān)系。描述性信息是評論內(nèi)容的極性。所有的交互關(guān)系使用一個三階張量X∈{0,1}N×M×E表示。評論的極性分為三類： 正面、中性、負面。若用戶i對用戶j進行了一次極性傾向為k的評價，那么Xijk=1，否則為0。這里判定一條評論的極性是根據(jù)正負面情感詞的數(shù)量。若評論中正面詞多于負面詞，則記為正面評論。若正面詞少于負面詞，則記為負面評論。否則為中性評論。

4 實驗及分析

表1 實驗數(shù)據(jù)集構(gòu)成細節(jié)

數(shù)據(jù)集中目標用戶粉絲數(shù)量分布如圖2所示，所選取的目標用戶,其粉絲數(shù)量分布近似服從冪律分布，具有一定的代表性。不同主題下，固定BM25值范圍內(nèi)目標用戶數(shù)量的分布如圖3所示，BM25是一種衡量用戶主題相關(guān)度的度量(BM25越大則與主題越相關(guān))，雖然我們使用關(guān)鍵詞搜索出目標用戶，但是主題弱相關(guān)的用戶還是占到大部分，這也是為什么我們使用主題詞搜索目標用戶，而不是隨機選取目標用戶。

實驗中另一個關(guān)鍵問題是在給定主題下如何確定真實的用戶社會影響力排序列表。例如，給定主題籃球，我們通過人工排序確定真實的用戶影響力排序列表。五位分別來自數(shù)學和計算機系的學生,根據(jù)投票原則，分別選出影響力排名1～5、5～10、11～20的列表作為真實的用戶影響力排序列表。特別需要說明的是，這五位學生均參加過COAE2012，COAE2013和SIGHAN2015的語料標注工作。

圖2 擁有不同規(guī)模粉絲數(shù)的目標用戶分布圖

4.2 實驗性能分析

參數(shù)包括調(diào)節(jié)因子α和潛在特征維度R。這里將擬合原始張量和限制項視為同等重要，令α=1。確定R的方法則以籃球主題為例，如圖4所示，RMSE為均方根誤差，當R>5后RMSE下降幅度極小，故實驗中R=5。圖4也印證了本文方法的收斂性。

為了更好地體現(xiàn)本文方法在社會影響力分析上的有效性，本文設(shè)置了如下基準方法：

(1) 為了驗證本文加入的拉普拉斯限制項能夠起到作用，我們設(shè)置了兩個基準實驗CP及融合BM25的CP。第一個是為了說明本文加入的拉普拉斯限制項是有效的。第二個是為了說明本文的方法能夠更好地融合主題因素到社會影響力分析中。

(2) OOLAM的結(jié)果是正面、負面兩種社會影響力大小。我們將其均值看作用戶社會影響力得分。同樣，OOLAM并沒有加入主題信息，我們還設(shè)置了一個加入BM25值的OOLAM基準實驗。

圖4 隨迭代次數(shù)變化的RMSE

(3) TwitterRank能夠計算出用戶在給定主題下的影響力，但是沒有加入交互關(guān)系因素。因此我們還設(shè)置了一個添加評論關(guān)系的TwitterRank基準實驗，記為TR+RA。

(4) 粉絲數(shù)和評論量也被設(shè)置為對比實驗，分別記為FA和RA。

實驗中使用p@k評價指標評判各個方法的排序精度，實驗結(jié)果如表2所示，從中可以得到如下結(jié)論： (1)比起CP和CP+BM25，本文的方法在排序精度上有明顯的提升。這說明加入拉普拉斯限制項在該數(shù)據(jù)集上是有效的，能夠更好地融合主題信息到社會影響力分析中。(2)本文的方法在該應(yīng)用場景下優(yōu)于OOLAM和TwitterRank。同時，本文方法的平均準確率要高出第二好性能10%。(3)根據(jù)排序結(jié)果，本文方法在部分指標下并未取得最好性能。主要有兩方面原因： 一方面是那些主題相關(guān)并且影響力大的用戶，他們的影響力會被拉普拉斯限制項降低；另一方面是優(yōu)化算法的優(yōu)化程度，例如部分主題無關(guān)且影響力大的用戶，他們的影響力并未減小。

表2 本文方法與基準方法在p@k下的性能對比

這里使用Pearson相關(guān)系數(shù)，來衡量本文方法能否在張量分解之后仍然保留用戶影響力極性分布的特征。從表3中可以看出，分解后預(yù)測的結(jié)果與真實結(jié)果有較強的相關(guān)性，能夠反映用戶社會影響力的極性分布特性。從一定程度上可以說明本文的限制項對用戶影響力極性信息的影響較小。

表3 預(yù)測用戶影響力極性分布與真實值的相關(guān)性

為了驗證本文算法的可擴展性，我們使用MapReduce編程模型實現(xiàn)該算法，實驗平臺為Hadoop。Hadoop集群由六臺相同配置的節(jié)點構(gòu)成，共24個Intel 處理器(2.83GHz)、96GB內(nèi)存。按不同節(jié)點數(shù)和不同大小潛在特征維度R，測試加速比，實驗結(jié)果如圖5所示?？梢钥闯?本文的方法具有良好的可擴展性。

圖5 在不同節(jié)點數(shù)與潛在因子維數(shù)下的加速比

5 結(jié)論

本文針對給定主題下用戶影響力的問題，提出一種新的受限張量分解方法，并應(yīng)用到影響力用戶識別中，保持了用戶影響力的極性分布。首先，利用張量對用戶間交互關(guān)系建模。其次，提出一種受限張量分解，利用張量補全計算用戶影響力得分。最后，根據(jù)分解結(jié)果計算用戶影響力極性分布。實驗表明，與OOLAM、TwitterRank等方法比較，本文方法在挖掘主題相關(guān)用戶社會影響力上更加有效，能夠保持用戶影響力極性且擴展性良好。

[1] Tang J, Sun J, Wang C, et al. Social influence analysis in large-scale networks[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Paris, France, 2009: 807-816.

[2] Bakshy E, Eckles D, Yan R, et al. Social influence in social advertising: evidence from field experiments[C]//Proceedings of the 13th ACM Conference on Electronic Commerce. Valencia, Spain, 2012: 146-161.

[3] Rashid A M, Karypis G, Riedl J. Influence in ratings-based recommender systems: An algorithm-independent approach[C]//Proceedings of the 15th SIAM International Conference on Data Mining. California, USA, 2005: 556-560.

[4] Domingos P, Richardson M. Mining the network value of customers[C]//Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA, 2001: 57-66.

[5] Liu L, Tang J, Han J, et al. Learning influence from heterogeneous social networks[J]. Data Mining and Knowledge Discovery, 2012, 25(3): 511-544.

[6] Iwata T, Shah A, Ghahramani Z. Discovering latent influence in online social activities via shared cascade poisson processes[C]//Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Chicago, USA, 2013: 266-274.

[7] Mehmood Y, Barbieri N, Bonchi F, et al. Csi: Community-level social influence analysis[M].Machine learning and knowledge discovery in databases. Springer Berlin Heidelberg, 2013: 48-63.

[8] 張玥,張宏莉,張偉哲. 基于冪律分布的網(wǎng)絡(luò)用戶快速排序算法[J]. 中文信息學報, 2012,26(4): 122-128.

[9] 郭巖,劉春陽,余智華,等. 網(wǎng)絡(luò)輿情信息源影響力的評估研究[J]. 中文信息學報. 2011,25(3): 64-71.

[10] Weng J, Lim E P, Jiang J, et al. Twitterrank: finding topic-sensitive influential twitterers[C]//Proceedings of the 3rd ACM International Conference on Web Search and Data Mining. New York City, USA, 2010: 261-270.

[11] Cai K, Bao S, Yang Z, et al. OOLAM: an opinion oriented link analysis model for influence persona discovery[C]//Proceedings of the 4th ACM International Conference on Web Search and Data Mining. Hong Kong, China, 2011: 645-654.

[12] Cui P, Wang F, Liu S, et al. Who should share what?: item-level social influence prediction for users and posts ranking[C]//Proceedings of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval. Beijing, China, 2011: 185-194.

[13] Dunlavy D M, Kolda T G, Acar E. Temporal link prediction using matrix and tensor factorizations[J]. ACM Transactions on Knowledge Discovery from Data (TKDD), 2011, 5(2): 10.

[14] Rendle S, Schmidt-Thieme L. Pairwise interaction tensor factorization for personalized tag recommendation[C]//Proceedings of the 3rd ACM International Conference on Web Search and Data Mining. New York City, USA, 2010: 81-90.

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

[16] Wang C, He X, Bu J, et al. Image representation using Laplacian regularized nonnegative tensor factorization[J]. Pattern Recognition, 2011, 44(10): 2516-2526.

[17] Davidson I, Gilpin S, Walker P B. Behavioral event data and their analysis[J]. Data Mining and Knowledge Discovery, 2012, 25(3): 635-653.

[18] Zhang Z Y, Li T, Ding C. Non-negative tri-factor tensor decomposition with applications[J]. Knowledge and Information Systems, 2013, 34(2): 243-265.

陳暢(1991—)，碩士研究生，主要研究領(lǐng)域為面向社會媒介的觀點挖掘。

E-mail: 175695762@qq.com

魏晶晶(1984—)，博士研究生，主要研究領(lǐng)域為網(wǎng)絡(luò)文本傾向性分析。

E-mail: weijj_0517@163.com

廖祥文(1980—)，通信作者，副教授，主要研究領(lǐng)域為網(wǎng)絡(luò)文本傾向性分析。

E-mail: liaoxw@fzu.edu.cn

Social Influence Analysis Considering User Opinion

CHEN Chang, WEI Jingjing, LIAO Xiangwen, LIN Bogang, CHEN Guolong

(College of Mathematics and Computer Science, Fuzhou University, Fuzhou, Fujian 350116, China)

1003-0077(2017)04-0191-08

TP391

A