陳 暢，魏晶晶，廖祥文，林柏鋼，陳國(guó)龍

(福州大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福建 福州 350116)

融合用戶觀點(diǎn)的社會(huì)影響力分析

陳 暢，魏晶晶，廖祥文，林柏鋼，陳國(guó)龍

(福州大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福建 福州 350116)

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

張量分解；觀點(diǎn)；拉普拉斯矩陣；社會(huì)影響力分析

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

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

1 引言

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

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

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

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

2 基于拉普拉斯限制項(xiàng)的非負(fù)張量分解

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

2.1 加入拉普拉斯限制項(xiàng)的目標(biāo)函數(shù)

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

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

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

2.2 求解目標(biāo)函數(shù)

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

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

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

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

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

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

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

2.3 收斂性證明

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

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

那么我們稱Z(M,M′)是一個(gè)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，求其極小值點(diǎn)，可以得到式(12)。

計(jì)算式(12)可以得到：

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

3 社會(huì)影響力分析

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

4 實(shí)驗(yàn)及分析

表1 實(shí)驗(yàn)數(shù)據(jù)集構(gòu)成細(xì)節(jié)

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

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

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

4.2 實(shí)驗(yàn)性能分析

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

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

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

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

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

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

(4) 粉絲數(shù)和評(píng)論量也被設(shè)置為對(duì)比實(shí)驗(yàn)，分別記為FA和RA。

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

表2 本文方法與基準(zhǔn)方法在p@k下的性能對(duì)比

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

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

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

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

5 結(jié)論

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

[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]. 中文信息學(xué)報(bào), 2012,26(4): 122-128.

[9] 郭巖,劉春陽(yáng),余智華,等. 網(wǎng)絡(luò)輿情信息源影響力的評(píng)估研究[J]. 中文信息學(xué)報(bào). 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)域?yàn)槊嫦蛏鐣?huì)媒介的觀點(diǎn)挖掘。

E-mail: 175695762@qq.com

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

E-mail: weijj_0517@163.com

廖祥文(1980—)，通信作者，副教授，主要研究領(lǐng)域?yàn)榫W(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