（计算机软件与理论专业论文）基于流量的web社区挖掘技术的研究与应用.pdf

摘要 如何发现w e b 上根据“主题”聚集在一起的多个社区，使用户很快地 从互联网上提取知识，是w e b 挖掘的一个研究方向。本文在深入研究w e b 社区挖掘技术的基础上，提出一种新的w e b 社区挖掘技术，并给出了该技 术在图的划分问题的应用。w e b 社区挖掘技术的研究对集中式爬取器和搜 索引擎、门户网站内容自动分类以及互联网内容的过滤都有重要的意义。 首先，本文通过对比以往w e b 社区的表示法，提出一种定义较为严格 的w e b 社区数学模型，同时对w e b 社区内、外的网页进行约束，很好地 解决了w e b 社区定义模糊的问题。 其次，提出了与表示法相应的w e b 社区挖掘算法。利用图论中网络流 的概念，把w e b 构造成图，利用图的入度、出度性质给它们之间的边赋予 容量，构造网络流模型，然后使用最大流最小割原理，得到最终的社区。 再次，由于该社区挖掘技术能够解决以往社区边界模糊的问题，使得 所挖掘的社区唯一，所以可以把该技术应用到图的划分问题上。本文提出 了使用w e b 社区的等级的相等关系来划分w e b 网页，其中两个网页相等 当且仅当它们同属于同一个w e b 社区；还提出了层次化划分，重复对压缩 图进行划分，即把属于同一划分的点集压缩成一个点。 最后，本文还利用w e b 抓取器和开放源代码的l u e e n e 全文检索部件 构造了简单的w e b 社区搜索引擎系统，提供了按照相关度对结果进行排 序、对搜索结果进行分组等功能。 关键词w e b 社区；最大流最小割；社区发现；h i t sg o m o r y - - h u 树； 图的划分 燕山大学工学硕士学位论文 a b s t r a c t h o wt od i s c o v e rt h e t o p i c c o m m u n i t y , m a k i n gu s e r sq u i c k l yf i n dt h e k n o w l e d g ef r o mi m e r n e t , i sar e s e a r c hd i r e c t i o no fw e bm i n i n g w i t hd e e p r e s e a r c ho f t h ew e bc o n l n l h n i t ym i n i n gm e t h o d , an e ww 曲c o m m u n i t ym i n i n g m e t h o dw a sd e v e l o p e da n dt h i sm e t h o dw a sa p p l i e dt ot h eg r a p hc l a s s i f i c a t i o n i nt h i sp a p e r a p p l i c a t i o n so ft h i sa p p r o a c hi n c l u d ef o c u s e dc r a w l e ra n ds e a r c h e n g i n e s ，a u t o m a t i cp o p u l a t i o no f p o r t a lc a t e g o r i e s ，a n di m p r o v e df i l t e r i n g f i r s t l y , c o n t r a s t e dw i t ht h ed e f i n i t i o n so ft h ew e bc o m m u n i t y , an e w s t r i c t e rw 曲c o m m u n i t yd e f i n i t i o nw a si n t r o d u c e d ，w i t hb o t hi n s i d ev e r t e xa n d o u t s i d ev e r t e x s a t i s f y i n ga s t r i c t e rc o n d i t i o n i no r d e rt oo v e r c o m et h e a m b i g u o u sb o u n d a r yp r o b l e m s e c o n d l y ，aw e bc o m m u n i t ym i n i n ga l g o r i t h mw a sp r o p o s e d ，u s i n gt h e c o n c e p to fn e tf l o wi ng r a p ht h e o r y , s e t t i n gw e b a sg r a p h ，a n dt h e nu t i l i z i n gt h e p r o p e r t yo fi n d e g r e e a n do u t - d e g r e ea s s i g nc a p a c i t yf o rt h ee d g e ，a n d c o n s t r u c t i n g n e tf l o w m o d e l ，a n du s i n g t h e p r i n c i p l e o fm a x i m u m f l o w m i n i m u mc u tt oo b t a i nt h ec o m m u n i t y , t h i r d l y , b e c a u s et h ew 曲c o m m u n i t ym i n i n gt e c h n o l o g yc a no v e r c o m e t h ea m b i g u o u sb o u n d a r yp r o b l e ma n dm a k et h ec o m m u n i t ym i n e du n i q u e ，t h e t e c h n o l o g yc a nb ea p p l i e di n t ot h ep a r t i t i o n i n go ft h eg r a p h w 曲p a g e p a r t i t i o n i n gw a sp r o p o s e db yt h ee q u i v a l e n c er e l a t i o nd e f i n e du s i n gt h ec l a s so f w e bc o m m u n i t y , w h e r et w op a g e sa r ee q u i v a l e n ti fa n do n l yf ft h es e t so fw 曲 c o m m u n i t i e si n c l u d i n ge a c hp a g ec o i n c i d e ，a n dh i e r a r c h i c a lp a r t i t i o n i n gw a s a l s op r o p o s e db yr e p e a t e d l ya p p l y i n gt h i sp a r t i t i o n i n gt ot h ec o n t r a c t e dg r a p h i nw h i c ha l lo r i g i n a lv e r t i c e si nt h es a m ep a r t i t i o nw e r ec o n t r a c t e di n t oo n e v e r t e x f i n a l l y a ne a s yw e bc o m m u n i t ys e a c he n g i n es y s t e mw a sc o n s t r u c t e db y a b s t r a c t u s i n gw e bc r a w l e ra n do p e ns o u r c el u c e n e w h i c hh a st h ef u n c t i o no fr a n k a c c o r d i n gt ot h ec o r e l a t i o na n dg r o u pb ys e a r c hr e s u l t k e y w o r d sw e bc o m m u n i t y ；m a x i m u mf l o w m i n i m u mc u t ；c o m m u n i t ) ， d i s c o v e r i n g ；h i t s ；g o m o r y - h ut r e e ；g r a p hp a r t i t i o n i n g i i i 燕山大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文基于流量的w e b 社区挖 掘技术的研究与应用，是本人在导师指导下，在燕山大学攻读硕士学位期 间独立进行研究工作所取得的成果。据本人所知，论文中除已注明部分外 不包含他人已发表或撰写过的研究成果。对本文的研究工作做出重要贡献 的个人和集体，均已在文中以明确方式注明。本声明的法律结果将完全由 本人承担。 作者签字宣易刚 日期：渺舞弘月，伯 燕山大学硕士学位论文使用授权书 基于流量的w e b 社区挖掘技术的研究与应用系本人在燕山大学攻 读硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归 燕山大学所有，本人如需发表将署名燕山大学为第一完成单位及相关人员。 本人完全了解燕山大学关于保存、使用学位论文的规定，同意学校保留并 向有关部门送交论文的复印件和电子版本，允许论文被查阅和借阅。本人 授权燕山大学，可以采用影印、缩印或其他复制手段保存论文，可以公布 论文的全部或部分内容。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密口。 ( 请在以上相应方框内打“4 ”) 作者签名： 衫刚 i 导师签名自冬承 价 寸 年 年 中竹 南 第1 章绪论 第1 章绪论 1 1w e b 社区研究背景 随着互联网的不断发展，人们越来越多地在互联网上发布和获取信息， w e b 已经成为信息制造、发布、加工和处理的主要平台。作为一个巨大的 信息源，w w w ( w o r l dw i d ew e b ) 已经允许在一个空前的规模下共享思想和 信息。一方面，随着w 曲成指数级地快速增长，引发了人们使用计算机和 进行日常生活的一场革命；但是。另一方面，w e b 也导致了撅的闻题，极 大地改变了信息检索和管理的传统方式l l 捌。 由于w e b 文档缺乏统一的模式，许多搜索引擎精度较低，以及w w w 上的信息爆炸，用户经常淹没在海量的信息中。另外，由于缺乏为w e b 定 义好的数据模型，寻找有用的信息和管理w e b 上的数据通常是非常单调和 复杂的f 3 1 。 通常，信息检索和管理的作用和有效性主要是受由信息系统采用的数 据逻辑视图所影响的。对于w e b 上的数据，它和传统数据库管理系统上的 数据相比较，有它自身的重大不同特征。w e b 数据的特征如下。 w e b 上的数据是巨大的。没人可以精确地估计w e b 上的数据量。w e b 的指数级增长导致存在大量难以处理的主题，即使是目前功能强大的搜索 引擎，也只能覆盖w e b 上的一部分文档，w e b 上数据量巨大使得传统的数 据库和数据仓库技术不容易管理这些数据。 w e b 上的数据是分散的。由于w e b 的内在属性，数据分布在大量的计 算机和平台上，它们之间没有预先定义好的拓扑结构相互连接。 w e b 上的数据是异质的。除了经常用来传递信息的文本信息，还有大 量的图象，音频文件，视频文件和w e b 上的其它应用。在大部分情况下， 这些异构的数据在w e b 文档中共存，这样很难使用一种技术同时对这些数 据进行处理。 燕山大学工学硕士学位论文 w e b 上的数据是非结构化的。一方面，它没有严格和统一的模型或模 式，所以，实际上也不能控制什么样的用户可以把这些数据发布到w e b 上。 不同的用户可以以自己的方式把信息放到w e b 上，只要满足最基本的w e b 文档显示格式即可，如h t m l 形式。缺乏定义好的w e b 数据可能带来一 系列问题，例如数据冗余和低质量的数据；另一方面，w e b 上的文档有大 量的文档内部变量，还有许多可用的外部元信息变量。尽管当前使用的 h t m l 形式包含一些结构化的基本变量，如标记和锚，但是这些主要处理 文档的显示方面，有很少的语义。所以，很难从w e b 文档中抽取所需的数 据并寻找他们之间的关系。这个特征同传统的数据库很不同。 w 曲上的数据是动态的。w e b 数据固有的和外在的结构可能进化很快， 数据元素可能改变类型，没有遵循先前结构的数据可能被增加，当域和文 件名字更改或者消失的话，相应的链接和重新定址等问题将产生，这些特 征导致频繁的模式修改，是数据库系统的一个非常头疼的问题。 w 曲上的数据是超链接的。不像“平”的文档聚集，w w w 是超文本， 人们可能使用他们的链接图来冲浪。w e b 网页中的超链接在w e b 网页的文 本顶端提供了可观的附属信息，而且建立了数据之间的拓扑和语义关系。 但是，这种关系不是事先定义好的框架，它有许多不确定性，也有许多隐 藏的语义信息。 w w w 的快速发展有了更多的可用的信息，这种增长给社会许多层 次都带来了好处，但是却给搜索弓i 擎的设计者带来了困难：为了使搜索引 擎在现实社会中更加实用，需要平衡大量的冲突1 4 , s 】。 一个冲突就是对索引网页的裁剪。理论上，搜索引擎爬行器可以爬取 所有索引的网页，足够保证结果有效，足够保证所有有价值文档被索引【6 j 。 但是，没有一个搜索引擎可以覆盖超过w e b 上1 6 的网页，1 1 个主要的 搜索引擎联合起来也只能覆盖不足5 0 的网页。而且，由于爬取速度的受 限和网页的平均寿命比较低，搜索引擎经常部分过期。 第二个冲突就是对于查询结果的查准率和查全率的平衡。因为很多搜 索引擎都是用一个自定的测量规则来对结果划分等级的，对于普通搜索引 擎，主题广泛的查询很容易返回大量的查询结果，这样查全率高，但是查 2 第1 章绪论 准率很低1 7 l ；另外一个极端的侈1 j 子，门户网站( 如y a h o o ! ) 通过以层次结构 组织相对少的网页链接，这样可以得到好的查准率，但是查全率比较低。 由于以上这两个问题，引进了一个概念w e b 社区j ，使w e b 爬行器可 以更加有效的关注一个范围相对较窄但是主题相关的网页，还可以提高搜 索引擎和门户网站搜索结果的查全率和查准率。 1 2w e b 社区研究意义 w e b 社区是一些具有共同兴趣的单位和个人所组成的独特小组，这些 小组的兴趣通常表现为某个主题下的若干子题，他们通过共同认可的网页 实现相互同的联系，这些小组可以被一些公开页面所引用，称为“c y b e r 社区”、“w e b 社区”或者直接称为“社区”1 9 1 。 社区可以为用户提供有价值的、可靠的、及时的信息。社区代表了 w e b 中的社区活动，对社区的深入研究可以了解w e b 中知识信息及其组织 结构的发展状况：社区也有利于商家准确地找到客户；发现这些社区可以 对w e b 知识性和社会性徽出评估，也可以帮助研究某个方面感兴趣用户的 组成形式。因此，采用将w e b 信息以社区的形式组织，为信息查询提供了 有效和便捷的途径。 w e b 中存在着大量知名的、定义明确的社区，这些社区基本表现为新 闻组m e w s g r o u p ) 、网圈( w e b r i n g ) 或者如y a h o o ! 和i n f o s e e k 中目录形式的 资源集合，以及如g e o c i t y 中的社区等。 这些知名的社区主要是靠人工发现和维护的【l0 1 ，如y a h o o ! 和i n f o s e e k 中的目录，请一些分类专家对w e b 信息进行分类组织成为树形结构，而用 户则喜欢通过信息结构树方式浏览页面。虽然人工维护的结构树对于许多 主题的搜索非常得有效，但是该树的建立一般都是主观的。结构树的建立 和维护极为昂贵，不但更新缓慢，面且无法覆盖窄范围的主题。另外，由 于社区的数量巨大，其中许多社区处于形成阶段，现有的社区也在不断更 新，通过人工的方式去跟踪这些社区是非常困难的。由于这些潜在社区的 数量大大超过明确定义的社区，人工明确定义的社区则无法识别出这些潜 3 燕山大学工学硕士学位论文 在的社区。 因此，需要开展自动化或半自动化的社区发现和维护技术f l l 】，尤其是 发现技术主要针对那些潜在的、即将形成的社区。 1 3 研究现状和存在的问题 很多技术都在致力于社区发现技术【1 2 】。g i b s o n 等人通过用 h i t s ( h y p e r - l i n k - i n d u c e dt o p i cs e a r c h ) 方法分析链接拓扑结构来分析w e b 社区，将社区定义为一个由“h u b ”页面链接起来的，很稠密的“a u t h o r i t y ” 页面构成的核。k u m a r 等人【”】提出了t r a w l i n g 方法来挖掘社区，把社 区抽象为一个二分有向图。后来r e d d y 1 4 j 等人认为t r a w l i n g 使用的共 同引用( c o c i t a t i o n ) 过于严格而排除了一些可能的潜在社区，通过挖掘稠密 二部图来挖掘w e b 社区。以上这些定义都非常的模糊，虽然用完全二分图 定义的社区比较清晰，但是使用这种方法找到的社区大部分都非常小，而 且大部分的网页都不属于任何社区。 f l a k e 等人根据图形理论【1 5 】，从另外一个角度提出了发现社区的方法。 将社区定义为在w e b 图中具有这样一些特性的网页的集合：社区内的每个 网页同社区内其他网页的链接数要大于同社区外网页之间的链接数，从而 把社区的识别问题等同于解决网络的s - t 最大流最小割问题。这种定义比 较清晰，对于每个子图，可以判断出它是否是一个社区；此外，大的社区 存在的可能性比较大，很多网页都可能属于一些社区。 以上这些方法容易发生主题偏移的现象，使所找到的社区或者太小， 或者太大而没有意义：而且都存在边界模糊的问题。 以上介绍了三种社区发现的方法，每一种方法都是从社区的某一个角 度去考虑【1 6 】。h i t s 是从页面间的社会关系考虑：完全二分图核的算法是 从图论二分图的角度考虑的；基于流量的社区发现方法是从社区的图结构 考虑。尽管它们能够成功地从w e b 中发现社区，但是仍然存在着一些问题。 ( 1 ) 存在边界模糊的问题前两种方法没有清楚的定义出什么样的网 页集合组成w e b 社区，虽然f l a k e 方法提出的方法能够判定什么样的网页 4 第1 章绪论 集合是w e b 社区，但是它仍然存在着边界模糊的问题。 ( 2 ) 未考虑h u b 网页多主题的特性许多页面( 特别是h u b 页面) 包含多 个主题，以页面为基本单位作为顶点，会建立不正确的页面间的社会关系， 降低结果的准确度。所以，应考虑利用w e b 页面的内结构将页面划分为基 于单个主题的块，再在块的粒度上利用链接结构发现社区。 ( 3 ) 未考虑噪音网页的干扰页面内包含了许多“垃圾链接”，不考虑 它们的影响，也会降低结果的准确度。应该考虑研究“垃圾链接”的模式， 对进行计算的链接作清洗，以提高算法的精度；同时社区内的页面由于基 于同一主题，具有一定的内容相似性。可以利用内容特征信息和w e b 页面 上下文( 夕h 部) 结构特征信息的融合方法，开发出基于内容与结构的w 曲社 区发现算法，可以消除单纯依赖某个特征带来的“噪音”影响，提高精度。 ( 4 ) 缺乏层次化特性上述所有算法发现的社区都是“平”的，而非“层 次”化的，即不能发现子社区。应该考虑社区的层次化特性，设计发现包 含子社区的社区树算法。 ( 5 ) 具有片面性每种算法考虑的是w e b 社区的一种性质，具有一定的 片面性。应该考虑社区的多种结构特性来发现社区。 1 4 本文主要研究内容 根据上面所阐述的研究背景和研究现状，课题的研究内容是实现w e b 社区自动挖掘技术。 本课题研究的目标是解决三个问题，课题的具体研究内容安排如下。 为了解决w e b 社区边界模糊的问题。本文提出了一种新的w e b 社区 定义，把w e b 看作一个巨大的图，w e b 社区看作一个子图，对社区内部的 点和外部点同时进行约束，使得符合该定义的w e b 社区唯一；而且提出一 种新的w e b 社区挖掘算法，利用图论中最大济最小割算法的知识，可以 有效的发现符合该定义的w e b 社区。 为了解决图的划分问题。本文提出了使用w e b 社区的等级的相等关系 来划分w e b 网页，其中两个网页相等当且仅当它们属于同一个w e b 社区， 5 燕山大学工学硕士学位论文 由于w e b 社区可以解决边界模糊的问题，因此可以进行层次化划分，重复 对压缩图进行划分。 为了构造一个w e b 社区搜索系统。本文利用w e b 抓取器和开放源代 码的l u e e n e 全文检索部件构造了简单的w e b 社区搜索引擎系统。 1 5 本文组织结构 本论文总体上分为五章，从第2 章开始具体布局如下。 第2 章是基础知识概述。本章主要介绍了要使用的数学概念及公式， 主要是图论的基本知识和最大流最小割方面的知识，以及w e b 是一些基本 性质，还有目前所使用的w e b 社区挖掘技术。 第3 章深入分析f l g 社区定义，指出该定义的不足，并提出了一种新 的w e b 社区挖掘的表示法，解决了以往社区边界模糊的问题：且分析该定 义的性质和特征，从而相应的w e b 社区挖掘算法，挖掘出符合该定义的 w e b 社区。 第4 章根据w e b 社区的性质，用发现w e b 社区的方法可以进行图的 划分，提出一种新的w e b 图的划分算法；且使用开源框架l u c e n e 设计一 个w e b 社区搜索系统。 第5 章对于w e b 社区挖掘算法和图的划分算法，利用j a v a 语言进行 编程实现，介绍实验所用数据集的来源和开发环境的搭建，并给出较为全 面的性能实验分析。 最后是本文的结论，并对下一步的研究工作进行了展望。 6 第2 章w e b 社区挖掘基本知识 第2 章w e b 社区挖掘基本知识 2 1图论的基础知识 图经常被用作分析w e b 页面之间超链接关系的模8 0 1 7 , 1 s 。在超链接的 分析中，w e b 网页可以看成图的节点，网页之间的超链接看作图的边。 2 1 1基础知识 图g ( v ，d 被定义为顶点集矿和边集昱。每个元素e e 代表y 中顶点 对( 甜，1 ，) 的连接。 有向图是指图中的边是有序顶点对( “，v ) ，代表从u 到v 的一个连接。 通常有向图中有序的顶点对( ”，d 用到1 ，的箭头来表示。 在无向图g 中，如果从顶点u 到顶点v 有路径，则称u 和v 是连通的。 如果对于图中任意两个顶点“，v v ，“，v 都是连通的，则称g 是连通图 f c o n n e c t e dg r a p h ) 。一个连通图的生成树是一个极小连通子图，它含有图 中全部顶点，但只是足以构成一棵树的n 1 条边。 权重图是指图中每条边p 都有个非负的权重睨。给定一个权重图，最 小权重最大匹配指的是用最小的权重得到最大的匹配。 顶点v 的度( d e g r e e ) 是与v 相关联的边的数目。在有向图中，以顶点v 为 头的弧的数目称为v 的入度( i nd e g r e e ) ，以v 为尾的弧的数目称为v 的出度 ( o u td e g r e e ) 。 假设有两个图g ( v ，e ) 和g ( v ，e ，如果v v 且e e ，则称g 为g 的子图( s u b g r a p h ) 。 2 1 2 最大流最d , t 0 g ( v ，e ) 表示图，矿顶点集，五为边集，那么： 定义2 1 ：n ( s ，t ，矿，e ，f ) 是一个网络流( n o wn e t w o r k ) 。其中，y 代表 7 燕山大学工学硕士学位论文 顶点集，e 是有向图g ( v ，e ) 的有向边集，s ，t 是矿中两个不同的点，称为 始点( s o u r c e ) 和汇点( s i n k ) ，每条边( k ，一) e ，伴随一个容量c ( e a p a e i t y ) ， 表示为c ( ，一) 。容量指定了从k 到巧通过边( k ，) 流的上限。 定义2 2 ：给定一个网络流n ( s ，t ，v ，e ，c ) ，流( f l o w ) 是一个函数，为每 条有向边( v ，v ，) e 赋予非负数，( 一，v ，) ，满足以下条件。 0 f ( v f ，v ，) sc ( v t ，v ，) ( 2 - 1 ) ( 。) e 。m ，v ) = ( v , v j ) e e f ( v , u j ) ，v v 矿一( 2 - 2 ) 定义2 3 ：给定一个n 络流n ( s ，t ，v ，e ，c ) ，n 的s - t 最小割就是寻找割 集的最小值c ( k ，k ) ，把顶点集v 划分为两个不连接的集合和k ，其中 s k ，f k ，c ( k ，巧) = ( e ，叶) i ( v ，_ ) e e v j 巧 ，割集的容量表 示成倒( c ) = 姚，) c ( v ，v ，) 。 f o r d 和f u i k e r s o n 已经证明了，在同一个网络流中，j t 最大流问 题等同于j t 最小割问题。因此，称此类问题为最大流最小割问题。基于 f o r d 和f u t k e r s o n 理论，提出了许多有效的最大流最小割算法。最短增广 路径算法就是一种非常有效的算法，复杂度为o ( v e 2 ) 。 许多最大流算法的实现是在考虑了整个图，这样可以使得流量分析有 效。例如p r e f l o w - p u s h 算法( 实际中认为是最快的) 通常先对所有边进行拓 扑排序来提高效率。很显然，如果想要计算整个精确的社区，对w e b 进行 全局访问是不现实的。 另一个极端，最短增广算法通过简单地寻找始点和汇点之间地最短路 径，在发现地路径上增加流，重复知道始点和汇点不相连。这个方法地问 题是它需要在每一次增加后都重新进行社区搜索( b r e a d t hf i r s t s e a r c h ： b f s ) 。 根据研究，对最短增广算法进行改进，让它尽可能多地保持以前b f s 搜索树的信息。最坏的情况下执行时间等于标准的最短增广算法的执行时 间：但是，校正阶段的运行时间同新增无效距离标签的顶点的数和那些顶 8 第2 章w e b 社区挖掘基本知识 点向外连接的边数的总和成线性关系的。 2 2w e b 自组织性 自2 0 世纪9 0 年代之后，随着网络技术的发展，尤其是i n t e r a c t 的广 泛应用，w w w 已经成为一个巨大的，分布广泛的全球信息服务中心。因 此，如何利用w e b 快速、准确地获得信息及隐藏在信息中的知识是人们迫 切需要的。由于w e b 上数据具有海量的、无组织的、异构等特征，使得如 何有效地利用w e b 上的数据成为难题1 1 9 】。 2 2 1w 曲的形状 尽管w e b 数据存在无组织、海量的特点，但是w e b 仍存在一些规律。 从宏观上看，w e b 是一个“b o w - t i e ”形状，由一个巨大的“强链接部件”， 连接到“强链接部件”的“i n ”部件，一个被“强链接部件”连接的“o u t ” 部件，和其他页面组成的“t e n d r i l ”部件。如图2 1 所示。 图2 - 1w e b 的连通性 f i g 2 - 1c o n n e e t i v i t yo f t h ew e b 从微观上看，它是根据“主题”聚集在一起的多个社区。w e b 社区可 9 燕山大学工学硕士学位论文 以松散地被定义为基于某个特定主题的、相互连接的w e b 页面集，且社区 内页面的连接密度大。由于w e b 本身的这些结构特点，可以在极度分散和 无序的互联网环境中，发现更多潜在的未被发现和定义的互联网社区。而 这些社区信息又方便了从互联网上提取知识，如： ( 1 ) 在搜索引擎中使用w e b 社区，能够缩小查询范围，快速定位到用户 所需的知识。 ( 2 ) 门户网站通过识别和区分这些社区，可以更有效地组织它们的目录 层次，使得互联网的自动分类成为可能。 ( 3 ) 研究和发展这些社区可以深入了解互联网的进化过程。 由于w e b 以完全分散的形式增长，缺乏统一的管理机制。许多人都一 直认为w e b 是不具备结构和组织特点的。但是近期的研究表明，w e b 还是 具有一定的密度和自我组织形式的。链接结构分析对于研究w e b 的信息组 织形式、改进搜索的方法、了解w e b 的社区内容都是很有价值的【2 们。 在对w e b 的链接结构分析的研究过程中，w e b 图属性的研究具有非常 重要的意义，涉及爬取器、链接信息构造算法、预测结构w e b 图的发展趋 势等方面。 社区的发现和w e b 结构的研究是密不可分的，对于w e b 的形成、节 点的分布形式以及节点未来的发展趋势的掌握，对于加深理解社区的形成 是非常重要的。因此，在社区发现的研究过程中，必须对w e b 的结构做进 一步的研究。 大部分w e b 结构的研究均使用图形理论，b a r a b a s i 和a l b e r t 等人为社 会网络的发展提出了一个局部的模型，基于选择性的附加机制：具有较大 入度的节点很有可能产生新的链接。他们将这一理论应用于w e b 图中，除 了低密度节点外，该模型较为精确地预测到p o w e r - l a w 的度分布。 2 2 2 随机网络 客观世界中存在许多复杂的关系结构，如现有的互联网，页面间通过 超级链接相互引用，从一个页面出发，可以通过链接访问到其他页面。这 种结构呈现很明显的网状特征，从图论的角度出发，将每个页面看作一个 1 0 第2 章w e b 社区挖掘基本知识 节点，当前页面指向其他页面的超级链接看作当前节点到其他节点的边。 对于人际关系来说，通过进一步的抽象，也可以将其看作一个复杂的拓扑 图结构。在客观世界中可以找到非常多的例子，它们的共同特点是：某一 个体和其他个体都可能存在着关系，从整体来看，这些关系组成了一个结 构复杂的拓扑图1 2 ”。 对于具有复杂拓扑结构的网络，一般采取随机图的相关理论进行研究， 这类网络拓扑图被称为随机图( r a n d o mn e t w o r k ) ，它的相关理论已经发展 较为成熟，再次不在赘述。 2 2 3s c a l e f r e e 特性 研究人员经过对大量数据进行分析后发现，将客观世界存在的许多网 络结构，如互联网、人际关系网等抽象为对应的网络拓扑图后，拓扑图节 点的“出度入度数”所对应的分布函数及其相关参数受网络规模的影响非 常小，他们把这种特性称之为s c a l e f r e e 特性【“。 直观的，在拓扑图中，一个节点和别的节点存在直接通路的可能性是 均等的。考虑一个网络拓扑图从无到有的建立过程，节点被逐个加入到图 中，每增加一个节点时，它和拓扑图中已有的每一个节点存在通路的可能 性是均等的。以w w w 为例，把它看成一个有向网络拓扑图，一般情况下， 拓扑图上的每一个节点和其它节点间存在连接边( 无论正向还是反向) 的可 能性是均等的，即页面上的链接指向是随机分布的。然而，这种直观感觉 是缺乏客观依据的，实际情况往往并不是这样。 s c a l e f r e e 特性对w e b 社区也是很有价值的。因为在s c a l e f r e e 的网络 中，节点的出度、入度分布大致符合上述指数分布函数，这使得出入度高 的节点是节点中的极少数，而根据w e b 社区的定义，在一个w e b 社区内 的节点之间具有较多的相互链接，因此可以根据这种链接分布指数退化的 特性，来识别一个w 曲社区中的主体节点。 在页面的访问过程中，由于进行了链接的主题预测，一旦链接主题预 测失败，将可能会发生某些页面或网站不能被网络蜘蛛发现的情况。这将 对最终得到的w e b 社区的完整性造成影响。从可行性来说，要保证w e b 燕山大学工学硕士学位论文 上所有满足条件的页面最终都划分到相应的社区是很难实现的，只能在构 造w e b 社区的过程中，尽量保证其完整性。出度入度数的分布情况反应 了页面间的相互关联程度。从w e b 社区的角度说，社区内的页面集合间的 出度一入度分布情况反应了社区页面间联系的紧密程度【2 3 j 。一般情况下， 社区的规模都达到了满足s c a l e f r e e 特性需要的最小规模。对于大多数社 区来说，其构建过程是从一些初始种子节点出发的。在一开始的构架过程 中，由于数据样本极为有限，计算其分布函数p ( k ) k 1 中的参数f ，将会 发生很大的波动。但是，随着社区规模的不断扩大，参数r 将逐渐稳定下 来，最终，s c a l e f r e e 的特性将体现出来。这种稳定性的体现，该社区已经 具有了较好的稳定性，其内部的成员较均匀地分布于互联网，而不是集中 在某个局部区域，这使得这些成员组成的子集，即该社区相应地具有了 s c a l e f r e e 特性，这可以作为判断社区完整性的重要依据之一。同时， s c a l e f r e e 特性也保证了对于出入度很高的节点，即使在构建过程中发生了 若干次链接主题预测失败的情况，这些节点仍然还有多次机会被添加到 w 曲社区中。 2 3w e b 挖掘技术 随着i n t e r n e t 的快速发展，w e b 正在成为一种新的数据源，其中汇集 了大量信息。但是w e b 具有无结构、动态、组织复杂的特点，给用户搜索 数据造成了很大困难。信息检索是解决网络信息无序和混乱的一个基本方 法，同时也使得网络搜索变得十分关键。目前的网上检索机制都无法满足 用户对于检索信息相关性和准确性的要求，为了从大量半结构化数据中发 现可用的模式，w e b 挖掘技术应运而生，w e b 数据挖掘是目前数据挖掘领 域中的一个很重要的研究领域 2 4 j 。 2 3 1w e b 数据挖掘 w e b 挖掘是指从大量的w e b 文档集合中发现蕴含的、未知的、有潜在 价值的、非平凡的模式。在所处理的对象包括：静态网页( 文字、多媒体信 1 2 第2 章w e b 社区挖掘基本知识 息等) ，w e b 数据库，w e b 页面的内部结构，w e b 结构，用户使用记录等信 息。通过对这些信息的挖掘，可以得到仅通过文字检索不能得到的信息。 w e b 数据挖掘大致分为3 类：内容挖掘，结构挖掘，使用挖掘。w e b 结构挖掘是用来提取网络的拓扑信息，即页面之间的链接信息【2 5 】。如哪些 页面被其它页面所链接，哪些页面指向了其它页面等；使用挖掘用来提取 客户如何运用浏览器浏览和使用链接信息，客户访问的页面以及在每一页 上待了多长时间，下一步单击了什么等【2 6 】；内容挖掘是用来提取文字、图 片或者其它组成网页内容成分的信息、搜索引擎、智能代理和一些推荐引 擎都使用内容挖掘来帮助客户在浩翰的网络空间中寻找所需的内容1 2 ”，如 图2 2 所示。 图2 2w e b 挖掘分类 f i g 2 - 2c l a s s i f i c a t i o no f w e bm i n i n g 2 3 2w e b 结构挖掘 w e b 结构挖掘主要是从w e b 组织结构和链接关系中推导信息、知识。 根据科学引文分析理论，文档之间的互联数据中蕴含着丰富有用的信息。 在通常的搜索引擎中由于考虑到结构的复杂性，近将w e b 看作是一个平面 文档的集合，忽略其结构信息。挖掘页面的结构和w e b 结构，可以用来指 导对页面进行分类和聚类，找到权威页面、中心页面，从而提高检索的性 能；同时还可以用来知道网页采集工作，提高采集效率0 2 扪。 每个w e b 页面并不完全是平面结构，而是有自己的特定结构。w e b 结 1 3 燕山大学工学硕士学位论文 构挖掘的目的是发现页面的结构( 文档内部结构) 和w e b 的结构( 文档间超 链接结构1 ，利用这些结构所蕴含的信息可以发现很多有用的模式或知识。 文档间超链接结构挖掘主要基于s c i 的科学引文分析理论，如果两篇 文献具有同被弓l ( c o - c i t a t i o n ) 和耦合( c o u p l i n g ) 等关系，则两篇文献具有相 互关系或相互联系。充分利用这些关系，能够客观地反映科学活动中许多 隐蔽的和深层次的相关关系，显示出有用的结构2 9 1 。 m r h e n z i n g e r 认为目前的w e b 超链接分析大多是基于以下两条基本 假设。 假设1 ：从w e b 页面彳指向页面曰的超链接是网页a 作者对网页b 的 推荐。 假设2 ：如果一条超链接将网页彳和网页占相互链接起来，则网页爿和 网页b 可能有共同的主题( t o p i c ) 。 基于上面两个假设，还可以引申出以下的几个假设。 假设3 ：一个页面被多次引用，即很多页面有指向它的链接，则这个 页面很重要。 假设4 ：一个页面尽管没有被多次引用，但是被一个重要的页面引用， 则这个页面可能很重要。 假设5 ：一个页面的重要性被均匀分布并传递到它所引用的页面。 假设6 ：如果页面p 和口同被引，则它们可能是相关的，同被引度越 大，相关度越大。 假设7 ：如果页面p 和g 耦合，则它们是相关的，耦合度越大，相关 度越大。 p a g e r a n k 算法和h i t s 算法就是根据以上的假设提出来的，下面主要 介绍一下h i t s 算法思想。 2 3 3h i t s 算法 h i t s ( h y p e r t e x ti n d u c e dt o p i cs e a r c h ) 最早是在1 9 9 9 年由k l e i n b e r g 提 出【3 l 】。他认为每个网页有两个级别：权威级别( 依赖于指向它的页面) 、中 心级别( 依赖于它指向别人的页面) 。工作过程如下：首先用计入文本的搜 1 4 第2 章w e b 社区挖掘基本知识 索引擎得到某一查询的结果集合r ；然后，将r 所指向的页面集合以及其 它指向r 页面集合包含进来形成集合s ；再将所有页面的权威级别、中心 级别全部置初始值为1 ，然后执行以下两步直到收敛。 f o ra l lp a g ef i n 墨q = ，。( f ) h j ；岛= ，c f ( f ) 口j ( 2 3 ) n o r m a l i z e ：= 1 ；。砰= 1 ( 2 - 4 ) 式中四( f ) 代表指向页面i 的所有页面集合；f ( o 代表页面f 所指向的页面集 合：珥代表页面i 的权威级别；h ，代表页面i 的中心级别。最后根据权威界 别大小返回给用户。 2 4w e b 社区挖掘技术 很多技术都在致力于社区发现技术，从具体的实现细节来分，社区发 现技术可分为3 个不同的实现途径：基于h i t s 的技术、基于有向二分图 的技术和基于网络流量的技术【3 2 1 。 2 4 1基于 t s 的技术 k l e i n b e r g 等人在提出h i t s 算法之后，进一步用中心性网页和权威性 网页这两个基本概念来描述互联网的链接结构特征口3 1 。他们认为，尽管互 联网页的创建和链接过程是一种分散和难以描述的过程，但是，从全局的 角度来理解，这些互不关联的创建过程由于作者某种共同的偏好而使得相 互问产生了越来越紧密的联系。当这种联系达到一定程度时，某个潜在的 社区便产生了。 g i b s o n 和k l e i n b e r g 等人在这方面的研究是基于链接分析搜索算法 h i t s 。h i t s 算法模型提供了一种很自然的方式，将链接的结构用一组中 心性网页和权威性网页展现出来，尽管这些中心性网页之间并不知道相互 的存在，同样，这些权威性网页间也不了解相互的存在，但是可以将这一 组中心性网页和权威性网页理解为一个w e b 社区【3 射。这种w e b 社区的定 1 s 燕山大学工学硕士学位论文 义是完全基于结构的，所以，可以在不知道特定主题的情况下发现它们。 当然，这并不是说将整个互联网分割成许许多多个这样的社区。k l e i n b c r g 等人认为需要通过用一小部分高权威性的相关网页来表示社区的主题。 g i b s o n 和k l c i n b e r g 等人的研究主要集中在3 个问题上【3 5 1 。第一，通 过h i t s 算法产生的网上社区究竟是什么；第二，用h i t s 算法发现的网上 社区是否依赖于根集合的选择；第三，在通过多少次迭代以后，社区的主 题才会出现。下面主要介绍前两个问题。通过实验和观察，他们发现对于 足够广泛的主题，h i t s 算法发现社区的效果比较理想，同时，所发现的主 题社区也和h i t s 算法根集合的选择几乎无关( 9 0 根集合具有很强的鲁棒 性) 。他们还发现，利用h i t s 算法除了依赖于主题的广泛性之外，同时还 依赖于互联网上的知识结构，那些流行的学科( 例如，计算机科学) 在互联 网上表现为存在更多的甚至更合理的链接，因此h i t s 算法具有较好的结 果。相反，如果针对那些在互联网中体现较少的学科，h i t s 的效果便不令 人满意了。他们还发现，对于一些在互联网中存在较少链接的主题，h i t s 算法似乎能对主题作某种程度的概念上升和抽象。也就是说，尽管主题并 没有明确广义和非广义的界限，但是h i t s 算法倾向于将返回比给定主题 更一般的主题( 例如，比原主题大但包含原主题) 。 2 4