弱連接視角下的高影響力節(jié)點(diǎn)識別

姚月嬌 劉 向 余博文

(華中師范大學(xué)信息管理學(xué)院，湖北 武漢 430079)

面對現(xiàn)實(shí)生活中存在的輿論傳播[1]、疫情防控[2]、交通調(diào)度[3]等重要問題，可以將其抽象為復(fù)雜網(wǎng)絡(luò)進(jìn)行分析，找到高影響力的因素是解決問題的關(guān)鍵環(huán)節(jié)。學(xué)者們基于不同的情境和理論提出了多種衡量節(jié)點(diǎn)影響力的算法，其中基于特征向量的方法同時(shí)考慮了相鄰節(jié)點(diǎn)的數(shù)量和質(zhì)量，例如特征向量中心性算法、PageRank算法、LeaderRank算法、Hits算法等。

PageRank算法由Sergey和Lawrence提出，是目前最經(jīng)典的排序算法之一。為了增強(qiáng)PageRank算法的適用性，姜帆[4]采用PageRank算法與引文分析方法考察了經(jīng)濟(jì)管理學(xué)領(lǐng)域的44項(xiàng)國際學(xué)術(shù)獎(jiǎng)項(xiàng)的中心性影響力與文獻(xiàn)影響力；張欣等[5]結(jié)合專利的被引次數(shù)和年齡得到了PatentRank算法；霍朝光等[6]利用PagaRank算法進(jìn)行國際深度學(xué)習(xí)領(lǐng)域研究熱點(diǎn)文獻(xiàn)排序，強(qiáng)調(diào)全部關(guān)鍵詞共詞網(wǎng)絡(luò)的重要性；戴炳榮等[7]將公證人評價(jià)機(jī)制與PageRank算法相融合，提出跨鏈公證人機(jī)制評價(jià)模型。也有一些學(xué)者從原理層面對PageRank算法進(jìn)行了改進(jìn)：LeaderRank算法[8]將跳轉(zhuǎn)概率轉(zhuǎn)化為背景節(jié)點(diǎn)，更加靈活地解決了懸掛節(jié)點(diǎn)的問題；臧思思等[9]在考慮時(shí)間異質(zhì)性后得到了T-PR算法并用于評價(jià)作者的學(xué)術(shù)影響力；張憲立等[10]根據(jù)反向PageRank思想和度中心性來評估節(jié)點(diǎn)影響力，形成啟發(fā)式算法MPRD；臧志棟等[11]融入時(shí)間異質(zhì)性因子，構(gòu)建了基于PageRank算法的被引時(shí)間影響因子，并以圖書情報(bào)領(lǐng)域的44種期刊為例進(jìn)行實(shí)證研究。

盡管改進(jìn)PageRank算法的研究已經(jīng)不勝枚舉，但是考慮弱連接的研究不多。在度量強(qiáng)弱連接的研究中，Arthur A等[12]提出了IOS量表、Dibble J L等[13]提出了單維關(guān)系緊密度尺度(URCS)，均通過人的主觀意識來判斷連接強(qiáng)度；岳增慧等[14]將節(jié)點(diǎn)之間的連邊權(quán)重作為連接強(qiáng)度，但是沒有給出區(qū)分強(qiáng)弱的依據(jù)；Kr?mer N C等[15]采用定性與定量相結(jié)合的方法，通過交互參數(shù)、感知到的社會(huì)支持等指標(biāo)來綜合衡量連接強(qiáng)度，并提出連接強(qiáng)度應(yīng)該是一個(gè)連續(xù)變量，而非二分變量。Liu Z等[16]提出，相似性是節(jié)點(diǎn)相互作用的依據(jù)，可以度量關(guān)系緊密程度。在此基礎(chǔ)上，Zhang Y等[17]利用關(guān)系強(qiáng)度挖掘高影響力節(jié)點(diǎn)，認(rèn)為關(guān)系越緊密則影響力越大。但根據(jù)Mark S G提出的弱連接理論[18]，不僅是聯(lián)系緊密的節(jié)點(diǎn)，聯(lián)系疏遠(yuǎn)的節(jié)點(diǎn)也會(huì)對彼此產(chǎn)生一定的作用?；诖耍狙芯吭赑ageRank的基礎(chǔ)上，根據(jù)節(jié)點(diǎn)相似性和弱連接理論重新構(gòu)建了節(jié)點(diǎn)間相互影響的關(guān)系，得到了模型TransRank。通過在推特網(wǎng)絡(luò)、引文網(wǎng)絡(luò)、比特幣網(wǎng)絡(luò)和發(fā)明者網(wǎng)絡(luò)中進(jìn)行SI傳染實(shí)驗(yàn)，檢驗(yàn)新模型的優(yōu)化效果。

1 節(jié)點(diǎn)影響力模型

1.1 PageRank算法

PageRank算法認(rèn)為萬維網(wǎng)中一個(gè)頁面的重要性取決于指向它的其他頁面的數(shù)量和質(zhì)量，被很多高質(zhì)量頁面指向的頁面也會(huì)有很高的質(zhì)量。算法初始，賦予網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)相同的PR值，并且和為1；在每次迭代時(shí)，節(jié)點(diǎn)需要把當(dāng)前的PR值平分給指向的節(jié)點(diǎn)，新PR值是其收到的PR值之和；當(dāng)所有節(jié)點(diǎn)的PR值不再變化時(shí)停止迭代。

對于網(wǎng)絡(luò)中出度為0的節(jié)點(diǎn)(稱為懸掛節(jié)點(diǎn))，它的PR值會(huì)隨著每次迭代不斷增長。為解決這個(gè)問題，引入一個(gè)隨機(jī)跳轉(zhuǎn)概率c，即在迭代過程中每個(gè)節(jié)點(diǎn)的PR值都將以(1-c)的概率均分給網(wǎng)絡(luò)中所有節(jié)點(diǎn)，以c的概率均分給它指向的節(jié)點(diǎn)。節(jié)點(diǎn)i在t時(shí)刻的PR值為：

(1)

PageRank算法中的節(jié)點(diǎn)會(huì)將自己的值平均分配給其指向的節(jié)點(diǎn)，但是不同節(jié)點(diǎn)對同一節(jié)點(diǎn)的影響力是有差異的，同一節(jié)點(diǎn)對不同節(jié)點(diǎn)的影響程度也有高低之分，所以平均分值的傳值方法不能真實(shí)反映節(jié)點(diǎn)之間的影響關(guān)系，由此計(jì)算出的節(jié)點(diǎn)PR值也不能準(zhǔn)確表示節(jié)點(diǎn)在網(wǎng)絡(luò)中的影響力。

1.2 弱連接的影響

Hansen M T[19]將組織中密切、頻繁的直接聯(lián)系稱為強(qiáng)連接，疏遠(yuǎn)、不頻繁的直接聯(lián)系稱為弱連接。1973年，Mark S G提出了弱連接理論[18]，強(qiáng)調(diào)弱連接可以幫助人們在社會(huì)網(wǎng)絡(luò)中獲得重復(fù)率低、價(jià)值性高的信息，進(jìn)而擴(kuò)大信息交流的范圍。Abbasi A等[20]發(fā)現(xiàn)，弱連接可以促使節(jié)點(diǎn)與不同類群中的節(jié)點(diǎn)建立更為廣泛的關(guān)聯(lián)；牌艷欣等[21]根據(jù)引文之間的弱關(guān)系構(gòu)建網(wǎng)絡(luò)，在此基礎(chǔ)上識別出的跨學(xué)科相關(guān)知識組合在指導(dǎo)跨學(xué)科合作上具有一定的意義。

弱連接理論可以應(yīng)用到復(fù)雜網(wǎng)絡(luò)中計(jì)算節(jié)點(diǎn)之間的影響力。將兩個(gè)節(jié)點(diǎn)之間的聯(lián)系程度定義為連接強(qiáng)度，用Rij表示；將兩個(gè)節(jié)點(diǎn)對彼此的影響力定義為影響強(qiáng)度，用Eij表示。研究認(rèn)為，若節(jié)點(diǎn)j與節(jié)點(diǎn)i相連，那么隨著它們的連接強(qiáng)度逐漸增強(qiáng)，雖然相互作用的頻次和強(qiáng)度有所提高，但它們之間的異質(zhì)性會(huì)隨之降低，所以它們對彼此的影響強(qiáng)度會(huì)逐漸減弱；之后隨著兩個(gè)節(jié)點(diǎn)之間的連接強(qiáng)度繼續(xù)加強(qiáng)，相互作用的頻次和強(qiáng)度大幅提升，對彼此的影響強(qiáng)度會(huì)不斷增強(qiáng)。

1.3 TransRank算法

TransRank算法是本研究提出的用于衡量節(jié)點(diǎn)影響力的新模型，在PageRank算法的基礎(chǔ)上改善了傳值規(guī)則，可以抽象為網(wǎng)絡(luò)中各節(jié)點(diǎn)互相傳值的過程，于是取“傳遞”的英文“Transmit”來命名新算法。在TransRank算法初始，賦予網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)均等的初始TR值，且和為1。然后，根據(jù)Liu Z等[16]的研究，計(jì)算每兩個(gè)節(jié)點(diǎn)的共同鄰居在它們所有鄰居中的比例，即節(jié)點(diǎn)相似性，以此判斷節(jié)點(diǎn)之間的關(guān)系是否緊密[22]，本研究將該比例值對應(yīng)為連接強(qiáng)度Rij，公式如下：

(2)

其中，m為節(jié)點(diǎn)i的鄰居數(shù)量，n為節(jié)點(diǎn)j的鄰居數(shù)量，k為節(jié)點(diǎn)i和j的共同鄰居數(shù)量。

之后，根據(jù)弱連接理論，影響強(qiáng)度Eij會(huì)隨著連接強(qiáng)度Rij變化而變化，過程類似于倒置的拋物線[23]，可以用以下函數(shù)來擬合：

(3)

其中0

最后，為了防止懸掛節(jié)點(diǎn)不斷接收其他節(jié)點(diǎn)的值，每個(gè)節(jié)點(diǎn)以c的概率根據(jù)影響強(qiáng)度的比例將TR值分配給它指向的節(jié)點(diǎn)，以(1-c)的概率均分給網(wǎng)絡(luò)中所有節(jié)點(diǎn)。當(dāng)所有節(jié)點(diǎn)的TR值都不再變動(dòng)時(shí)迭代停止，最終節(jié)點(diǎn)的TR值越大，說明節(jié)點(diǎn)在網(wǎng)絡(luò)中影響力越大。節(jié)點(diǎn)i在t時(shí)刻的TR值為：

(4)

其中，OUTj為節(jié)點(diǎn)j的后向節(jié)點(diǎn)集，INi為節(jié)點(diǎn)i的前向節(jié)點(diǎn)集。

1.4 TransRank算法收斂性

1)設(shè)T是一個(gè)n×n的矩陣，其中：

(5)

2)設(shè)R是一個(gè)包含著n個(gè)元素的向量，對應(yīng)著每個(gè)節(jié)點(diǎn)的TR值，其中：

‖R‖=1

(6)

3)算法迭代過程如下：

(7)

其中，e的長度為n、元素都是1的列向量。

4)算法迭代終止條件為：

(8)

5)令：

(9)

無論網(wǎng)絡(luò)連通性如何，T′都是一個(gè)正矩陣。根據(jù)Perron-Frobenius定理，可以得到：

a.矩陣T′的最大特征值為正實(shí)數(shù)特征值λ，其絕對值是所有特征值中最大的。

b.與正實(shí)數(shù)特征值λ對應(yīng)的特征向量的元素均為正。

c.矩陣T是行隨機(jī)矩陣，所以矩陣R*也是行隨機(jī)矩陣，故存在λ=1，對應(yīng)的向量為e，即對于任意非零和非負(fù)的單位初始向量，都可以收斂到R*(此時(shí)R*=e)。

2 實(shí) 驗(yàn)

2.1 數(shù) 據(jù)

本研究的實(shí)驗(yàn)對象是4個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)[24]。其一，Twitter是一個(gè)在線社交平臺，用戶可以發(fā)表推文，也可以對其他用戶的推文進(jìn)行評論或者轉(zhuǎn)發(fā)。本研究截取部分推特用戶之間的轉(zhuǎn)發(fā)關(guān)系，構(gòu)成了推特網(wǎng)絡(luò)，其中推文被轉(zhuǎn)發(fā)的數(shù)量是用戶影響力的一種表現(xiàn)。其二，ArXiv是由康奈爾大學(xué)運(yùn)營維護(hù)的一個(gè)非盈利的數(shù)據(jù)庫，學(xué)術(shù)研究人員可以將自己最新的研究成果發(fā)布到該平臺上，其中論文之間的引用可以看作是研究影響力的擴(kuò)散。本研究使用1993年1月至2003年4月發(fā)表在ArXiv的有關(guān)高能物理理論的文章，并通過引用關(guān)系構(gòu)建了引文網(wǎng)絡(luò)。其三，Bitcoin-OTC是人們進(jìn)行比特幣場外交易的線上市場，其中的用戶都是匿名的，為了維護(hù)交易秩序，用戶需要在每次交易完成后為彼此評分，被多次評分的用戶活動(dòng)廣泛，會(huì)在市場中產(chǎn)生一定程度的影響。本研究選擇了一些匿名用戶及其評論關(guān)系，構(gòu)成了比特幣網(wǎng)絡(luò)。其四，美國專利數(shù)據(jù)庫收錄了1790年至今的美國專利全文，本研究提取了化學(xué)領(lǐng)域1978—2002年的專利數(shù)據(jù)，根據(jù)專利發(fā)明者之間的引用關(guān)系構(gòu)建了發(fā)明者網(wǎng)絡(luò)。

各個(gè)網(wǎng)絡(luò)的特征如表1所示，它們的數(shù)據(jù)規(guī)模和平均度、最大度和平均聚類系數(shù)等網(wǎng)絡(luò)特征均有較大的差異，具有一定的代表性。

表1 實(shí)驗(yàn)網(wǎng)絡(luò)數(shù)據(jù)特征

2.2 實(shí)驗(yàn)過程

本研究根據(jù)式(4)與(1)計(jì)算出了每個(gè)實(shí)驗(yàn)網(wǎng)絡(luò)中各節(jié)點(diǎn)的TR值和PR值，值越大表明節(jié)點(diǎn)的影響力越大。在每個(gè)實(shí)驗(yàn)網(wǎng)絡(luò)中，分別按照TR值和PR值由大到小排列所有節(jié)點(diǎn)，排名較前的節(jié)點(diǎn)被視為對應(yīng)算法識別出的高影響力節(jié)點(diǎn)。

為了檢驗(yàn)TransRank算法識別出的高影響力節(jié)點(diǎn)是否具有更高的影響水平，本研究選擇SI模型，每個(gè)節(jié)點(diǎn)只會(huì)保持易染態(tài)或者從易染態(tài)轉(zhuǎn)變?yōu)楦腥緫B(tài)。將識別出的高影響力節(jié)點(diǎn)作為初始感染節(jié)點(diǎn)，根據(jù)一定的感染率開始傳染進(jìn)程，感染節(jié)點(diǎn)會(huì)逐漸增多并達(dá)到穩(wěn)定，感染的速度和范圍可以體現(xiàn)出算法的優(yōu)劣。具體實(shí)驗(yàn)過程如下：

實(shí)驗(yàn)初始，設(shè)定SI的模型兩個(gè)參數(shù)，感染率p和初始感染范圍α。感染率p可以代表不同的影響情境，比如不同的疾病傳染力大?。怀跏几腥痉秶量梢员硎居绊懥Φ牟煌燃?，α的值越小，說明節(jié)點(diǎn)的排名越靠前，在網(wǎng)絡(luò)中的影響力就越大。

其次，確定初始感染節(jié)點(diǎn)集。先提取出兩種算法排序結(jié)果中前α的節(jié)點(diǎn)集P和T，再剔除重復(fù)節(jié)點(diǎn)，得到初始感染節(jié)點(diǎn)集P′和T′。

再次，比較傳染進(jìn)程。設(shè)定兩個(gè)算法的跳轉(zhuǎn)概率c為0.85，SI模型的感染率p=0.2、初始感染范圍α=2%，結(jié)果如圖1所示。

最后，觀察SI模型參數(shù)變化對算法優(yōu)化效果的影響。定義優(yōu)化值β來更加直觀地反映兩個(gè)算法感染效果的差距，計(jì)算公式如下：

(10)

其中，TI(k)和PI(k)分別表示由初始感染節(jié)點(diǎn)集T′和P′在傳染到第k代時(shí)的感染比例。

檢驗(yàn)TransRank算法在不同影響情境中的優(yōu)化效果時(shí)，初始感染范圍α控制為2%(比特幣網(wǎng)絡(luò)中控制為3.5%)，感染率p分別取0.1、0.2、0.3、0.4，結(jié)果如圖2所示；檢驗(yàn)TransRank算法在挖掘各級影響力節(jié)點(diǎn)的優(yōu)化效果時(shí)，感染率p控制為0.2，初始感染范圍α以0.5%為單位從0.5%遞增到6%，結(jié)果如圖3所示。圖2、圖3中的橫坐標(biāo)為傳染代數(shù)(iters)，縱坐標(biāo)為優(yōu)化值β，不同顏色的線條表示不同的參數(shù)取值。

2.3 實(shí)驗(yàn)結(jié)果

在圖1中，TransRank算法對應(yīng)的曲線始終高于PageRank算法對應(yīng)的曲線，但在子圖B、C、D中，兩個(gè)算法對應(yīng)的曲線會(huì)達(dá)到相同的穩(wěn)定值。以上說明，TransRank算法在3個(gè)真實(shí)網(wǎng)絡(luò)中對應(yīng)的傳染進(jìn)程均明顯快于PageRank算法，在推特網(wǎng)絡(luò)中的感染范圍也大于PageRank算法。

圖1 兩種算法的傳播效果

在圖2中，前3個(gè)子圖里曲線的形態(tài)均為先升高再降低最后保持平穩(wěn)，最后1個(gè)子圖中的曲線一直升高最后保持平穩(wěn)，取值均不小于0。這說明在不同的網(wǎng)絡(luò)中，基于不同的感染率，TransRank算法的傳染速度都優(yōu)于PageRank算法，最終感染范圍也不會(huì)劣于PageRank算法。

圖2 不同感染率下兩種算法的傳播效果

在圖3中，每一列圖像代表1個(gè)網(wǎng)絡(luò)的全部實(shí)驗(yàn)數(shù)據(jù)，其中絕大多數(shù)的曲線分布在0值以上。說明在不同的網(wǎng)絡(luò)中，基于不同的初始感染比例，TransRank算法的傳染速度很大概率優(yōu)于PageRank算法，最終感染范圍很少會(huì)劣于PageRank算法。

綜上所述，TransRank算法具有明顯的優(yōu)化效果，但是會(huì)受到SI模型參數(shù)變化的影響。

3 討 論

3.1 高影響力節(jié)點(diǎn)

根據(jù)TransRank算法和PageRank算法計(jì)算出實(shí)驗(yàn)網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的TR值和PR值后，按照大小順序進(jìn)行排列。由于網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量巨大，為便于比較，不妨選擇排名前2%的節(jié)點(diǎn)作為高影響力節(jié)點(diǎn)。推特網(wǎng)絡(luò)中，共有467個(gè)高影響力節(jié)點(diǎn)，剔除相同節(jié)點(diǎn)后，兩種算法各剩余31個(gè)節(jié)點(diǎn)，如表2所示；引文網(wǎng)絡(luò)中，共有555個(gè)高影響力節(jié)點(diǎn)，剔除相同節(jié)點(diǎn)后，兩種算法各剩余9個(gè)節(jié)點(diǎn)，如表3所示；比特幣網(wǎng)絡(luò)中，共有117個(gè)高影響力節(jié)點(diǎn)，剔除相同節(jié)點(diǎn)后，兩種算法各剩余1個(gè)節(jié)點(diǎn)，如表4所示；發(fā)明者網(wǎng)絡(luò)中，共有162個(gè)高影響力節(jié)點(diǎn)，剔除相同節(jié)點(diǎn)后，兩種算法各剩余1個(gè)節(jié)點(diǎn)，如表5所示。

表2 推特網(wǎng)絡(luò)中的高影響力節(jié)點(diǎn)

表3 TransRank算法在引文網(wǎng)絡(luò)中識別的高影響力節(jié)點(diǎn)

表3(續(xù))

表4 TransRank算法在比特幣網(wǎng)絡(luò)中識別的高影響力節(jié)點(diǎn)

表5 TransRank算法在發(fā)明者網(wǎng)絡(luò)中識別的高影響力節(jié)點(diǎn)

在推特網(wǎng)絡(luò)和發(fā)明者網(wǎng)絡(luò)中，TransRank算法識別的高影響力節(jié)點(diǎn)集在入度和聚類系數(shù)方面平均值較低，在出度方面平均值較高，說明這些節(jié)點(diǎn)更擅長面向多類節(jié)點(diǎn)傳播自身影響力。TransRank算法在引文網(wǎng)絡(luò)中識別的高影響力節(jié)點(diǎn)集有更高的入度平均值和出度平均值，其聚類系數(shù)平均值略低于PageRank算法識別的高影響力節(jié)點(diǎn)集，表明這些節(jié)點(diǎn)不僅會(huì)受很多節(jié)點(diǎn)影響，還會(huì)將自身影響輻射到周圍許多節(jié)點(diǎn)。在比特幣網(wǎng)絡(luò)中，TransRank算法識別的高影響力節(jié)點(diǎn)在聚類系數(shù)、入度和出度方面均有更高取值，從而有更多樣的影響對象。綜上，TransRank算法識別的高影響力節(jié)點(diǎn)有更為廣泛的影響覆蓋面。研究還選擇了5%和10%的比例進(jìn)行分析，結(jié)果和結(jié)論沒有改變。

具體來看，以發(fā)明者網(wǎng)絡(luò)為例，TransRank算法識別的高影響力節(jié)點(diǎn)為發(fā)明者、澳大利亞科學(xué)家巴里·馬歇爾，與羅賓·沃倫一同發(fā)現(xiàn)了幽門螺桿菌以及這種細(xì)菌在胃炎和胃潰瘍等疾病中的作用，被授予2005年諾貝爾生理學(xué)或醫(yī)學(xué)獎(jiǎng)。1978—2002年，巴里·馬歇爾在化學(xué)領(lǐng)域共申請成功了7項(xiàng)專利，均有關(guān)于腸胃內(nèi)的微生物和分泌物。由于他沒有較高的被引量和施引量，所以被PageRank算法識別為邊緣節(jié)點(diǎn)。但是根據(jù)TransRank算法，巴里·馬歇爾被標(biāo)記為高影響力節(jié)點(diǎn)，體現(xiàn)出了他在該領(lǐng)域的重要地位。

3.2 不同影響情境

圖2代表著在4個(gè)網(wǎng)絡(luò)中不同感染率下TransRank算法的優(yōu)化效果，每個(gè)圖像中的4個(gè)曲線表示不同的感染率，取值越大則表示TransRank算法越有利于影響力傳播。圖2A和2D中曲線的取值始終大于0，說明對于不同的影響情境，TransRank算法在推特網(wǎng)絡(luò)中識別出的高影響力節(jié)點(diǎn)既有較快的影響速度，又有較大的影響范圍。在圖2B和2C中，曲線在前期均高于0，在后期平穩(wěn)時(shí)取值為0，說明在引文網(wǎng)絡(luò)和比特幣網(wǎng)絡(luò)中，TransRank算法識別出的高影響力節(jié)點(diǎn)擁有更快的影響速度。

在所有實(shí)驗(yàn)網(wǎng)絡(luò)中，TransRank算法識別的高影響力節(jié)點(diǎn)均有更快的影響速度，可以迅速發(fā)揮自身影響力；同時(shí)，這些節(jié)點(diǎn)的影響范圍不會(huì)低于PageRank算法識別出的節(jié)點(diǎn)，可以將影響力擴(kuò)散到與PageRank算法相同甚至更廣泛的區(qū)域。綜上，不論環(huán)境是否有利于影響力傳播，TransRank算法的優(yōu)化效果都很明顯。

3.3 不同影響等級

圖3比較了TransRank算法在4個(gè)網(wǎng)絡(luò)中不同初始感染比例下的優(yōu)化效果，每個(gè)網(wǎng)絡(luò)都包含12條曲線，每條曲線對應(yīng)一個(gè)初始感染比例α，比例越小則選出的節(jié)點(diǎn)影響力越大。

在推特網(wǎng)絡(luò)中，當(dāng)α等于0.5%和2.5%時(shí)，曲線會(huì)上升并在最高點(diǎn)保持平穩(wěn)；當(dāng)α等于1%、2%、3.5%和6%時(shí)，曲線會(huì)有少許的上下波動(dòng)，以上6種初始感染比例對應(yīng)的優(yōu)化值都始終大于0，說明TransRank算法在速度和范圍上均優(yōu)于PageRank算法。當(dāng)α等于3%時(shí)，曲線先上升后下降，最后在0值保持平穩(wěn)，說明兩算法的最終感染范圍相同但TransRank算法的感染進(jìn)程更快；當(dāng)α取其他值時(shí)，曲線會(huì)下降并在最低點(diǎn)保持平穩(wěn)，并且大部分處于0值以下，說明TransRank算法在速度和范圍上均比PageRank算法差。由上可知，在多數(shù)初始感染比例下，TransRank算法在推特網(wǎng)絡(luò)中識別的節(jié)點(diǎn)會(huì)有更好的影響效果。

在引文網(wǎng)絡(luò)中，當(dāng)α等于1.5%、2%、2.5%、4.5%和5.5%時(shí)，曲線會(huì)先上升后下降，最后在0值處保持平穩(wěn)，說明TransRank算法的傳染速度更快，但兩種算法的感染范圍一致；α等于3%、3.5%、4%、5%和6%時(shí)，曲線大致是先下降后上升最后在0值處保持平穩(wěn)，說明PageRank算法的傳染速度更快，而兩種算法的感染范圍相同；當(dāng)α取其他值時(shí)，曲線會(huì)下降并在最低點(diǎn)保持平穩(wěn)，說明TransRank算法在速度和范圍上都較差。對于大多數(shù)的初始感染比例，兩個(gè)算法在引文網(wǎng)絡(luò)識別的節(jié)點(diǎn)的影響范圍一致，其中半數(shù)情況下TransRank算法識別的節(jié)點(diǎn)有更快的影響速度。

在比特幣網(wǎng)絡(luò)中，當(dāng)α為0.5%、1%、2%、2.5%、3%和4.5%時(shí)，兩個(gè)算法識別出的節(jié)點(diǎn)完全一致，所以沒有對應(yīng)的曲線；當(dāng)α為1.5%、3.5%、4%、5%和6%時(shí)，曲線會(huì)先上升后下降，最后在0值處保持平穩(wěn)，說明TransRank算法的傳染速度更快，兩種算法的感染范圍相同；當(dāng)α為5.5%時(shí)，曲線先下降后上升，最后在0值處保持平穩(wěn)，說明PageRank算法的傳染速度更快，兩種算法的感染范圍相同。由此可知，在比特幣網(wǎng)絡(luò)中，在半數(shù)情況下，兩個(gè)算法識別節(jié)點(diǎn)的影響效果一致；在部分情況下，TransRank算法識別的節(jié)點(diǎn)會(huì)在影響速度上表現(xiàn)更好。

在發(fā)明者網(wǎng)絡(luò)中，當(dāng)α為0.5%、2%、2.5%、3%、4%和5.5%時(shí)，兩個(gè)算法識別出的節(jié)點(diǎn)完全一致，所以沒有對應(yīng)的曲線；當(dāng)α為1%時(shí)，曲線先上升，然后在最高點(diǎn)保持平穩(wěn)，說明TransRank算法的傳染速度更快、感染范圍更廣；當(dāng)α為1.5%、3.5%時(shí)，曲線一直貼合于0值，說明兩個(gè)算法效果相當(dāng)；當(dāng)α為5%時(shí)，曲線先下降后，稍微回升，最后在0值處保持平穩(wěn)，說明TransRank算法的傳染速度更快，兩種算法的感染范圍相同；當(dāng)α為4.5%和6%時(shí)，曲線會(huì)先在0值下起伏，最后在0值處保持平穩(wěn)，說明PageRank算法的傳染速度更快，兩種算法的感染范圍相同。由此可知，在發(fā)明者網(wǎng)絡(luò)中，在多數(shù)情況下，兩個(gè)算法識別節(jié)點(diǎn)的影響效果一致；在部分情況下，TransRank算法識別的節(jié)點(diǎn)會(huì)在影響速度上表現(xiàn)更好。

表6匯總了在4個(gè)網(wǎng)絡(luò)中不同初始感染比例下TransRank算法的優(yōu)化效果，從中可以清晰看到，當(dāng)選擇排名前2%或者2.5%的節(jié)點(diǎn)時(shí)，TransRank算法的優(yōu)勢會(huì)穩(wěn)定地體現(xiàn)出來；在選擇其他α值時(shí)，TransRank算法也只會(huì)在部分實(shí)驗(yàn)網(wǎng)絡(luò)中表現(xiàn)較差，大多數(shù)情況下都會(huì)在影響速度上優(yōu)于PageRank算法。

表6 不同網(wǎng)絡(luò)中在不同初始感染比例下的優(yōu)化效果

相對于其他網(wǎng)絡(luò)，引文網(wǎng)絡(luò)的優(yōu)化效果較差，可能是因?yàn)橐木W(wǎng)絡(luò)的平均度更大，節(jié)點(diǎn)之間的聯(lián)系更加密集和頻繁，弱連接的比例較低。推特網(wǎng)絡(luò)的優(yōu)化效果最好，原因可能是該網(wǎng)絡(luò)聚類系數(shù)較低，節(jié)點(diǎn)較為分散，主要是通過弱連接進(jìn)行聯(lián)系。

3.4 弱連接的作用

實(shí)驗(yàn)顯示TransRank算法的影響效果普遍較好，那么這是不是弱連接發(fā)揮的作用呢？為驗(yàn)證此想法，將節(jié)點(diǎn)集T′和指向它的節(jié)點(diǎn)集toT′都提取出來，計(jì)算弱連接連邊對識別重要節(jié)點(diǎn)的貢獻(xiàn)率γ(連接強(qiáng)度為0的連邊集傳給節(jié)點(diǎn)i的值占節(jié)點(diǎn)i接收總值的比例)，結(jié)果如表7所示。

表7 不同網(wǎng)絡(luò)中弱連接對兩種算法貢獻(xiàn)率的比較

在4個(gè)實(shí)驗(yàn)網(wǎng)絡(luò)中，節(jié)點(diǎn)集T'和toT′之間的弱連接均占有很高的比例，是節(jié)點(diǎn)接收值的主要途徑。同時(shí)，相較于PageRank算法，TransRank算法會(huì)賦予節(jié)點(diǎn)集中絕大部分節(jié)點(diǎn)更大的值，并且經(jīng)由弱連接接收到的值更大、貢獻(xiàn)率更高。以上說明，弱連接確實(shí)在識別重要節(jié)點(diǎn)時(shí)發(fā)揮了很大的作用，幫助改善了算法的準(zhǔn)確性和有效性。

4 結(jié) 語

本研究根據(jù)弱連接理論提出了新的節(jié)點(diǎn)影響力模型TransRank算法。新算法識別出的高影響力節(jié)點(diǎn)會(huì)將影響力擴(kuò)展到更廣的范圍中，通過在推特網(wǎng)絡(luò)、引文網(wǎng)絡(luò)、比特幣網(wǎng)絡(luò)、發(fā)明者網(wǎng)絡(luò)4個(gè)真實(shí)網(wǎng)絡(luò)中進(jìn)行SI傳播實(shí)驗(yàn)，發(fā)現(xiàn)新算法可以有效地改善影響速度，即在同樣的時(shí)間里基于相同影響力的節(jié)點(diǎn)群開展感染進(jìn)程，TransRank算法影響到的節(jié)點(diǎn)數(shù)量更多。同時(shí)，新算法也有可能擴(kuò)大影響范圍，即從相同影響力的節(jié)點(diǎn)群開展感染進(jìn)程，TransRank算法影響到的節(jié)點(diǎn)數(shù)量更多。在此基礎(chǔ)上，不論所處的情境是否有利于影響力的傳播，TransRank算法的優(yōu)化效果都不會(huì)改變；對于不同影響等級的節(jié)點(diǎn)集，TransRank算法大概率會(huì)優(yōu)于PageRank算法，其中當(dāng)初始感染比例為2%和2.5%時(shí)，優(yōu)化效果會(huì)更加明顯和穩(wěn)定。

目前，本研究還存在以下不足：首先，只是在無權(quán)有向網(wǎng)絡(luò)中進(jìn)行了算法檢驗(yàn)并得到了較好的結(jié)果，還需要在加權(quán)網(wǎng)絡(luò)和無向網(wǎng)絡(luò)中開展實(shí)驗(yàn)，驗(yàn)證TransRank算法的普適性；其次，只考慮了在靜態(tài)網(wǎng)絡(luò)中挖掘高影響力節(jié)點(diǎn)，忽視了節(jié)點(diǎn)影響力的動(dòng)態(tài)變化。在未來的工作中，將繼續(xù)考察TransRank算法在不同類型網(wǎng)絡(luò)中的表現(xiàn)，并探索節(jié)點(diǎn)影響力的演化軌跡，繼續(xù)完善模型以識別出動(dòng)態(tài)更新的高影響力節(jié)點(diǎn)集。