基于加權轉發關系的社交網絡意見領袖識別算法
2018-09-26 11:30:48仇麗青范鑫
軟件導刊 2018年7期
仇麗青 范鑫
摘要：在社交網絡中進行意見領袖的識別對信息傳播分析、輿情監測、網絡營銷等有著重要意義。目前，很多挖掘意見領袖的研究僅基于簡單的粉絲關注或轉發方式，而忽視了用戶關系中的權重因素，不符合信息傳播的實際情況。因此，提出加權網絡下基于微博轉發關系的FW-Rank（ForwardingWeightRank）算法。該算法使用新浪微博數據進行實驗，相比于通過簡單關注關系形成社交網絡的方式，FW-Rank算法的最終結果更加合理準確。
關鍵詞：社交網絡；意見領袖；微博；FW-Rank
DOI：10.11907/rjdk.181151
中圖分類號：TP312
文獻標識碼：A文章編號：1672-7800（2018）007-0111-05
Abstract：Identificationofopinionleadersinsocialnetworkshasgreatsignificanceontheanalysisofinformationdissemination，publicopinionmonitoring，networkmarketingandsoon.Atpresent，mostoftheresearchonopinionleadersinsocialnetworkisbasedonsimplefansorrewardconcernedaboutthelinkmerelyfocusedonfansattentionorforwardingmethod，andignorestheweightfactorsintheuserrelationship，whichmakesthefinalresultunreasonable.Therefore，thepaperproposesanovelalgorithmcalledFW-Rankwhichtakestheforwardingrelationshipofthenetworkintoaccount.AtlastweconducttheexperimentsonSinaMicroBlogdataset.Comparedtothebaselinealgorithms，thefinalresultsoftheproposedalgorithmismorereasonableandaccurate.
KeyWords：socialnetworks；opinionleader；micro-blog；FW-Rank
0引言
隨著移動互聯網的迅速發展，社交網絡使用戶之間可以隨時隨地進行交流和溝通，微博作為社交網絡中的典型應用，已成為如今應用最廣泛的信息傳播媒介之一。微博作為一種分享和交流平臺，更注重時效性和隨意性，并具有便捷性、原創性和用戶草根化等特點。在微博傳播過程中，通常存在著一些很有影響力的用戶，他們在網絡口碑效應、突發事件傳播、社會輿論等方面起著重要作用，這些用戶被稱為“意見領袖”?！耙庖婎I袖”最早由美國學者拉扎斯菲爾德提出，他認為信息是按照“媒體—意見領袖—受眾”的模式傳播[1]，后續學者研究結果表明，“意見領袖”具有“信息中間人”和“有影響力的人”兩種角色特點[2]。在微博的信息網絡中挖掘意見領袖，對微博營銷、輿論引導、網絡干預等都有著重大意義。
微博平臺上的用戶數量龐大，用戶的任何一次“轉發”行為都可看作信息的一次傳播，用戶的個人觀點和影響力可沿著信息的“轉發”網絡進行傳播。本文提出基于微博“轉發”網絡的新型排序算法，用于挖掘微博用戶中的意見領袖，同時驗證算法的有效性。
1相關研究
微博網絡是社會網絡的一種形式，屬于復雜網絡的范疇[3]。在微博網絡中可以將用戶的注冊ID作為網絡節點，進而在用戶節點之間建立聯系。目前用于挖掘意見領袖的方法主要分為兩大類：指標聚類法和鏈接排序法。
（1）指標聚類法。指標聚類法是以節點基本特征為基礎，通過對節點基本特征的分析，建立相應的評分指標體系，運用聚類算法進行意見領袖的挖掘。例如劉志明等[4]采用粗糙集理論，進行聚類并挖掘意見領袖；祝帥等[5]采用X-means迭代聚類算法挖掘意見領袖；尹衍騰等[6]建立領袖影響體系，提出D-means聚類算法；王鈺等[7]采用EM期望最大化算法識別意見領袖。
以上采用指標聚類方法，通過獲取符合條件的節點簇識別社交網絡的意見領袖，但其數據的條目性過于清晰，破壞了用戶之間的聯系[6]。指標聚類法較為全面，同時也使用較多，但是屬性指標選取很大程度上由個人主觀決定，因此推廣時具有一定難度。
（2）鏈接排序法。鏈接排序法通常是根據用戶之間的相互關系構建社會網絡，然后利用網絡結構算法分析用戶間的關系，進而進行重要性排名，識別意見領袖。自從Pagerank算法[8]被提出以來，不僅被谷歌成功應用于搜索引擎排序，還被廣泛應用于社交網絡分析中。Weng等[9]提出基于PageRank算法的TwitterRank算法實現某一特定主題下的意見領袖識別；肖宇等[10]在PageRank基礎上加入感情權重，提出挖掘意見領袖的LeaderRank算法；熊濤等[11]構建基于微博轉發關系的社交網絡，通過改進后的HITS算法識別意見領袖；席運江等[12]綜合考慮微博博主粉絲質量和微博用戶的交互行為，提出MUR-IBM算法對微博用戶進行影響力排名。
鏈接排序法與信息傳播路徑的關系密切，因此在客觀性上占有很大優勢。但是在傳統的基于網絡鏈接排序算法中，存在以下不足之處：①大量的基于網絡鏈接排序算法通過用戶“關注”關系建立社會網絡。相關研究表明，由于意見領袖屬于信息中間人的角色，相對于用戶之間的關注關系，微博轉發情況更能準確地衡量用戶影響力[13]。即使轉發者的觀點與原文相反，也體現出該信息對轉發者產生了一定影響。因此，研究基于微博轉發關系的社會網絡有重要意義；②在已有微博的意見領袖挖掘研究中，多數使用用戶的注冊ID作為網絡節點，進而形成有向社會網絡。但在使用排序算法處理網絡結構時，很少提出節點之間信息傳播流量對節點之間交互的影響。
基于以上研究，本文以微博中意見領袖的識別為目的，考慮到用戶之間的交互活躍度，采用能夠代表社交網絡中信息流向的轉發關系構建網絡模型，提出一種基于轉發關系的帶權新型算法——FW-Rank算法。
2FW-Rank算法
現階段大多數基于網絡鏈接排序法識別微博網絡意見領袖都采用用戶之間“關注”關系形成的有向網絡，且關系過于單一。因此，提出基于微博“轉發”關系形成的帶權有向社會網絡，并利用FW-Rank算法進行意見領袖識別。
假設A、B、C、D為4個微博用戶，用戶A關注了用戶B，用戶B關注了用戶C，用戶C關注了用戶A，用戶D則沒有關注其他人，同時也沒有被其他人關注，如圖1所示。
在圖中，假設用戶B發表原創微博，用戶A對其進行了轉發；用戶B是用戶C的粉絲，用戶C卻并未關注用戶B，但用戶C依舊可以轉發用戶B的微博；用戶D雖然與其他用戶沒有關注關系，但其依舊可以轉發相關微博。圖1充分體現了信息傳播路徑和轉發路徑的密切關系，同時也能體現出網絡中用戶之間的影響力是沿信息傳播路徑逆向傳播的。
根據圖1可以得到用戶之間基于轉發關系的鄰接關系矩陣：
Tr=0100000001000010
FW-Rank采用有向加權的人際網絡模型，以便準確識別意見領袖。因此，將模型定義為G=（V，E，W）。V代表網絡中的用戶集合，E表示邊集，
其中rj表示j用戶發布帖子被轉發的總次數之和，rij表示i轉發j的總次數。其轉發關系模型及其影響力關系模型如圖2所示。
根據以上論述，定義FW-Rank算法公式為：
其中，FW（Vi）表示當前Vi節點權重，Vj為Vi指向節點的所有節點集合中第j個節點。S（Vi）表示指向Vi節點的所有節點集合，d為阻尼系數，一般取值為0.85；C（Vj）表示Vj節點的所有出鏈權重之和，wjk表示節點Vj指向節點Vk邊的權重。
假設在圖2中用戶vi、vj和vk初始權值都為1，各自被轉發的總次數分別為0次、3次和8次，其中vi轉發過vj3次，vi轉發過vk7次，vj轉發過vk1次，由公式（1）可以得出wij=1，wik=0.875，wjk=0.125；由公式（3）得出C（Vi）=0.875+1=1.875，C（Vj）=0.125，C（Vk）=0；由公式（2）得出FW（vi）=1-0.85=0.15，FW（vj）=（1-0.85）+0.85*（1*1/1.875）=0.6033，FW（vk）=（1-0.85）+（1*0.875/1.875+1*0.125/0.125）=1.3967。
FW-Rank算法使用節點出鏈權重之和作為公式的分母，克服了PageRank算法平均分配權值的缺點；采用轉發關系形成的影響力有向網絡圖，從而使社交網絡中的網絡指向符合信息傳播軌跡，使用時更加符合現實情況。FW-Rank的偽代碼如下：
算法：FW-Rank
INPUT：“邊起點+終點+邊的權值”格式的文件nodes.txt，迭代次數N，阻尼系數d
OUTPUT：排名+節點號+FW值
對所有節點設置初始值1，循環進行以下過程，直至收斂：
依次遍歷所有節點，執行以下過程：
（1）獲取當前節點所有鏈出邊的數量n。
（2）循環n次{
計算每條邊的權重wij=rijrj；
}
（3）計算與當前節點相連鏈出邊的權值和C（Vj）=∑Vk∈S（Vj）wjk。
（4）計算并重新設置當前節點的權值FW（Vi）=（1-d）+d∑Vj∈S（Vi）FW（Vj）·wjiC（Vj）。
3實驗分析
3.1實驗數據準備
使用“中國爬盟”論壇提供的爬蟲工具對新浪微博進行爬取，上傳爬取結果后利用獲得的積分下載微博數據。由于意見領袖大多是話題依賴的，因此針對“轉基因”、“霧霾”、“小米”、“火箭”、“房價”和“公務員”6個較為具體的話題進行數據集下載。原始數據主要內容有：①用戶信息：用戶ID、用戶昵稱、省份城市、性別、粉絲數、狀態數、創建時間；②微博信息：微博ID、發布時間、微博內容、被轉發次數、被評論次數、源用戶、話題類型；③用戶關注關系：用戶ID、關注ID；④微博關系：微博ID、來源微博ID。獲得數據統計情況如表1所示。
經過對數據的去重、噪聲數據識別等預處理，最終獲得質量較高的6個主題微博數據，各主題的基本數據情況如表2所示。
將各個主題的數據集使用開源軟件Gephi進行處理，可以得到各個主題的社會網絡圖，其中節點大小代表節點度數大小，如圖3所示。
由圖3可以看出，6個話題中的用戶關系并不是非常密切，網絡平均度較低，形成的鄰接矩陣皆屬于稀疏矩陣，與現實社會相似。其中“房價”、“小米”和“轉基因”3個話題的節點數較多且圖密度較大，更切合實際社交網絡。
3.2實驗及結果分析
在得到各個話題數據集的基本屬性之后，對每個話題使用FW-Rank算法進行排序，得到的前10名用戶如表3所示。
為了比較FW-Rank算法的實際效果，使用PageRank算法在基于關注關系形成的社會網絡上進行實驗，結果如表4所示。
由表3、表4的實驗結果可以明顯觀察到，某些官方微博賬號始終占有較為重要的社交地位，如“轉基因”話題中的“崔永元”，“霧霾”話題中的“新周刊”和“學習粉絲團”，“小米”話題中的“小米公司”、“小米手機”等。但是相比于給予關注關系的PageRank算法，FW-Rank算法是按照信息傳播路徑進行意見領袖識別的，因此結果中的官方賬號明顯少于前者，即更容易挖掘普通用戶中的潛在意見領袖，例如“轉基因”話題中的“洞庭湖面風11”和“武漢陳國恩”，“霧霾”話題中的“五行屬二”、“腐宅集中營”、“鐵人唐吉柯德”等都是在基于關注關系的PageRank算法結果中不曾出現的。
以上兩種算法平均運行時間隨節點數變化折線圖如圖4所示。在運行時間方面，FW-Rank與PageRank運行時間相差無幾，雖然FW-Rank屬于基于PageRank算法的一種演變，但是該算法是基于轉發網絡進行計算的，更符合信息傳播實際；此外，FW-Rank算法克服了PageRank平均分配權值的缺點，在加強重要節點地位的同時，弱化了普通節點作用，加快了計算速度。
中心性可以定義網絡中的節點重要性，通過中心性度量方案，可以識別網絡中的部分中心界定[14]。為了驗證FW-Rank算法的有效性，選取社會網絡研究領域較為熟知的度中心性、接近中心性和中介中心性3個典型的中心性度量指標，并將FW-Rank算法計算結果中排名前10位和前20位用戶分別與3種中心性結果進行相關性計算，結果如表5所示。
由表5可以看出，在該測試數據集中，FW-Rank算法與度中心性的相關性非常強，相關系數均達到0.9以上；而FW-Rank算法接近中心性與中介中心性在不同話題中的相關系數有所不同，例如在“小米”話題中中介中心性達到0.86以上，相關性非常強，而在“霧霾”和“公務員”話題中的相關性較弱。
4結語
本文在分析社會網絡意見領袖識別研究現狀的同時，根據社會網絡中的信息傳播路徑，提出基于微博轉發關系的加權FW-Rank算法。實驗結果表明，FW-Rank算法在識別意見領袖時得到的結果更加符合實際需求，且算法執行效率較高，有助于挖掘社會網絡中的潛在意見領袖。然而，在執行FW-Rank算法之前對數據質量要求較高，原始數據預處理過程較為繁瑣，后續研究將進一步尋找符合算法要求的更加高效便捷的數據預處理方法。
參考文獻：
[1]LAZARSFELDPF，BERELSONB，GAUDETH.Thepeople′schoice[M].NewYork：ColumbiaUniversityPress，1948.
[2]ROGERSEM，SHOEMAKERFF.Communicationofinnovations：across-culturalapproach[M].NewYork：FreePress，1971.
[3]熊濤，何躍.微博轉發網絡中意見領袖的識別與分析[J].現代圖書情報技術，2013（6）：55-62.
[4]DorogovtsevSN，MendesJFF.Evloutionofnetworks[J].AdvPhys，2002，51：1079-1187.
[5]劉志明，劉魯.微博網絡輿情中的意見領袖識別及分析[J].系統工程，2011（6）：8-16.
[6]祝帥，鄭小林，陳德人.論壇中的意見領袖自動發現算法研究[J].系統工程理論與實踐，2011（S2）：7-12.
[7]尹衍騰，李學明，蔡孟松.基于用戶關系與屬性的微博意見領袖挖掘方法[J].計算機工程，2013（4）：184-189.
[8]王玨，曾劍平，周葆華，等.基于聚類分析的網絡論壇意見領袖發現方法[J].計算機工程，2011（5）：44-46，49.
[9]BRINS，PAGEL.Theanatomyofalarge-scalehypertextualWebsearchengine[J].ComputerNetworks&IsdnSystems;，1998，30：107-117.
[10]WENGJS，LINEP，JINGJ，etal.Twitterrank-findingtopic-sensitiveinfluentialtwitterers[C].Proceedingofthe3rdACMInternationalConferenceonWebSearchandDataMining，2010：261-270.
[11]肖宇，許煒，夏霖.一種基于情感傾向分析的網絡團體意見領袖識別算法[J].計算機科學，2012（2）：34-37，46.
[12]席運江，吳柯，廖曉.改進PageRank算法對微博用戶交互行為的影響[J].計算機仿真，2015（11）：437-440.
[13]KWAKH，LEEC，PARKH，etal.Whatistwitter，asocialnetworkoranewsmedia？[C].Proceedingofthe19thInternationalConferenceonWorldWildWeb，2010：591-600.
[14]LUJ，WANGW.Identificationofkeynodesinmicroblognetworks[J].EtriJournal，2016，38（1）：52-61.
（責任編輯：黃?。?/p>
