常見網絡實體地標挖掘算法綜述

朱光

中原工學院計算機學院 河南 鄭州 450007

社交網絡存在著龐大的用戶行為數據，通過對這些網絡數據的收集、處理和分析，可獲取數據中的重要信息，這些數據具有重要的研究價值。網絡實體定位就是大量利用網絡數據作為參考地標來獲取IP地址對應地理位置的技術[1]，其是應用廣泛的LBS的基礎。現有的高精度IP定位技術如GeoPing[2]、Constraint-Based Geolocation[3]、Octant[4]、Topology-Based Geolocation[5]等方法，這些方法的定位精度通常依賴于網絡地標[6]的密度和可靠性[7-8]。因此，網絡實體地標是基于地標的IP定位技術的基礎，只有獲取足夠多的高可靠性地標，才能實現對網絡目標實體的高精度定位。

現有的網絡實體地標挖掘與篩選方法主要有：基于Web的地標挖掘方法[6，9]、基于Internet論壇的地標挖掘方法[10]、基于路由跳數的地標篩選方法[11]以及其他地標獲取方法。本文將對上述大批量地標獲取與篩選方法的基本原理、特點以及局限性進行比較與分析。

1 基于Web的地標挖掘方法

基于Web的地標挖掘方法主要是通過對Web 的HTML信息提取、匹配，獲取該Web域名的IP地址及其對應的地理位置[6]，現有典型的方法有Structon[6]方法和基于Web網頁和在線地圖相結合的地標挖掘方法[10]。

基于Web的地標挖掘方法基本原理如下：Web的HTML頁面的尾部或內容部分中常常包含著該Web網站所屬公司注冊地、駐地的地理位置信息，通過提取、匹配，可將這些地理位置信息映射到Web服務器的IP地址。即從Web的HTML中提取的地理信息，并將該Web網站的域名解析為IP地址，實現IP地址與地理位置的映射關系。Guo等人提出的Structon[6]方法是較早且可大批量挖掘網絡地標的一種網絡實體地標挖掘方法。

Wang等人提出了另一種基于Web網頁和在線地圖相結合的地標挖掘方法[10]。同Structon方法，許多公司、政府部門都運行著對外開放的Web網站，通過將這些Web網站所屬的Web服務器與在線地圖查詢結合，實現Web服務器與地理位置的映射。該方法的基本原理如下：首先，在對外公開提供服務的在線地圖服務（如Google地圖）輸入“公司”或“政府”等關鍵字與想要查詢區域的Zip Code后，地圖服務器將會檢索出一系列與關鍵字相關網站的域名以及郵政編碼，獲取網站IP與其所有可能的地理位置的映射關系。但是，通過在線地圖篩選出的IP地址及所有的可能的其地理位置可能出現信息不一致或信息映射有誤等問題。接著，該方法逐個驗證上一步獲取的所有網絡實體地標。

文章[10]對存在此類問題的地標通過多種方法進行驗證與篩選，但往往只能排除部分存在此類問題的地標，效果并不理想。基于Web的地標挖掘方法雖可獲取大量網絡地標，但在可靠度方面仍有一定的提高空間，通過基于Web的地標挖掘方法獲取的地標，需進一步驗證與篩選，以提高網絡地標的可靠性。

2 基于lnternet論壇的網絡實體地標挖掘方法

因Web服務器存在共享主機、虛擬專用服務器、CDN網絡等情況，基于Web的地標挖掘方法在原理上受到局限，為彌補上述不足，文章[11]提出了基于Internet論壇的網絡實體地標挖掘方法。

基于Internet論壇的網絡實體地標挖掘方法包括3個部分：論壇選擇策略、獲選地標獲取、候選地標評估。

與基于Web的地標挖掘方法相比，該方法可獲取的網絡地標數量多：基于Web的地標挖掘方法挖掘對象為Web服務器IP地址，這類IP地址僅僅占全球IP地址的較少部分，而該方法將挖掘對象指向了個人用戶IP，因此，在網絡地標挖掘數量上顯著提高；獲取地標的范圍廣：Web服務器通常位于經濟較為發達城市，對于沒有Web服務器的地方（如鄉村等地），基于Web的地標挖掘方法將會受到限制，而該方法彌補了基于Web網頁的地標挖掘方法在挖掘范圍方面的不足；獲取地標的可靠性高：基于Web的地標挖掘方法可能受到共享主機、VPS、CDN等情況的影響，導致地標的可靠性較低，而個人用戶IP通常不存在上述情況，因此，該方法獲取的地標可靠性更高。然而，該方法也存在一定的局限性，為緩解IP地址緊張問題，網絡運營商通常在一個城市內建立一個或多個動態IP地址池，用來動態分配IP地址給用戶。因此，該方法獲取的網絡地標通常為城市級粒度。基于Web的地標挖掘方法可獲得城市級甚至是街道級粒度。

3 基于路由跳數的網絡地標篩選方法

為驗證與評估網絡地標的可靠性，文章[11]提出了基于路由跳數的網絡實體地標篩選方法，包括訓練部分和篩選部分。

4 幾種網絡地標挖掘與篩選方法比較

實驗選取位于北京、深圳、杭州三地VPS，分別根據基于Web網頁和在線地圖相結合的地標挖掘方法（方法一）獲取北京、深圳、杭州地標數量分別為546條、637條、403條。實驗選取互聯網論壇 “北京吧” “杭州吧” “深圳吧”等9個百度貼吧，根據基于Internet論壇的網絡實體地標挖掘方法（方法二）獲取有效IP地址，并通過E-GeoTrack算法驗證后，獲取北京、深圳、杭州三地地標數量分別為3225條、5781條、5144條。兩種方法獲取數量比較如下表所示：

基于SLG算法，對100個已知地理位置的目標IP進行城市級定位結果如表2所示：

表2 定位結果比較

對兩種地標集進行誤差比較，地標集定位誤差的累積概率分布如圖1所示：

圖1 兩類地標集誤差比較

對上述定位結果數據進行統計，基于論壇獲取的地標對定位平均誤差為14.8km，基于Web方式獲取的地標對定位的平均誤差為42.5km。可知，采用相同的定位算法，基于論壇獲取的地標的可靠性更高，即基于論壇獲取的地標可提高基于地標的定位算法的精度。

將上述兩種方法獲取的地標作為候選地標，并通過基于路由跳數的網絡地標篩選方法進行篩選。

同樣基于SLG算法，對篩選后地標對100個已知地理位置的目標IP進行城市級定位。兩者的定位誤差的累積概率分布如圖2所示：

圖2 篩選后的兩類地標集誤差比較

對上述定位結果數據進行統計，基于論壇獲取的地標對定位平均誤差為8.9km，基于Web方式獲取的地標對定位的平均誤差為21.1km。可知， 通過定位結果可知，基于路由跳數的網絡地標篩選方法可有效提高地標的可靠性，進而提高基于地標的定位算法的精度。

5 結束語

基于Web的地標挖掘方法、基于Internet論壇的地標挖掘方法是目前較為常用的大批量地標獲取方法，基于路由跳數的地標篩選方法可作為地標的驗證與評估方法，進一步提高網絡地標的可信度。本文對上述方法的基本原理、特點以及局限性進行比較與分析，并對100個目標IP進行實測的結果進行誤差比較與分析。