姜?jiǎng)傥?/p>

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065）

復(fù)雜網(wǎng)絡(luò)中重要節(jié)點(diǎn)的發(fā)現(xiàn)

姜?jiǎng)傥?/p>

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065）

復(fù)雜網(wǎng)絡(luò)中重要節(jié)點(diǎn)的發(fā)現(xiàn)在實(shí)際應(yīng)用中有著重要意義。重要節(jié)點(diǎn)的發(fā)現(xiàn)依賴于節(jié)點(diǎn)的重要性評(píng)估，而如今的一些節(jié)點(diǎn)重要性評(píng)估參數(shù)如介數(shù)、度分布、聚類(lèi)系數(shù)等存在適用范圍有限、評(píng)估結(jié)果不夠全面等局限性，因?yàn)楣?jié)點(diǎn)在復(fù)雜網(wǎng)絡(luò)中的重要性程度不僅僅只受單一因素的影響。提出一種基于拉普拉斯特征映射算法的節(jié)點(diǎn)重要性綜合評(píng)估方法。這種方法能綜合考慮全部節(jié)點(diǎn)的局部特征，可以準(zhǔn)確地對(duì)節(jié)點(diǎn)在復(fù)雜網(wǎng)絡(luò)中的重要性程度進(jìn)行評(píng)估，同時(shí)能夠得到良好的結(jié)果。由于該方法無(wú)需對(duì)復(fù)雜網(wǎng)絡(luò)中所有節(jié)點(diǎn)的全部特征進(jìn)行評(píng)估，極大地縮減計(jì)算時(shí)間，在保證精確性的同時(shí)，提高效率，并通過(guò)MATLAB仿真與現(xiàn)有算法的結(jié)果進(jìn)行分析對(duì)比，證明該算法的有效性和可行性。

復(fù)雜網(wǎng)絡(luò)；重要節(jié)點(diǎn)；拉普拉斯特征映射

0 引言

復(fù)雜網(wǎng)絡(luò)的各項(xiàng)基礎(chǔ)研究工作中，節(jié)點(diǎn)的重要程度評(píng)估，重要節(jié)點(diǎn)的發(fā)掘，具有重要的理論與應(yīng)用價(jià)值[1-2]。國(guó)內(nèi)外在復(fù)雜網(wǎng)絡(luò)重要節(jié)點(diǎn)發(fā)現(xiàn)研究領(lǐng)域已有諸多成果，對(duì)節(jié)點(diǎn)的重要性評(píng)估方法也有很多，其本質(zhì)均是源于圖論和基于圖的數(shù)據(jù)挖掘，對(duì)應(yīng)于圖論中的最關(guān)鍵的節(jié)點(diǎn)問(wèn)題和最關(guān)鍵邊問(wèn)題[3-4]。一般可以通過(guò)復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)的中心性指標(biāo)衡量節(jié)點(diǎn)的重要性程度，人們經(jīng)常使用的復(fù)雜網(wǎng)絡(luò)中心性評(píng)估指標(biāo)有介數(shù)中心性、特征向量中心性、度中心性、接近中心性等。這些評(píng)估指標(biāo)分別從不同角度描述了每個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要性程度[5-7]。但現(xiàn)實(shí)世界中的復(fù)雜網(wǎng)絡(luò)千變?nèi)f化、錯(cuò)綜復(fù)雜，很難只從單一評(píng)估指標(biāo)來(lái)評(píng)估某個(gè)節(jié)點(diǎn)在復(fù)雜網(wǎng)絡(luò)中的重要性程度，由于單一指標(biāo)在不同的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)上的評(píng)估具有很大的片面性，復(fù)雜網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的重要性和這個(gè)網(wǎng)絡(luò)的整體結(jié)構(gòu)相關(guān)，需要從多個(gè)角度，利用節(jié)點(diǎn)的多個(gè)重要性指標(biāo)來(lái)進(jìn)行綜合評(píng)估[8]。因此本文提出了基于拉普拉斯特征映射算法利用節(jié)點(diǎn)的多個(gè)指標(biāo)來(lái)進(jìn)行綜合評(píng)估，以確定其在復(fù)雜網(wǎng)絡(luò)中的重要程度。因?yàn)楹饬抗?jié)點(diǎn)的多個(gè)重要性指標(biāo)對(duì)節(jié)點(diǎn)進(jìn)行綜合評(píng)估能夠涵蓋影響節(jié)點(diǎn)重要性的多種因素，也不再是片面強(qiáng)調(diào)某種單一指標(biāo)的影響，因此能夠得到比使用單一指標(biāo)評(píng)估更為精準(zhǔn)的節(jié)點(diǎn)重要性評(píng)估結(jié)果。利用該方法對(duì)大家普遍使用的 “ARPA網(wǎng)絡(luò)”數(shù)據(jù)集的仿真結(jié)果表明，此方法能夠有效評(píng)估與發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中的重要節(jié)點(diǎn)。

1 拉普拉斯特征映射算法介紹

1.1 算法描述

復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)重要性發(fā)現(xiàn)是復(fù)雜網(wǎng)絡(luò)研究各領(lǐng)域的一個(gè)基本課題,本節(jié)從特征映射角度出發(fā),介紹了一種基于流形學(xué)習(xí)思想的節(jié)點(diǎn)重要性評(píng)估算法，即拉普拉斯特征映射算法（Laplacian Eigenmaps，LE）。拉普拉斯特征映射算法[9]是一種非線性降維方法，它將原始數(shù)據(jù)集映射到低維空間，映射關(guān)系分別是X∈Rm×N與Y∈Rd×N，其中m是原始特征維數(shù)，d是新特征維數(shù)（d〈m），N是數(shù)據(jù)集的樣本個(gè)數(shù)，原始數(shù)據(jù)集與映射集中的樣本分別是xi∈Rm和yi∈Rd。拉普拉斯特征映射是基于局部保序，能夠找到一種映射方式X-〉Y，同時(shí)也能保持?jǐn)?shù)據(jù)集中的數(shù)據(jù)在特征空間分布的局部幾何屬性。它的主要思想是，如果兩個(gè)數(shù)據(jù)實(shí)例Xi和Xj很相似，那么它們?cè)诮稻S后的目標(biāo)子空間中應(yīng)該盡量接近。對(duì)于高維空間的點(diǎn)構(gòu)建連通的無(wú)向加權(quán)圖，再通過(guò)求解圖拉普拉斯算子的廣義特征值實(shí)現(xiàn)映射[10]。該算法首先在數(shù)據(jù)圖形中構(gòu)建 Laplace-Bel-trsmi算子，然后從與 Laplace-Beltrsmi算子相一致的幾個(gè)最小特征值的特征向量中得出降維后的低維數(shù)據(jù)集[11]。

1.2 拉普拉斯特征映射算法流程

步驟1構(gòu)建圖 確定每個(gè)Xi∈Rm的近鄰，并構(gòu)建鄰域關(guān)系圖G（V，E），如采用KNN算法。

步驟2確定權(quán)值

（2）簡(jiǎn)單方法：在圖G（V,E）中，若數(shù)據(jù)點(diǎn)Xi與Xj相連接，則權(quán)重設(shè)定為Wij=1，否則，Wij=0。

步驟3特征映射 尋找關(guān)系映射Ψ：G（V，E）→Y= {y1，y2，…，Yn-1，yN}?Rd，即將鄰域加權(quán)圖 G（V，E）的節(jié)點(diǎn)映射為低維歐氏空間Rd中的一組像點(diǎn)Y={y1，y2，…，Yn-1，yN}，然后定義最小化目標(biāo)函數(shù)：

矩陣L叫作圖的拉普拉斯矩陣，優(yōu)化問(wèn)題則可以寫(xiě)成更簡(jiǎn)潔的形式：

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

2.1 實(shí)驗(yàn)條件與方法

利用大家普遍使用的“APRA網(wǎng)絡(luò)”拓?fù)浣Y(jié)構(gòu)[12]（如圖1）來(lái)分析驗(yàn)證基于拉普拉斯特征映射算法的網(wǎng)絡(luò)節(jié)點(diǎn)重要性多指標(biāo)多維度的評(píng)估方法的正確性。該“APRA網(wǎng)絡(luò)”拓?fù)浣Y(jié)構(gòu)為北美常用干線拓?fù)浣Y(jié)構(gòu)，它由21個(gè)節(jié)點(diǎn)與26條邊組成，根據(jù)網(wǎng)絡(luò)拓?fù)淇傻酶鞴?jié)點(diǎn)指標(biāo)數(shù)據(jù)如下（表1）：

圖1 “APRA網(wǎng)絡(luò)”拓?fù)?/p>

表1 “ARPA網(wǎng)絡(luò)”各節(jié)點(diǎn)的相關(guān)指標(biāo)數(shù)據(jù)

2.2 實(shí)驗(yàn)結(jié)果及分析

根據(jù)上一節(jié)介紹的拉普拉斯特征映射算法，可以計(jì)算得出APRA網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)的得分情況。圖2是APRA網(wǎng)各節(jié)點(diǎn)相應(yīng)指標(biāo)折線對(duì)比 （為了更清晰地觀察結(jié)果，故將相應(yīng)指標(biāo)放在兩張圖里面）。

由圖2可以看出，本文介紹的拉普拉斯特征映射算法得到的最重要節(jié)點(diǎn)為v3，同時(shí)另幾種方法得到的結(jié)果也為v3（互信息中心性方法與點(diǎn)度中心性中v3和v2得分一樣，認(rèn)為它們?cè)诰W(wǎng)絡(luò)中的重要性是相同的），而除了v3之外，拉普拉斯算法認(rèn)為剩下節(jié)點(diǎn)中最重要的5個(gè)節(jié)點(diǎn)為14，2，19，12，6，而其他幾種方法得出的結(jié)果也為14，2，12，6，19，說(shuō)明拉普拉斯算法的結(jié)果和其他幾種方法的結(jié)果是一致的。下面再來(lái)看一下拉普拉斯算法與普遍公認(rèn)的PCA與LDA算法進(jìn)行對(duì)比分析。

圖2

表2 APRA網(wǎng)絡(luò)三種算法結(jié)果對(duì)照（前面數(shù)值為節(jié)點(diǎn)序號(hào)，括號(hào)內(nèi)為相對(duì)應(yīng)指標(biāo)得分）

由表2仍然可以看出，PCA （主成分分析法）和LDA（線性判別分析）以及拉普拉斯算法都認(rèn)為v3為APRA網(wǎng)絡(luò)中最重要的節(jié)點(diǎn)，其次為v14，v2。同時(shí)我們可以觀測(cè)v19、v12、v16這三個(gè)節(jié)點(diǎn)，這些節(jié)點(diǎn)的LDA得分與點(diǎn)度中心性評(píng)分相同，可以認(rèn)為這三個(gè)節(jié)點(diǎn)的重要性相同，而根據(jù)中介中心性評(píng)分指標(biāo)，認(rèn)為網(wǎng)絡(luò)中有更多的節(jié)點(diǎn)通過(guò)v12這個(gè)節(jié)點(diǎn)和其他節(jié)點(diǎn)進(jìn)行通信，另外互信息中心性則認(rèn)為網(wǎng)絡(luò)中有更多的節(jié)點(diǎn)和v6進(jìn)行通信，較少節(jié)點(diǎn)與v19通信；而特征向量中心性認(rèn)為v6在網(wǎng)絡(luò)中更受v5、v7、v8、v9這些節(jié)點(diǎn)歡迎，因?yàn)樗鼈兌夹枰ㄟ^(guò)v6與網(wǎng)絡(luò)中其他的節(jié)點(diǎn)進(jìn)行通信。本文提出的復(fù)雜網(wǎng)絡(luò)中重要節(jié)點(diǎn)的評(píng)估方法綜合考慮了以上所有指標(biāo)，經(jīng)過(guò)客觀分析，最終認(rèn)為v12節(jié)點(diǎn)優(yōu)于v6節(jié)點(diǎn)優(yōu)于v19節(jié)點(diǎn)。因此，本文算法結(jié)果與其他算法基本一致且更細(xì)致合理。由此可見(jiàn)，本文提出的拉普拉斯特征映射方法完全可以用來(lái)找出復(fù)雜網(wǎng)絡(luò)中位置重要的節(jié)點(diǎn)，并且具有很好的參考價(jià)值。

3 結(jié)語(yǔ)

節(jié)點(diǎn)在復(fù)雜網(wǎng)絡(luò)中的重要程度不應(yīng)該僅用單一指標(biāo)來(lái)衡量，而需要從多個(gè)角度和方面，充分利用節(jié)點(diǎn)的多個(gè)評(píng)估指標(biāo)來(lái)進(jìn)行綜合評(píng)估與分析。本文提出了基于拉普拉斯特征映射算法評(píng)估復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)重要性的方法，此方法綜合考慮了每個(gè)節(jié)點(diǎn)的局部特征，可以準(zhǔn)確地對(duì)節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要程度進(jìn)行評(píng)估，得到了良好的結(jié)果。由于只需對(duì)網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)的局部屬性進(jìn)行評(píng)估，大大縮減了計(jì)算時(shí)間，在保證精確性的同時(shí)，提高了效率。該方法在 “ARPA網(wǎng)絡(luò)”的仿真實(shí)驗(yàn)中，驗(yàn)證了它的可行性與有效性，為進(jìn)一步分析復(fù)雜網(wǎng)絡(luò)中重要節(jié)點(diǎn)的性質(zhì)，并有效地加以利用奠定了基礎(chǔ)。

[1]HE Nan，LI De-Yi，GAN Wen-Yan，ZHU Xi.Mining Vital Nodes in Complex Networks.Computer Science，2007，34（12）:15-16.

[2]張翼.復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要性評(píng)估及其應(yīng)用研究.計(jì)算機(jī)科學(xué)，2011，5:26-28

[3]許進(jìn).一種研究系統(tǒng)的新方法-核與核度法[J].系統(tǒng)工程與電子技術(shù)，1994（6）:1-10.

[4]P Onnela J，Saramaki J，Kertesz K，Kaski.Intensity and Coherence of Motifs in Weighted Complex Networks[J].Phys Rev.2005.9:34-36.

[5]李鵬翔，任玉晴，席酉民.網(wǎng)絡(luò)節(jié)點(diǎn)（集）重要性的一種度量指標(biāo).系統(tǒng)工程，2004，12:56-59.

[6]譚躍進(jìn)，鄧宏鐘.復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)重要度評(píng)估的節(jié)點(diǎn)收縮方法[J].系統(tǒng)工程理論與實(shí)踐，2006（11）:79-105.

[7]王延慶.基于接連失效的復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要性評(píng)估[J].網(wǎng)絡(luò)安全技術(shù)與應(yīng)用，2008（3）:59-61.

[8]于會(huì)，劉尊，李勇軍.基于多屬性決策的復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要性綜合評(píng)價(jià)方法[J].物理學(xué)報(bào)，2013（2）:54-62.

[9]Belkin M，Niyogi P.Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering.Advances in Neural Information Processing Systems，2002：1585-592.

[10]姜偉，楊炳儒.基于流形學(xué)習(xí)的維數(shù)約簡(jiǎn)算法[J].計(jì)算機(jī)工程，2010（12）:25-27.

[11]畢達(dá)天，邱長(zhǎng)波，張晗.數(shù)據(jù)降維技術(shù)研究現(xiàn)狀及其進(jìn)展.情報(bào)理論與實(shí)踐，2013，36（2）:125-126.

[12]晉建志.復(fù)雜網(wǎng)絡(luò)基于節(jié)點(diǎn)重要性的社團(tuán)探測(cè)及社團(tuán)演化模型研究.華中師范大學(xué)博士論文，2014.5.

Discovery for Important Nodes of Complex Networks

JIANG Sheng-wen
（College of Computer Science，Sichuan University，Chengdu 610065）

In complex networks,it is important how to evaluate the nodes according to their importance.Discovering the important nodes depends on the importance evaluation of nodes.Nowadays most of the existing methods of evaluating pivotal nodes(e.g.betweenness-based,degree distribution,clustering efficient)only think about one factor but not the integration of all complex network in evaluating the importance of nodes,so this methods each can do work in limited application scope.Proposes Laplacian Eigenmaps algorithm to discover the vital nodes in complex networks.In this algorithm,ranking key nodes will consider each node′s integration of whole complex network.After that,it can be accurate to evaluate important degree of the node in the network,and can get a good result.Due to the evaluation does not need calculate whole attribute of complex networks′nodes,so it can greatly reduce the computing time,and the efficiency to discover the key nodes can be improved.Finally,the experiment′s result of MATLAB simulation about the proposed algorithm shows that this algorithm is feasible and effective.

Complex Networks;Key Nodes;Laplacian Eigenmaps

1007-1423（2017）09-0007-05

10.3969/j.issn.1007-1423.2017.09.002

姜?jiǎng)傥模?990-），男，湖北黃岡人，碩士研究生，研究方向?yàn)榫W(wǎng)絡(luò)與信息安全

2017-02-23

2017-03-15