王 建，馮偉森，邱興超，劉 繼，盧 林

WANG Jian1，2,FENG Weisen1,QIU Xingchao1,LIU Ji1,LU Lin1

1.四川大學 計算機學院，成都 610041

2.四川大學 錦城學院 計算機科學與軟件工程系，成都 611731

◎網(wǎng)絡、通信、安全◎

基于BP模型的KAD網(wǎng)絡核心節(jié)點識別算法研究

王 建1，2，馮偉森1，邱興超1，劉 繼1，盧 林1

WANG Jian1，2,FENG Weisen1,QIU Xingchao1,LIU Ji1,LU Lin1

1.四川大學 計算機學院，成都 610041

2.四川大學 錦城學院 計算機科學與軟件工程系，成都 611731

針對在KAD網(wǎng)絡中核心節(jié)點的識別問題，提出了一種基于BP模型對節(jié)點重要程度進行實時判定的方法。結合KAD網(wǎng)絡測量的結果，對網(wǎng)絡中核心節(jié)點的屬性特征進行提取和歸一化處理，獲得了一組可分離度較高特征集合。采用MatLab設計相應的學習算法對BP網(wǎng)絡進行訓練，使結果收斂于預定誤差區(qū)間。將完成訓練的BP網(wǎng)絡模型應用于對測試節(jié)點的判定，實驗結果表明該方法可以實時地完成核心節(jié)點的判定，并且識別準確率可達到約70%。

反向傳播算法；KAD網(wǎng)絡；核心節(jié)點；識別

1 引言

網(wǎng)絡節(jié)點的排序問題是復雜網(wǎng)絡中的一個基本和重要問題，被廣泛應用于數(shù)據(jù)挖掘、網(wǎng)絡分析、網(wǎng)絡預測、網(wǎng)絡安全與控制等領域。隨著復雜網(wǎng)絡研究的深入發(fā)現(xiàn)，大量真實的網(wǎng)絡既不是規(guī)則的，也非完全隨機的。因此，有效地評估和度量網(wǎng)絡中節(jié)點的重要性，不但是網(wǎng)絡數(shù)據(jù)挖掘的首要問題，也是復雜網(wǎng)絡、社會關系網(wǎng)和互聯(lián)網(wǎng)搜索、系統(tǒng)科學的研究重點[1]。KAD是P2P技術歷經(jīng)10年發(fā)展后的新一代DHT網(wǎng)絡[2]，其去中心化、可測量、易擴展、高容錯性等優(yōu)點使它迅速滲透到文件共享、即時通訊、分布式存儲、云存儲等領域。這種無中心服務器的設計使得各個節(jié)點相對平等，既是服務的提供者，又是服務的請求者。KAD網(wǎng)絡的發(fā)展使其并發(fā)用戶已達到數(shù)百萬級，海量的用戶使得對于網(wǎng)絡的控制和監(jiān)管變得十分困難。大量網(wǎng)絡測量實驗表明，DHT網(wǎng)絡中節(jié)點負載非均衡性廣泛存在[3-5]。可以將那些在KAD網(wǎng)絡中為其他節(jié)點提供了更多路由服務或下載服務的節(jié)點稱為核心（重要或關鍵）節(jié)點。如果能利用這種非均衡性，發(fā)現(xiàn)和識別網(wǎng)絡中發(fā)揮了核心作用的節(jié)點，則是對KAD網(wǎng)絡的監(jiān)督將有著重要的作用。

2 相關工作

基于鏈接的節(jié)點排序是網(wǎng)絡分析中的一個核心任務，它通過圖中節(jié)點之間鏈接表現(xiàn)出的重要性不同對節(jié)點進行排序。目前國內外研究者對節(jié)點排序方法有四種典型的方式[6]：一是基于純粹網(wǎng)絡靜態(tài)參數(shù)指標來進行衡量節(jié)點的關鍵程度，常用評價指標有點中心度、凝聚中心度、子圖中心度、網(wǎng)絡流中心度等等?；趥鹘y(tǒng)的靜態(tài)社會分析方法有著明顯的缺點，它忽略引起網(wǎng)絡狀態(tài)變化的重要因素[7]，從而造成信息缺失問題。例如，不注重個體之間的連接關系、相關個體之間的相互影響以及隨時間變化趨勢[8]。二是借鑒圖分割方法中標準來進行衡量，即找出圖中的割點作為核心節(jié)點，因為刪除該節(jié)點后可以將圖割裂為多個子圖[9]。三是使用搜索引擎中節(jié)點排序的思想來進行核心節(jié)點發(fā)現(xiàn)排序，其主要的思想是基于隨機行走模型[10]。四是使用基于統(tǒng)計方法或數(shù)據(jù)挖掘的算法，如頻繁項集[11-12]、隱空間模型[13]、兩階聚類等經(jīng)典模型。數(shù)據(jù)挖掘算法中以使用頻繁項集的方法最為典型，但目前這些方法存在著節(jié)點判斷的滯后性這個明顯的缺點，即對于節(jié)點的重要程度的差別需要較大的時間和空間復雜度為代價才能得到，而無法實時地對一個未知節(jié)點進行判定。這在一些實時性要求較高的應用場景下將有著較大的限制。

3 核心節(jié)點評價算法

在KAD網(wǎng)絡中，核心節(jié)點是指那些對網(wǎng)絡的基本服務起著重要作用的節(jié)點，它們實際提供了更多其他節(jié)點的訪問、路由工作，其定義表示如下[14]：

定義2（關鍵字熱點）在任一區(qū)域Zx中，假設該區(qū)域中節(jié)點的索引Ia，若每個節(jié)點接受的訪問數(shù)量為Ca。給定一個關鍵字訪問次數(shù)閥值c，若Ca＞c則稱Ia為一個關鍵字熱點。當其共有n個索引時，該節(jié)點的訪問次數(shù)為其所有索引被訪問次數(shù)之和：

定義3（核心節(jié)點）在任一區(qū)域Zx中，若節(jié)點A是一個路由熱點，或節(jié)點A是一個關鍵字節(jié)點，若在給定的時間T內，A收到的訪問次數(shù)R大于給定的閥值c，則A為一個核心節(jié)點。

神經(jīng)網(wǎng)絡是一個多學科交叉領域，它通過模仿人的大腦思維來挖掘海量數(shù)據(jù)背面的潛在規(guī)律，已在各個領域中得到了廣泛應用，并取得了很多重要的成果。采用BP網(wǎng)絡對當前已獲取到的樣本節(jié)點進行學習，期望挖掘出有價值的規(guī)律，以便對未知節(jié)點進行更加實時準確的判定。圖1顯示了使用BP神經(jīng)網(wǎng)絡進行訓練和測試的整個流程，其中關鍵的環(huán)節(jié)在于樣本特征提取和處理及網(wǎng)絡訓練兩個步驟。

圖1 樣本數(shù)據(jù)訓練流程圖

圖1中特征提取是指根據(jù)訓練目標，從一組特征集合中選取一組最好的子集。為了處理方便，還需對特征數(shù)據(jù)進行歸一化預處理，使其值均在[0，1]區(qū)間內變化。下面對KAD中可用的特征屬性進行歸納和改進。

（1）R′c：返回節(jié)點的有效率

KAD每一次查詢中，若該點不為目標節(jié)點時，會為請求者返回α個路由表中更靠近的節(jié)點。從KAD路由選擇算法中可看出，當鄰居節(jié)點收到請求后，先從對應K桶中選出指定數(shù)量的節(jié)點，當該桶中節(jié)點數(shù)量小于指定數(shù)量時，則從鄰近的K桶中進行選取。那么，只要路由表中的節(jié)點總量不小于指定返回的節(jié)點數(shù)量，就一定會返回指定數(shù)量的節(jié)點。當各個鄰居節(jié)點若在線，每次提供的下一跳路由節(jié)點的數(shù)量均相等。因此，采用數(shù)量計算并不能使其具有較好地可分離性，這里使用返回節(jié)點的有效率來進行衡量，計算公式如下所示：

其中，Bn表示節(jié)點I返回的下一跳的路由節(jié)點總數(shù)，Ln則為當前仍在線的節(jié)點數(shù)量。對于Ln值的獲取，可以在鄰居節(jié)點返回信息后，使用Ping操作探測其中仍在線節(jié)點數(shù)量。該值反映了一個鄰居節(jié)點返回的路由信息中，仍然有效的節(jié)點占所有返回總量的比例。

人像蠶一樣拼命織關系的網(wǎng)，但織成之后，卻又千方百計逃之夭夭。范堅強給了一杭一個逃離的機會，可以放下一切，每日枕著書香入眠。一杭成為這間石屋實質上的主人以后，范堅強給他送來了書，讓他在漫長的白天與黑夜，不至于孤獨。但單純的生活結束了，石屋的門終于打開來。

（2）S′c：平均異或距離

在KAD中以跳數(shù)作為度量依據(jù)，并不能準確地表明節(jié)點之間的距離，這里采用平均異或距離進行度量。此值描述了對一個節(jié)點進行詢問后，返回結果能更接近目標節(jié)點的程度，反映了該點在一次查詢過程中所起到的作用。若節(jié)點I共返回n個路由節(jié)點，則節(jié)點I的平均距離值由下列公式計算得到：

式中，ri代表I的一個返回節(jié)點，s與d分別代表請求節(jié)點與目標節(jié)點。從上式容易看出，當返回的距離越大，則表明通過節(jié)點I的查詢后，與目標節(jié)點的位置將更接近。

（3）T′t：處理查詢返回時間

該值越大表明了被查詢節(jié)點處理性能更高。通常將發(fā)出消息和接收消息的時間間隔作為其往返時間。為了處理的方便，設定一個固定的TTL基數(shù)作為參照物，若小于此值則也近似地認為與此值相等，這里將TTL設定為2 000 ms。則該值由以下公式?jīng)Q定，其中Mt為返回時間中最大的一個值，也可設置一個固定的較大數(shù)值：

（4）R′i：節(jié)點返回查詢數(shù)量比

該值反映了一個目標節(jié)點返回的文件數(shù)量占所有返回結果數(shù)量中的比例。采用如下公式進行計算：

其中，Rc表明本次查詢所有節(jié)點返回的文件總和，但該值僅針對有返回結果的節(jié)點才可適用。由于不能保證測試的節(jié)點均為有存儲結果返回的節(jié)點，因此，需要對經(jīng)過多個節(jié)點路由轉發(fā)得到的R′i進處理，確定每個節(jié)點的R′i值的大小。這里的基本思想是按各點的S′c的大小來按比例分配，S′c反映了節(jié)點推薦的路由節(jié)點接近目標的程度。即節(jié)點I推薦節(jié)點的距離越大，使得請求節(jié)點能更接近目標，則I所分到的R′i值則越多。其值的計算公式如下：

（5）F′d：節(jié)點返回查詢質量比

該值反映了某點對查詢返回結果文件名與查詢詞的平均匹配程度，它的計算公式如下：

Fi代表了一個返回文件與查詢關鍵字的匹配程度；n代表某點所有返回的文件數(shù)量；c為不同節(jié)點返回的文件索引數(shù)量的總和。其值越大，表明本次查詢所返回的值更好地匹配了關鍵字查詢要求。

由于該值也僅適合于計算有返回結果的情況，因此，參照上一特征值處理過程，對其值使用以下公式進行轉化：

通過以上的處理過程，可以得到一個歸一化后的特征集合＜R′c，S′c，N′m，R′i，F(xiàn)′d＞。該集合中所有取值都已限定在[0，1]范圍中變化。

為了進行訓練，需要收集正反例樣本進行學習與測試。訓練樣本的采集工具使用了自設計的軟件KFetch[14]對網(wǎng)絡拓撲快照進行獲取，采用社會網(wǎng)絡中凝聚中心度指標和隨機行走算法對節(jié)點進行評價，將兩種算法共同評價為核心和非核心的節(jié)點選出。測試的時間開始于2012年2 月4日20：00，采樣時間持續(xù)40 min。這里選取了已有的核心節(jié)點作為正例樣本，選擇其中60%的節(jié)點作為訓練樣本，將余下的節(jié)點作為測試樣本，產(chǎn)生了所需的訓練樣本和測試樣本集。

4 實驗過程與結果分析

針對不同的目的，可以在上述特征集中選取適合的子集進行訓練。從KAD的消息類型可知，其主要有四種基本的RPC（Remote Process Command，RPC）。與查詢相關的包括節(jié)點查詢和關鍵字查詢操作。由于兩種消息用于不同的場景，因此其特征值子集也不相同。將兩種消息命令與上面的特征集合進行一個映射后，選取適合的特征屬性建立對應的特征子集。

將與Find_Node相關的特征集合標記為Cn，選取與其對應的特征有＜R′c，S′c，N′m＞。因為在以節(jié)點為目標的查詢中，其返回的結果只有兩種可能性，即能命中或不能目標。因此，對于返回結果的處理相對簡單，則記為C′n=＜R′c，S′c，N′m＞。選擇與Find_Value相關的特征集合標記為Vn，則與其對應的特征有＜R′c，S′c，N′m，R′i，F(xiàn)′d＞。該特征集合中含有查詢結果索引及索引結果質量，這樣可以更全面地考核用戶查詢后結果的命中情況，記為Vn= ＜R′c，S′c，N′m，R′i，F(xiàn)′d＞。

使用Find_Node采集節(jié)點的特征屬性。先將該區(qū)域劃分為?個部分，在各部分中隨機挑選一個節(jié)點ID作為待查詢目標ID。這樣做的目的是更有效地考察某點到各個距離位置的情況。?個測試服務器分別選定一個ID的鄰居來生成客戶端ID。開始測試時需保證一定的節(jié)點已將?個節(jié)點的加入自己的路由表中。實驗中參數(shù)?設定為8，先對通過前面選的核心節(jié)點進行特征采集，測試時間持續(xù)25 min，完成所有待訓練和測試節(jié)點的樣本所需特征值的獲取。

將得到的歸一化處理后的樣本數(shù)據(jù)組成為學習和訓練樣本，格式為：L=T=＜R′c，S′c，N′m，E＞。E為該節(jié)點的對應期望取值，即該節(jié)點為核心節(jié)點的概率。由于希望輸出結果為一個概率值，因此在進行重要程度排序的時候，不能將一個最重要的節(jié)點與一般重要節(jié)點進行等同，這樣將降低結果的精度。因此，需要將上述兩種算法得到的核心節(jié)點進行相應變換操作。其方法是取兩種方式所共同選中的核心節(jié)點，按重要程度排序后，對應指定結果的概率范圍為[0.6，1]。即將所有核心節(jié)點進行5等分，每一部分區(qū)域中的節(jié)點給定一個對應的概率期望值，對反例樣本的處理也是按此方法進行。將這樣組成后的訓練樣本送入網(wǎng)絡中進行學習，這里的實驗中對學習誤差設置為0.001。隱層神經(jīng)元個數(shù)取輸入層的1.4倍，即設置為5個，輸入層的傳遞函數(shù)設置S型正切函數(shù)tansig，輸出層的傳遞函數(shù)S型對數(shù)函數(shù)logsin，采用負梯度權值修正方法。為了降低編碼的難度，其學習和測試過程均使用了MatLab[15]工具箱中的神經(jīng)元組件進行實驗，程序清單如下所示，其中輸入數(shù)據(jù)整理為矢量形式，其值對應變量P，輸出的期望值也按矢量方式賦值于變量T。

上面代碼中minmax（P）是指以輸入數(shù)據(jù)中的最大和最小值為訓練數(shù)據(jù)的變化范圍，net_1為訓練后得到的輸出網(wǎng)絡。

通過多步的網(wǎng)絡訓練可得到了滿足誤差要求的樣本數(shù)據(jù)擬合情況，實驗結果如圖2所示。

圖2 Find_Node特征學習擬合效果圖

由圖2可以看出，當學習的次數(shù)到達889時，則誤差已經(jīng)控制在指定的范圍了。將該訓練完成的網(wǎng)絡輸出結果概率與期望值進行對比，將誤差范圍在0.2之內的均認為成功。那么，其中正例樣本識別達到78.3%，反例樣本的識別率達到了67.1%。將訓練好的網(wǎng)絡模型在實際的KAD中進行了驗證，采用KFetch工具對節(jié)點關系進行獲取后，抽取出在線節(jié)點的對應屬性集送入模型中進行判定。每次實驗時間持續(xù)30 min，實驗共重復5次，對實驗結果進行統(tǒng)計和分析。同時，將識別結果與使用凝聚中心度與隨機行走算法所篩選出的核心節(jié)點進行對比，結果顯示采用BP模型的核心節(jié)點識別率平均為63.8%。雖然實際網(wǎng)絡中識別率略低于訓練結果，但仍可證明該方法具有一定的可行性和實用性。

5 小結

本文通過利用測量實驗收集KAD節(jié)點的屬性特征，并根據(jù)查詢命令選取了對應的特征子集進行實驗。從實驗結果可以看出，由于網(wǎng)絡中節(jié)點的動態(tài)性命使得識別效率仍有待提高，但這種實時的判定方法可有效地解決判定的滯后性，具有更廣闊的應用前景。為了改進識別的準確性，今后，將重點對節(jié)點的屬性進行更為深入的研究。從上可知，BP網(wǎng)絡性能的高低主要取決于兩個因素：抽取的節(jié)點屬性特征數(shù)量和選擇的屬性特征質量。尋找有效的節(jié)點屬性特征需要更深入地對KAD網(wǎng)絡中節(jié)點進行分析，抽取出節(jié)點有效屬性特征來豐富屬性集合。其次，嘗試采用其他模式識別的方法，如模擬退火算法、Tabu搜索算法和遺傳算法等[16]，可以對現(xiàn)有的特征屬性進行適當?shù)刈冃?、計算和提取，以得到更佳的具有可分屬特征值，從而有效地提升核心?jié)點識別的準確率。

[1]何建軍，李仁發(fā).改進的隨機游走模型節(jié)點排序方法[J].計算機工程與應用，2011，47（12）：87-89.

[2]Maymounkov P，Mazieres D.Kademlia：a peer-to-peer informaticssystem based on theXOR metric[C]//Proceedings of the 1th International Workshop on P2P Systems，2002：53-65.

[3]蔣君，鄧倩妮.eMule系統(tǒng)中的非均勻性分布[J].微電子學與計算機，2007，24（10）：153-156.

[4]熊偉，謝冬青，焦炳旺，等.一種結構化P2P的自適應負載均衡方法[J].軟件學報，2009，20（3）：661-663.

[5]李振宇，謝高崗.基于DHT的P2P負載均衡算法[J].計算機研究與發(fā)展，2006，43（9）：1579-1580.

[6]周春光，曲鵬程，王曦，等.DSNE：一個新的動態(tài)社會網(wǎng)絡分析算法[J].吉林大學學報：工學版，2008，38（2）：408-411.

[7]Cai Hua，Zhou Chunguang，Wang Zhe，et al.Algorithm research on community mining from dynamic social network[J].Journal of Jinlin University，2008，26（4）：380-382.

[8]Berger-Wolf T Y，Saia J.A framework for analysis of dynamic social networks[C]//Proceeding of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2006，12：523-528.

[9]赫南，李德毅，淦文燕，等.復雜網(wǎng)絡中重要性節(jié)點發(fā)掘綜述[J].計算機科學，2007，34（12）：1-4.

[10]郭軍，李明輝，董社勤，等.隨機行走的電路分析應用及并行化改進[J].計算機工程與應用，2010，46（18）：199-201.

[11]鄧忠軍，宋威，鄭雪峰，等.P2P網(wǎng)絡中最大頻繁項集挖掘算法研究[J].計算機應用研究，2010，27（9）：3490-3492.

[12]宋文軍，劉紅星，王崇駿，等.以圖頻繁集為基礎的核心節(jié)點發(fā)現(xiàn)[J].計算機科學與探索，2010，4（1）：82-85.

[13]Sarkar P.Dynamic social network analysis using latent space models[C]//ProceedingsoftheACM SIGKDD Explorations Newsletter，2005：31-35.

[14]王建.基于KAD網(wǎng)絡監(jiān)督的關鍵技術研究與實現(xiàn)[D].成都：四川大學，2012.

[15]飛思科技產(chǎn)品研發(fā)中心.神經(jīng)網(wǎng)絡理論與MATLAB7實現(xiàn)[M]// MATLAB應用技術.北京：電子工業(yè)出版社，2005：4-90.

[16]邊肇祺，張學工.模式識別[M].北京：清華大學出版社，2006：176-208.

1.College of Computer,Sichuan University,Chengdu 610041,China

2.Department of Computer Science and Software Engineering,Jincheng College of Sichuan University,Chengdu 611731,China

In view of the core node recognition in the KAD（Kademlia）,a model based on BP is presented to determine whether a node is core node in real time.According to the result of the measurement for KAD,some attribute characteristics extraction and normalization processing is implemented to obtain an attribute set with higher separable degree.An algorithm in MatLab is designed to train the BP network until the results limit in a predetermined error range.In addition,the trained BP model is adapt to test prepared data,the results of the experiment show that the method can judge a node degrees of importance,and the recognition accuracy rate is up to about 70%.

Back-Prorogation（BP）;KAD network;core node;recognition

A

TP393

10.3778/j.issn.1002-8331.1210-0276

WANG Jian,FENG Weisen,QIU Xingchao,et al.Study of recognition algorithm for core node in kad network based on BP model.Computer Engineering and Applications,2013,49（7）：72-75.

王建（1979—），男，博士，講師，研究領域為網(wǎng)絡安全與應用；馮偉森（1962—），男，副教授，研究方向為網(wǎng)絡信息系統(tǒng)。E-mail：wj_98@163.com

2012-10-26

2012-12-28

1002-8331（2013）07-0072-04