社交網(wǎng)絡(luò)高影響力用戶發(fā)現(xiàn)算法研究

毋建軍

(北京政法職業(yè)學(xué)院信息技術(shù)系，北京 102628)

早在1955年，卡茲及拉茲菲爾德把高影響力用戶即“意見領(lǐng)袖”描述為：“一個(gè)人能對(duì)其周圍環(huán)境中的人產(chǎn)生影響”[1].同時(shí)在其二級(jí)傳播理論中驗(yàn)證了源自大眾媒介的消息，通常會(huì)經(jīng)由意見領(lǐng)袖的中轉(zhuǎn)再傳遞到普通用戶.同樣，Roch等人的研究也發(fā)現(xiàn)，在市場(chǎng)交易中少數(shù)有影響的用戶是加速或阻礙大眾交易行為發(fā)生的關(guān)鍵節(jié)點(diǎn).發(fā)掘社交網(wǎng)絡(luò)中具有特殊影響力的用戶，已經(jīng)成為生物、醫(yī)學(xué)、社會(huì)學(xué)、物理學(xué)、人文學(xué)、計(jì)算機(jī)等多學(xué)科在社區(qū)發(fā)現(xiàn)、網(wǎng)絡(luò)和社會(huì)信息傳播、疾病傳染、輿情、信任傳播、公共健康等領(lǐng)域的研究熱點(diǎn)，也是商業(yè)中廣告定點(diǎn)投放、病毒式或口碑營(yíng)銷等推廣應(yīng)用的重點(diǎn)問題.

當(dāng)前社交網(wǎng)絡(luò)中影響力用戶的發(fā)現(xiàn)方法，可以歸納為基于網(wǎng)絡(luò)結(jié)構(gòu)的、基于消息內(nèi)容的、網(wǎng)絡(luò)結(jié)構(gòu)與消息內(nèi)容相結(jié)合的三類.基于網(wǎng)絡(luò)結(jié)構(gòu)的社交網(wǎng)絡(luò)有影響的用戶發(fā)現(xiàn)，通常假設(shè)在社交網(wǎng)絡(luò)中鏈接距離越近的用戶，彼此之間會(huì)產(chǎn)生更大影響，鏈接距離越遠(yuǎn)，彼此所能產(chǎn)生的影響越弱.在實(shí)際網(wǎng)絡(luò)中，具有大量粉絲的用戶，由于其粉絲是僵尸粉或不感興趣等原因，不一定閱讀或轉(zhuǎn)發(fā)其消息，也就是說，具有高粉絲量的用戶不一定在所有消息上都具有很高的影響力，不是所有的消息經(jīng)過它的發(fā)布或轉(zhuǎn)發(fā)，都能產(chǎn)生廣泛的傳播或轉(zhuǎn)發(fā).用戶在不同的社交網(wǎng)絡(luò)群體結(jié)構(gòu)中、不同的話題上可能具有不同的影響[2]，那么如何刻畫社交網(wǎng)絡(luò)用戶在社交網(wǎng)絡(luò)中的影響并提取有影響的用戶呢？

在社交網(wǎng)絡(luò)中，用戶發(fā)布的消息是度量用戶影響力，進(jìn)行有影響的用戶發(fā)現(xiàn)的重要因素.本文把基于消息的所產(chǎn)生的影響引申轉(zhuǎn)化為話題影響.社交網(wǎng)絡(luò)用戶影響力度量轉(zhuǎn)化為：用戶話題的影響力度量.如何在社交網(wǎng)絡(luò)短文本消息字?jǐn)?shù)限制、稀疏、用戶行為多樣等局限下，解決社交網(wǎng)絡(luò)人物(用戶)影響力度量的關(guān)鍵問題，是本文所提社交網(wǎng)絡(luò)影響力人物發(fā)現(xiàn)方法與其他方法的主要區(qū)別.

本文通過考慮上述因素，將影響力用戶發(fā)現(xiàn)問題泛化為體系化的用戶影響力模型，提出了基于話題和行為關(guān)聯(lián)機(jī)制的社交網(wǎng)絡(luò)高影響用戶發(fā)現(xiàn)算法，通過話題傳播的用戶所構(gòu)成的話題影響力樹和話題引發(fā)行為所傳播的用戶構(gòu)成的行為影響力樹的并集，構(gòu)建用戶影響力樹，系統(tǒng)性解決社交網(wǎng)絡(luò)中影響力用戶發(fā)現(xiàn)問題.對(duì)社交網(wǎng)絡(luò)用戶影響力進(jìn)行度量，并發(fā)現(xiàn)高影響力用戶.在下文的內(nèi)容結(jié)構(gòu)中：第二節(jié)介紹了社交網(wǎng)絡(luò)話題問題描述及定義；第三節(jié)描述了話題影響樹模型；第四節(jié)在不同的數(shù)據(jù)集上，與現(xiàn)有的典型社交用戶影響力度量算法進(jìn)行對(duì)比及分析；第五節(jié)探討了其未來發(fā)展的方向及存在的問題.

1 子網(wǎng)定義

1.1 子網(wǎng)描述

話題是社交網(wǎng)絡(luò)人物影響力度量的兩個(gè)關(guān)鍵因素.如何通過話題度量社交網(wǎng)絡(luò)用戶影響力？本文通過話題內(nèi)容、用戶的行為、話題與行為的級(jí)聯(lián)關(guān)系三個(gè)維度來描述和界定人物影響力度量中所涉及的問題和重要因素.

短文本話題描述問題：在社交網(wǎng)絡(luò)中，如Twitter，消息內(nèi)容即推文，一條推文(Tweet)通常包含純文本、短鏈接(url)、圖像、#標(biāo)簽(hashtag)、@username組成[3].#標(biāo)簽后面的文字，在Twitter中通常被用來表示用戶感興趣的標(biāo)題或話題，其他用戶也可以通過#標(biāo)簽相鄰的標(biāo)題，能夠快速地找到出現(xiàn)此標(biāo)簽標(biāo)題的所有推文.針對(duì)用戶的所有推文內(nèi)容解析并提取了短鏈接、@username(提及)、#label和純文本四類特征，圖像特征在本文中并沒有進(jìn)行提取及應(yīng)用.本文采用了基于消息內(nèi)容的純文本和#label兩類特征作為短文本話題描述的基礎(chǔ)，純文本以詞向量(word embedding)的形式進(jìn)行描述，短文本話題以子網(wǎng)絡(luò)的形式進(jìn)行描述，具體見后續(xù)描述.

行為提取問題：本文僅應(yīng)用了轉(zhuǎn)發(fā)、回復(fù)和提及(來自消息內(nèi)容)三類行為，轉(zhuǎn)發(fā)表示在用戶間真實(shí)的影響發(fā)生；回復(fù)代表了用戶基于具體消息的互動(dòng)行為；提及表示了消息可能傳播的范圍及廣度.用戶的不同行為，構(gòu)建出不同的行為子網(wǎng)絡(luò).推文、話題、用戶處理框架如圖1所示.

圖1 推文、話題、用戶處理框架

話題與行為級(jí)聯(lián)關(guān)系描述：話題是基礎(chǔ)，行為是關(guān)聯(lián)觸發(fā).不同的話題，會(huì)產(chǎn)生不同的行為，并形成不同的隱性社區(qū)[4].在隱性社區(qū)之外的用戶，并不能對(duì)此話題社區(qū)產(chǎn)生影響，即使它與話題社區(qū)中的用戶具有鏈接關(guān)系，或是其他話題的組織者.也就是說，話題是用戶角色與行為、消息與行為之間的隱式變量.

1.2 子網(wǎng)絡(luò)定義

2 社交網(wǎng)絡(luò)用戶影響力測(cè)量

基于上述構(gòu)建的不同關(guān)系子網(wǎng)，我們對(duì)用戶的影響力進(jìn)行了建模，其分為用戶的話題影響力建模、行為影響力建模、用戶影響力建模三部分，其中話題與行為之間的關(guān)聯(lián)通過顯式變量用戶進(jìn)行連接.

2.1 話題影響力模型

對(duì)于社交網(wǎng)絡(luò)用戶而言，所有的話題都來源于消息，如前所述，本文通過#(hahstag)標(biāo)簽及文字和純文本消息來描述短文本話題.處理過程：先把每一個(gè)用戶的所發(fā)布全部推文進(jìn)行解析，提取對(duì)應(yīng)的內(nèi)容特征，形成以用戶為單位兩個(gè)特征集合：#(hashtag)標(biāo)簽文字集合和純文本消息集合.兩個(gè)集合都以詞向量進(jìn)行描述，在描述前先以所有用戶的#(hashtag)標(biāo)簽文字集合和純文本消息集合用word2vec模型進(jìn)行訓(xùn)練，向量的維度選擇50維的向量空間.然后對(duì)每一個(gè)推文的詞向量進(jìn)行加權(quán)，形成每一個(gè)推文的向量，在此基礎(chǔ)上，進(jìn)行話題影響力的計(jì)算.這里描述的話題模型實(shí)質(zhì)是隱式話題模型，我們的目標(biāo)是得到每一個(gè)用戶的影響力樹.用戶的影響力樹由用戶的話題影響子樹和行為影響子樹生成.話題影響子樹，表示用戶在話題下影響的所有用戶構(gòu)成的樹.P(Tc|u)表示用戶u的話題影響樹，用戶以u(píng)表示，Tc表示基于消息內(nèi)容的話題影響樹，計(jì)算如下式(1)所示

P(Tc|u)=P(Tc|z)P(z|u)

(1)

式中z表示一個(gè)話題，P(z|u)表示用戶u對(duì)話題z感興趣的概率，P(Tc|z)概率簡(jiǎn)化為以對(duì)話題z感興趣所用用戶與所用用戶的比率進(jìn)行表示.

在話題影響樹生成過程中，假設(shè)話題之間相互獨(dú)立.所用用戶#(hashtag)標(biāo)簽文字形成的集合以Ih進(jìn)行表示，Iu表示所用用戶的純文本消息形成的集合，每個(gè)用戶所發(fā)推文提取的純文本消息，并構(gòu)建成一個(gè)大的集合以Iut表示，每個(gè)用戶所發(fā)的所有#(hashtag)標(biāo)簽文字集合，以Iuh進(jìn)行表示.那么，用戶u的在所有話題下影響樹轉(zhuǎn)化為式2，如下：

(2)

式中i和j分別表示在Hashtag標(biāo)簽下的話題i和在純文本消息下的話題j,P(Tc|u)表示對(duì)于用戶u在所有話題上會(huì)以多大的概率，生成影響力樹Tc，對(duì)Tc中的用戶在話題層面產(chǎn)生影響.

用戶u的hashtag標(biāo)簽標(biāo)題集合用Iuh表示，UTuih矩陣的行代表用戶，矩陣的行數(shù)是用戶的個(gè)數(shù)，矩陣的列代表標(biāo)簽標(biāo)題，列數(shù)是hashtag標(biāo)簽標(biāo)題的個(gè)數(shù)(每一個(gè)hashtag標(biāo)簽標(biāo)題表示一個(gè)話題).矩陣元素UTuih表示話題i在用戶u的集合Iuh中出現(xiàn)的次數(shù)，本文簡(jiǎn)化以UTuih表示P(i|uh).

用戶u的純文本集合用Iut表示，先以Iut集合內(nèi)的推文向量進(jìn)行向量相似度聚類，形成用戶u的話題分布，再以用戶與用戶間話題的相似度聚類，以JSD(Jensen-Shannon Divergence)進(jìn)行計(jì)算獲取并形成UTujt矩陣，同樣，P(j|ut)簡(jiǎn)化為UTujt.

在上述基礎(chǔ)上，用戶u的話題影響力樹P(Tu|u)，被歸約簡(jiǎn)化表述為公式3：

P(Tu|u)=P(Ta|u)×P(Tc|u)

(3)

注意：用戶u對(duì)話題影響力樹Tu中每個(gè)用戶產(chǎn)生影響的時(shí)間順序以及對(duì)用戶間影響的大小， 并沒有討論.

2.2 行為影響力模型

當(dāng)前，對(duì)用戶行為的工作主要著重于用戶間的轉(zhuǎn)發(fā)行為和關(guān)注/被關(guān)注行為，尤其是轉(zhuǎn)發(fā)行為被認(rèn)為是表示用戶間真實(shí)影響的發(fā)生，但并沒有深入考察用戶推文與引發(fā)行為之間的關(guān)聯(lián)關(guān)系對(duì)用戶所造成的影響.本文從用戶推文及引發(fā)行為之間的關(guān)聯(lián)關(guān)系出發(fā)，引進(jìn)用戶行為影響力樹模型，圍繞話題度量社交網(wǎng)絡(luò)用戶間交互的強(qiáng)度和頻度[5].在用戶行為影響力樹模型中，考慮了三種用戶行為：轉(zhuǎn)發(fā)、提及和回復(fù)，用戶的行為影響力樹模型Au表示為

(4)

P(Au|u)表示用戶u發(fā)布的所有推文，引發(fā)其他用戶的行為(三種，轉(zhuǎn)發(fā)、提及和回復(fù))所形成的影響樹Au的概率，a 表示用戶所有行為的集合，Γ(z)是話題z引發(fā)的所有行為子樹集合(并沒有考慮行為時(shí)間).

2.3 用戶影響力模型

用戶u在上述話題影響力和行為影響力的基礎(chǔ)上，用戶u的影響力樹生成概率，表示為

(5)

本文把發(fā)現(xiàn)用戶u的最大影響力樹轉(zhuǎn)化為優(yōu)化問題，即通過損失函數(shù)來評(píng)價(jià)期望最大影響力樹和用戶u每次迭代生成的影響力樹之間的最小差值.

3 實(shí)驗(yàn)評(píng)價(jià)

本文實(shí)驗(yàn)數(shù)據(jù)采用了兩個(gè)不同來源的真實(shí)數(shù)據(jù)集，分別是TUAW[6](The Unofficial Apple Weblog)數(shù)據(jù)集和Twitter數(shù)據(jù)集.

3.1 評(píng)價(jià)標(biāo)準(zhǔn)

為了評(píng)價(jià)算法的有效性，本文在上述兩個(gè)數(shù)據(jù)集上，與社交網(wǎng)絡(luò)意見領(lǐng)袖影響力排序算法MIIB[6]、TwitterRank(TR)[7]、PageRank(PgR)[8]、ProfileRank(ProR)[9]以及基于單特征的算法進(jìn)行了對(duì)比和分析.

3.2 實(shí)驗(yàn)分析及討論

3.2.1 話題分析

如表1所示，基于TUAW數(shù)據(jù)集的blogger參與的話題(topic)越多，blogger則越活躍，但話題也更容易漂移、消失，blogger在發(fā)帖內(nèi)容和發(fā)帖標(biāo)題方面，具有很強(qiáng)的相關(guān)性.用戶的發(fā)帖內(nèi)容和發(fā)布標(biāo)題在話題(topic)方面，具有幾乎一致的趨勢(shì)，也就是說，標(biāo)題是與內(nèi)容強(qiáng)關(guān)聯(lián)的話題標(biāo)示，對(duì)于具有標(biāo)題的在線用戶內(nèi)容相似性檢測(cè)具有一定的借鑒意義.

表1 基于TUAW數(shù)據(jù)集的不同算法的Top10用戶

3.2.2 模型評(píng)價(jià)

在TUAW數(shù)據(jù)集上，算法與基于單特征的算法、MIIB、MIBI、MIBIX算法在Top 10用戶序列上進(jìn)行實(shí)驗(yàn)對(duì)比，在Kendall系數(shù)方面都具有相似的相關(guān)性，尤其是Top10用戶具有較大的重疊.基于評(píng)論的單特征排序和基于多話題的單特征排序，具有更強(qiáng)的相關(guān)性，說明了評(píng)論越活躍，話題分解的子話題越多，話題也較容易漂移焦點(diǎn).

本文算法算出的每一個(gè)話題上，排序前10的用戶中高影響力用戶占了3個(gè)，而TR算法產(chǎn)生的排序前10的用戶中占了2個(gè)，SCMex是話題2上最有影響的用戶，也是兩個(gè)算法排序前10共有用戶.也可以說，基于詞向量的短文本話題描述能力不遜于LDA，因?yàn)樗鼘W(xué)習(xí)了推文中詞的搭配習(xí)慣，而LDA并沒有考慮. 如圖2所示，算法在話題(topic)社區(qū)[10]的意見領(lǐng)袖用戶與其他用戶的關(guān)系，顯示了意見領(lǐng)袖用戶在不同的社區(qū)具有不同的影響力，也就是說，不同的話題社區(qū)有不同的話題組織者和意見領(lǐng)袖用戶，一個(gè)用戶不可能在所有社區(qū)或話題上都具有較強(qiáng)的影響力.

圖2 在話題(Topic)社區(qū)中意見領(lǐng)袖用戶與其他用戶的關(guān)系

4 結(jié)論及未來工作

本文討論了基于話題的社交網(wǎng)絡(luò)意見領(lǐng)袖的度量方法，用生成話題(topic)影響力樹的方法評(píng)價(jià)度量社交網(wǎng)絡(luò)用戶的意見領(lǐng)袖影響力大小及影響范圍，并通過實(shí)驗(yàn)對(duì)比驗(yàn)證了其有效性，但在消息與話題(topic)映射層面(即短文本話題描述)、尋找最大概率、最大范圍影響樹生成方面還有許多工作需要完成.

參考文獻(xiàn)：

[1]Katz E, Lazarsfeld P F. Personal Influence: The Part Played by People in the Flow of Mass Communications[M]. Illinois: The Free Press,1955.

[2]Tang J, Sun J, Wang C, el at. Social influence analysis in large-scale networks[A]. The Proceeding of 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C]. Paris:ACM, 2009:807-816.

[3]Hashtag[EB/OL]. https://en.wikipedia.org/wiki/Hashtag，2018-04-16.

[4]Freeman L C. Centrality in social networks conceptual clarification[J]. Social Networks, 1979,(3): 215-239.

[5]Pathak N, DeLong C, Banerjee A. Social topic models for community extraction[A]. The Proceeding of 2th SNAKDD Workshop[C]. Las Vegas: SNAKDD, 2008.

[6]Khan H U, Daud A, Malik T A. MIIB: A metric to identify top influential bloggers in a community[J]. Plos One, 2015,(9):e0138359.

[7]Weng J, Lim E P, Jiang J, el at. TwitterRank: Finding topic-sensitive influential twitterers[A]. Proceedings of 3th ACM International Conference on Web Search and Data Mining[C]. New York :ACM, 2010: 216-231.

[8]Page L,Brin S, Monwani R, el at. The PageRank Citation Ranking: Bringing Order to the Web [EB/OL]. http://diglib.stanford.edu:8091/diglib/pub/,1998.

[9]Silva A, Meira W, Zaki M. ProfileRank: Finding relevant content and influential users based on information diffusion[A]. The Proceeding of 7th Workshop on Social Network Mining and Analysis[C]. New York: ACM,2013.

[10]Saito K, Kimura M, Ohara K, et al. Learning continuous-time information diffusion model for social behavior data analysis[A]. The Proceeding of Asian Conference on Machine Learning: Advances in Machine Learning[C].2009:322-337.