LocalRank：考虑地理位置的网页排名方法

### LocalRank：考虑地理位置的网页排名方法 在当今的互联网环境中，网页排名是一个至关重要的技术，它直接影响着用户获取信息的效率和质量。传统的网页排名算法如PageRank主要关注网页之间的链接关系，而忽略了网页的地理位置信息。然而，在很多实际应用场景中，地理位置信息对于用户查找相关网页具有重要的参考价值。本文将介绍一种新的网页排名方法——LocalRank，它在网页和数据库的集成空间中计算排名，并额外考虑了语义链接和地理位置信息。 #### 1. 相关研究背景 - **网页地理位置提取**：从网页中提取特定地理区域相关的页面有多种方法。例如，有研究提出了局部性程度的概念来发现网页中的本地信息，还有研究提出了一种增强的网页空间，它由网页、超链接和表示网页间地理关系的语义链接组成。 - **主题聚焦爬虫**：主题聚焦爬虫是高效收集网页的关键技术。不同的主题聚焦爬虫有不同的策略，如PageRank爬虫倾向于访问PageRank值高的网页，基于超文本分类器的聚焦爬虫会根据主题分类法对爬取的页面进行分类，基于贝叶斯分类器的上下文聚焦爬虫会根据爬取页面与相关目标页面的链接距离来引导爬取。我们的LocalRank值可以像PageRank爬虫一样，引导爬虫找到与数据库高度相关的页面，因此该方法可应用于主题聚焦爬虫，其中“主题”由数据库条目确定。 #### 2. 提出的方法 ##### 2.1 扩展数据库 以筑波市的餐厅数据库为例，我们首先构建其扩展数据库。扩展数据库以实体 - 关系图的形式展示了数据库和网页之间的关系。其中，餐厅实体代表数据库中的餐厅条目集合，页面实体代表所有网页的集合。网页的URL、地址、电话号码和邮政编码等信息被视为页面实体的属性。“has - HP”关系连接餐厅和页面实体，表示一个餐厅条目必须有对应的主页，但并非所有网页都必须有对应的餐厅条目。“refers”关系表示网页之间的超链接引用。对于其他数据库，也可以使用额外的属性类似地构建扩展数据库，属性不限于地址、电话号码等，可根据用户需求使用可用工具从网页中提取。 | 实体 | 描述 | | ---- | ---- | | 餐厅实体 | 数据库中餐厅条目的集合 | | 页面实体 | 所有网页的集合 | | has - HP关系 | 连接餐厅和页面实体，一个餐厅条目必须有对应主页，并非所有网页有对应餐厅条目 | | refers关系 | 表示网页之间的超链接引用 | ##### 2.2 权威转移图 基于扩展数据库构建权威转移图，该图反映了其元素之间的一些关系。为简化起见，省略了属性。图中的实线和虚线都被视为链接，分配给链接的值（0到1之间）称为权重。实线对应扩展数据库中的“has - HP”和“refers”关系，不同的权重表示页面得分的转移比例。虚线表示语义关系，如“is - close1”链接在两个餐厅条目地址接近时生成，“is - close2”链接在餐厅和页面实体地理位置接近时生成，“matches”链接在网页描述的信息与餐厅条目相关时生成。通常，语义链接具有一定的灵活性，我们假设使用用户定义的谓词来定义语义链接。 ```mermaid graph LR classDef entity fill:#E5F6FF,stroke:#73A6FF,stroke-width:2px; A(restaurant):::entity -->|0.1 is-close1| A A -->|0.7 refers| B(page):::entity B -->|0.1 refers| A A -->|0.8 has-HP| B A -->|0.2 is-close2| B B -->|0.4 matches| A ``` ##### 2.3 链接分析 - **构建数据图**： 1. 为餐厅表的每个条目生成对应的节点。 2. 使用表中的“URL”属性下载每个餐厅的主页，将这些页面集合记为S1。 3. 获取与主页在同一网站中可访问的网页，记为集合S2。 4. 使用搜索引擎（如Google）为每个主页检索其反向链接页面，组成集合S3。 5. 使用餐厅表每行的属性值（如“Name”和“Phone”）进行关键字搜索，得到的网页集合记为S4。 6. 为S1、S2、S3和S4中的所有网页生成对应的节点。 7. 从S1、S2、S3和S4中的网页中提取URL，并为未下载的对应页面生成节点。 节点生成后，生成节点之间的链接： 1. 对于S1中的网页，用双向的“has - HP”链接将它们与对应的餐厅条目连接起来。 2. 根据节点生成步骤7中URL提取的结果，在网页（包括已下载和未下载的）之间创建“refers”和“refers”链接。 3. 对于S4中的网页，用双向的“matches”链接将它们与对应的餐厅条目连接起来。 4. 当用户定义的“is - close1”谓词为真时，在数据库条目之间生成双向的“is - close1”链接。在实验中，通过将数据库条目的“Address”属性映射到坐标，并判断它们之间的距离是否低于给定阈值来实现该谓词。 5. 类似地，当“is - close2”谓词为真时，在S1 ∪ S2 ∪ S3 ∪ S4中的网页与其对应的数据库条目之间生成双向的“is - close2”链接。 链接的权重根据权威转移图的设置进行分配。当从同一节点发出两个或多个属于同一种链接的边时，权重会除以出边的数量。 - **分数计算**：使用以下方程计算数据图中每个节点的LocalRank分数： \[r = dA'r + (1 - d)\frac{e}{n}\] 其中，n是数据图中的节点数量，d是用户给定的阻尼因子，A是一个n × n矩阵，其元素(i, j)的值是从i到j的所有边的权重之和，A'是A的转置矩阵，r是一个n维列向量，其元素是每个节点的LocalRank值，e是一个所有元素都设为1的n维列向量。r的所有元素初始化为1，计算在r收敛时终止。 与PageRank不同，LocalRank基于集成了网页和用户数据库的数据图计算分数，它不仅反映了网页在网页空间的受欢迎程度，还反映了网页与用户提供的数据库条目的相关性。同时，由于使用了地理上的“is - close1”和“is - close2”链接进行链接分析，地理位置信息也融入了网页排名中。 #### 3. 实验 ##### 3.1 数据库构建和相关页面收集 从筑波市的一些门户网站的美食导航页面中选择54家餐