第8章链接结构分析子系统设计及核心算法

2017-03-27

17265

第 8 章链接结构分析子系统设计及核心算法本章内容：万维网链接结构图及特性；链接结构分析方法的形式化基础；链接结构分析Page Rank 算法、HITS 算法；链接结构分析结果在搜索结果排序中的应用

第 8 章链接结构分析子系统设计及核心算法

本章内容：

万维网链接结构图及特性；

链接结构分析方法的形式化基础；

链接结构分析Page Rank 算法、HITS 算法；

链接结构分析结果在搜索结果排序中的应用。

8.1 万维网链接结构图

万维网的链接结构可用有向图来描述，网页是节点，超链接是有向边。从源网页指向目的网页的超链接，为源网页的“出链接”，为目的网页的“入链接”。

● 节点 A-H 表示网页；

● 链接关系用有向边来表示；

● 网页

● 网页A 、B 、C 之间的双向边，表示三个网页之间相互链接； F 与G 各自有一个指向自身的有向边。

链接结构关系图的邻接矩阵描述。

邻接矩阵是用来描述图中节点邻接关系的一种方式，设n 为链接结构图 Graph 的节点规模，则邻接矩阵 M 是一个n*n的矩阵，其中某个元素 m i,j 的取值满足：

图 8.1 所示链接结构图，其邻接矩阵如下：

万维网链接图GWeb (V, E)

V ：节点集合，V = { v1 , v2 , v3 ， „ ， v n ｝，节点数|V| = n ;

E ：边集合， E = { e1 , e2 , e3 ， „ ，e m ｝，边数|E|=m 。

将万维网的整个链接结构图作为对象来研究不仅对理解万维网的各种属性有直接的意义，同时还对搜索引擎领域的相关算法研究也有着重要的帮助。

很多实验和观察促进了万维网链接图结构的研究。

针对图 GWeb ( V , E )，研究；

V 、E 的规模；

拓扑结构；

节点入度、出度分布。

图G ( V , E）的某节点所关联的边数称为该节点的“度”。

对于图 GWeb ( V , E）而言，某节点的入度就是指以该节点作为目的网页的超链接数（该节点入链接数）；

某节点的出度则是指以该节点为源网页的超链接数（该节点出链接数）。

8.1.1 万维网链接图的规模

GWeb (V, E）规模难以统计

(1) 图中的节点存在形式复杂；

非自由访问的网页（网页对用户访问加以限制，如采取登录策略等）；自由访问的网页；

传统形式的静态页面；随用户查询需求在服务器端实时生成的动态页面；用 Ajax 技术生成的 URL 相同但内容千差万别的页面；

(2) 超链接的界定，存在诸多困难；

“博客日历”，每个日期都是一个超链接。

服务器端自动生成的超链接VS 网页作者手工编辑添加的链接。

GWeb ( V , E）的节点集合规模

通过域名注册服务商可统计网站、域名数量且较为准确；

统计网站涉及的网页数目就会面临上面提到的问题；

研究中通常用搜索引擎的索引规模来估算万维网链接图的节点规模； 3

没被任何一个搜索引擎收录的网页，被用户访问到的可能性微乎其微； 2008年7月，谷歌索引量1万亿网页，一定程度上反映了GWeb (V, E）节点集合的规模。

GWeb ( V , E）的边集合规模

估计边集合规模更困难；

超链接的添加不需要登记、备案，各大搜索引擎也很少公布统计数据；只能通过实验性万维网语料库的相关数据对GWeb (V , E ）的边集合规模有一个概括性的认识；

AltaVista 语料库，链接关系图包含 2.03 亿个网页、14.66 亿条链接。 Clueweb09 语料库，链接关系图包含的节点数为 1040 809705个，对应的出链接数为7944351835个。

sogouT 语料库，链接关系图包含1.39 亿个网页、33 . 4亿条链接。

从这些语料库，可以估计，边集合的规模要大于节点集合的规模，约为节点集合规模的几到几十倍。

8.1.2 万维网链接图的连通情况

定义：导出子图

给定 G=(V, E)，如果存在另外一个图 G /=(V/,E /) ，满足V /包含于V ，E /包含于E ，则称G /是G 的一个子图。特别地，如果V /包含于V ，且E /包含了在节点子集V /之间的所有边，则称G /是G 的导出子图。

定义：强连通子图

给定一个有向图，该有向图的一个强连通子图是指由一部分节点组成的一个导出子图，对于该子图中其中的任意两个节点u 和v ，都存在一条路径使得从u 可以访问到v 。

性质：

1、一个有向图中可有多个强连通子图。

2、强连通子图之间不存在公有节点；否则可以合二为一。

对万维网连接图，每个强连通子图都代表着构成该子图的节点是相互连通的，通过超链接通过一个网页可访问另一个。

定义：弱连通子图

给定一个有向图，该有向图的一个弱连通子图是指由一部分节点组成的一个导出子图，对于该子图中其中的任意两个节点u 和v ，都存在一条无向路径使得从u 可以访问到v 。

对于万维网链接图，重点考察其包含的强、弱连通子图的规模分布情况，借此了解整个链接图的拓扑结构和连通情况。

2000年，Broder 的研究成果，万维网链接结构图的强、弱连通子图的规模 5

分布情况如下图所示。

● 图中，横轴为连通子图规模，纵轴为连通子图数量；

● 横轴、纵轴使用对数坐标轴。

● 可以看出强连通子图、弱连通子图的规模分布规律基本相同； ● 设连通子图规模为Size ，具有规模Size 的连通子图的数目Number 近似满足；

指数形式表示为：

几点结论：

● 规模大的连通子图数目远小于规模小的连通子图数目。

● 规模最大的连通子图所覆盖的网络资源数量，占网络资源总量中相当比例。 ● 基于链接结构抓取，很难抓取到网络环境中所有数据，但通过抓取规模较大的连通子图可获取最主要部分的数据。

规模最大的强连通子图，其节点规模达到560余万，此连通子图在 Broder 研究的网页集合总规模中占有近28的网页。

以此连通子图为中心，考察其他网页与此连通子图的链接关系，可以对整个网络页面的链接结构关系有一个清晰的认识。

根据Broder 的研究结论绘制的万维网链接结构示意图如下图所示。 6

Core 部份

规模最大的强连接子图；

IN 部分

所有链接到Core 中网页，且同时不被Core 中的网页所链接的网页集合； OUT 部分

所有被Core 中的网页所链接，且同时不链接到Core 中网页的网页集合； Others 部分

剩余的网页集合。

万维网链接和连通结构概貌

● 从IN 中任何网页，都可以链接到Core 中网页，进而可访问OUT 中任何网页。

之外网页，一部份与IN 、OUT 有链接关系，另一部分与IN 、● IN 、Core 、OUT

Core 、OUT 不相连的孤立点或点集合，规模约为所分析网页总数的8.2。 ● 万维网链接结构以Core 为核心，构成了“领结”形式的结构。

8.1.3 万维网链接图的入度和出度分布

万维网链接图的入度、出度分别反映了某节点被其他节点链接，以及链接到其他节点的情况。

万维网链接图 GWeb (V,E) 的入度、出度分布符合幂律；

入度为Indegree 的网页数目 N ( Indegree ）近似满足：

出度为Outdegree 的网页数目 N ( Outdegree ）近似满足：

其中α、β均为值大于零的参数，而C 与 C /为常数。

Broder 的实验结果如下图所示。

8.2 超链接结构分析的基础

超链接：

两个网页或网页的两个不同部分之间的一种指向关系，源网页是指包含超链接的网页，目标网页是超链接所指向的网页。

超链接HTML 格式：

超链接的特性

如果存在超链接L 从页面Psource 指向页面Pdestiny ，则Psource 与 Pdestiny 满足：

特性1 :内容推荐特性

页面Psource 的作者推荐页面Pdestiny 的内容，且利用L 的链接文本内容对Pdestiny 进行描述。

特性2 :主题相关特性

被超链接连接的两个页面Psource 与Pdestiny 的页面内容涉及类似的主题。

特性1说明：

● 入链接个数是页面受其他页面推荐程度大小的标志，入链越多，该页面受其他网页作者的推荐越多，其网页内容质量高。

● 入链接个数越少，说明该页面不被其他网页作者推荐，意味着页面内容或组织形式不受欢迎。

● 链接文本起到对网页内容描述的作用，由于描述来自他人，通常被认为是对网页内容更加客观的描述。

这就在页面质量与超链接结构图的拓扑关系间建立了联系，为页面内容质量评价提供了一种不基于内容的方式。

HITS 算法、PageRank 算法是依据该特性设计的。

特性2说明

● 与特性1相比，特性2的重要程度、适用性低一些；

页面内容相关的可能性要大于随机抽取的两个页面； ● Psource 、Pdestiny

● 超链接表示的不仅是内容相关关系。

万维网的超链接关系比特性1、特性2描述的复杂。

导航栏链接

● 源、目标页面的作者相同，不是内容推荐关系，而是方便用户访问的设置。 ● 可以认为符合特性2，显然不符合特性1。

广告链接

● 内容推荐特性、主题相关特性都无法得到保证（尤其是主题相关性) 。 ● 方面变化快、时效性强，对链接结构分析造成了相当的困难。

版权、注册链接

● 版权信息、注册信息往往以超链接的形式存在，以便查阅；

● 这类超链接数目大；

● 不符合超链接应具有的两个特性。

相当多超链接不符合超链接算法设计中的假设

● 各种链接结构分析算法在真实环境中无法单独被用于网页质量评估

● 改进算法还是可以为页面质量评估提供参考；

● 数据清理后的近似理想环境中，还是可以发挥作用。

本章，假设万维网结构中的超链接满足以上两个特性。

8.3 HITS 算法的基本思路及实现

HITS 算法：

HITS 是Hyperlink-Induced Topic Search的缩写，基于超链接推演的主题搜索算法。

核心思想；

● 对网页的“内容权威度”、“链接权威度”进行评价；

● 内容权威度 ( Authority Value )：网页本身内容的受欢迎程度；

：网页链接到其他受欢迎资源的程度。 ● 链接权威度（Hub Value )

例：学术论文

内容权威度：内容质量比较高、创新性较强、对学科发展能起到较大的推进作用。链接权威度：对某个特定领域进行了较为详尽的调研，能够介绍相当数目的内容

质量高的其他论文和研究工作。

网页内容权威度：

相关推荐