孫百兵，孫家政，何 泉，杜彥輝

1.中國(guó)人民公安大學(xué) 信息網(wǎng)絡(luò)安全學(xué)院，北京 100038

2.中國(guó)人民公安大學(xué) 偵查學(xué)院，北京 100038

當(dāng)前，世界正處在經(jīng)濟(jì)全球化的高速發(fā)展階段，社會(huì)經(jīng)濟(jì)不斷發(fā)展，隨之而來(lái)也有競(jìng)爭(zhēng)的加劇、新舊企業(yè)的更替，社會(huì)矛盾也在逐漸顯現(xiàn)，群體性事件、團(tuán)體活動(dòng)不斷增加[1-2]。公安機(jī)關(guān)面臨的巨大維穩(wěn)壓力。為此，如何正確識(shí)別群體中起到關(guān)鍵作用的人物就顯得非常具有研究意義。

隨著社交網(wǎng)絡(luò)分析研究的不斷深入，各種各樣的事務(wù)都可以被轉(zhuǎn)化成社交網(wǎng)絡(luò)，通過(guò)社交網(wǎng)絡(luò)分析可以更好地了解事務(wù)的特征[3-4]。在實(shí)際生活中，將目標(biāo)群體映射為社交網(wǎng)絡(luò)，即使該網(wǎng)絡(luò)擁有眾多節(jié)點(diǎn)，節(jié)點(diǎn)間關(guān)系復(fù)雜，也可以通過(guò)節(jié)點(diǎn)重要性分析識(shí)別群體中起到關(guān)鍵作用的重要節(jié)點(diǎn)，把握住重要節(jié)點(diǎn)便可以掌控整個(gè)網(wǎng)絡(luò)[5]。因此，如何準(zhǔn)確、高效地對(duì)社交網(wǎng)絡(luò)進(jìn)行重要度分析有著廣闊的發(fā)展前景。

目前節(jié)點(diǎn)重要性分析已經(jīng)取得了很多研究成果。然而，現(xiàn)階段的節(jié)點(diǎn)重要性算法很容易造成重要節(jié)點(diǎn)聚集的情況，這種情況也被稱為“富人俱樂(lè)部”現(xiàn)象。造成這現(xiàn)象的根本原因是重要性算法的“重要節(jié)點(diǎn)的鄰居節(jié)點(diǎn)也很重要”思想，該思想會(huì)造成與群體核心成員有直接關(guān)系的普通成員的影響力被抬高，而與核心成員沒(méi)有直接聯(lián)系但是也起到較大作用的其他成員的影響力會(huì)被相對(duì)壓低，從而造成不客觀的評(píng)價(jià)結(jié)果。針對(duì)此問(wèn)題，本文分析目標(biāo)群體網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，將群體根據(jù)鏈路結(jié)構(gòu)的疏密進(jìn)行社區(qū)劃分，評(píng)估社區(qū)在整個(gè)群體中的重要程度，并綜合考慮節(jié)點(diǎn)在本社區(qū)的影響力以及其他社區(qū)的聯(lián)通能力，提出了融合社區(qū)評(píng)估的節(jié)點(diǎn)重要性分析算法（node importance analysis integrated with community assessment，NI-CA）。

1 相關(guān)工作

關(guān)鍵節(jié)點(diǎn)是在整個(gè)網(wǎng)絡(luò)具有較大影響的節(jié)點(diǎn)[6-7]，如何評(píng)價(jià)該影響力具有很多角度和方法，最經(jīng)典評(píng)價(jià)指標(biāo)有度中心性、特征向量中心性、介數(shù)中心性和K核分解等。近年來(lái)，國(guó)內(nèi)外學(xué)者在經(jīng)典算法的基礎(chǔ)上不斷完善改進(jìn)，提出了很多新的評(píng)價(jià)方法。Bian等人[8]將多種評(píng)價(jià)指標(biāo)與證據(jù)理論相結(jié)合，結(jié)合了多種算法的優(yōu)越性，改進(jìn)了算法性能。Zhang等人[9]將度值和K核值的結(jié)合作為定義節(jié)點(diǎn)初始權(quán)值，運(yùn)用庫(kù)侖定律融合度量節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要性。Li等人[10]結(jié)合了聚類系數(shù)與鄰域內(nèi)度值總和，提出聚類度的評(píng)價(jià)指標(biāo)，提高了度中心性的準(zhǔn)確度，但是也增大了計(jì)算的時(shí)間復(fù)雜度。Fei等人[11]研究認(rèn)為節(jié)點(diǎn)的影響力與網(wǎng)絡(luò)中其他節(jié)點(diǎn)有關(guān)，將目標(biāo)節(jié)點(diǎn)的鄰域與網(wǎng)絡(luò)最短路徑相結(jié)合，綜合考慮每個(gè)節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)的相互關(guān)系得出影響力估值。Xu等人[12]針對(duì)目前大多重要性算法只針對(duì)靜態(tài)網(wǎng)絡(luò)的問(wèn)題，提出能夠面向動(dòng)態(tài)網(wǎng)絡(luò)的ALR算法，該算法將偏加權(quán)體系與Leaderrank算法相結(jié)合，提高算法在動(dòng)態(tài)網(wǎng)絡(luò)的適用性。Xu等人[13]認(rèn)為節(jié)點(diǎn)的重要程度考慮其鄰接信息熵，在加權(quán)網(wǎng)絡(luò)用節(jié)點(diǎn)的強(qiáng)度來(lái)計(jì)算信息熵而在有向網(wǎng)絡(luò)則綜合了節(jié)點(diǎn)的入度和出度值。Yang等人[14]認(rèn)為實(shí)際中的網(wǎng)絡(luò)很多是在不斷變化的，所以網(wǎng)絡(luò)中各邊的權(quán)重也在不斷變化，提出了灰色關(guān)聯(lián)和SIR傳染病模型相結(jié)合的評(píng)價(jià)方法，對(duì)網(wǎng)絡(luò)中的各個(gè)權(quán)重進(jìn)行動(dòng)態(tài)分配。Zhong等人[15]利用魯棒性的思路，按照特定順序刪除網(wǎng)絡(luò)中的節(jié)點(diǎn)，分析剩余網(wǎng)絡(luò)的連通性等特征，并以此評(píng)估被刪除節(jié)點(diǎn)的重要性。

2 基于社區(qū)評(píng)估的節(jié)點(diǎn)重要性算法

實(shí)際的社交群體中，具有較高影響力的人物或許具有一定的聚集性。但是在利用節(jié)點(diǎn)重要性算法進(jìn)行理論分析時(shí)，這種聚集性被不斷放大，導(dǎo)致具有較高影響力的節(jié)點(diǎn)都處于群體核心位置，而沒(méi)有處于核心位置的節(jié)點(diǎn)影響力被過(guò)分低估，從而造成了“兩極分化”的現(xiàn)象。由此可見(jiàn)傳統(tǒng)算法在針對(duì)目標(biāo)群體搜索重點(diǎn)人的應(yīng)用上并不完善，據(jù)此，本文提出融合社區(qū)評(píng)估的節(jié)點(diǎn)重要性（NI-CA）算法。

2.1 社區(qū)評(píng)估

社區(qū)評(píng)估（community assessment，CA）是本文提出的衡量目標(biāo)群體各社區(qū)重要程度的評(píng)價(jià)指標(biāo)。本文根據(jù)社交網(wǎng)絡(luò)的鏈路結(jié)構(gòu)將目標(biāo)群體進(jìn)行社區(qū)劃分，并根據(jù)各社區(qū)節(jié)點(diǎn)數(shù)量和平均路徑長(zhǎng)度分析其重要程度。

模塊度是評(píng)價(jià)社區(qū)劃分效果優(yōu)良的關(guān)鍵指標(biāo)[16]，一個(gè)好的劃分結(jié)果其表現(xiàn)形式是：在社區(qū)內(nèi)部的節(jié)點(diǎn)相似度較高，而在社區(qū)外部節(jié)點(diǎn)的相似度較低。模塊度也是Louvain算法[17]的核心思想，Louvain算法是一種基于模塊度高效社區(qū)劃分算法，除了運(yùn)算速度快、時(shí)間復(fù)雜度低，還有很高的準(zhǔn)確度，不會(huì)遺漏小型社區(qū)。因此，本文采用Louvain算法對(duì)目標(biāo)群體進(jìn)行社區(qū)劃分。

Louvain算法思想簡(jiǎn)單，是一個(gè)不斷迭代和合并的過(guò)程，在這個(gè)過(guò)程中是否需要進(jìn)行下一次是由模塊度增益來(lái)確定的。網(wǎng)絡(luò)中的模塊度值計(jì)算方法如公式（1）所示：

其中，Aij代表節(jié)點(diǎn)i和j之間邊的權(quán)重，Ki表示所有指向節(jié)點(diǎn)i的連邊權(quán)重之和，Kj同理。δ(i,j)表示判斷i與j是否為同一個(gè)社區(qū)，如果為同一個(gè)社區(qū)此值為1，否則為0。如一個(gè)節(jié)點(diǎn)從當(dāng)前社區(qū)移動(dòng)到另外一個(gè)社區(qū)時(shí)，圖的結(jié)構(gòu)就會(huì)發(fā)生變化，相應(yīng)的模塊度也會(huì)發(fā)生變化，把這種變化稱為模塊度增益，用ΔQ表示，計(jì)算方法如公式（2）所示：

∑in表示在社區(qū)C中的所有邊權(quán)值之和；C表示指點(diǎn)a要加入的社團(tuán)；a表示將要移動(dòng)的節(jié)點(diǎn)；Ki,in表示i點(diǎn)到C的所有邊的權(quán)值之和；∑tot表示所有連接到社區(qū)C的邊的權(quán)值之和。Louvain算法在初始的分區(qū)階段有盡可能多的社區(qū)有節(jié)點(diǎn)。對(duì)每一個(gè)節(jié)點(diǎn)i，考慮將它加入到它的鄰居節(jié)點(diǎn)j并計(jì)算模塊度增量的變化，如果模塊度增量變化大于0，則將它放到對(duì)應(yīng)模塊度變量變化最大的鄰居節(jié)點(diǎn)，否則，該節(jié)點(diǎn)仍然保持在原來(lái)的社區(qū)，直至全網(wǎng)絡(luò)沒(méi)有可以分配的節(jié)點(diǎn)后停止迭代。

譚躍進(jìn)等人提出了一種凝聚度的評(píng)估方式[18]，具有較高的準(zhǔn)確性。目標(biāo)群體網(wǎng)絡(luò)的凝聚度取決于群體中各成員間的聯(lián)通能力和群體規(guī)模，聯(lián)通能力用網(wǎng)絡(luò)的平均路徑長(zhǎng)度l衡量，群體規(guī)模用成員數(shù)量n衡量。對(duì)于有n個(gè)成員的目標(biāo)群體網(wǎng)絡(luò)G的凝聚度如公式（3）所示：

其中，節(jié)點(diǎn)i和節(jié)點(diǎn)j是目標(biāo)網(wǎng)絡(luò)的不同的兩個(gè)節(jié)點(diǎn)，dij代表節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的最短距離。當(dāng)n＝1時(shí)，ω[G]=1。

本文運(yùn)用Louvain算法將目標(biāo)群體網(wǎng)絡(luò)劃分成t個(gè)社區(qū)，各社區(qū)分別用C1,C2,…,Ct表示。對(duì)網(wǎng)絡(luò)社區(qū)分別進(jìn)行重要性評(píng)估時(shí)，本文將需要評(píng)估的社區(qū)中的所有節(jié)點(diǎn)聚合為一個(gè)超節(jié)點(diǎn)，其他社區(qū)保持原樣，C1,C2,…,Ct各社區(qū)分別聚合后形成的網(wǎng)絡(luò)分別記為C1,C2,…,Ct，根據(jù)聚合后使得網(wǎng)絡(luò)凝聚程度變化率評(píng)估社區(qū)重要性，在評(píng)估下一個(gè)社區(qū)時(shí)，原聚合的社區(qū)恢復(fù)成原本的拓?fù)浣Y(jié)構(gòu)，社區(qū)劃分和聚合的過(guò)程如圖1所示。

圖1 社區(qū)劃分和聚合Fig.1 Community segmentation and aggregation

定義1基于社區(qū)劃分和凝聚度的社區(qū)評(píng)估（CA）可以進(jìn)一步表示為公式（4），ω[Gi]的值表示Ci社區(qū)的重要度值。

2.2 基于社區(qū)評(píng)估的節(jié)點(diǎn)重要性算法

針對(duì)傳統(tǒng)節(jié)點(diǎn)重要性算法的高影響力節(jié)點(diǎn)過(guò)度聚集的現(xiàn)象，本文提出的NI-CA算法在評(píng)估節(jié)點(diǎn)影響力時(shí)，考慮目標(biāo)節(jié)點(diǎn)在其社區(qū)外部影響力的同時(shí)，融合該節(jié)點(diǎn)在其本社區(qū)的影響力。由于對(duì)目標(biāo)群體網(wǎng)絡(luò)進(jìn)行社區(qū)評(píng)估，并且分析了目標(biāo)節(jié)點(diǎn)的局域影響力，NI-CA算法可以在客觀評(píng)價(jià)節(jié)點(diǎn)重要性的同時(shí)避免節(jié)點(diǎn)影響力的“兩極分化”。

節(jié)點(diǎn)的社區(qū)內(nèi)部影響力應(yīng)當(dāng)考慮節(jié)點(diǎn)在本社區(qū)的聯(lián)通能力，由于介數(shù)考慮的是網(wǎng)絡(luò)中所有最短路徑的占比問(wèn)題，因此介數(shù)中心性能夠很好地反映點(diǎn)或邊在整個(gè)社區(qū)中的重要性。本文引入介數(shù)中心性對(duì)節(jié)點(diǎn)內(nèi)部的聯(lián)通能力進(jìn)行評(píng)價(jià)，其核心思想是認(rèn)為的處于網(wǎng)絡(luò)中間位置的節(jié)點(diǎn)相比于周邊節(jié)點(diǎn)具有“更大的人際關(guān)系影響”。對(duì)于節(jié)點(diǎn)i的介數(shù)中心性（betweenness centrality，BC）的計(jì)算公式如公式（5）所示：

其中，v(i)表示經(jīng)過(guò)節(jié)點(diǎn)i的最短路徑個(gè)數(shù)，∑δst表示網(wǎng)絡(luò)中是從頂點(diǎn)s到頂點(diǎn)t的最短路徑數(shù)，V是網(wǎng)絡(luò)G的節(jié)點(diǎn)集合。對(duì)于節(jié)點(diǎn)在其社區(qū)內(nèi)部影響力評(píng)價(jià)，還應(yīng)當(dāng)考慮目標(biāo)節(jié)點(diǎn)所在社區(qū)的整體影響力，社區(qū)評(píng)估的影響力越大，該社區(qū)領(lǐng)袖的影響力越大。

定義2社區(qū)成員的內(nèi)部影響力（internal influence）用I表示，C1社區(qū)成員i的內(nèi)部影響力如公式（6）所示，其中BCiC1表示節(jié)點(diǎn)i在其社區(qū)內(nèi)部的介數(shù)中心性值。

在實(shí)際生活中，如果一個(gè)人在其他社區(qū)有很多朋友，他可以發(fā)揮重要的角色來(lái)接收和傳播他的圈子周圍的信息，因此本文在評(píng)估重要性時(shí)還要考慮該節(jié)點(diǎn)在其社區(qū)外部的影響力。

定義3社區(qū)成員的外部影響力（external influence）用E表示，節(jié)點(diǎn)i的外部影響力計(jì)算公式可以進(jìn)一步表示為：

節(jié)點(diǎn)j是節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)，當(dāng)節(jié)點(diǎn)j與節(jié)點(diǎn)i不屬于同一社區(qū)時(shí)，aij=1；當(dāng)節(jié)點(diǎn)j與節(jié)點(diǎn)i屬于同一社區(qū)時(shí)，aij=0。CA(j)表示節(jié)點(diǎn)j所在社區(qū)的社區(qū)評(píng)估值。

定義4基于社區(qū)評(píng)估的節(jié)點(diǎn)重要性算法NI-CA，綜合考慮目標(biāo)節(jié)點(diǎn)在其社區(qū)外部影響力和該節(jié)點(diǎn)在其本社區(qū)的影響力，節(jié)點(diǎn)i的重要性度值可以表示為：

基于標(biāo)準(zhǔn)化歐氏距離的修正：

標(biāo)準(zhǔn)化歐氏距離公式是基于二維坐標(biāo)的直線距離，可以消除在計(jì)算兩因素時(shí)，其中一個(gè)因素?cái)?shù)值過(guò)大從而壓制另一因素的弊端。

2.3 NI-CA算法應(yīng)用步驟

根據(jù)社交網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)分析成員重要度的研究，傳統(tǒng)算法很容易得出高影響力成員“扎堆”的結(jié)果，而未處于網(wǎng)絡(luò)核心位置的其他成員的影響力卻相對(duì)被低估。以詐騙團(tuán)伙為例，對(duì)于一個(gè)擁有幾百甚至上千的團(tuán)伙，團(tuán)伙中的每個(gè)成員都有各自的分工，有指揮組、劇本組、一線電話組、二線電話組、倒賣電話卡組、洗錢(qián)組等。每個(gè)組都有該組中相對(duì)重要的成員，而根據(jù)傳統(tǒng)節(jié)點(diǎn)重要性算法分析，重要成員大都集中在處于網(wǎng)絡(luò)核心位置的指揮組，即使是指揮組中的只起到輔助作用的人員也會(huì)得出很高的影響力估值，而其他組中的起到一定作用的成員影響力被相對(duì)低估。針對(duì)這一問(wèn)題，對(duì)一個(gè)已知目標(biāo)人群的社交網(wǎng)絡(luò)G=(V,E)，基于社區(qū)評(píng)估的NI-CA算法的應(yīng)用步驟如下：

步驟1根據(jù)目標(biāo)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，運(yùn)用Louvain算法對(duì)網(wǎng)絡(luò)進(jìn)行社區(qū)劃分，將群體劃分為多個(gè)小群體。

步驟2對(duì)被劃分后各社區(qū)進(jìn)行重要性評(píng)估，分別聚合各社區(qū)節(jié)點(diǎn)，根據(jù)公式（3）和公式（4）計(jì)算出各社區(qū)在整個(gè)網(wǎng)絡(luò)中的重要程度CA值。

步驟3根據(jù)目標(biāo)節(jié)點(diǎn)所在社區(qū)的社區(qū)評(píng)估CA值和鏈路結(jié)構(gòu)，通過(guò)公式（5）和公式（6）計(jì)算出目標(biāo)節(jié)點(diǎn)的社區(qū)內(nèi)部影響力，找出各社區(qū)的領(lǐng)導(dǎo)人。

步驟4考慮目標(biāo)節(jié)點(diǎn)的跨社區(qū)聯(lián)通性，通過(guò)公式（7）計(jì)算出目標(biāo)節(jié)點(diǎn)的社區(qū)外部影響力。

步驟5將步驟3和步驟4的計(jì)算結(jié)果有機(jī)結(jié)合，通過(guò)公式（8）、（9）計(jì)算出目標(biāo)節(jié)點(diǎn)的NI-CA值。

NI-CA算法流程如圖2所示。

圖2 NI-CA算法流程圖Fig.2 Flow chart of NI-CA algorithm

社區(qū)評(píng)估（CA）的計(jì)算如算法1所示：

算法1社區(qū)重要性評(píng)估

輸入：無(wú)向網(wǎng)絡(luò)G=（V，E）

輸出：各社區(qū)重要性度值CA(Ci)

1.將G中各個(gè)點(diǎn)初始化為一個(gè)社團(tuán)，根據(jù)式（1）計(jì)算此時(shí)的模塊性值；

2.for viin V

節(jié)點(diǎn)到其鄰居節(jié)點(diǎn)所在的社區(qū)，根據(jù)式（1）、（2）計(jì)算模塊度的變化ΔQ，若移動(dòng)后致使ΔQ變化最大，則移動(dòng)成功，否則保持不變；

end for

3.fori=1 to t/*t為社區(qū)個(gè)數(shù)）*/

將Ci社區(qū)分別聚合后形成的網(wǎng)絡(luò)記為Gi；

根據(jù)式（3）、（4）計(jì)算各社區(qū)重要性評(píng)估值CA(Ci)；end for

4.return各社區(qū)評(píng)估CA值

基于社區(qū)評(píng)估的節(jié)點(diǎn)重要性（node importance algorithm based on community assessment，NI-CA）如算法2所示：

算法2節(jié)點(diǎn)重要性評(píng)估的NI-CA算法

輸入：無(wú)向網(wǎng)絡(luò)G=（V，E），各社區(qū)評(píng)估值

輸出：網(wǎng)絡(luò)中各節(jié)點(diǎn)重要度NI-CA值

1.統(tǒng)計(jì)各社區(qū)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)；

2.for viin V

根據(jù)公式（5）、（6）計(jì)算目標(biāo)節(jié)點(diǎn)在其社區(qū)內(nèi)部影響力；

根據(jù)公式（7）計(jì)算目標(biāo)節(jié)點(diǎn)與其他社區(qū)間聯(lián)通能力；

根據(jù)公式（8）、（9）計(jì)算目標(biāo)節(jié)點(diǎn)的綜合重要性；

end for

3.return每個(gè)節(jié)點(diǎn)的重要度NI-CA值

3 實(shí)驗(yàn)與分析

3.1 數(shù)據(jù)描述

本文選取四個(gè)不同的鏈路網(wǎng)絡(luò)進(jìn)行驗(yàn)證實(shí)驗(yàn)，分別是空手道俱樂(lè)部（Karate）網(wǎng)絡(luò)[19]、《冰與火之歌》（A Song of Ice and Fire）人物關(guān)系網(wǎng)絡(luò)[20]、Facebook社交賬號(hào)數(shù)據(jù)集[21]和中國(guó)某地區(qū)詐騙團(tuán)伙（fraud ring）人物關(guān)系。其中Karate網(wǎng)絡(luò)是最常用的復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)集之一，源自于美國(guó)一所大學(xué)空手道俱樂(lè)部的真實(shí)人物關(guān)系，在眾多社交網(wǎng)絡(luò)實(shí)驗(yàn)中被應(yīng)用；A Song of Ice and Fire是美國(guó)著名長(zhǎng)篇奇幻小說(shuō)，其人物角色眾多，關(guān)系復(fù)雜，適合作為實(shí)驗(yàn)數(shù)據(jù)；Facebook是目前最大的線上社交平臺(tái)之一，可以代表線上交流網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn)；Fraud ring網(wǎng)絡(luò)源自于已經(jīng)偵破的網(wǎng)絡(luò)詐騙犯罪案件（長(zhǎng)興縣劉東等詐騙案與劉羅亮等詐騙案，詳見(jiàn)裁判文書(shū)網(wǎng)（2020）浙0522刑初15、16號(hào)判決書(shū)），本文根據(jù)該組織的成員的職務(wù)分工構(gòu)建鏈路網(wǎng)絡(luò)，該案件系犯罪團(tuán)伙的典型代表，案件清晰、判決明確，非常適合進(jìn)行驗(yàn)證實(shí)驗(yàn)。以上四種網(wǎng)絡(luò)的基本特征如表1所示。

表1 網(wǎng)絡(luò)數(shù)據(jù)基本參數(shù)Table 1 Basic parameters of network data

其中，N表示數(shù)據(jù)集中的節(jié)點(diǎn)數(shù)量，E代表節(jié)點(diǎn)間的邊數(shù)，＜K＞表示數(shù)據(jù)集的度平均值，Kmax表示網(wǎng)絡(luò)數(shù)據(jù)中節(jié)點(diǎn)度的最大值，C表示網(wǎng)絡(luò)的平均聚類系數(shù)，＜d＞表示網(wǎng)絡(luò)的平均最短路徑。

3.2 實(shí)驗(yàn)設(shè)計(jì)及分析

本文的研究目的是根據(jù)拓?fù)浣Y(jié)構(gòu)，對(duì)群體網(wǎng)絡(luò)中的成員進(jìn)行重要性評(píng)價(jià)。為了驗(yàn)證算法的優(yōu)越性，運(yùn)用四個(gè)不同類型的群體網(wǎng)絡(luò)作為實(shí)驗(yàn)數(shù)據(jù)，通過(guò)SI傳染病模型、魯棒性測(cè)試以及肯德?tīng)栂嚓P(guān)系數(shù)進(jìn)行驗(yàn)證，橫向?qū)Ρ榷戎笜?biāo)（degree）、特征向量中心性（eigenvector）、介數(shù)中心性（betweenness）和PageRank的實(shí)驗(yàn)結(jié)果。Degree指標(biāo)表示一個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)越多，節(jié)點(diǎn)的重要性越大；Eigenvector指標(biāo)既考慮鄰居節(jié)點(diǎn)的數(shù)量，也考慮鄰居節(jié)點(diǎn)的重要性，是一種迭代的計(jì)算過(guò)程；Betweenness指標(biāo)由經(jīng)過(guò)目標(biāo)節(jié)點(diǎn)的最短路徑數(shù)目來(lái)刻畫(huà)節(jié)點(diǎn)的重要性；PageRank算法最初用作互聯(lián)網(wǎng)網(wǎng)頁(yè)重要度的計(jì)算，后廣泛用于節(jié)點(diǎn)重要性評(píng)估，它對(duì)每個(gè)節(jié)點(diǎn)賦予一個(gè)正實(shí)數(shù)，代表節(jié)點(diǎn)的重要度，經(jīng)過(guò)隨機(jī)游走模型，PageRank值越高，節(jié)點(diǎn)就越重要。

3.2.1 SI模型實(shí)驗(yàn)

SI傳播模型[22-24]驗(yàn)證節(jié)點(diǎn)重要性準(zhǔn)確度的最常用的方法之一，其中S表示易感染者（Susceptible），I表示已感染者（Infectious）。SI模型是將部分節(jié)點(diǎn)作為傳染源（I狀態(tài)），以β的概率不斷傳染與其鄰近的易感染者（S狀態(tài)）。

公式（10）所表達(dá)的含義為：對(duì)于網(wǎng)絡(luò)中的狀態(tài)為易感染S的節(jié)點(diǎn)i，如果該節(jié)點(diǎn)與感染狀態(tài)I的節(jié)點(diǎn)j接觸，節(jié)點(diǎn)i將會(huì)以β概率被傳染，從而成為感染狀態(tài)節(jié)點(diǎn)，成為新的感染源，更新?tīng)顟B(tài)為I(i)，而原感染狀態(tài)I的節(jié)點(diǎn)j，狀態(tài)不會(huì)再發(fā)生變化。此刻這些節(jié)點(diǎn)又成為新的感染源，感染網(wǎng)絡(luò)中其他節(jié)點(diǎn)，直至網(wǎng)絡(luò)中所有節(jié)點(diǎn)都變?yōu)镮狀態(tài)，傳播過(guò)程結(jié)束。

由圖3可以看出，當(dāng)感染到達(dá)T時(shí)刻，SI模型的最終狀態(tài)是網(wǎng)絡(luò)中所有節(jié)點(diǎn)都感染為I類節(jié)點(diǎn)。因此，本文依托SI傳播模型，衡量組織中具有重要角色的成員向其他成員傳遞其影響力的傳播能力，并根據(jù)傳播結(jié)果進(jìn)行評(píng)價(jià)，傳播越快、感染數(shù)量越多，則說(shuō)明感染源節(jié)點(diǎn)對(duì)于其所在的網(wǎng)絡(luò)重要程度準(zhǔn)確性越高，即算法得出的網(wǎng)絡(luò)重要節(jié)點(diǎn)排序越準(zhǔn)確。

圖3 SI傳播過(guò)程圖Fig.3 SI propagation process diagram

實(shí)驗(yàn)結(jié)果如圖4所示，縱坐標(biāo)為感染者的數(shù)量，橫坐標(biāo)為迭代次數(shù)。實(shí)驗(yàn)結(jié)果表明NI-CA算法的效果整體較好，在Karate網(wǎng)絡(luò)和Fraud ring網(wǎng)絡(luò)因?yàn)楣?jié)點(diǎn)數(shù)較少，傳播效果最為明顯，各傳播實(shí)驗(yàn)效果差別明顯。A Song of Ice and Fire人物網(wǎng)絡(luò)和Facebook網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)較多，傳播結(jié)果的區(qū)分不明顯，但是仍然能夠看出在A Song of Ice and Fire人物網(wǎng)絡(luò)中的傳播效果最好，即在該網(wǎng)絡(luò)中，NI-CA算法評(píng)價(jià)的重要節(jié)點(diǎn)具有更高的連通性，可以更快速地將信息傳遍整個(gè)網(wǎng)絡(luò)。在Facebook網(wǎng)絡(luò)中的傳播效果前期并不是最優(yōu)，但是在中后期的傳播速度明顯提升，也就說(shuō)明在Facebook網(wǎng)絡(luò)中，NI-CA算法在計(jì)算各節(jié)點(diǎn)重要性時(shí)，最初評(píng)價(jià)效果并不突出，但是中后期對(duì)節(jié)點(diǎn)的重要性評(píng)價(jià)較為準(zhǔn)確。傳統(tǒng)節(jié)點(diǎn)重要性算法因?yàn)橹匾?jié)點(diǎn)聚集，將這些節(jié)點(diǎn)作為傳播源時(shí)，信息傳播會(huì)大量出現(xiàn)重疊的情況，即花費(fèi)太多時(shí)間重復(fù)將信息傳播給聚集圈周圍的節(jié)點(diǎn)。NI-CA算法通過(guò)社區(qū)評(píng)估找出不同社區(qū)的重要成員，并以此為傳播源進(jìn)行信息傳播，由于信息源較為分散，所以傳播至整個(gè)網(wǎng)絡(luò)的速度更快，有效減少了信息傳播重疊的情況。

圖4 SI傳播實(shí)驗(yàn)結(jié)果Fig.4 Experimental results of SI propagation

3.2.2 魯棒性測(cè)試

魯棒性指標(biāo)[25-27]可以衡量某些節(jié)點(diǎn)在被移除后網(wǎng)絡(luò)功能變化情況。在網(wǎng)絡(luò)魯棒性實(shí)驗(yàn)仿真中，按照節(jié)點(diǎn)重要度排序順序依次移除節(jié)點(diǎn)。這樣可以考察攻擊一部分節(jié)點(diǎn)使之失去效果后，即移除該節(jié)點(diǎn)，網(wǎng)絡(luò)整體結(jié)構(gòu)和功能上的變化，用圖中的最大連通分量中的節(jié)點(diǎn)數(shù)目與整個(gè)圖中節(jié)點(diǎn)的總數(shù)目得到比值，作為衡量復(fù)雜網(wǎng)絡(luò)功能魯棒性的強(qiáng)弱。比值越接近1，說(shuō)明整個(gè)網(wǎng)絡(luò)中實(shí)現(xiàn)功能的結(jié)構(gòu)體越大越完整，也說(shuō)明魯棒性越強(qiáng)。其計(jì)算方式如公式（11）所示：

L是表示最大聯(lián)通分量，G為當(dāng)前的圖，θ隨著被移除節(jié)點(diǎn)數(shù)i的增加而下跌如果該曲線下降的越快，則認(rèn)為移除的節(jié)點(diǎn)越能使網(wǎng)絡(luò)碎片化的程度越高。換句話說(shuō)，如果依次移除通過(guò)節(jié)點(diǎn)重要性算法得到的節(jié)點(diǎn)序列可以使整個(gè)網(wǎng)絡(luò)的碎片化程度越大，則這樣的節(jié)點(diǎn)越重要，這個(gè)算法也就越好。

由于魯棒性測(cè)試中，在依次移除節(jié)點(diǎn)時(shí)，移除到中后期的網(wǎng)絡(luò)會(huì)非常分散，并且無(wú)法對(duì)比出各算法之間的優(yōu)越性差異，所以本實(shí)驗(yàn)分別運(yùn)用NI-CA指標(biāo)、Degree指標(biāo)、Eigenvector指標(biāo)、Betweenness指標(biāo)和PageRank的實(shí)驗(yàn)結(jié)果分別對(duì)四個(gè)不同的網(wǎng)絡(luò)進(jìn)行節(jié)點(diǎn)重要度計(jì)算，按照各種計(jì)算出的節(jié)點(diǎn)重要性排序依次移除各網(wǎng)絡(luò)的節(jié)點(diǎn)，橫向?qū)Ρ雀魉惴ㄖg的θ值。

魯棒性實(shí)驗(yàn)結(jié)果如圖5所示，橫坐標(biāo)為移除節(jié)點(diǎn)占比，縱坐標(biāo)為最大連通分量規(guī)模占比。由于很多網(wǎng)絡(luò)在節(jié)點(diǎn)移除后期剩下節(jié)點(diǎn)大多是單節(jié)點(diǎn)，為了實(shí)驗(yàn)效果的區(qū)分度，本實(shí)驗(yàn)將節(jié)點(diǎn)移除至最大連通分量規(guī)模占比低于0.1時(shí)結(jié)束實(shí)驗(yàn)。繪制曲線可以準(zhǔn)確地得到移除節(jié)點(diǎn)對(duì)圖的影響過(guò)程，從而間接衡量了節(jié)點(diǎn)重要性排序的效果。實(shí)驗(yàn)結(jié)果表明各算法在前期移除節(jié)點(diǎn)的過(guò)程中效果相差不大，但是在持續(xù)的移除過(guò)程中，各算法之間的差別逐漸顯現(xiàn)。NI-CA算法的實(shí)驗(yàn)結(jié)果整體較好，但是在Karate網(wǎng)絡(luò)中的實(shí)驗(yàn)效果并不突出，此外，在Facebook網(wǎng)絡(luò)和Fraud ring網(wǎng)絡(luò)的實(shí)驗(yàn)前中期效果顯著，但是在實(shí)驗(yàn)后期效果較差。整體而言，按照NI-CA算法計(jì)算結(jié)果順序移除節(jié)點(diǎn)，對(duì)目標(biāo)網(wǎng)絡(luò)的破壞性較大，移除后網(wǎng)絡(luò)更加分散。傳統(tǒng)節(jié)點(diǎn)重要性算法所形成的重要節(jié)點(diǎn)聚集現(xiàn)象，在魯棒性測(cè)試中可以明顯看出該現(xiàn)象的影響，當(dāng)移除一個(gè)重要節(jié)點(diǎn)后，下一次移除的節(jié)點(diǎn)很可能是該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)，從而對(duì)網(wǎng)絡(luò)的整體性破壞很小。NI-CA算法通過(guò)評(píng)估節(jié)點(diǎn)的社區(qū)內(nèi)部、外部影響力，有效減少了重要節(jié)點(diǎn)聚集的現(xiàn)象，更快速地分散整個(gè)網(wǎng)絡(luò)。

圖5 魯棒性測(cè)試結(jié)果Fig.5 Robustness test results

3.2.3 肯德?tīng)栂嚓P(guān)系數(shù)驗(yàn)證

肯德?tīng)栂嚓P(guān)系數(shù)τ[28-29]是一個(gè)用來(lái)測(cè)量?jī)山M序列相關(guān)性的統(tǒng)計(jì)值，在統(tǒng)計(jì)學(xué)領(lǐng)域多用于分布未知、數(shù)據(jù)類型離散的相關(guān)樣本的比較，取值范圍在-1到1之間，當(dāng)τ為1時(shí)，表示兩個(gè)隨機(jī)變量擁有一致的等級(jí)相關(guān)性；當(dāng)τ為-1時(shí)，表示兩個(gè)隨機(jī)變量擁有完全相反的等級(jí)相關(guān)性；當(dāng)τ為0時(shí)，表示兩個(gè)隨機(jī)變量是相互獨(dú)立的。由此可知，當(dāng)通過(guò)算法得出的重點(diǎn)人排序與網(wǎng)絡(luò)中真實(shí)的頭部重點(diǎn)人比較時(shí)，肯德?tīng)栂嚓P(guān)系數(shù)越大，說(shuō)明和諧的節(jié)點(diǎn)數(shù)越多、算法效果越好。

其中，nc和nd分別表示和諧以及不和諧的個(gè)數(shù)，n為網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)，公式（12）之所以用和諧與不和諧的個(gè)數(shù)差除n(n-1)÷2，是為了解決歸一化問(wèn)題。

本文選取Karate網(wǎng)絡(luò)、A Song of Ice and Fire人物網(wǎng)絡(luò)和Fraud ring網(wǎng)絡(luò)進(jìn)行肯德?tīng)栂嚓P(guān)系數(shù)實(shí)驗(yàn)，通過(guò)網(wǎng)絡(luò)結(jié)構(gòu)背后的實(shí)際意義、劇情和主演列表以及中國(guó)裁判文書(shū)網(wǎng)對(duì)相關(guān)Fraud ring判決文書(shū)確定各網(wǎng)絡(luò)的關(guān)鍵節(jié)點(diǎn)序列，分別運(yùn)用NI-CA指標(biāo)、Degree指標(biāo)、Eigenvector指標(biāo)、Betweenness指標(biāo)和PageRank算法所計(jì)算出的重要成員進(jìn)行相關(guān)性分析，橫向比較各組數(shù)據(jù)的肯德?tīng)栂嚓P(guān)系數(shù)。

四種網(wǎng)絡(luò)的肯德?tīng)栂嚓P(guān)系數(shù)驗(yàn)證結(jié)果如表2所示，實(shí)驗(yàn)結(jié)果顯示，各算法對(duì)Karate網(wǎng)絡(luò)節(jié)點(diǎn)的驗(yàn)證都較為準(zhǔn)確，NI-CA算法的優(yōu)越性并沒(méi)有過(guò)于突出，但對(duì)于其他三個(gè)網(wǎng)絡(luò)NI-CA算法結(jié)果相較于其他算法更為準(zhǔn)確，即NI-CA算法對(duì)各網(wǎng)絡(luò)頭部重點(diǎn)人評(píng)價(jià)適用性、準(zhǔn)確性較高。該結(jié)果表明NI-CA算法整體上準(zhǔn)確性較高，同時(shí)適用大型網(wǎng)絡(luò)和小型網(wǎng)絡(luò)。

表2 肯德?tīng)栂嚓P(guān)系數(shù)實(shí)驗(yàn)結(jié)果Table 2 Kendall correlation coefficient experimental results

4 總結(jié)

本文提出了基于社區(qū)評(píng)估的NI-CA算法，對(duì)劃分社區(qū)后的目標(biāo)人群進(jìn)行社區(qū)評(píng)估分析，通過(guò)融合成員社區(qū)內(nèi)部影響力和外部連通性，識(shí)別各社區(qū)的領(lǐng)袖人物，削弱傳統(tǒng)節(jié)點(diǎn)重要性分析的“富人俱樂(lè)部”現(xiàn)象。于該理論，本文運(yùn)用四個(gè)不同的社交網(wǎng)絡(luò)進(jìn)行驗(yàn)證，驗(yàn)證表明NI-CA算法準(zhǔn)確性高，受網(wǎng)絡(luò)結(jié)構(gòu)特征的影響較小，所需數(shù)據(jù)維度少、普適性高，除用于目標(biāo)人群關(guān)鍵人員挖掘，還可用于網(wǎng)絡(luò)輿論控制等能抽象出具有此類網(wǎng)絡(luò)拓?fù)涮卣鞯陌讣Ｐ汀?/p>

本文提出的方法還有一定的不足之處，本文在考慮節(jié)點(diǎn)的外部連通性上仍有改進(jìn)空間。另外，在本文的研究基礎(chǔ)上仍有需要進(jìn)一步研究的事項(xiàng)，例如本文所使用的網(wǎng)絡(luò)為靜態(tài)網(wǎng)絡(luò)，綜合考慮網(wǎng)絡(luò)中節(jié)點(diǎn)的時(shí)序特征對(duì)其重要性的影響。此外，有向網(wǎng)絡(luò)和加權(quán)網(wǎng)絡(luò)的重要節(jié)點(diǎn)挖掘，例如email交流的社交網(wǎng)絡(luò)，考慮節(jié)點(diǎn)間關(guān)系的有向性和兩節(jié)點(diǎn)之間的交流次數(shù)，也是后續(xù)工作的研究方向之一。