社交網絡高影響力用戶發現算法研究

毋建軍

(北京政法職業學院信息技術系，北京 102628)

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

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

在社交網絡中，用戶發布的消息是度量用戶影響力，進行有影響的用戶發現的重要因素.本文把基于消息的所產生的影響引申轉化為話題影響.社交網絡用戶影響力度量轉化為：用戶話題的影響力度量.如何在社交網絡短文本消息字數限制、稀疏、用戶行為多樣等局限下，解決社交網絡人物(用戶)影響力度量的關鍵問題，是本文所提社交網絡影響力人物發現方法與其他方法的主要區別.

本文通過考慮上述因素，將影響力用戶發現問題泛化為體系化的用戶影響力模型，提出了基于話題和行為關聯機制的社交網絡高影響用戶發現算法，通過話題傳播的用戶所構成的話題影響力樹和話題引發行為所傳播的用戶構成的行為影響力樹的并集，構建用戶影響力樹，系統性解決社交網絡中影響力用戶發現問題.對社交網絡用戶影響力進行度量，并發現高影響力用戶.在下文的內容結構中：第二節介紹了社交網絡話題問題描述及定義；第三節描述了話題影響樹模型；第四節在不同的數據集上，與現有的典型社交用戶影響力度量算法進行對比及分析；第五節探討了其未來發展的方向及存在的問題.

1 子網定義

1.1 子網描述

話題是社交網絡人物影響力度量的兩個關鍵因素.如何通過話題度量社交網絡用戶影響力？本文通過話題內容、用戶的行為、話題與行為的級聯關系三個維度來描述和界定人物影響力度量中所涉及的問題和重要因素.

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

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

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

話題與行為級聯關系描述：話題是基礎，行為是關聯觸發.不同的話題，會產生不同的行為，并形成不同的隱性社區[4].在隱性社區之外的用戶，并不能對此話題社區產生影響，即使它與話題社區中的用戶具有鏈接關系，或是其他話題的組織者.也就是說，話題是用戶角色與行為、消息與行為之間的隱式變量.

1.2 子網絡定義

2 社交網絡用戶影響力測量

基于上述構建的不同關系子網，我們對用戶的影響力進行了建模，其分為用戶的話題影響力建模、行為影響力建模、用戶影響力建模三部分，其中話題與行為之間的關聯通過顯式變量用戶進行連接.

2.1 話題影響力模型

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

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

(1)

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

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

(2)

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

用戶u的hashtag標簽標題集合用Iuh表示，UTuih矩陣的行代表用戶，矩陣的行數是用戶的個數，矩陣的列代表標簽標題，列數是hashtag標簽標題的個數(每一個hashtag標簽標題表示一個話題).矩陣元素UTuih表示話題i在用戶u的集合Iuh中出現的次數，本文簡化以UTuih表示P(i|uh).

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

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

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

(3)

注意：用戶u對話題影響力樹Tu中每個用戶產生影響的時間順序以及對用戶間影響的大小， 并沒有討論.

2.2 行為影響力模型

當前，對用戶行為的工作主要著重于用戶間的轉發行為和關注/被關注行為，尤其是轉發行為被認為是表示用戶間真實影響的發生，但并沒有深入考察用戶推文與引發行為之間的關聯關系對用戶所造成的影響.本文從用戶推文及引發行為之間的關聯關系出發，引進用戶行為影響力樹模型，圍繞話題度量社交網絡用戶間交互的強度和頻度[5].在用戶行為影響力樹模型中，考慮了三種用戶行為：轉發、提及和回復，用戶的行為影響力樹模型Au表示為

(4)

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

2.3 用戶影響力模型

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

(5)

本文把發現用戶u的最大影響力樹轉化為優化問題，即通過損失函數來評價期望最大影響力樹和用戶u每次迭代生成的影響力樹之間的最小差值.

3 實驗評價

本文實驗數據采用了兩個不同來源的真實數據集，分別是TUAW[6](The Unofficial Apple Weblog)數據集和Twitter數據集.

3.1 評價標準

為了評價算法的有效性，本文在上述兩個數據集上，與社交網絡意見領袖影響力排序算法MIIB[6]、TwitterRank(TR)[7]、PageRank(PgR)[8]、ProfileRank(ProR)[9]以及基于單特征的算法進行了對比和分析.

3.2 實驗分析及討論

3.2.1 話題分析

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

表1 基于TUAW數據集的不同算法的Top10用戶

3.2.2 模型評價

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

本文算法算出的每一個話題上，排序前10的用戶中高影響力用戶占了3個，而TR算法產生的排序前10的用戶中占了2個，SCMex是話題2上最有影響的用戶，也是兩個算法排序前10共有用戶.也可以說，基于詞向量的短文本話題描述能力不遜于LDA，因為它學習了推文中詞的搭配習慣，而LDA并沒有考慮. 如圖2所示，算法在話題(topic)社區[10]的意見領袖用戶與其他用戶的關系，顯示了意見領袖用戶在不同的社區具有不同的影響力，也就是說，不同的話題社區有不同的話題組織者和意見領袖用戶，一個用戶不可能在所有社區或話題上都具有較強的影響力.

圖2 在話題(Topic)社區中意見領袖用戶與其他用戶的關系

4 結論及未來工作

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

參考文獻：

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