基于用戶行為和結構洞的用戶影響力評價模型

魏建冬 覃錫忠 賈振紅 牛紅梅

關鍵詞： 用戶影響力; 非冗余信息; 用戶行為; 結構洞; 網絡約束系數; 覆蓋率

中圖分類號： TN911?34; TP393 ? ? ? ? ? ? ? ? ? ?文獻標識碼： A ? ? ? ? ? ? ? ? ? ? 文章編號： 1004?373X（2019）05?0164?05

User influence comprehensive evaluation model based on user behavior

and structure hole principle

WEI Jiandong1， QIN Xizhong1， JIA Zhenhong1， NIU Hongmei2

（1. College of Information Science and Engineering， Xinjiang University， Urumqi 830046， China;

2. Department of Network Monitoring， China Mobile Communications Group Xinjiang Limited， Urumqi 830046， China）

Abstract： Since the non?redundant information is not fully considered in current most user influence measurement methods， the user influence comprehensive evaluation model based on user behavior and structure hole principle is constructed. The user behavior is quantified， and integrated into the edge weight of the network. On this basis， the network constraint coefficients are improved by means of structural hole method to consider the influence of user behavior on the edge weight of the network， and solve the problem of three?layer topological relationship among the node， adjacent node and subjacent node. The user influence comprehensive evaluation model is constructed， and verified with the data from Sina MicroBlog. The results of sequencing experiment and coverage ratio experiment show that the user influence measurement of the model is accurate and valid.

Keywords： user influence; non?redundant information; user behavior; structural hole; network constraint coefficient; coverage ratio

0 ?引 ?言

用戶影響力度量是在線社交影響力分析的核心問題之一，用戶影響力指通過用戶等受其他用戶的影響而變化的現象[1]，它可以應用到推薦系統、網絡信息傳播的預測、鏈路預測、病毒式營銷、突發事件預測等領域[2?3]。

目前用戶影響力的度量方法大多基于網絡拓撲結構、用戶交互行為（轉發、評論、提及）兩個角度[4]。這些方法各有側重點，但對用戶間的非冗余信息考慮不全[5]。基于網絡拓撲結構的方法中，度中心性[6]、聚類系數[7]等方法從局部角度出發，考慮了節點與鄰居節點的數量關系，對節點間拓撲結構欠缺考慮，對節點間的非冗余信息考慮不足[1];Closeness和Betweeness[8]等方法從全局角度出發，以網絡平均路徑衡量用戶影響力，無法兼顧節點間的非冗余信息，且要求全連通網絡且計算復雜度高，不適用于大型社交網絡[4];基于用戶交互行為的方法基于用戶的評論、轉發、提及等行為，文獻[9]將用戶行為與PageRank算法[10]相結合，同時考慮用戶文本，對用戶影響力進行度量;文獻[11]從消息的轉發和時間角度對用戶影響力度量，沒有考慮網絡拓撲的影響。這類方法多考慮了鄰近節點間的用戶行為，對非冗余信息的考慮同樣不足。

針對用戶影響力度量中非冗余信息考慮不全的問題，研究發現[12]：結構洞節點可以從網絡中獲得更多的非冗余信息，更好地觀測信息的流向，評價用戶影響力。文獻[13]實驗發現，在線社交網絡Twitter上1%的結構洞用戶決定了用戶之間25%的信息傳播。文獻[14]提出一種小范圍度量方法尋找目標網絡中的結構洞節點。文獻[15]提出識別Top?[k]結構洞關鍵節點的HIS算法和MaxD算法，文獻[5]基于平均距離尋找結構洞節點，文獻[16]結合評價結構洞的多個指標，利用排序學習算法對節點影響力進行評價。這些方法都未考慮用戶行為對網絡邊權的影響，同時未考慮節點與鄰近節點、次鄰近節點的三層拓撲結構。文獻[17]研究發現，在線社交網絡中91.6%的消息連續傳播在3次以內，考慮三層節點的拓撲結構能全面地評價用戶節點的影響力。

針對用戶影響力度量非冗信息考慮不全的問題，本文引入結構洞理論，同時針對結構洞評價中存在的問題，對結構洞評價方法——網絡約束系數進行改進，最后構建基于用戶行為和結構洞的用戶影響力評價模型。通過新浪微博對用戶影響力進行度量實驗，說明本文模型度量用戶影響力的有效性與準確性。

1 ?理論與方法

1.1 ?結構洞理論

假設存在用戶節點[A]，[B]，[C]，[D]，節點間連接情況如圖1所示。非冗余信息[5]指通過不同用戶的聯系獲得的非重疊信息，節點[A]和節點[D]沒有直接連接而存在非冗余信息。文獻[14]指出，結構洞是連接兩個非冗余用戶的橋梁，用戶間的非冗余聯系即為結構洞。節點[C]分別與[A]和[D]，[B]和[D]構成了結構洞關系，[C]作為結構洞節點。而由于[A]和[B]有連接，存在冗余聯系，則[C]與[A]和[B]不能構成結構洞關系。

1.2 ?結構洞評價方法分析

為了描述節點間的閉合程度，文獻[14]提出網絡約束系數（CT），描述節點運用結構洞的程度：

[Cij=pij+qpiqpqj2] ?（1）

式中：[Cij]表征節點[j]與節點[i]的約束大小，[q≠i，j]，節點[q]是節點[i]和[j]的共同相鄰節點;[pij]為節點[i]花費在節點[j]上的精力占[i]花費總精力的比例，[pij=zijk∈Γ（i）zik]，[zij]表示[i，j]兩節點的連接情況，有連接其值為1，反之為0，[Γi]表示節點[i]的鄰居集合。那么節點[i]的網絡約束系數[Ci]為：

[Constri=jcij] ?（2）

上述方法進行節點重要性評價時，存在兩個問題：

1） 沒有考慮用戶行為（評論、轉發等）對網絡邊權的影響。如圖2所示，該方法依據節點的度進行計算，對于節點[D]和[E]，根據式（1），節點[i]與節點[E]、節點[D]的網絡約束系數表示為：[CiD=（piD+piBpBD）2=（16+16×13）2=0.049 4=CiE]，兩者的網絡約束系數大小相同，但節點[i]與[E，D]以及[E]與[K，D]與[L]連接的邊的權值不同，兩節點重要性顯然有差異，同時節點間的用戶行為也沒有考慮，這一點結構洞評價沒有兼顧到。

2） 節點與鄰居節點間的兩層拓撲結構無法反映部分節點的重要性差異。如圖2所示，對于節點[E]和[F]，根據式（1），兩節點有共同的鄰居節點[A]，計算得：

[CiE=（piE+piApAE）2=（16+16×14）2=0.043 ?4=CiF]

網絡約束系數只考慮了節點與其鄰居節點的兩層拓撲結構，但節點[E]與節點[F]在本文網絡中的重要性是不同的，節點[F]由于與和多節點存在聯系的節點[G]有聯系，重要程度顯然強于節點[E]。換言之，節點[i]在與節點[F]保持聯系投入的精力較節點[E]要多，這一點在結構洞的評價中沒有兼顧到。

2 ?用戶影響力評價模型

本文在進行用戶影響力度量時引入結構洞理論，同時針對1.2節結構洞評價方法的兩個問題，做了相應改進，本文算法流程如圖3所示。

2.1 ?融入用戶行為的網絡邊權

為考慮用戶行為對網絡邊權的影響，本節首先對用戶行為進行量化，然后融入到網絡邊權計算中。以新浪微博網絡為例，在考慮用戶行為（轉發、評論等）的基礎上，定義網絡邊權值。通過收集微博用戶的三種用戶行為關系，定義網絡拓撲結構為[G{V，（E，D）}]，[V]代表用戶節點集合，[E]代表邊集合，[D]代表邊權值集合，它由評論權值集合[C]、轉發權值集合[T]、提及權值集合[M]三部分構成。其中，[C={cij}]，[cij]代表評論權值，其大小為用戶[vj]對用戶[vi]所發微博的評論總數。

同理，可得轉發權值[tij]和提及權值[mij]，且[T={tij}]，[M={mij}]。融入用戶行為的邊權為：

[dij=w1cij+w2tij+w3mij] ? ?（3）

本文默認三種用戶行為重要性是一樣的，定義[w1=w2=w3=1]，最后得到網絡的邊權[dij]。

2.2 ?結構洞評價方法的改進

為更全面地體現用戶在網絡中的地位，本節考慮節點與鄰近節點、次鄰近節點的三層拓撲結構對網絡約束系數計算方法進行改進，最后實現用戶影響力的度量。

在2.1節加權網絡[G{V，（E，D）}]的基礎上，定義網絡節點[i]的權值度為：

[wi=j∈Gdij] ? （4）

式中[dij]為網絡邊權值。節點[i]的權值度為與節點[i]連接的所有邊的邊權之和，改進基于節點的度的計算方法為結合2.1節網絡邊權的計算方法。

定義節點[i]的總權值度為：

[Wi=j∈Γiwj] ?（5）

式中[Γi]表示節點[i]的鄰居集合。為反映節點間的三層拓撲結構，定義節點的總權值度。節點[i]的總權值度為與節點[i]相連的所有節點的權值度之和。

定義節點[i]花費在節點[j]上的精力比例[pij]的計算方法如下：

[pij=wjm∈ΓiWm] （6）

改進之后用戶節點[j]與用戶節點[i]的網絡約束系數為：

[CTij=pij+q（piq×pqj）2] （7）

圖2中，根據式（7）得：對于節點[D]和[E]，經計算得：[CTiD=0.022 ?5]，[CTiE=0.022 ?6]，兩者的網絡約束系數存在差異，這是考慮用戶行為對網絡邊權影響的結果，符合實際情況。對于節點[E]和[F]，有[CTiE=0.022 ?6]，[CTiF=0.049 ?3]，由結果可知，節點[i]向節點[F]投入的精力比向節點[E]投入的精力多，考慮了兩節點的三層拓撲結構，符合實際情況。

最后，提出本文的用戶影響力評價模型：

[Si=j=1nCTij] （8）

3 ?實驗分析

3.1 ?數據抓取

通過新浪微博平臺，以一部分用戶作為起點，獲取其發表、轉發等微博內容信息，輪流抓取用戶的關注用戶作為新起點，重復以上操作。本文抓取了自2017?05?27—2017?07?01的微博數據。其中包括14 543個用戶和127 426條微博。

3.2 ?評價指標

1） 為驗證本文模型度量用戶影響力的準確性，對比不同算法模型下，影響力排序后用戶中大V用戶所占比例，通過比較說明本文模型的準確性。

2） 為驗證本文模型對用戶影響力度量的有效性，采用覆蓋率[18]（Coverage Ratio，CR）對模型進行評估。它表征用戶的傳播能力，覆蓋率越大，同時隨著用戶的傳播能力變強，用戶的影響力也會變大。覆蓋率定義為：

[覆蓋率=傳播范圍總節點數×100%] ? ? ? ? （9）

總節點數表示用戶通過自身行為形成的網絡拓撲圖中的節點個數;傳播范圍指網絡拓撲圖中受到用戶行為和結構洞原理的影響，信息通過用戶行為傳遞，波及到的用戶節點數量。

3.3 ?實驗及結果分析

3.3.1 ?用戶影響力度量準確性實驗

將本文模型[Si]、度中心性[6]、原始網絡約束系數CT、PageRank算法[10]、基于用戶?內容分析的TURank模型[9]用在數據集上，對比影響力排序結果見表1。

表1中為各算法模型篩選的影響力排名前10的用戶（英文簡寫）。 最后一行表示篩選用戶中的大V用戶數，本文模型篩選的大V用戶有“雷軍”“王煜全”“盧健生”“王自如ZEALER”等8人，準確性最好;網絡約束系數CT識別關注更多的是社團間的連接用戶，而忽略了用戶行為因素與三層節點網絡拓撲因素的影響，如排名10號的“小米王川”雖然與高影響力節點“雷軍”等用戶有聯系，但互動頻率低，這點CT沒能兼顧;度中心性沒有考慮用戶之間的互動行為和節點在網絡中的位置，對非冗余信息考慮不足，效果最差;PR值用戶的粉絲數相關過高，僅識別出“雷軍”“盧健生”大V用戶，而其他用戶“僵尸粉”用戶過多，實驗結果不準確;TURank綜合考慮用戶文本和用戶行為，效果較好，但缺乏對節點三層結構的考慮，相較本文算法不能充分評價非冗余信息。

本文進一步比較各模型影響力Top100用戶中的大V用戶數，結果表明，本文模型識別大影響力用戶數最多，如圖4所示。

3.3.2 ?用戶影響力度量有效性實驗

進行下一步實驗之前，首先進行數據預處理，剔除“僵尸粉”用戶的干擾，這類用戶往往以增加目標用戶人氣、廣告推銷為目的，基本沒有有效的用戶行為。本文篩選出已收集數據集中網絡邊權[dij]大于3的用戶，把它作為標準集。

把本文模型[Si]、PageRank算法、TURank模型用在此標準集上，對比覆蓋率，結果如圖5所示。

圖5中，各算法模型隨著用戶數量的增加，信息傳播的范圍逐漸增大，傳播范圍增長率大于節點數的增長率，覆蓋率逐漸增大，而隨著用戶數量的上升，會出現一些獨立的用戶節點，覆蓋率增長速度會變緩并穩定在一定水平。PageRank算法關注粉絲數量，忽略了用戶行為和三層節點網絡拓撲的影響，覆蓋率總體較低。TURank模型缺乏對三層節點間拓撲關系的考慮，傳播能力較本文模型低。本文從多角度對用戶影響力進行度量，覆蓋率指標表現最優，說明了本文模型的有效性。

4 ?結 ?語

本文基于用戶行為和結構洞原理構建用戶影響力綜合評價模型，以新浪微博為例，對用戶影響力進行度量實驗。針對目前用戶影響力度量中對非冗余信息考慮不全的問題，本文模型將結構洞原理運用到用戶影響力評價中，同時改進其評價方法——網絡約束系數未考慮用戶行為以及節點與鄰近節點、次鄰近節點的三層拓撲結構的問題，最終實現對用戶影響力的度量。實驗結果驗證了本文模型度量用戶影響力的有效性和準確性。在下一步的工作中，將在本文研究成果的基礎上，對用戶行為中的主題進行識別，情感進行分析，進一步優化對用戶影響力的評價。

注：本文通訊作者為覃錫忠。

參考文獻

[1] 吳信東，李毅，李磊.在線社交網絡影響力分析[J].計算機學報，2014（4）：735?752.

WU X D， LI Y， LI L. Influence analysis of online social networks [J]. Chinese journal of computers， 2014（4）： 735?752.

[2] 王濤，覃錫忠，賈振紅，等.基于相似度和信任度的關聯規則微博好友推薦[J].計算機應用，2016，36（8）：2262?2267.

WANG T， QIN X Z， JIA Z H， et al. Association rules recommendation of MicroBlog friend based on similarity and trust [J]. Journal of computer applications， 2016， 36（8）： 2262?2267.

[3] KANNA A F， YACINE A， AJITH A. Models of influence in online social networks [J]. International journal of intelligent systems， 2013， 29（2）： 161?183.

[4] 王楠，孫欽東，周亞東，等.基于區域交互模型的SNS網絡用戶影響力評估[J].通信學報，2016，37（1）：160?169.

WANG N， SUN Q D， ZHOU Y D， et al. Study on user influence analysis via regional user interaction model in online social networks [J]. Journal on communications， 2016， 37（1）： 160?169.

[5] REZVANI M， LIANG W， XU W， et al. Identifying top? k， structural hole spanners in large?scale social networks [C]// 2015 ACM International on Conference on Information and Knowledge Management. Melbourne： ACM， 2015： 263?272.

[6] ALBERT R， BARABASI A L. Topology of evolving networks： local events and universality [J]. Physical review letters， 2000， 85（24）： 5234?5237.

[7] CHEN D B， GAO H， L? L， et al. Identifying influential nodes in large?scale directed networks： the role of clustering [J]. Plos ONE， 2013， 8（10）： 77455.

[8] LU L J， ZHANG M. Edge betweenness centrality [M]. New York： Springer， 2013.

[9] YAMAGUCHI Y， TAKAHASHI T， AMAGASA T， et al. TURank： twitter user ranking based on user?tweet graph analysis [C]// 2010 International Conference on Web Information Systems Engineering. Berlin： Springer， 2010： 240?253.

[10] WENG J， LIM E P， JIANG J， et al. TwitterRank： finding topic?sensitive influential twitterers [C]// Proceeding of the Third ACM International Conference on Web Search and Data Mining. New York： ACM， 2010： 261?270.

[11] TANG X， YANG C C. Ranking user influence in healthcare social media [J]. ACM transactions on intelligent systems & technology， 2012， 3（4）： 1?21.

[12] GUPTA J P， MENON K， MUKKAMALA R R， et al. Identi?fying weak ties from publicly available social media data in an event [C]// 2016 International Academic Mindtrek Confe?rence. Tampere： ACM， 2016： 11?19.

[13] KONG H， LI X， WANG L， et al. Generalized 2D principal component analysis [C]// 2005 IEEE International Joint Conference on Neural Networks. Montreal： IEEE， 2005： 108?113.

[14] BURT R S. Structural holes： the social structure of competition [M]. Cambridge： Harvard University Press， 2010.

[15] LOU T， TANG J. Mining structural hole spanners through information diffusion in social networks [C]// Proceedings of the 22nd International Conference on World Wide Web. Rio de Janeiro： ACM， 2013： 825?836.

[16] 韓忠明，吳楊，譚旭升，等.面向結構洞的復雜網絡關鍵節點排序[J].物理學報，2015，64（5）：421?429.

HAN Z M， WU Y， TAN X S， et al. Ranking key nodes in complex networks by considering structural holes [J]. Acta physica Sinica， 2015， 64（5）： 421?429.

[17] YE S， WU S F. Measuring message propagation and social influence on Twitter.com [C]// Proceedings of the Second International Conference on Social Informatics. Laxenburg： Springer?Verlag， 2010： 216?231.

[18] HOU W， HUANG Y， ZHANG K. Research of micro?blog diffusion effect based on analysis of retweet behavior [C]// 2015 IEEE International Conference on Cognitive Informatics & Cognitive Computing. Beijing： IEEE， 2015： 255?261.