常见网络实体地标挖掘算法综述

朱光

中原工学院计算机学院 河南 郑州 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进行实测的结果进行误差比较与分析。