基于網絡節點聚類的目標IP城市級定位方法

李明月 羅向陽 柴理想 袁福祥 甘 勇

1(中國人民解放軍戰略支援部隊信息工程大學 鄭州 450001)2(數學工程與先進計算國家重點實驗室(中國人民解放軍戰略支援部隊信息工程大學) 鄭州 450001)3(鄭州輕工業大學計算機與通信工程學院 鄭州 450001) (lmypretty@163.com)

IP定位的目的是確定目標IP在某個粒度上的地理位置.定位結果往往包括目標IP對應的用戶或設備所在的國家名、地區名、經緯度和時區等[1].IP定位技術能為用戶提供IP地址的地理位置，作為提供位置服務的基礎，具有相當廣泛的應用前景和市場需求[2]，例如商業公司可以利用IP定位推廣定向商業廣告[3-6]；移動APP可以為用戶提供基于位置的服務(location based service, LBS)，谷歌、高德地圖導航、大眾點評等[7-9]利用IP定位可向指定區域的用戶推送用戶所在地的天氣預報、新聞和定向廣告等；IP定位也可為區域版權保護提供支持，例如為電視節目與數字音像等提供區域限制(只在法律允許的網絡區域內復制、傳播和下載)；IP定位還可為網絡治理與國家反恐維穩提供技術支持，如實施區域性網絡管控、識別垃圾郵件、發現與改善網絡節點性能、判定網絡欺詐及追蹤網絡攻擊源頭、定位網絡敏感目標等.因此，開展IP定位技術研究具有重要意義.

現有IP定位方法主要分為2類：基于數據庫查詢的定位方法和基于網絡測量的定位方法.

基于數據庫查詢的IP定位方法是目前常用的定位方法，主要通過查詢數據庫來獲取目標IP地理位置信息，這種方法的特點是簡單快捷.主流的IP數據庫有IP138[10],QQWry[11],IPcn[12],IP2Location[13],MaxMind[14],Whois[15]等.其中，IP2location聲稱其在半徑50 km范圍內的定位準確率平均為77%[16].現有文獻對上述部分數據庫研究后發現，對于實際的互聯網目標，單個數據庫聲明的定位準確度并不可靠，不同數據庫中的IP城市級位置信息存在較大偏差，最大可達800 km[17].因此，現有方法往往將2個以上數據庫查詢一致的結果視為目標IP的地理位置.基于網絡測量的IP定位方法是當前研究的主要方向，其主要思想是通過測量網絡時延或拓撲信息來估計目標IP的地理位置，因此主要包括基于網絡時延測量和基于網絡拓撲信息等方法.基于網絡時延測量的IP定位經典方法有CBG(constraint-based geolocation)[18]，SLG(street-level geolocation)[19]，Octant[20]，其中Gueye等人[18]提出的CBG方法是用3個以上的探測源同時探測一個目標，依據探測源位置及探測時延信息確定可能的地理區域，該方法能夠定位目標IP所在的大致區域或城市.這類城市級定位方法是進行更高精度定位方法的前提.Octant是在CBG基礎上進行的改進，但是需要大量的地標作為輔助.Wang等人[19]提出的SLG方法的主要思想是基于相對時延越短對應的距離越近的規律，找到與探測源到目標IP的相對時延最近的地標，將該地標的位置作為目標IP的地理位置估計.上述方法盡管具有一定的定位能力，但都容易受探測源部署和測量時延誤差的影響.

Tian等人[21]首次將基于數據庫查詢和網絡測量的2類IP定位方法結合，針對查詢IP數據庫返回錯誤或空信息的問題，創造性地提出了一種基于網絡拓撲啟發式聚類的IP定位方法(HC-Based).該方法對現有IP位置數據庫，利用Traceroute探測得到多條拓撲路徑并構建網絡拓撲圖，分析網絡拓撲中骨干網、非骨干網以及它們之間的通連關系，采用啟發式聚類方法對IP節點進行聚類，得到不同的集群，根據同一集群內部的IP節點地理位置往往相同的特點，確定目標IP所屬集群，最終根據集群的地理位置確定目標IP的地理位置.然而，該方法得到的集群往往節點數太少，且采用的簡單投票規則可能會因為用于投票的相鄰節點在IP位置數據庫中查詢的地理位置存在錯誤，導致基于投票結果的定位出現錯誤.

針對HC-Based定位方法存在的上述不足，本文提出一種基于網絡節點聚類的IP定位方法(network node clustering based IP geolocation，NNC).將網絡拓撲視為一種典型的復雜網絡結構，將HC-Based定位方法中的集群與復雜網絡理論中的社區對應起來，采用模塊度衡量社區結構的強度，利用Louvain社區發現算法對網絡拓撲中的節點進行聚類，將網絡拓撲劃分為不同的社區，最終利用投票確定社區及目標IP的地理位置.與經典的基于網絡測量的IP定位方法相比，本文提出的NNC定位方法不再簡單地依賴單個時延或相對時延和網絡路徑，而是利用網絡拓撲的結構特性，將目標IP定位與網絡拓撲中的網絡社區有機結合起來，基于對網絡社區的分析實現對目標IP的定位，從而克服了傳統基于網絡測量的定位方法對探測路徑的依賴.而且，與HC-Based定位方法相比，NNC方法避免使用人工劃分得到的小集群和簡單投票規則，采用社區投票方法，可有效容忍地標數據的地理位置錯誤對定位結果精度的影響，從而顯著提高了定位準確性.

1 HC-Based定位方法原理簡介及分析

針對基于數據庫查詢結果不可靠的不足，Tian等人[21]提出了一種基于啟發式聚類的定位方法(HC-Based定位方法)，將網絡測量與數據庫查詢相結合，在網絡拓撲基礎上，對網絡節點進行啟發式聚類，獲得多個社區，對社區利用數據庫查詢方法進行定位，為網絡IP定位提供了一種新的途徑.HC-Based定位方法主要包括5個步驟：預處理、單集群識別、非骨干網節點聚類、骨干網節點聚類和集群合并.其中，預處理過程需要去除一些探測路徑中的匿名路由器，為排除探測源對路徑的干擾去掉探測源到骨干網之間的路徑，并利用IP地址數據庫標識骨干網節點與非骨干網節點；單集群識別從網絡拓撲的邊緣節點開始，依據特定規則找出符合構成單集群條件的節點或節點對；非骨干網聚類從單集群出發，利用鄰居投票規則逐步對其他節點進行合并，到骨干網節點停止；骨干網聚類在骨干網節點中進行，方法與非骨干網聚類一致；集群合并對網絡拓撲中的所有集群進行統一處理，設定最小集群節點個數閾值，將較小的集群向周圍的大集群合并.最終，得到網絡拓撲中的所有集群劃分的結果.方法的主要流程如圖1所示，圖1①到②找出單集群，其中，紅色節點是單集群；圖1②到③是非骨干網聚類過程；圖1③到④是骨干網聚類過程；圖1④到⑤是聚類后各個集群進行合并.依照上述步驟最終聚類成多個集群.

Fig. 1 Steps and processes of the HC-Based圖1 HC-Based定位方法的步驟與流程

相比單一的數據庫查詢或基于網絡測量的IP定位方法，HC-Based定位方法將兩者結合，通過網絡拓撲聚類得到集群，將IP定位問題轉換為對IP節點聚類到特定集群的問題，并采用投票方法確定目標IP的地理位置.該方法既解決了IP地址數據庫中有部分錯誤數據的問題，又在一定程度上解決了此前網絡測量方法中對探測源和地標的過度依賴問題.

但是，該方法也存在2點不足：

1) 依賴簡單投票規則時容易導致錯誤

HC-Based定位方法在尋找單集群的過程中將網絡拓撲中到其他節點沒有連接的節點作為一個單集群或者將任意2個節點之間形成回路并且到其他節點沒有連接的2個節點分別作為單集群.盡管利用這2個簡單的規則，能夠較好地解決網絡拓撲邊緣單集群發現的問題，但是在非骨干網聚類與骨干網聚類的過程中，由于處理的節點之間結構較為復雜，簡單的投票規則不能覆蓋所有情況，如果集群中一些節點通過查詢IP位置數據庫得到的位置有誤，可能導致基于投票得到的其他節點的位置出現錯誤.如圖2中①到②所示，若節點2,3,4屬于同一個集群，利用節點2,3,4的地理位置投票決定節點1所處地理位置.若節點2,3,4能夠在IP地址數據庫查詢到城市級信息，則利用該信息投票確定節點1所屬地理位置；否則，使用集群信息對節點1進行投票.若節點2,3,4,5中超過一半的節點認為節點1屬于A集群，即投票比例超過0.5，則認為節點1屬于A集群.若節點2,3,4位置信息正確將得到正確的集群化分，反之可能出現投票結果錯誤，如圖2中③到④所示，若節點2,3,4信息錯誤，投票所得的節點1位置很可能出錯.

Fig. 2 Voting error problem of the HC-Based圖2 HC-Based定位方法投票出錯問題

2) 集群合并的閾值設定缺乏依據

HC-Based定位方法在非骨干網聚類和集群合并過程中，簡單地將節點數小于閾值的集群合并到與其相連的大集群中，默認的閾值為5，但遺憾的是文獻[21]并沒有說明閾值設定為5的依據.

從實際情況看，一些集群節點數量大于5的集群也符合合并的條件，但受閾值設定的影響，最終導致網絡拓撲中存在大量小集群，而小集群中任意一個節點的位置發生變化或出現錯誤將會對該集群所處位置產生較大影響，因此大量小集群的產生會影響定位的最終結果.

如圖3所示，紅色節點和淺藍色節點表示不同的2個地理位置，節點6是與骨干網相連的第1個路由器，作為標識路由器[22](該路由器代表一個城市的網絡入口)，因此與節點6相連的節點理論上處于同一集群，假設基于節點2,3,4對節點1投票，則通過投票得到的節點1的位置將會與節點2,3,4一致，由于節點2,3,4的位置與節點6不同，所以通過投票得到的節點1的位置會與節點6不一致，從而出現錯誤，這種錯誤在集群合并階段不能有效解決，因為若節點1與其周圍若干個節點構成的集群大小為5或者大于5，啟發示聚類方法并不會將該集群與其他集群進行合并，從而使得節點1與節點6處于不同集群.

Fig. 3 Cluster consolidation problem of the HC-Based圖3 HC-Based定位方法集群合并問題

3) 需要多次循環遍歷網絡拓撲

HC-Based定位方法從尋找單集群開始，每一步都需要多次循環遍歷整個目標網絡拓撲.原因在于該方法依賴人工設定參數和規則，而基于規則的方法需要逐個節點判斷執行，難以進行高效的優化處理，從而導致HC-Based定位方法整體效率較低.

2 網絡拓撲中社區與城域網的關系分析

錢學森先生指出：具有自組織、自相似、吸引子、小世界、無標度中部分或全部性質的網絡稱為復雜網絡[23].現實世界的網絡大部分都不是隨機網絡，少數的節點往往擁有大量的連接，而大部分節點卻擁有很少連接，節點的度數分布符合冪律分布，而這種特點被稱為網絡的無標度特性(scale-free)，研究者將度分布符合冪律分布的復雜網絡稱為無標度網絡.對于分層結構的網絡拓撲，骨干網結點的度非常高，非骨干網節點的度較低.骨干網節點主要分布在若干個大城市，數量較少，其他非骨干網節點數量多，符合復雜網絡中的無標度特性.骨干網與城市、城市與城市之間的網絡拓撲呈現高度的集群化特征[23].網絡拓撲的集群化特征可理解為網絡拓撲具有社區特性.

2.1 城域網結構與地理位置特性

考慮到網絡拓撲結構具有的社區特性，本文提出一種假設：社區與所處城市可能存在相關性，并且屬于同一社區的節點往往位于同一個城市.若這個假設成立，則可基于該假設進行基于社區位置的目標IP定位.

事實上，在實際網絡環境中，多級分層架構的網絡運營商網絡通常包括省(或州)際和省內骨干網絡，省內又包含許多城域網等，這種結構將運營商網絡劃分成等級不同的區域網絡如省網、城域網等.骨干網與非骨干網(包括省網和城域網)之間的關系如圖4所示：

Fig. 4 The relation between backbone network and non-backbone network圖4 骨干網與非骨干網之間的關系

城域網是承載城市與骨干網連接的網絡，其作用是為降低同一個城市內部節點之間的網絡時延.由于城域網的存在，實際網絡的拓撲結構除滿足復雜網絡中的無標度特性外，還存在著顯著的社區結構特性，處于同一社區內部的網絡實體之間的連接較為緊密.反過來看，我們可通過分析網絡拓撲中的社區結構特性，對目標IP進行定位.定位的基本思路是：對目標IP進行多次探測，將探測得到的拓撲路徑集合進行網絡社區結構劃分，依據社區位置投票的結果實現對目標IP的定位.

2.2 社區與城域網關系分析

本文利用1臺主機作為探測源，隨機抽取了河南省7個城市內部的3 000個IP作為探測目標，并基于探測得到的網絡拓撲圖分析社區結構的存在性.圖5是河南省內部部分網絡節點和部分骨干網節點構成的網絡拓撲圖.在該網絡拓撲中，可通過統計同一城市內部和不同城市之間節點的連接數，更細粒度地分析城域網條件下網絡拓撲結構的社區特性.

Fig. 5 Internal network node and some backbone network nodes in Henan province圖5 河南省內部網絡節點與部分骨干網絡節點拓撲圖

表1列出了本文隨機抽取的河南省7個城市的IP分布情況和該網絡拓撲中城市內部與城市之間的連接數.由表1統計結果可以看出，社區結構滿足如下特征：屬于同一社區的節點之間連接數較多，而屬于不同社區的節點之間連接數較少.

從表1中還可以看出，在河南省網絡拓撲中，城市內部的連接數占總連接數的比重較高.例如鄭州市內部IP節點之間連接數為818，占其總連接數的86%.需要說明的是，表1中去除了骨干網節點與這些城市的連接，原因是骨干網節點的具體位置信息往往不夠明確，并且骨干網節點在復雜網絡中屬于數量較少而度又較高的節點，容易對統計城市之間的連接數量造成較大干擾；與非骨干網節點的通連關系，會對社區劃分造成影響，從而影響目標IP定位的準確性.

表1結果表明：在互聯網分層架構以及城域網的綜合影響下，城市內節點的網絡連接數要遠高于城市之間節點的連接數，城市與城市之間的社區結構較為明顯，從一定程度上證明了網絡拓撲中社區結構的存在性.為此，我們可以推斷：同一社區內的IP地址位于同一城市的可能性較高.需要指出的是，在同一城市內部的網絡拓撲也有可能存在更小的社區結構，這些IP可能分布于政府部門、企業或某個網絡中.只是由于本文所抽取的IP數量限制，尚不足以形成更細粒度的小社區結構.

上述探測分析結果表明：城域網與網絡拓撲中的社區分布的確有著較強的關聯，屬于同一社區的節點往往位于同一個城市，這驗證了我們2.1節提出的假設.

Table 1 The Number of IP Connections Inside the Cities and Between Cities in Henan Province表1 河南省城市內部與城市之間IP連接數統計

Note: The results highlighted in bold denote that IP addresses in the same network community are more likely to be located in the same city.

Fig. 6 Steps of the NNC 圖6 步驟流程示意圖

網絡拓撲本身就是一種典型的復雜網絡，而網絡拓撲中任意2個節點之間的網絡路徑也能通過有限的幾跳互相連接，符合復雜網絡的小世界特性[24]，因此，可利用復雜網絡理論中的社區發現算法，將全局網絡拓撲中具有社區特性的集群按照緊密程度進行聚類，而模塊度能夠很好地反映一個社區的聚合程度，因此，可基于模塊度最優化進行網絡社區發現，并在此基礎上通過分析社區結構特性對網絡拓撲進行研究.

3 NNC定位方法原理及主要步驟

為了改進HC-Based定位方法存在的不足，本文通過分析社區結構特性與網絡拓撲的關系，提出一種基于網絡節點聚類的IP城市級定位方法(NNC定位方法)，其主要思想是利用社區發現算法對網絡拓撲社區進行聚類，結合投票機制定位社區所在地理位置，根據所處社區確定目標IP地理位置.定位方法原理框架如圖6所示，主要包括預處理、社區發現和社區投票3個階段，其中預處理階段包括選定探測源、目標路徑、構建網絡拓撲圖和分離骨干網與非骨干網等；社區發現是核心模塊，包含最大化局部模塊度和合并超點2個迭代循環的過程；社區投票根據社區發現的結果對目標IP進行投票估計其位置，完成定位.

NNC定位方法的主要步驟如下：

步驟1. 根據探測目標位置分布與特性，從探測源到目標的所有路徑中，盡量選擇與目標IP路徑較長的探測源，充分遍歷經過的骨干網與非骨干網信息，得到較為完整的路徑信息.

步驟2. 構建網絡拓撲.在步驟1獲取的完整路徑信息中，去除探測源到骨干網之前的路徑.不考慮節點權重，將網絡拓撲圖中所有邊的權值賦為1.

步驟3. 分離骨干網與非骨干網.利用IP數據庫查詢網絡拓撲圖中所有IP節點的(Internet server provider, ISP)信息，依據ISP信息將網絡拓撲初步劃分為骨干網與非骨干網，并將兩者分離.

步驟4. 社區發現.該步驟包括2個階段，最大化模塊度和合并超點，這是一個迭代循環的過程.首先，最大化局部模塊度.在分離得到的非骨干網上，將所有節點視為獨立社區并計算模塊度，在此基礎上嘗試將每個節點向周圍社區遷移，使模塊度盡可能增大，直至模塊度達到局部最優.其次，合并超點.在模塊度達到局部最優的網絡拓撲上合并超點.最后，判斷當前模塊度是否為全局最優，若是則進入社區投票階段，否則返回循環步驟4.

步驟5. 基于投票機制的社區位置定位.根據步驟4得到的社區劃分的結果，每個社區內部的節點通過IP地理位置數據庫對其城市級地理位置進行查詢，根據自身位置對該社區所處位置進行投票，將社區內多數節點一致的位置作為社區的地理位置，通過此次投票更正社區內節點錯誤的位置信息.

步驟6. 確定目標IP位置.將從探測源到待定位的目標IP的探測路徑加入步驟2中構建的網絡拓撲中，判斷其所屬社區并將對應社區的地理位置作為待定IP的地理位置.

在上述步驟中，社區發現和確定目標IP位置是關鍵，下面分別進行具體闡述.

3.1 網絡社區發現

本文在對網絡進行社區發現時采用了Blondel等人[25]于2008年提出的Louvain社區發現算法，該算法是一種貪心的基于模塊度優化的非重疊社區發現算法.

模塊度也稱模塊化度量值，是目前常用的一種衡量網絡社區結構強度的方法，模塊度的定義為

(1)

Louvain社區發現算法由最大化模塊度和合并超點2個階段組成，是一個迭代循環的過程.

1) 最大化模塊度.在分離得到的非骨干網上，將所有節點視為獨立社區并計算模塊度.對任意節點，掃描其所有鄰接節點，在此基礎上嘗試將每個節點向周圍社區遷移，使模塊度盡可能增大，若模塊度達到局部最優，則將其加入鄰接社區.

2) 合并超點.在模塊度達到局部最優的網絡拓撲上合并超點.合并超點的基本思路是將原網絡拓撲中的社區各自合并為1個節點，進一步尋找深層社區結構特性.具體來說有3條規則：①合并得到的節點的權值不變；②合并后的節點增加1條自連邊，邊的權值為原社區中所有節點權值之和的2倍；③合并后節點之間邊的權值為原2社區之間邊權值總和.

3) 判斷當前模塊度是否為全局最優，若是則進入社區投票階段，否則返回循環1)和2)這2個階段.

Louvain社區發現算法中單輪執行過程如圖7所示.階段1以最大化局部模塊度為目標，合并社區直到模塊度不再增加為止；階段2將前一階段所得的每個社區視作1個新的節點，合并成新的社區.

Fig. 7 The single round of the implementation process of the Louvain algorithm圖7 Louvain社區發現算法的單輪執行過程

我們采用Louvain算法來進行網絡社區發現，有兩大好處：1)效率高.表現在通過模塊度計算公式能夠快速計算模塊度的增加值，且在每一輪合并超點時能夠大大減小網絡的節點數，這使得算法的大部分時間開銷集中在第1輪迭代中，而算法的時間復雜度為O(|E|)，其中|E|為網絡拓撲中的節點個數；2)算法整個執行過程中，社區結構的粒度逐漸增大，可以得到不同層次的社區結構，因而能夠發現不同層次的社區.Louvain社區發現算法的不足是：階段1的輸入結果可能跟節點處理的順序有關，文獻[26]指出節點處理的順序對最終結果模塊度的數值影響不大，但會影響到計算的時間開銷.

3.2 基于社區位置定位目標IP

社區投票定位建立在社區發現的基礎之上，是整個方法的最后一個步驟，用于最終確定目標IP的城市級地理位置.具體來說，利用社區投票對目標IP進行定位包含2種情況:1)目標IP已包含在當前網絡拓撲中;2)目標IP不包含在當前網絡拓撲中.下面分別對這2種情況進行討論：

1) 目標IP已包含在當前網絡拓撲中

目標IP已包含在當前網絡拓撲中，那么在社區發現階段應該確定了所屬社區.利用該社區中所有節點對社區所屬位置進行投票，若某城市所得票數的比例超過一半，則認為該社區中所有節點均處于該城市.若無一個城市所得票數超過一半，說明當前網絡拓撲中的節點數量過少，不足以形成有城域網特征的社區結構，應當適當增加地標數量和探測次數，直到整個網絡拓撲中所有社區均能確定地理位置信息.

得到所有社區的地理位置后，再對目標IP的定位時只需要確定其所屬社區，即可完成城市級定位.

2) 目標IP不包含在當前網絡拓撲中

目標IP不包含在當前網絡拓撲中，為了利用社區信息對該目標進行定位，需要與當前網絡拓撲建立關聯，可通過增加探測次數，必要時可增加探測源數量，盡可能獲得更完整的拓撲路徑，保證與當前網絡拓撲有重合路徑.在該前提下，可不用重新對整個網絡拓撲進行社區發現，而采用社區增量的方式確定目標IP及其探測路徑上IP所屬社區.具體來說，類似Louvain社區發現算法中第1階段優化模塊度的過程，嘗試將目標IP及其探測路徑上的IP向與之連通的社區遷移并計算模塊度增量，然后將目標IP及其探測路徑上的IP并入使模塊度增量最大的社區.此時目標IP已經增加至當前網絡拓撲中，可采用與第1種情況相同的方法確定目標IP的城市級地理位置.

4 NNC定位方法的性能分析

本節將主要對本文提出的基于NNC的城市級IP方法的性能進行分析.

4.1 方法可行性分析

本文方法利用社區發現算法對網絡節點進行聚類，將多個網絡節點根據計算其模塊度，將模塊度最優情況下的社區劃分結果作為最終的網絡節點聚類結果，相比經典的HC-Based算法，該算法利用模塊度衡量社區劃分的好壞，而不是設定經驗值，因此能夠得到更為有效的節點聚類結果，從而有效減少了由于社區劃分錯誤導致目標節點的地理位置定位錯誤.

經典的Louvain算法是一種社區劃分算法，該算法根據社區結構特性，利用模塊度得到社區的最優劃分，本文查詢多個IP節點的ISP信息，并利用Louvain算法將這些IP節點劃分為多個社區，能夠得到最優的社區劃分結果，社區的位置可通過社區內多個IP節點的位置確定，當目標IP需要定位時，只需要確定其屬于哪個社區即可確定其城市級地理位置.由于該方法利用經典的社區算法能夠得到最優的社區劃分，從而得到合理的社區地理位置，而目標IP是根據社區位置確定其所在城市級位置，因此，該方法結合社區劃分算法將網絡節點聚類，從而確定目標IP地理位置從原理上是可行的.

4.2 分離骨干網與非骨干網對定位結果的影響

基于社區發現的網絡拓撲聚類算法中，將骨干網與非骨干網分離是重要的一步，尤其在連通性較弱的分層網絡環境中.通過分離骨干網和非骨干網絡，能夠使網絡拓撲的社區結構特性更加明顯，提高目標IP的定位精度.以河南省內的網絡拓撲為例，如圖8所示.

圖8是分離骨干網與非骨干網之后的網絡拓撲結構，圖8(a)為骨干網節點，社區結構的非常明顯，對目標IP的社區定位更加精準和高效，甚至可用肉眼區分不同的社區.

Fig. 8 Separation of backbone and non-backbone network圖8 骨干網與非骨干網分離示意圖

從復雜網絡理論的角度來看，骨干網節點屬于少量但卻擁有大量連接的節點.對社區發現算法而言，這樣的節點往往與多個社區有著很強的關聯，容易引入較多初始噪聲.因此，本文通過分離骨干網與非骨干網，不僅可以強化骨干網與非骨干網中的社區結構強度，還可以提高社區發現的效率.

4.3 與HC-Based定位方法的原理對比

相比HC-Based定位方法，本文提出NNC定位方法，主要有4點優勢：

1) 不依賴固定的規則、通用性較好

HC-Based定位方法提出的規則大多基于作者對網絡拓撲結構的直觀認識，本質上是一種規則化的方法，缺乏很好的理論支持.在實際應用中，能解決一些問題，而在另一些規則中未定義的或例外場景的條件下，往往不能發揮作用.若要適應這些例外場景，必須人工額外定義新規則，添加進規則庫才能保證算法正確運行.而本文提出的NNC定位方法，通過引入社區模塊度的概念并以此作為評價社區結構強度的標準，不依賴固定的規則，實質是將復雜網絡理論作為理論基礎，有著較好的通用性.

2) 有明確的社區結構強度衡量標準、不需要設置閾值

HC-Based定位方法中將若干有一定通連關系的節點構成的集合稱為集群(cluster)，與社區發現中的社區有一定相似性，但由于采用的是規則化的劃分方法，因此缺少一個科學的衡量社區結構強度的標準.例如HC-Based定位方法中集群最小節點個數設定為5，但并未給出一個合理的解釋，而基于社區發現的網絡拓撲聚類定位算法使用模塊度衡量社區結構強度.模塊度的定義是在概率論基礎上通過隨機圖中節點的度以及它們之間的連接關系推導而來，既符合人們的直觀理解，又有嚴密的數學推導.因此，使用模塊度衡量社區結構強度更加科學合理.

3) NNC定位方法對地標準確性要求低、具有很好的容錯性

在傳統的IP定位方法中，對目標IP進行測量往往離不開準確的地標信息作為輔助.因此，地標挖掘在IP定位中是非常重要的一個步驟，地標的可靠性直接決定著IP定位的準確度.從現有研究來看，最可靠的地標挖掘方式是實地勘察，但是其成本和代價較為高昂，而通過其他方式(如基于網絡數據挖掘獲取地標)又難以保證獲取到的地標具有高可靠性.本文提出的NNC定位方法不依賴于準確的地標數據，而是利用位置查詢結果可靠性較為一般的IP地址數據庫，在社區劃分的基礎之上利用社區投票估計目標IP的地理位置.這樣做的依據是：IP地理位置數據庫中的大多數IP，其城市級地理位置信息是準確的，只要大部分IP的城市級位置信息是準確的，即可保證最后的社區投票結果是可信的.而現有研究[16]指出IP地理位置數據庫其城市級信息準確率大約為77%，因此該算法的大部分投票結果是可信的.

4) NNC方法采用了層次化的社區發現算法、遍歷次數大大降低、時間復雜度較低

文獻[21]中所提出的HC-Based定位方法需要反復循環遍歷網絡拓撲圖，時間復雜度較高.本文提出的NNC定位方法采用Louvain算法進行網絡節點聚類，Louvain算法作為一種層次化的社區聚類算法，通過合并超點將社區發現的過程逐步簡化，每次合并超點之后，下一輪迭代的效率均有大幅提升.已有分析表明，Louvain算法的時間復雜度接近O(nlogn)，其中，n為節點個數[25].因此，與現有HC-Based定位方法相比，本文采用Louvain算法，能有效提高網絡節點聚類的效率.

5 實驗結果與分析

為了驗證本文提出的NNC定位方法的性能，我們在實際互聯網環境下，進行了大量目標IP定位實驗.

5.1 實驗設置

1) 實驗數據

為測試驗證本文方法的有效性，利用阿里云內部的1臺主機作為探測源，選取了河南省內7個城市、山東省內6個城市、廣東省6個城市、浙江省6個城市和陜西省內6個城市的IP作為探測目標，從每個省份內隨機抽取3 000個IP，共計15 000個待探測目標IP.實驗部分IP地址數據是從2015年12月20日純真IP地址數據庫[11]發布的數據中抽取的，該數據庫給出了IP地址的城市級位置信息和運營商信息，實驗中用的數據庫包括純真數據庫、IPcn，IP138.

2) 評價標準

本文選擇了2種評價指標對算法的效果進行評估：1)模塊度.模塊度是復雜網絡領域中一個經典的評價指標，可用于衡量網絡拓撲中社區結構的強度，反映算法對網絡拓撲中復雜關系的解析能力.模塊度的計算方法如式(1).2)準確率、召回率和F1值(準確率和召回率的調和平均值).該評價指標反映了算法對目標IP的定位能力和對IP地址數據庫的糾錯能力.對目標IP的定位問題可視為對IP地址數據庫的糾錯問題，只是在定位完成之后無需與數據庫中的地理位置信息進行比對.在計算準確率和召回率時，需要先統計真陽、假陽等值.

實驗通過上述聚類算法得到的L個IP地址的地理位置與通過查詢純真數據庫得到的IP地址的地理位置作比較，若比較結果不一致則認為IP地址修改，修改的IP地址個數為A；與IPcn和IP138查詢結果一致的IP有TP(true positive)個；與IPcn和IP138查詢結果不一致的IP有FP(false positive)個，FP=A-TP.

若比較結果一致則認為IP地址未修改，未修改的IP地址個數為B；未修改的數據B(B=L-A)中，與IPcn和IP138數據庫查詢結果一致的IP有TN(true negative)個；與IPcn和IP138查詢結果不一致的IP有FN(false negative)個，FN=B-TN.

在統計得到上述4個值后，設準確率(accuracy ratio)為P，召回率(recall ratio)為R，則準確率為

P=TP(TP+FP),

(2)

召回率為

R=TP(TP+FN),

(3)

則有：

(4)

5.2 定位結果實驗

本節將對本文提出的NNC定位方法與現有的HC-Based定位方法[21]進行比較.HC-Based定位方法通過人工定義規則對目標網絡拓撲進行聚類，采用啟發式聚類的方式確定目標IP所屬集群(即社區)，根據集群特性估計目標IP的城市級地理位置.在實現HC-Based定位方法時，采用其默認的參數設定：鄰居投票閾值為0.5，集群內最小IP數量為5.在上文所述的數據集和參數的設定條件下，對HC-Based定位方法和本文方法聚類劃分的社區結構模塊度進行實驗，基于河南省、山東省、和陜西省9 000個網絡節點的結果如表2所示：

Table 2 Comparison of the Proposed Method withHC-Based Method

Fig. 9 Cluster result display圖9 聚類結果展示圖

從表2可以看出，本文方法對網絡拓撲聚類劃分得到的社區結構模塊度均在0.9左右，具有較高的社區結構強度.而使用HC-Based定位方法得到的社區結構模塊度均在0.7以下，社區結構強度較弱，這主要是因為在HC-Based定位方法中，存在大量分散的小集群.相比而言，本文方法以模塊度為優化社區結構的指標，不需要指定社區內最小IP數量，而是通過算法自適應調整社區大小，因此得到的社區結構更加科學合理.實驗對河南省網絡拓撲采用上述2種方法的聚類結果可視化如9所示，圖中相同顏色的點處于同一集群.圖9(a)是使用HC-Based定位方法對河南省的網絡拓撲進行聚類的結果示意圖，由圖中可以看出共劃分了117個集群，小集群較多，模塊度較低.圖9(b)是使用本文提出的方法對其進行聚類的結果，從圖中可以看出共得到56個集群，模塊度較高，能更好地展示各個IP節點之間的關系，為下一步定位提供了更加準確的網絡結構信息.

5.3 對IP位置數據庫的糾錯能力實驗

本文還針對2種方法對IP位置數據庫的糾錯能力進行了實驗比較.基于NNC定位方法和HC-Based定位對IP位置數據庫中的IP進行地理位置定位和修正，分別統計出HC-Based定位方法和本文方法在糾錯能力上的準確率、召回率和F1值.結果如表3所示.從表3中可以看出，本文方法在準確率、召回率、和調和值等各項指標上均優于HC-Based定位方法.這表明本文方法能夠有效利用劃分好的社區信息，從社區內部大量IP地址信息的統計特征估計出目標IP的地理位置，并對異常的位置進行糾正.

Table 3 Accuracy, Recall Ratio and F1 Value of Error Correction for IP Database表3 對IP數據庫進行糾錯的準確率、召回率和F1值比較

6 結束語

本文從復雜網絡理論出發分析了現有HC-Based定位方法中存在的不足，提出了一種基于網絡節點聚類的目標IP城市級定位方法.該方法以模塊度作為衡量社區結構強度的標準，采用高效Louvain社區發現算法實現對網絡拓撲的聚類，得到不同的社區劃分，最終利用社區投票確定目標IP的地理位置.實驗結果表明:與HC-Based定位方法相比，本文方法劃分得到的社區結構在模塊度上有較大提升，在對網絡拓撲的社區結構劃分上更加合理準確；利用該方法對國內常用的IP地址數據庫進行糾錯，無論是在準確率、召回率或是F1值上，本文方法均高于HC-Based定位方法.

然而，盡管本文獲得了較好的定位結果，但仍存在2點不足：1)在構建網絡拓撲時僅考慮節點之間的連接關系，未考慮路徑時延信息，如能在路徑信息的基礎上充分利用時延信息，可能能夠得到更好的網絡節點聚類效果；2)網絡拓撲中的社區結構可能存在重疊社區現象[27]，重疊社區中的IP節點與2個甚至多個社區均有較多連接關系，因此其地理位置信息歸屬較為模糊.在下一步研究中，將針對上述問題開展進一步的研究.