王 利，于 磊，吳 渝

重慶郵電大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，重慶400065

微博作為社會經(jīng)濟(jì)活動中常見的一種網(wǎng)絡(luò)信息交互形式，因為其自身便利、快捷的傳播機(jī)制而受到廣泛的肯定和應(yīng)用，微博中的大量活躍用戶使得微博每天產(chǎn)生海量的數(shù)據(jù)。這些數(shù)據(jù)包括微博用戶發(fā)表的微博帖子、點贊、分享轉(zhuǎn)發(fā)、評論等。微博用戶的這些錯綜復(fù)雜的關(guān)系形成了一個巨大的社交網(wǎng)絡(luò)結(jié)構(gòu)。由于微博的這些自身特點和優(yōu)勢，逐漸成為專家和學(xué)者研究的重點。

在社交網(wǎng)絡(luò)群體與互動方面的相關(guān)研究中，個體影響力評估一直是一個重要方向。在社交網(wǎng)絡(luò)中，用戶基于社交目的或者自我價值實現(xiàn)的需要，發(fā)布和傳播特定話題的信息并與他人互動，以獲得和增強(qiáng)其在網(wǎng)上的話語影響力[1]，用戶的影響力是用戶在微博中特定領(lǐng)域重要性的綜合體現(xiàn)。目前關(guān)于微博用戶影響力的研究，大體上從以下兩個方面進(jìn)行。

基于用戶的靜態(tài)屬性來研究，Cha等[2]分別從入度、出度、提到以及轉(zhuǎn)發(fā)指標(biāo)入手，分別研究了各個指標(biāo)對用戶影響力的影響，并分析了這幾個指標(biāo)的效果。Wang 等[3]提出了一種在具有可調(diào)參數(shù)的復(fù)雜網(wǎng)絡(luò)中節(jié)點重要性的新度量。與其他幾個中心度量相比，他們提出的度量比網(wǎng)絡(luò)節(jié)點的度數(shù)、中間度和緊密度中心性更具有區(qū)別性。Chen等[4]提出Personal Rank算法，該算法也可以用于計算微博用戶的影響力，但在計算時還是需要依賴PageRank算法。

基于用戶行為特征來研究，Kwak 等[5]提出的TunkRank算法，是基于PageRank的變形，是基于Twitter社交網(wǎng)絡(luò)提出的，其思想是粉絲數(shù)越多的用戶他們所發(fā)布的相關(guān)信息越有可能傳播擴(kuò)散整個網(wǎng)絡(luò)。張俊豪等[6]結(jié)合用戶自身行為與微博平臺各個用戶之間的關(guān)注關(guān)聯(lián)關(guān)系，基于經(jīng)典PageRank算法提出改進(jìn)算法UIA（User Influence Assessment）。Kang[7]結(jié)合用戶發(fā)表微博活躍度和PageRank算法，提出了Behavior-Relation-ship Rank算法來評價用戶影響力。孫紅等[8]在傳統(tǒng)的PageRank算法模型上加入了微博用戶自身在微博中的行為活動，同時考慮到了微博用戶的自身行為，結(jié)合用戶權(quán)值得到最終影響力。

微博話題直觀地反射了當(dāng)下大眾對社會熱點及事件的關(guān)注，話題中無數(shù)個體的態(tài)度聚集在一起形成一個動態(tài)整體行為，從這個角度看，對微博整體動態(tài)行為的研究亦屬于突現(xiàn)計算的研究范疇。本文的主要研究內(nèi)容是從突現(xiàn)的角度來對微博用戶行為影響力進(jìn)行評價。

本文從綜合分析用戶的轉(zhuǎn)發(fā)、評論和點贊三種行為入手，結(jié)合突現(xiàn)計算Swarm 模型提出一種基于突現(xiàn)計算Swarm 模型的用戶排序算法（Swarm Model user Rank，SMRank），基于PageRank和用戶行為的影響力評價方法是研究者采用和改進(jìn)比較多的方法，本文算法不同于以往的PageRank 的方法，給出了計算用戶行為影響力的一種新的思維方法。

本文的創(chuàng)新點可以總結(jié)為以下兩點：

（1）不再以用戶為節(jié)點、用戶之間的關(guān)注和粉絲為邊來構(gòu)建網(wǎng)絡(luò)，而是根據(jù)微博話題中t 時刻的參與用戶發(fā)布微博、轉(zhuǎn)發(fā)微博、評論及點贊關(guān)系來構(gòu)建t 時刻的用戶交互關(guān)系網(wǎng)絡(luò)。

（2）可以計算不同用戶在不同時刻的影響力，如果需要在某個時間段對微博話題進(jìn)行引導(dǎo)控制，可以根據(jù)用戶不同時刻影響力的不同，對這個時間段用戶影響力值高的用戶進(jìn)行管理，為微博話題的傳播提供可管可控的思路。

1 相關(guān)技術(shù)基礎(chǔ)

1.1 突現(xiàn)計算

突現(xiàn)計算（Emergent Computation，又稱涌現(xiàn)計算）[9-10]是多agent系統(tǒng)在處理復(fù)雜問題時所展現(xiàn)出來的一種創(chuàng)新的思路邏輯。它是通過利用多個簡單模塊的相互溝通和協(xié)作來自我突現(xiàn)出更加復(fù)雜行為的系統(tǒng)。突現(xiàn)存在于自然和社會各個領(lǐng)域，如自然界的魚群、鳥群和蟻群，社會領(lǐng)域中城市交通流、掌聲同步和復(fù)雜網(wǎng)絡(luò)行為等[11]。

1.2 Swarm模型

Swarm 模型[12]是基于自然界群集行為建立的一個用于研究系統(tǒng)突現(xiàn)行為的模型，它以Reynolds 的“Boids”理論為基礎(chǔ)，其中每個個體根據(jù)對齊、聚集和分離三條基本規(guī)則確定下一步的行為，最終個體在整體上會形成各種不同的排列方式，即產(chǎn)生突現(xiàn)行為。借助Swarm 模型，可以簡化復(fù)雜系統(tǒng)中突現(xiàn)規(guī)律的研究模式。Spector和Klein在文獻(xiàn)[13]中提出了相關(guān)行為的具體計算方法，每個Agent根據(jù)周圍的環(huán)境及行為參數(shù)決定下一刻的方向和速度。

2 基于Swarm模型的微博用戶影響力計算

2.1 問題提出和模型框架

針對大多數(shù)微博用戶影響力評價算法都是事前或事后進(jìn)行計算的問題，本文結(jié)合Swarm突現(xiàn)計算模型提出了一種可以在不同時刻對用戶影響力進(jìn)行計算的方法（SMRank）。SMRank算法的模型框架如圖1所示。

圖1 模型框架圖

2.2 微博特征及定義

由于微博用戶的行為主要受自身認(rèn)知水平和網(wǎng)絡(luò)環(huán)境兩大因素的影響，本文中用戶的影響力由兩方面構(gòu)成：用戶自身影響初值和用戶不同時刻的行為影響力。用戶自身影響初值主要通過用戶粉絲數(shù)和用戶在話題傳播前發(fā)布微博數(shù)計算，用戶t 時刻的行為影響力通過用戶t 時刻交互關(guān)系網(wǎng)絡(luò)計算，t 時刻用戶交互關(guān)系網(wǎng)分為：t 時刻用戶轉(zhuǎn)發(fā)關(guān)系網(wǎng)和t 時刻用戶評論點贊關(guān)系網(wǎng)。

現(xiàn)有的微博傳播研究通常會直接以用戶為節(jié)點、用戶之間的關(guān)注和粉絲為邊來構(gòu)建用戶關(guān)系網(wǎng)絡(luò)，為了減少冗余節(jié)點信息（例如僵尸節(jié)點）對研究的影響，并非直接依賴關(guān)注和粉絲信息來構(gòu)建網(wǎng)絡(luò)，而是依靠微博話題不同時刻中用戶的轉(zhuǎn)發(fā)、評論及點贊關(guān)系來構(gòu)建網(wǎng)絡(luò)，為了方便問題的描述，這里先給出如下幾個定義：

定義1（微博話題中t 時刻的用戶轉(zhuǎn)發(fā)關(guān)系網(wǎng)絡(luò)）用戶轉(zhuǎn)發(fā)關(guān)系網(wǎng)絡(luò)用一個二元組G1t=(U1t,E1t,W1t) 表示，其中，G1t表示微博話題t 時刻的用戶轉(zhuǎn)發(fā)關(guān)系網(wǎng)絡(luò)，U1t表示t 時刻參與話題的全部用戶，E1t表示網(wǎng)絡(luò)中的邊集合，邊集合中的每條邊表示兩個用戶之間存在轉(zhuǎn)發(fā)關(guān)系，W1t為有向邊的轉(zhuǎn)發(fā)權(quán)重。

定義2（微博話題中t 時刻的用戶評論點贊關(guān)系網(wǎng)絡(luò)）用戶評論點贊關(guān)系網(wǎng)絡(luò)用一個二元組G2t=(U2t,E2t,W2t)表示，其中，G2t表示微博話題t 時刻用戶評論點贊關(guān)系網(wǎng)絡(luò)，U2t表示t 時刻參與話題的全部用戶，E2t表示網(wǎng)絡(luò)中的邊集合，邊集合中的每條邊表示兩個用戶之間存在評論或點贊關(guān)系，W2t為有向邊的評論點贊權(quán)重。

定義3（用戶影響力）微博話題中用戶影響力用一個四元組I=(G,U,It,f)進(jìn)行表示，其中，G 包含G1t和G2t，U 表示參與話題的用戶集合，It表示t 時刻的用戶影響力，f 為五元組I 中各元素的映射關(guān)系。對于用戶ui的影響力的定義如下：

2.3 Swarm模型定義

Swarm 模型中agent 在群體沒有控制中心的環(huán)境下，完全依照自身判斷與其他個體交互，從而對整體產(chǎn)生影響。與Swarm 模型中agent 相似，微博話題中的任一用戶都可以參與發(fā)布微博、關(guān)注互動、評論點贊等功能，同時用戶間的交互也會對個體的行為產(chǎn)生影響。根據(jù)微博話題中用戶互動交流與Swarm模型中agent交流的相似性，將swarm模型融入到微博話題用戶影響力評價算法中，關(guān)鍵在于agent 運(yùn)動過程中要靈活結(jié)合用戶發(fā)布微博、轉(zhuǎn)發(fā)、評論及點贊等行為。

基于Spector 和Klein 在文獻(xiàn)[13]提出的計算方法，根據(jù)本文的研究內(nèi)容，在此重新定義Swarm模型的物理含義，在給出定義之前，首先了解以下兩個概念：

微博話題中ui用戶在t 時刻鄰域用戶節(jié)點。指對用戶ui影響較大的用戶集合，為轉(zhuǎn)發(fā)用戶ui微博的用戶集合，在不同時刻用戶ui的鄰域用戶是不同的，可以根據(jù)微博話題t 時刻的用戶轉(zhuǎn)發(fā)關(guān)系網(wǎng)統(tǒng)計得出。

微博話題中ui用戶在t 時刻周圍用戶節(jié)點。指對用戶ui有影響，但是影響不是很大的用戶集合，為評論和點贊用戶ui微博的用戶集合，在不同時刻用戶ui的周圍用戶是不同的，可以根據(jù)微博話題t 時刻的用戶評論點贊關(guān)系網(wǎng)絡(luò)統(tǒng)計得出。

定義4（面向微博話題的Swarm模型）

（1）V1在Swarm模型中代表某一agent指向遠(yuǎn)離其自身范圍d 內(nèi)的所有agent 的均向量，在微博中使用用戶ui的鄰域用戶節(jié)點來進(jìn)行計算，通過用戶轉(zhuǎn)發(fā)關(guān)系網(wǎng)計算。計算公式如下：

其中，U 是參與微博話題的用戶集合，It-1( v )是用戶v上一時刻的用戶影響力，W1t( vui)是用戶v 對用戶ui在t 時刻的微博轉(zhuǎn)發(fā)貢獻(xiàn)度大小，Rt( vui)為用戶v 對用戶ui在t 時刻微博轉(zhuǎn)發(fā)次數(shù)，S1t( vui)表示用戶v 對話題中所有用戶t 時刻轉(zhuǎn)發(fā)微博總數(shù)。

（2）V2在Swarm 模型中是指向模擬世界中心的向量，在微博用戶影響力評價中用上次迭代的前20%的用戶影響力的均值表示。計算公式如下：

其中，Top 為上一時刻的前20%的用戶集合，n 為Top用戶個數(shù)。

（3）V3是某一agent 周圍所有agent 的平均速度向量，在微博用戶中，使用用戶ui周圍用戶節(jié)點對用戶的平均影響力來表示，計算公式如下：

其中，W2t( vui)是用戶v 對用戶ui在t 時刻的微博評論及點贊貢獻(xiàn)度大小，Dt( vui)表示用戶v 對用戶ui在t時刻的評論和點贊數(shù)，S2t( vui)表示用戶v 在t 時刻所有評論和點贊總數(shù)。

（4）V4是某一agent 指向其周圍所有agent 所構(gòu)成的中心的向量，在本文中給出的計算公式如下：

其中，N 為話題中所有用戶個數(shù)。

（5）V5是一個隨機(jī)單位長度向量，在微博用戶行為影響力計算過程中不考慮。

用戶ui在t 時刻影響力公式表示為：

2.4 基于Swarm模型的微博用戶影響力計算算法

一個微博話題發(fā)展要經(jīng)歷萌芽、醞釀、激活、高潮、平息等演變周期，這和復(fù)雜系統(tǒng)中魚群、鳥群等群體的突現(xiàn)行為相似，本文結(jié)合突現(xiàn)計算模型，提出一種基于突現(xiàn)計算Swarm 模型的用戶排序算法（Swarm Model user Rank，SMRank）。算法首先需要計算用戶影響力初值；然后通過迭代計算不同時刻的用戶影響力；最后對不同時刻用戶影響力求和，得出用戶總的影響力值。SMRank算法詳細(xì)描述如下：

用戶影響力初值計算，在本文中主要考慮兩個方面，用戶第一天發(fā)表與話題相關(guān)微博數(shù)、用戶的粉絲數(shù)來衡量。使用最大最小值歸一化方法進(jìn)行計算，用戶影響力初值計算公式如下：

其中，F(xiàn)( ui)為用戶ui在微博話題中的粉絲數(shù)，F(xiàn)min為用戶集中用戶擁有的最小粉絲數(shù)，F(xiàn)max為用戶集中用戶擁有的最大粉絲數(shù)，P( ui)為用戶ui發(fā)布微博數(shù)（原創(chuàng)微博），Pmin為用戶集中用戶發(fā)布的最少微博數(shù)，Pmax為用戶集中用戶發(fā)布的最大微博數(shù)。

SMRank算法描述如下。

算法微博用戶影響力計算

輸入：微博話題用戶參與關(guān)系網(wǎng)G，迭代次數(shù)T 。

輸出：用戶總影響力I( ui)。

執(zhí)行以下步驟：

步驟1 對于用戶ui，根據(jù)公式（9）計算用戶影響力初值I0( ui)。

步驟2 對于用戶ui，根據(jù)公式（8）計算t 時刻的用戶行為影響力It( ui)。

步驟3 t=t+1；當(dāng)t 小于T ，轉(zhuǎn)到步驟2，否則轉(zhuǎn)到步驟4。

步驟4 對于事件中所有的用戶，用公式I( ui)=I1( ui)+I2( ui)+…+IT( ui)。

步驟5 計算得到最終的用戶責(zé)任指數(shù)I( ui)，進(jìn)行排序后輸出結(jié)果，算法結(jié)束。

從算法描述中可以看到，如果用戶總數(shù)為 |U |，算法的迭代次數(shù)為T ，則SMRank 算法的時間復(fù)雜度為O(T |U|2)。在計算用戶影響等級時，需要T |U |個額外空間存儲每次迭代的用戶影響力值，因此，該算法的空間復(fù)雜度為O(T |U |)。

3 用戶影響力評價實驗和分析

3.1 實驗數(shù)據(jù)

在人們的微博社交活動中，很多時候都是以話題的形式產(chǎn)生和傳播的。所以本文使用不同話題作為基本研究對象。使用實驗室開發(fā)的爬蟲軟件，通過指定關(guān)鍵字搜索新浪微博進(jìn)行爬取，爬取的數(shù)據(jù)包含用戶的粉絲、關(guān)注關(guān)系，微博的評論信息和點贊關(guān)系等信息。

本文中數(shù)據(jù)集采用的是2018年11月26日至2018年11月28日的“基因編輯”和2019年2月15日至2月18日的“某品牌食品安全”的微博話題信息。經(jīng)過預(yù)處理和標(biāo)準(zhǔn)化后，得到兩個微博話題事件的統(tǒng)計信息如表1所示。

表1 數(shù)據(jù)統(tǒng)計

3.2 實驗方案

3.2.1 實驗對比對象

為了驗證、評估本文方法，采用下列三種常用微博用戶影響力評估算法進(jìn)行對比。

（1）粉絲數(shù)量（FansRank）。按照微博用戶的粉絲數(shù)量多少來對用戶排名。

（2）被轉(zhuǎn)發(fā)數(shù)量（RepostRank）。按照用戶發(fā)布的微博被其他用戶平均轉(zhuǎn)發(fā)數(shù)的多少對用戶排名。

（3）PageRank 算法[14]。PageRank 算法是一種用于分析網(wǎng)頁的重要程度的算法，現(xiàn)已被廣泛應(yīng)用于社交網(wǎng)絡(luò)分析、意見領(lǐng)袖識別的研究中。

3.2.2 算法參數(shù)設(shè)置

在進(jìn)行實驗時，需要對公式中的一些常量進(jìn)行設(shè)置，設(shè)置方法如下：

公式（8）中的常量c1～c4 用層次法計算得出，層次分析法[15]是一種對復(fù)雜且模糊的問題進(jìn)行量化決策的方法，在本文實驗中它們的值分別為0.561 9、0.075 4、0.324 4、0.038 4。

公式（9）中θ1和θ2參數(shù)，它們的值根據(jù)粉絲數(shù)和微博數(shù)的權(quán)重不同，分別設(shè)置為：θ1=0.4，θ2=0.6。在微博話題傳播中，發(fā)布微博的貢獻(xiàn)往往高于其他行為，這里的權(quán)重按6∶4 劃分，降低了粉絲數(shù)過高帶來的偏差，同時也保留了粉絲數(shù)對微博用戶影響力的表征能力。

3.2.3 具體實驗設(shè)計

本文實驗方案主要包括以下三種：

（1）用戶影響力排名的合理性對比。在“某品牌食品安全”事件數(shù)據(jù)集上，針對不同方法計算得到的影響等級排名結(jié)果，分析排名靠前的用戶的影響值、用戶影響覆蓋率[16]、發(fā)布和話題相關(guān)微博數(shù)等，以說明SMRank算法排名結(jié)果的合理性。

（2）影響覆蓋率[16]對比分析。為了評價SMRank 算法的有效性，在“某品牌食品安全”事件數(shù)據(jù)集上，實驗對比了FansRank 算法、RepostRank 算法和PageRank 算法，計算各方法排名結(jié)果靠前的用戶的影響覆蓋率。

（3）不同時間段的影響力對比。通過對排名靠前的用戶不同時刻影響力進(jìn)行分析，觀察用戶在不同時間的影響力的變化。

其中，（1）和（2）的實驗方案是為了說明本文算法的有效性和合理性，實驗方案（3）是本文與其他算法的主要區(qū)別。

3.3 實驗結(jié)果分析

3.3.1 用戶影響等級排名合理性分析

為了說明排名結(jié)果的合理性，對排名前10的用戶進(jìn)行分析。表2至表5分別展示了SMRank算法、FansRank算法、RepostRank算法和PageRank算法的實驗結(jié)果。

表2至表5中用戶編號是用戶在SMRank算法中的排名序號，從用戶發(fā)布微博數(shù)和用戶影響覆蓋率兩項指標(biāo)可以看出，SMRank算法的排名是比較合理有效的。

3.3.2 影響覆蓋率對比

通過SMRank算法、FansRank、RepostRank和PageRank四種算法分別獲得用戶傳播影響力排名，然后對排名前top k 的用戶影響覆蓋率進(jìn)行對比，實驗結(jié)果如圖2 所示。結(jié)果表明SMRank 算法可以有效地發(fā)現(xiàn)微博話題中影響等級較大的用戶。

表2 SMRank算法排名結(jié)果

表3 FansRank算法排名結(jié)果

表4 RepostRank算法排名結(jié)果

表5 PageRank算法排名結(jié)果

圖2 “某品牌食品安全”中四種算法影響覆蓋率

3.3.3 不同時間段影響力對比

本文提出SMRank 算法可以計算不同時間段不同用戶的影響力，在這里時間段設(shè)置為天，在不同的數(shù)據(jù)集上時間段可以根據(jù)需要設(shè)置為更短或更長的時間（如2 h、6 h或一個月），圖3和圖4分別顯示了不同數(shù)據(jù)集上的排名前5 的用戶每天影響力變化曲線?？梢钥吹矫總€用戶在不同的時刻影響力是不同的；圖3 中用戶1 和用戶4 在第一天影響力很大，而在后面兩天影響力降低，說明該用戶是該微博話題的發(fā)起者；用戶2、用戶3和用戶5在第二天影響力比較大，它們是話題的主要傳播者。圖4中用戶2、用戶1、用戶4和用戶5在第一天有較大的影響力，說明他們對微博話題的發(fā)起起到很重要的作用，而用戶1和用戶3在中間時刻影響較大，說明他們是此微博話題的主要傳播者；最后一天事件熱度降低且即將消亡時，所有用戶的影響力都減小。以上結(jié)論和真實網(wǎng)絡(luò)中的情況是相似的。

圖3 “基因編輯”中排名前5的用戶每天影響力變化

圖4 “食品安全”中排名前5的用戶每天影響力變化

4 結(jié)論

本文在真實的微博話題中進(jìn)行分析，考慮到微博話題的動態(tài)演化和突現(xiàn)計算的相似性，提出了基于Swarm突現(xiàn)計算模型的用戶影響力排序算法。本文算法的評價基礎(chǔ)不是建立在傳統(tǒng)的關(guān)注關(guān)系網(wǎng)上，而是建立在從微博話題參與用戶出發(fā)，結(jié)合發(fā)布微博、轉(zhuǎn)發(fā)、評論和點贊等用戶行為，構(gòu)建不同時刻微博話題轉(zhuǎn)發(fā)關(guān)系網(wǎng)和評論點贊關(guān)系網(wǎng)上；然后在這兩個網(wǎng)絡(luò)中進(jìn)行算法迭代，不僅可以得出用戶影響力排名，而且還可以計算出不同用戶不同時間段的影響力。微博用戶影響力是微博話題重要的研究方向之一，深入研究微博用戶影響力對了解話題信息在微博網(wǎng)絡(luò)中的傳播以及其演化規(guī)律具有重要的意義。

本文也存在一些不足。由于實驗數(shù)據(jù)的限制及不完善，對實驗結(jié)果會造成一定的影響；其次，本文算法也僅僅通過實驗結(jié)果表明它是有效的，缺乏充分的理論基礎(chǔ)。