一種基于局部傳播路徑的復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別方法

何欣怡 馬茜 楊丹丹 張茂郁

一種基于局部傳播路徑的復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別方法

何欣怡，馬茜，楊丹丹，張茂郁

（天津商業(yè)大學(xué)，天津? 300134）

摘? 要：復(fù)雜網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)識(shí)別是研究復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)、功能、性質(zhì)的重要基礎(chǔ)，在市場(chǎng)營銷、謠言控制、交通規(guī)劃等不同領(lǐng)域都有很強(qiáng)的應(yīng)用價(jià)值。節(jié)點(diǎn)的關(guān)鍵性等價(jià)于節(jié)點(diǎn)的影響力，因此，關(guān)鍵節(jié)點(diǎn)識(shí)別問題可看作節(jié)點(diǎn)影響力評(píng)估問題。文章提出了一種基于局部傳播路徑的復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別方法，該方法僅需計(jì)算目標(biāo)節(jié)點(diǎn)兩步之內(nèi)的拓?fù)浣Y(jié)構(gòu)，還綜合考慮了傳播概率對(duì)節(jié)點(diǎn)影響力評(píng)估的影響。與常見的度中心性、介數(shù)中心性、接近中心性、Kshell中心性相比，該算法識(shí)別結(jié)果更準(zhǔn)確，在不同傳播概率下表現(xiàn)更穩(wěn)定。

關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò)；關(guān)鍵節(jié)點(diǎn)識(shí)別；影響力；傳播路徑

中圖分類號(hào)：TP399；O157.5? 文獻(xiàn)標(biāo)識(shí)碼：A? ? 文章編號(hào)：2096-4706（2023）02-0008-04

A Method for Identifying Key Nodes in Complex Networks Based on Local Propagation Paths

HE Xinyi， MA Qian， YANG Dandan， ZHANG Maoyu

（Tianjin University of Commerce， Tianjin? 300134， China）

Abstract： The identification of key nodes in complex networks is an important basis for studying the structure， function and nature of complex networks. It has strong application value in marketing， rumor control， traffic planning and other fields. The criticality of nodes is equivalent to the influence of nodes. Therefore， the problem of identifying key nodes can be regarded as the problem of evaluating the influence of nodes. This paper proposes a key node identification method for complex networks based on local propagation paths. This method only needs to calculate the topology structure of the target node in two steps， and it also comprehensively considers the effect of propagation probability on the evaluation of node influence. Compared with the common methods such as degree centrality， betweenness centrality， closeness centrality and kshell centrality， this method is more accurate and stable under different propagation probabilities.

Keywords： complex network; key node identification; influence; propagation path

0? 引? 言

關(guān)鍵節(jié)點(diǎn)識(shí)別是復(fù)雜網(wǎng)絡(luò)科學(xué)關(guān)注的熱點(diǎn)和前沿性問題，具有重要的理論意義和應(yīng)用價(jià)值。計(jì)算機(jī)病毒在網(wǎng)絡(luò)中的擴(kuò)散、某種言論觀點(diǎn)在社交網(wǎng)絡(luò)上的傳播、傳染病在人群中的蔓延、國家或城市之間的商品、資金、技術(shù)、人員、信息、車輛等的流動(dòng)都可以看成是服從某種規(guī)律的網(wǎng)絡(luò)傳播行為。這其中，關(guān)鍵節(jié)點(diǎn)在觀點(diǎn)、信息、車輛、人群等的傳播或流動(dòng)中扮演著重要的角色，往往起著推波助瀾或逆轉(zhuǎn)風(fēng)向的關(guān)鍵作用，識(shí)別這些節(jié)點(diǎn)可以幫助促進(jìn)傳播或抑制蔓延[1，2]。同時(shí)，網(wǎng)絡(luò)功能的正常運(yùn)轉(zhuǎn)也極大依賴著這些重要節(jié)點(diǎn)。研究表明，復(fù)雜網(wǎng)絡(luò)中只要5%～10%的重要節(jié)點(diǎn)同時(shí)失效，整個(gè)網(wǎng)絡(luò)就會(huì)無法正常運(yùn)轉(zhuǎn)[3]。識(shí)別這些關(guān)鍵節(jié)點(diǎn)并采取相應(yīng)的保護(hù)措施，可以提高整個(gè)網(wǎng)絡(luò)的穩(wěn)健性和安全性。例如，識(shí)別交通網(wǎng)絡(luò)中的重要樞紐，可以優(yōu)化交通路線，方便乘客換乘，預(yù)防交通擁堵[4]。在電力網(wǎng)絡(luò)中對(duì)關(guān)鍵節(jié)點(diǎn)進(jìn)行優(yōu)化，可以優(yōu)化調(diào)度，預(yù)防大規(guī)模停電[5]。關(guān)鍵節(jié)點(diǎn)識(shí)別的一般思路是根據(jù)某一指標(biāo)對(duì)節(jié)點(diǎn)的影響力進(jìn)行量化，并根據(jù)量化值對(duì)節(jié)點(diǎn)影響力進(jìn)行排序，關(guān)鍵節(jié)點(diǎn)識(shí)別問題可看作是節(jié)點(diǎn)影響力度量問題。節(jié)點(diǎn)影響力主要是通過信息、行為等的傳播體現(xiàn)的。因此，節(jié)點(diǎn)的影響力可表示為節(jié)點(diǎn)的傳播能力，復(fù)雜網(wǎng)絡(luò)的關(guān)鍵節(jié)點(diǎn)識(shí)別問題可看作對(duì)節(jié)點(diǎn)的影響力或傳播能力的評(píng)估問題[6]。

本文提出一種基于局部傳播路徑的復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別方法。本方法在獨(dú)立級(jí)聯(lián)模型的基礎(chǔ)上，首先遍歷搜索從目標(biāo)節(jié)點(diǎn)出發(fā)2步之內(nèi)能到達(dá)的所有節(jié)點(diǎn)，這些節(jié)點(diǎn)被稱為受影響節(jié)點(diǎn)，然后搜索從目標(biāo)節(jié)點(diǎn)出發(fā)到達(dá)受影響節(jié)點(diǎn)的所有路徑。基于每條傳播路徑計(jì)算激活概率，并基于此計(jì)算目標(biāo)節(jié)點(diǎn)對(duì)該受影響節(jié)點(diǎn)的所有2步之內(nèi)的傳播路徑的激活概率之和。將目標(biāo)節(jié)點(diǎn)對(duì)所有受影響節(jié)點(diǎn)的激活概率之和作為目標(biāo)節(jié)點(diǎn)的影響力。本方法除了考慮目標(biāo)節(jié)點(diǎn)的局部拓?fù)浣Y(jié)構(gòu)外，還綜合考慮了傳播概率對(duì)節(jié)點(diǎn)影響力評(píng)估的影響。通過在不同數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)可以發(fā)現(xiàn)，該方法可以在不同的傳播概率下更準(zhǔn)確地識(shí)別關(guān)鍵節(jié)點(diǎn)。

1? 相關(guān)工作

關(guān)鍵節(jié)點(diǎn)識(shí)別的前提是對(duì)節(jié)點(diǎn)的影響力進(jìn)行評(píng)估，節(jié)點(diǎn)的影響力評(píng)估是指采用一定的標(biāo)準(zhǔn)對(duì)節(jié)點(diǎn)影響力的大小進(jìn)行衡量、排序的問題。目前，復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)影響力評(píng)估方法大部分都是基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行的。該類方法多數(shù)較為簡(jiǎn)單，實(shí)用性強(qiáng)，且網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)數(shù)據(jù)，尤其是局部網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)數(shù)據(jù)較易獲得，因此受到大量的關(guān)注。在這類方法中，節(jié)點(diǎn)的影響力可理解為該節(jié)點(diǎn)在網(wǎng)絡(luò)中與其他節(jié)點(diǎn)相連使其具有的重要性。因此，節(jié)點(diǎn)的影響力也常被稱作節(jié)點(diǎn)的中心性（Centrality）[7-9]。

目前，較為常見的中心性方法包括基于局部網(wǎng)絡(luò)結(jié)構(gòu)的評(píng)價(jià)方法——度中心性（Degree Centrality）。此方法將目標(biāo)節(jié)點(diǎn)的鄰居數(shù)量作為影響力評(píng)估指標(biāo)，簡(jiǎn)單直觀，時(shí)間復(fù)雜度低，但在多數(shù)情況下，該方法衡量節(jié)點(diǎn)影響力的結(jié)果不夠準(zhǔn)確，因?yàn)槠淇紤]的信息太過局限?；谌志W(wǎng)絡(luò)結(jié)構(gòu)的評(píng)估方法考慮了節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)結(jié)構(gòu)中位置的重要性，包括介數(shù)中心性（Betweenness Centrality， BC）、接近中心性（Closeness Centrality， CC）等。介數(shù)中心性、接近中心性均假設(shè)節(jié)點(diǎn)影響力沿最短路徑向全網(wǎng)傳播。與基于局部網(wǎng)絡(luò)結(jié)構(gòu)的評(píng)價(jià)方法相比，基于全局網(wǎng)絡(luò)結(jié)構(gòu)的方法的評(píng)估結(jié)果更為準(zhǔn)確。但因網(wǎng)絡(luò)結(jié)構(gòu)一般較為復(fù)雜，規(guī)模龐大，該類方法的時(shí)間復(fù)雜度很高。而且現(xiàn)實(shí)中的很多復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)很難完整獲取，因此，該類方法有較大的局限性。Kitsak等人[10]認(rèn)為節(jié)點(diǎn)在網(wǎng)絡(luò)中的位置決定了節(jié)點(diǎn)的影響力，越接近網(wǎng)絡(luò)核心其影響力越大，并據(jù)此提出了k殼中心性（Kshell Centrality， KS）評(píng)價(jià)方法。該方法時(shí)間復(fù)雜度較低，但賦予很多節(jié)點(diǎn)相同的評(píng)估值，導(dǎo)致它們的影響力難以區(qū)分。此外，基于特征向量的評(píng)價(jià)方法也是評(píng)估節(jié)點(diǎn)影響力的重要方法，代表性的算法為谷歌的PageRank算法。基于特征向量的評(píng)價(jià)方法雖然可取得較好的評(píng)價(jià)效果，但它們只適用于有向、連通的網(wǎng)絡(luò)，應(yīng)用范圍有限，且也面臨著網(wǎng)絡(luò)結(jié)構(gòu)難以完整獲取的問題。近年來，很多工作致力于研究不同指標(biāo)的適用范圍，及在動(dòng)態(tài)網(wǎng)絡(luò)中的影響力評(píng)估問題[11-14]。

2? 本文涉及的基礎(chǔ)知識(shí)

2.1? 網(wǎng)絡(luò)表示

一般用圖的形式來表示復(fù)雜網(wǎng)絡(luò)。一個(gè)具體的復(fù)雜網(wǎng)絡(luò)可抽象為圖G=（V， E），其中V表示網(wǎng)絡(luò)中的節(jié)點(diǎn)集合，節(jié)點(diǎn)的數(shù)目用n表示，E表示邊集合，邊的數(shù)目用m表示。為方便處理和計(jì)算，圖G可表示成鄰接矩陣A={auv}∈{0，1}n×n的形式。auv=1則表示節(jié)點(diǎn)u和節(jié)點(diǎn)v之間有邊直接相連，auv=0則表示無邊直接相連。

2.2? 獨(dú)立級(jí)聯(lián)模型

在關(guān)鍵節(jié)點(diǎn)識(shí)別的工作中一般會(huì)根據(jù)傳播模型對(duì)目標(biāo)節(jié)點(diǎn)的影響力傳播過程進(jìn)行模擬，即假設(shè)節(jié)點(diǎn)影響力的傳播遵從某種模型。本文以獨(dú)立級(jí)聯(lián)模型（Independent Cascade Model， ICM）進(jìn)行相關(guān)工作并進(jìn)行實(shí)驗(yàn)。該模型是一種信息傳播模型，原理簡(jiǎn)單，且使用廣泛。根據(jù)ICM模型，網(wǎng)絡(luò)中的節(jié)點(diǎn)只有兩種狀態(tài)——激活（active）和非激活（inactive）。某一時(shí)刻網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)須處于這兩種狀態(tài)中的一種[15]。用戶收到某信息并會(huì)將該信息傳播給予它直接相連的鄰居節(jié)點(diǎn)，則稱該節(jié)點(diǎn)處于激活狀態(tài)；相反，用戶沒有收到該信息或者收到該信息但并不會(huì)傳播給予它相連的鄰居節(jié)點(diǎn)，則稱該節(jié)點(diǎn)處于未激活狀態(tài)。ICM在離散時(shí)間點(diǎn)t點(diǎn)的動(dòng)態(tài)傳播過程如下：

（1）在t=0時(shí)，網(wǎng)絡(luò)中大部分節(jié)點(diǎn)處于非激活狀態(tài)，只有少量節(jié)點(diǎn)處于激活狀態(tài)，這些處于激活狀態(tài)的節(jié)點(diǎn)被稱為種子節(jié)點(diǎn)。種子節(jié)點(diǎn)一般為提前指定的。

（2）在t≥1的任何時(shí)刻，每一個(gè)在t-1時(shí)刻被激活的節(jié)點(diǎn)u都有且僅有一次機(jī)會(huì)去嘗試激活它處于非激活狀態(tài)的所有鄰居節(jié)點(diǎn)v，激活成功的概率為puv。

（3）當(dāng)多個(gè)節(jié)點(diǎn)u1， u2， u3嘗試激活它們共同的處于未激活狀態(tài)的鄰居節(jié)點(diǎn)v時(shí)，它們嘗試激活的順序是隨機(jī)的，且嘗試激活的行為是互相獨(dú)立不受影響的。

（4）以上過程不斷重復(fù)，當(dāng)網(wǎng)絡(luò)中不再有新的節(jié)點(diǎn)被激活時(shí)，本次傳播終止。此時(shí)，網(wǎng)絡(luò)中處于激活狀態(tài)的節(jié)點(diǎn)的數(shù)量就是本次傳播中種子節(jié)點(diǎn)的影響力。

由于每次根據(jù)ICM模型進(jìn)行模擬產(chǎn)生的傳播結(jié)果可能不同，因此在實(shí)際應(yīng)用中通常要進(jìn)行1 000次以上的大量模擬來降低不確定性。一般取多次模擬出的處于激活狀態(tài)的節(jié)點(diǎn)數(shù)目的平均值作為初始種子節(jié)點(diǎn)的最終影響力。在關(guān)鍵節(jié)點(diǎn)影響力識(shí)別問題中，通常依次把每一個(gè)節(jié)點(diǎn)作為種子節(jié)點(diǎn)，把根據(jù)ICM模型進(jìn)行大量模擬得出的結(jié)果作為其真實(shí)影響力值。

2.3? 評(píng)價(jià)指標(biāo)

關(guān)鍵節(jié)點(diǎn)識(shí)別問題等價(jià)于節(jié)點(diǎn)影響力評(píng)估問題。目前評(píng)價(jià)各種影響力評(píng)估方法好壞的主要思路是：按照某種評(píng)估方法計(jì)算網(wǎng)絡(luò)中每一個(gè)節(jié)點(diǎn)的影響力評(píng)估值，將所有節(jié)點(diǎn)按照評(píng)估值大小降序排列。同時(shí)依次將網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)作為種子節(jié)點(diǎn)根據(jù)傳播模型進(jìn)行多次模擬求平均，這個(gè)值被看作是節(jié)點(diǎn)的真實(shí)影響力值，將所有節(jié)點(diǎn)的真實(shí)影響力值降序排列。通過計(jì)算這兩個(gè)序列的一致性來評(píng)價(jià)該評(píng)估方法的優(yōu)劣，這兩個(gè)序列越一致，則說明該方法越有效。Kendall's Tau（τ）系數(shù)常被用來衡量上述兩個(gè)排序列表的一致性，該系數(shù)的相關(guān)定義如下：

考慮兩個(gè)序列x和y。對(duì)任意一對(duì)觀測(cè)值（xi， yi）和（xj， yj），計(jì)算（xi-xj）（ yi-yj），如果大于0則稱這對(duì)觀測(cè)值是一致的，如果小于0則稱這對(duì)觀測(cè)值是不一致的；如果等于0則稱這對(duì)觀測(cè)值既不是一致的也不是不一致的。具體的計(jì)算公式為：

（1）

Nc和Nd分別表示一致的和不一致的觀測(cè)對(duì)數(shù)量。τ值越接近1，則兩個(gè)序列越一致，說明該評(píng)估方法準(zhǔn)確性越高。

2.4? 常用評(píng)估方法

度中心性（Degree Centrality， DC）。指與該節(jié)點(diǎn)直接相連的鄰居節(jié)點(diǎn)的個(gè)數(shù)。度中心性屬于基于局部拓?fù)浣Y(jié)構(gòu)的方法，計(jì)算非常簡(jiǎn)單，用來分析節(jié)點(diǎn)的直接影響力。

介數(shù)中心性（Betweenness Centrality， BC）。指網(wǎng)絡(luò)中通過該節(jié)點(diǎn)的最短路徑的數(shù)目與所有節(jié)點(diǎn)對(duì)之間最短路徑數(shù)目的比值，屬于全局影響力方法，計(jì)算復(fù)雜度較高。

接近中心性（Closeness Centraity， CC）。指的是目標(biāo)節(jié)點(diǎn)到網(wǎng)絡(luò)中所有其他節(jié)點(diǎn)的最短距離和，屬于全局影響力方法，計(jì)算復(fù)雜度高，但評(píng)估效果較好。

中心性Kshell中心性（Kshell Centrality， KS）。具體計(jì)算方法如下：首先將網(wǎng)絡(luò)中所有DC=1的節(jié)點(diǎn)及與它們相連的邊去掉，這些節(jié)點(diǎn)的KS值為1，重復(fù)這個(gè)過程直到網(wǎng)絡(luò)中沒有度值為1的節(jié)點(diǎn)存在；然后采用同樣的方式去掉網(wǎng)絡(luò)中度值為2的節(jié)點(diǎn)及與它們相連的邊，這些節(jié)點(diǎn)的KS值為2。重復(fù)上述過程直到網(wǎng)絡(luò)中的所有節(jié)點(diǎn)均被移除，此時(shí)，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)都有一個(gè)KS值。

3? 基于局部傳播路徑的關(guān)鍵節(jié)點(diǎn)識(shí)別方法

DC只統(tǒng)計(jì)目標(biāo)節(jié)點(diǎn)的鄰居數(shù)目，考慮的拓?fù)浣Y(jié)構(gòu)過少導(dǎo)致其效果不好。而BC、CC評(píng)估效果有改善但需要在整個(gè)網(wǎng)絡(luò)上進(jìn)行最短路徑的計(jì)算，盡管有很多優(yōu)化算法，但在大規(guī)模網(wǎng)絡(luò)中計(jì)算復(fù)雜度依然很高，且完整的網(wǎng)絡(luò)結(jié)構(gòu)難以獲取。KS方法計(jì)算復(fù)雜度介于DC和BC、CC之間，但對(duì)節(jié)點(diǎn)影響力的區(qū)分度不好，即很多節(jié)點(diǎn)的KS值相同?；诖耍疚奶岢隽艘环N基于局部拓?fù)浣Y(jié)構(gòu)和傳播路徑的節(jié)點(diǎn)影響力評(píng)估方法——局部傳播路徑法（Local Propagation Paths， LPP）。該方法將目標(biāo)節(jié)點(diǎn)對(duì)兩步之內(nèi)能到達(dá)的所有節(jié)點(diǎn)的所有兩步之內(nèi)的傳播路徑的激活概率之和作為目標(biāo)節(jié)點(diǎn)的影響力，因?yàn)閮H考慮了兩步之內(nèi)的節(jié)點(diǎn)，所以計(jì)算復(fù)雜度不高；又因?yàn)榭紤]的范圍比DC要大，且包含傳播概率等信息，評(píng)估會(huì)更加準(zhǔn)確。該方法的具體計(jì)算方法如下：

對(duì)于網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)v∈V，計(jì)算節(jié)點(diǎn)v對(duì)兩步之內(nèi)能到達(dá)的所有節(jié)點(diǎn)w的影響力之和，計(jì)算方法如下：

（2）

其中，PATHvw={path1， path2， …， pathk， …， pathL}，PATHvw表示節(jié)點(diǎn)v到節(jié)點(diǎn)w所有路徑（共有L條）的集合，pathk表示節(jié)點(diǎn)v到節(jié)點(diǎn)w的第k條具體路徑：

（3）

其中， 指節(jié)點(diǎn)Vi和節(jié)點(diǎn)Vi+1之間的傳播概率。因?yàn)長PP只考慮了目標(biāo)節(jié)點(diǎn)對(duì)兩步之內(nèi)節(jié)點(diǎn)的影響力，所以1≤n≤2。

圖1展示了利用LPP評(píng)估方法識(shí)別關(guān)鍵節(jié)點(diǎn)的流程。對(duì)網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)，根據(jù)式（2）、式（3）計(jì)算節(jié)點(diǎn)的LPP值。然后將所有節(jié)點(diǎn)按LPP值由大到小的順序排序，得到序列R。在序列R中，位置越靠前代表影響力越大，然后根據(jù)需要選擇前K個(gè)節(jié)點(diǎn)作為關(guān)鍵節(jié)點(diǎn)。

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

為了評(píng)估LPP評(píng)估方法的表現(xiàn)，本文在四個(gè)真實(shí)復(fù)雜網(wǎng)絡(luò)上進(jìn)行了實(shí)驗(yàn)，分別為空手道俱樂部網(wǎng)絡(luò)Karate、爵士音樂家網(wǎng)絡(luò)Jazz、郵件往來網(wǎng)絡(luò)Email、MSN博客空間博主之間的交流關(guān)系網(wǎng)Blog。這四個(gè)數(shù)據(jù)集均為網(wǎng)絡(luò)公開數(shù)據(jù)集，網(wǎng)絡(luò)基本情況如表1所示，其中，n表示網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量，m表示網(wǎng)絡(luò)邊的數(shù)量（四個(gè)網(wǎng)絡(luò)均為無向網(wǎng)絡(luò)），k表示網(wǎng)絡(luò)節(jié)點(diǎn)平均度。實(shí)驗(yàn)的硬件環(huán)境為：3.2 GHz的Intel（R）Core（TM）i5-3470 CPU，3.89 GB的內(nèi)存。軟件環(huán)境為MATLAB R2013a。

網(wǎng)絡(luò)節(jié)點(diǎn)的真實(shí)影響力采用ICM模型模擬獲得，模型中的傳播概率p取0.01～0.1之間。對(duì)每一個(gè)傳播概率，依次將每個(gè)節(jié)點(diǎn)作為初始激活的種子節(jié)點(diǎn)進(jìn)行模擬傳播，傳播終止時(shí)網(wǎng)絡(luò)中處于激活狀態(tài)的節(jié)點(diǎn)的數(shù)量作為該種子節(jié)點(diǎn)的影響力。為了結(jié)果準(zhǔn)確，本文對(duì)每個(gè)節(jié)點(diǎn)模擬10 000次取平均值作為該節(jié)點(diǎn)的真實(shí)影響力。將節(jié)點(diǎn)按其模擬出的真實(shí)影響力由大到小的順序排列，得到真實(shí)影響力排序序列。本文將LPP的評(píng)估效果與DC、BC、CC、KS對(duì)比。對(duì)每一種方法，計(jì)算網(wǎng)絡(luò)中所有節(jié)點(diǎn)在該方法下的評(píng)估值，按評(píng)估值由高到低的順序排序得到該方法的排序序列。然后計(jì)算真實(shí)影響力序列與該方法的排序序列的一致性τ。實(shí)驗(yàn)結(jié)果如圖2所示，橫軸代表傳播概率p，縱軸代表肯達(dá)爾系數(shù)τ。τ值越大，表明該方法準(zhǔn)確性越高。

如圖2所示，在這四個(gè)數(shù)據(jù)集中，在絕大多數(shù)傳播概率下，LPP均能取得最大的τ值，說明LPP在大多數(shù)傳播概率下評(píng)估效果最好。在Jazz網(wǎng)絡(luò)中，當(dāng)傳播概率較大時(shí)LPP表現(xiàn)稍遜于DC，但差距并不明顯。從圖2中還可以看出，DC、KS、BC等的評(píng)估效果隨傳播概率的變化而產(chǎn)生較大波動(dòng)，例如在Email和Blog數(shù)據(jù)集中，DC、BC等的評(píng)估效果隨傳播概率增大而明顯變差。LPP也有波動(dòng)但幅度較小，說明該方法較為健壯?？傮w看來，BC和KS效果最差，和它們?yōu)楹芏喙?jié)點(diǎn)賦予相同的評(píng)估值導(dǎo)致這些節(jié)點(diǎn)的影響力無法區(qū)分有很大關(guān)系。

除了比較各評(píng)估方法的評(píng)估效果外，本文還比較了各方法的運(yùn)行時(shí)間。因Karate和Jazz網(wǎng)絡(luò)規(guī)模小，運(yùn)行時(shí)間差距不明顯，本文只比較了各方法在Email和Blog中的運(yùn)行時(shí)間，結(jié)果如表2所示?；诰W(wǎng)絡(luò)局部結(jié)構(gòu)的評(píng)估方法DC、LPP的運(yùn)行時(shí)間比BC、CC等基于全局網(wǎng)絡(luò)結(jié)構(gòu)的方法的運(yùn)行時(shí)間短。在網(wǎng)絡(luò)規(guī)模較大時(shí)DC、LPP的優(yōu)勢(shì)將更明顯。

5? 結(jié)? 論

復(fù)雜網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)識(shí)別問題等價(jià)于節(jié)點(diǎn)影響力評(píng)估問題。本文分析了常見節(jié)點(diǎn)影響力評(píng)估方法DC、CC、KS等存在的問題，提出了一種基于局部傳播路徑的度量方法LPP。該方法結(jié)合了DC、CC的優(yōu)點(diǎn)，基于局部拓?fù)浣Y(jié)構(gòu)進(jìn)行計(jì)算使其能在大規(guī)模網(wǎng)絡(luò)上運(yùn)行，考慮了兩步之內(nèi)的節(jié)點(diǎn)的個(gè)數(shù)及它們之間的傳播概率，使得結(jié)果更加準(zhǔn)確。在四個(gè)真實(shí)復(fù)雜網(wǎng)絡(luò)上的實(shí)驗(yàn)證明LPP方法在準(zhǔn)確性、健壯性、運(yùn)行時(shí)間方面均有優(yōu)勢(shì)。

在未來的工作中，本文將嘗試在評(píng)估方法中加入更多的現(xiàn)實(shí)信息，例如考慮網(wǎng)絡(luò)的異質(zhì)性、社區(qū)結(jié)構(gòu)等因素，使得節(jié)點(diǎn)影響力評(píng)估結(jié)果更加準(zhǔn)確、貼近現(xiàn)實(shí)。

參考文獻(xiàn)：

[1] 王敏.復(fù)雜網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)挖掘與社區(qū)發(fā)現(xiàn)算法研究 [D].成都：電子科技大學(xué)，2020.

[2] 王安.基于復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)特征的節(jié)點(diǎn)重要性評(píng)估方法研究 [D].北京：中國人民公安大學(xué)，2020.

[3] 王晉，王伯禮.基于復(fù)雜網(wǎng)絡(luò)的城市群鐵路網(wǎng)絡(luò)節(jié)點(diǎn)重要度研究 [J].內(nèi)蒙古公路與運(yùn)輸，2021（4）：52-57.

[4] 汪軍，夏永躍，王運(yùn)明，等.基于貪心介數(shù)的地鐵-公交復(fù)合網(wǎng)絡(luò)關(guān)鍵車站識(shí)別算法 [J].鐵道標(biāo)準(zhǔn)設(shè)計(jì)，2022，66（7）：132-137.

[5] 朱大銳，王睿，程文姬，等.基于改進(jìn)PageRank算法的輸電網(wǎng)關(guān)鍵節(jié)點(diǎn)辨識(shí)方法研究 [J].電力系統(tǒng)保護(hù)與控制，2022，50（5）：86-93.

[6] 馬茜.社會(huì)網(wǎng)絡(luò)中的節(jié)點(diǎn)影響力度量和k-節(jié)點(diǎn)集的影響力最大化問題研究 [D].濟(jì)南：山東大學(xué)，2017.

[7] 修志博.城市交通復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要度評(píng)估與級(jí)聯(lián)失效研究 [D].長春：吉林大學(xué)，2020.

[8] 羅浩，閆光輝，張萌，等.融合多元信息的多關(guān)系社交網(wǎng)絡(luò)節(jié)點(diǎn)重要性研究 [J].計(jì)算機(jī)研究與發(fā)展，2020，57（5）：954-970.

[9] 郭程遠(yuǎn)，陳鴻昶，王庚潤，等.復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要性排序算法及應(yīng)用綜述 [J].信息工程大學(xué)學(xué)報(bào)，2021，22（3）：313-320+358.

[10] 謝麗霞，孫紅紅，楊宏宇，等.基于K-shell的復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別方法 [J].清華大學(xué)學(xué)報(bào)：自然科學(xué)版，2022，62（5）：849-861.

[11] 周庚.復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)中心性度量算法的研究及應(yīng)用 [D].蘭州：蘭州理工大學(xué)，2020.

[12] 馬媛媛，韓華.基于有效距離的復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)影響力度量方法 [J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2022，19（1）：12-19.

[13] 蔣偉進(jìn)，楊瑩，羅田甜，等.基于全局—局部屬性的復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)綜合影響力評(píng)估算法 [J].物聯(lián)網(wǎng)學(xué)報(bào)，2022，6（3）：133-145.

[14] 楊書新，梁文，朱凱麗.基于三級(jí)鄰居的復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)影響力度量方法 [J].電子與信息學(xué)報(bào)，2020，42（5）：1140-1148.

[15] 邵玉，陳崚，劉維.獨(dú)立級(jí)聯(lián)模型下基于最大似然的負(fù)影響力源定位方法 [J].計(jì)算機(jī)科學(xué)，2022，49（2）：204-215.

作者簡(jiǎn)介：何欣怡（2001—），女，漢族，貴州六盤水人，本科在讀，研究方向：數(shù)據(jù)挖掘；通訊作者：馬茜（1989—），女，漢族，山東威海人，講師，博士，研究方向：復(fù)雜網(wǎng)絡(luò)。

收稿日期：2022-09-12

基金項(xiàng)目：天津市大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計(jì)劃項(xiàng)目（202210069069）；天津市教委科研計(jì)劃項(xiàng)目（2021SK141）