（计算机软件与理论专业论文）一种改进的web社区挖掘算法.pdf

郑州大学硕士学位论文 摘要 随着i n t e r n e t 的快速发展，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 曲社区发现的三种典型算法， 并对这三种算法进行了具体的比较和分析，指出了算法中存在的缺陷和改进的方 向。 本文对传统的基于流量的社区发现算法中边容量与社区规模之间的关系进 行了深入的研究，传统算法给每条边的边容量分配一个常量值，把每条边看作同 等重要，而实际上每条边所包含的信息价值并不相同，因此常常把包含噪音页面 的图结构提取出来，并且在某些情况下不能提取出大小合适的社区。针对这一问 题，本文提出了一种改进的w e b 社区挖掘算法，改进算法考虑不同边的重要性差 异，将加权p a g e r a n k 算法中页面的重要度转化为衡量页面之间边重要性的传递概 率值，并使用该值对边容量进行赋值，解决了传统算法中存在的问题。 实验结果对比和分析表明，与原始算法相比，改进的算法所获得的社区中与 主题相关的平均页面数日有明显提高，并降低了提取出噪音页面的可能性，有效 的提高了w 曲社区的质量。 关键字：w e b 社区，链接分析，社区发现，最大流最小割，加权p a g e r a n k 第1 页 郑州大学硕十学位论文 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to ft h ei n t e m e t , w e br e s o u r c e sa r ei n c r e a s i n g d r a m a t i c a l l ya n de v o l v i n g i nd i r e c t i o n so fv a r i a b i l i t ya n dc o m p l i c a t i o n s i th a s b e c o m eac h a l l e n g i n ga n di m p o r t a n tp r o b l e mt h a th o wt or e v e a lt h eh i d d e na n du s e f u l i n f o r m a t i o na m o n gt h ee n o r m o u sa m o u n to fw e br e s o u r c e s ，a n du t i l i z ew e br e s o u r c e s i na ne f f i c i e n ta n de f f e c t i v ew a y w e bc o m m u n i t yi so n el 【i n do fi m p o r t a n tw e b r e s o u r c e s ，b yw h i c ht h ew e bi n f o r m a t i o nc a nb e d i v i d e di nam e a n i n g f u lw a y t h e r e f o r e ，i th a ss i g n i f i c a n tm e a n i n gf o ri n f o r m a t i o nr e t r i e v a la n ds e a r c he n g i n e st o d i s c o v e rw e bc o m m u n i t i e sf r o ma ne n o r m o u sn u m b e ro fw e bp a g e sq u i c k l y t h er e l a t i o n s h i p sa m o n gw e bp a g el i n k a g e sp r o v i d ea d e q u a t ei n f o r m a t i o nf o rw e b c o m m u n i t yd i s c o v e r y , s u c ha sf i n d i n gw e bt o p o l o g i e sf r o ml i n ks t r u c t u r e s w es t u d i e d t h r e et r a d i t i o n a lw e bc o m m u n i t yd i s c o v e r ya l g o r i t h m s ；m a d ed e t a i l e dc o m p a r i s o n a m o n gt h e ma n de l a b o r a t e dm e i rd i s a d v a n t a g e sa sw e l la sp o s s i b l ei m p r o v i n go n t h e m t h i st h e s i sf u r t h e r st h er e s e a r c ho nt h ec o n n e c t i o nb e t w e e ne d g ec a p a c i t i e sa n d t h es i z eo ft h eo b t a i n e dw e bc o m m u n i t i e so r i g i n a t e df r o mt h em a x i m u mf l o w a l g o r i t h m t h et r a d i t i o n a la l g o r i t h ms e t saf i x e de d g ec a p a c i t yw i t ht h ee f f e c to fe q u a l w e i g h tf o re a c he d g e h o w e v e rt h ei n f o r m a t i o nv o l u m eo fe a c he d g ei sd i f f e r e n t ，t h e i g n o r i n go fw h i c hw i l ln o to n l yr e s u l t i n gi nn o i s yg r a p h s t r u c t u r ee x t r a c t i o n ，b u ta l s o i m p r o p e rw e bc o m m u n i t yg e n e r a t i n g t h ea l g o r i t h mp r e s e n t e di nt h i sp a p e rc o n s i d e r s t h ed i f f e r e n c e sb e t w e e ne d g e si nt e r m so fm e i ri m p o r t a n c e , a n dt h e nt r a n s f e r st h e s i g n i f i c a n tm e a s u r e m e n to fp a g e se v a l u a t e db yw e i g h t e dp a g e r a n ka l g o r i t h mt o e d g e - t r a n s f e r r i n gp r o b a b i l i t ys c o r e s ，a n df i n a l l ya s s i g n st h e mt oa p p r o p r i a t ee d g e s a c c o r d i n gt ot h e i rc a p a c i t i e s t h ep r o p o s e da l g o r i t h md e a l sw i t ht h ep r o b l e m se x i s t e d i nt h et r a d i t i o n a la l g o r i t h m s t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h ea v e r a g en u m b e ro fr e l e v a n tp a g e s o b t a i n e db yt h ep r o p o s e da l g o r i t h mi sh i g h e rt h a nt h a ti nt r a d i t i o n a la l g o r i t h m s a tt h e s a m et i m e ，t h ep o s s i b i l i t yo fe x t r a c t i n gn o i s yp a g e sd e c r e a s e ss i g n i f i c a n t l yu s i n gt h e 第h 页 郑州大学硕士学位论文 p r o p o s e da l g o r i t h m ，a n dt h eq u a l i t yo ft h eg a i n e d w e bc o m m u n i t yi si m p r o v e d e f f e c t i v e l y k e yw o r d s ：w e bc o m m u n i t y , h y p e r l i n ka n a l y s i s ，w e bc o m m u n i t yd i s c o v e r y , w e b g r a p h ，m a x i m u mf l o wa l g o r i t h m ，w e i g h t e dp a g e r a n k 第1 页 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集 体已经发表或撰写过的科研成果。对本文的研究作出重要贡献的个人和集体，均 已在文中以明确方式标明。本声明的法律责任由本人承担。 学位论文作者：缎仓增 日颠：渺1 辱玛) 8 日 学位论文使用授权声明 本人在导师指导下完成的论文及相关的职务作品，知识产权归属郑州大学。 根据郑州大学有关保留、使用学位论文的规定，同意学校保留或向国家有关部门 或机构送交论文的复印件和电子版，允许论文被查阅和借阅；本人授权郑州大学 可以将本学位论文的全部或部分编入有关数据库进行检索，可以采用影印、缩印 或者其他复制手段保存论文和汇编本学位论文。本人离校后发表、使用学位论文 或与该学位论文直接相关的学术论文或成果时，第一署名单位仍然为郑州大学。 保密论文在解密后应遵守此规定。 学位论文作者： ；妖仓谢曾日期：力口7 年上月3 日 郑州大学硕士学位论文 1 1 研究背景 第一章绪论 随着i n t e m e t 的快速发展，w e b 资源飞速增长，万维网已经成为了一个巨大的、 分布广泛的、全球性的信息服务中心，涉及新闻、广告、金融、教育、政府、文 化、电子商务和许多其他信息服务。然而随着w e b 中海量信息给人们的同常和商 务用途提供丰富资源的同时，w e b 也产生了许多新的问题，使得传统的信息检索 技术和数据库技术在互联网环境中很难有效地利用。 与传统的数据源相比较，w e b 数据有它本身的不同特征。w e b 数据的特征如 下 h 2 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 曲上的数据没有任何控制，只要这些信 息的安排满足w e b 文档的格式就可以了，比如h t m l 格式。 w e b 是具有动态特性的资源。w e b 中的信息以成倍的速度扩大，此外访 问记录也在频繁的更新。 w e b 上的信息只有很小的一部分是相关的或是有用的。一个人只关心 w e b 上很小一部分信息，它所包含的其它信息对用户来说并不感兴趣。 这些特征使得如何快速准确的利用和发现w e b 中的有用信息成为难题。因 此，从大量的信息中提取出与某一特定主题相关的w e b 页面变得异常重要。尽 第1 页 郑州大学硕：t 学位论文 管w e b 数据存在无组织、海量的特点，但是w e b 仍存在着一些规律，万维网包 含了传统数据环境所没有的另一种丰富的信息，o o w e b 页面的超链接拓扑结构。 在整个w e b 环境中，绝大多数的w e b 页面之间都是通过超链接进行连通的。如 果网页p 存在一条指向网页q 的超链接，那么网页p 的作者认为网页g 包含了有价 值的信息。w e b 链接信息提供了丰富的关于w 曲内容相关、质量以及结构方面 的信息，因此，我们可以利用互联网页面之问的链接结构信息去发现潜在的w e b 社区。 w e b 由根据“主题 聚集在一起的多个社区组成，w e b 社区被定义为基于 某个特定主题的，相互链接的w e b 页面集组成。利用w e b 提供的内容和结构信 息，在分散的w e b 环境中，发现潜在的未发现和定义的社区，并从互联网中系 统的抽取出这些社区具有非常重要的意义。 1 2 研究现状 w e b 社区发现是w e b 挖掘的一个重要研究领域，近年来受到广大研究者的 密切关注，该领域内许多研究尚处于起步阶段，有待进一步的深入研究和探讨。 已有的网络社区挖掘算法，基本上都是建立在链接拓扑结构和网络图模型的 基础上的。利用w e b 的链接结构和w e b 图模型来发现网络社区资源已经取得了一 些成就，与此同时，出现了形形色色的以链接分析技术为基础的w e b 社区挖掘方 法。 b r i n 泵l p a g e 2 心最先提出了p a g e r a n k 算法，根据页面之间的相互链接来计算 衡量其重要性的权威值，然后对页面进行排名。r i c h a r d s o n 2 1 】等人将链接信息 和内容信息结合起来，对传统的p a g e r a n k 方法进行改进，在传递页面权威值时不 仅依据链接结构还考虑了页面间的主题相关性；h a v e l i w a l a 【2 2 1 针对不同主题采用 不同主题向量这思想提出了主题敏感的p a g e r a n k 算法。这些改进的算法在一定 程上解决了主题漂移问题，但由于未充分考虑页面的文本结构特性，仅仅只能对 页面之间的链接进行简单的区分。 g i b s o n l 4 等人通过用h i t s 方法分析链接结构来获得w e b 社区，把社区看作是 由中心页面和权威页面链接起来构成的核。这种w e b 社区可以在不清楚主题的情 况下使用链接结构来获取。h i t s 算法【5 】依附于主题的广泛性和网络的整体结构， 第2 页 郑州大学硕七学位论文 它在具有比较多的合理链接主题的网络上可以获得较好的效果。该方法的缺陷就 是对网络社区边界描述不够清晰，使得在没有给定特定主题时无法正确的挖掘出 潜在社区。 在t r a w l i n g 算法【6 j 中，k u m a r 等人利用二分有向图进行定义与描述网络中的 社区。将一个w e b 社区看作是完全有向图的核。对于社区核参数的确定以及从整 个网络中列举出所有社区核的方法，还有待进一步研究。 文献 7 】， 8 中根据图形理论，最先提出通过最大流算法来发现w e b 社区，该 算法为每条边分配一个固定的容量值，很好地解决h i t s 算法中存在的主题漂移 问题，但该算法常常把包含噪音页面的图结构提取出来，并且在一些情况下不能 提取出合适大小的社区。文献【9 【1 0 】通过实验对基于最大流的w 曲社区挖掘算法 进行了研究和分析。 以上的研究丰富了w 曲社区挖掘及相关领域的研究，进一步推动了国内外 该领域内相关技术的研究与发展，将吸引更多专家学者的密切关注。 1 3 本文的主要研究内容 本文在介绍了w e b 社区挖掘相关知识的基础上，对发现w e b 社区的三种典型 算法进行了详细的分析和深入的研究，指出了三种算法存在的不足之处以及改进 的方向。 对传统的基于最大流的w e b 社区发现算法中边容量与社区规模之间的关系 进行了深入的研究，传统最大流社区发现算法给每条边的边容量分配一个相同的 常量值，把每条边看作同等重要，然而实际上每条边所含有的重要度并不相同， 造成常常把包含噪音页面的图结构提取出来，并且在某些情况下不能提取出大小 合适的社区。针对这一问题，本文提出了一种改进的w e b 社区挖掘算法，改进算 法考虑不同边的重要性差异，将加权p a g e r a n k 算法中页面的重要度转化为衡量页 面之间边重要性的传递概率值，并使用该值对边容量进行赋值，解决了传统算法 中存在的问题。 在2 0 个真实的数据集上进行实验，实验结果表明，与原始算法相比，改进的 算法提高了w e b 社区的质量，为有效地发现w e b 中的潜在社区提供了保证。 第3 页 郑州人学硕十学位论文 1 4 本文的组织结构 本文总共分为六章，各章节的组织如下： 第一章是绪论，介绍了本课题的研究背景，研究现状，并给出了本文的主要 研究内容以及本文的组织结构。 第二章是w 曲社区挖掘的基础知识。首先从总体上对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 社区挖掘算法，介绍了相关工 作，指出了传统的最大流社区发现算法中存在的问题，在此基础上提出了一种新 的边容量分配思想，然后给出了改进的最大流社区发现算法的基本思想及详细的 步骤，并对该算法的性能进行了分析。 第五章是实验结果和分析。介绍了实验环境，数据集的获取过程，并将改进 算法和原始算法进行了比较对比分析，最后是本章小结。 第六章是总结与展望。对本文的内容进行了总结，并对下一步的研究工作进 行了展望。 最后是本文的参考文献、致谢及附录。 第4 页 郑州大学硕七学位论文 第二章w e b 社区挖掘基础知识 2 1w e b 数据挖掘概述 随着i n t e m e t 的飞速发展和广泛应用，w e b 正在成为一种新的数据源，蕴藏着 具有巨大潜在价值的信息。但是由于w e b 的无结构、动态、组织复杂等特性，使 得用户搜索自己所需的数据时遇到了阻碍。解决i n t e r n e t 数据资源无序和混乱的 基本方法就是信息检索，然而，已有的检索机制还没有办法满足用户对所搜索到 的资源准确性的要求，尤其是不能发现隐藏在海量w e b 数据背后的知识。而w e b 挖掘技术可以从大量半结构化数据中发现可用的模式从而找到真正有用的信息， 所以说它是当前数据挖掘领域中的一个研究的热点。 2 1 1w r e b 数据挖掘的定义 w e b 数据挖掘【l l 】，简称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 挖掘必须和其它研究手段结合起来，才能对 那些没有统一模式的数据进行分析和处理。 2 1 2w r e b 数据挖掘的分类 与基于关键词的w e b 搜索相比，w e b 挖掘是一项更具有挑战性的任务，它搜 索w e b 结构，依次确定w e b 内容的重要性，发现w e b l 内容的规律性和动态性，挖 掘w e b 的访闯模式。一般地，w e b 挖掘任务可以分为三类1 4 1 ：w 曲内容挖掘【1 2 1 、 w e b 结构挖掘【1 3 】和w e b 使用挖掘【1 1 。如下图所示。 第5 页 郑州大学硕士学位论文 图2 1w e b 挖掘分类图 w e b l 为容挖掘( w e bc o n t e n tm i n i n g ) w e b l 内容挖掘【1 2 】【1 4 】是从w e b 上的数据资源中挖掘出潜在的、有价值的信息的 过程，主要分为w e b 文本挖掘和w e b 多媒体挖掘。大部分w e b 信息资源可以通过 抓取或者建立索引进行检索等手段从网上直接获得，但是，有些资源对用户来说 是不透明的，例如存储在数据库管理系统中的某些数据，或者一些个人私有的信 息。从数据信息的角度来看，w 曲内容挖掘的对象是文本、图像、音频、视频、 元数据和其他各种形式的数据。现阶段，对于w 曲内容挖掘的研究基本上以w e b 文本挖掘为主，它主要对非结构化文本进行w e b 挖掘，而对多媒体挖掘的研究还 处于探索阶段。 研究w 曲内容挖掘一般从信息搜索和数据库两个角度进行。从信息资源的观 点来看，它主要是从使用者的角度出发，重视提高信息资源的质量和帮助用户过 滤信息；从数据库的观点看，其主要工作是对w e b 数据进行集成和建模，并在此 基础上进行网络数据的复杂查询。 w e b 结构挖掘( w e bs t r u c t u r em i n i n g ) w e b 结构挖掘【1 3 】【1 4 1 是根据网络的拓扑结构和页面之间的链接关系发现有用 的信息和知识的过程。主要分为超链接挖掘和页面结构挖掘。一般的搜索引擎都 将网络当作一个平面的文档集合，忽略了其结构的复杂性以及结构中包含的隐含 信息。对页面结构和网络结构的挖掘可以从中找出权威网页( a u t h o r i t y ) 和中心 ( h u b ) 网页，从而更利于提高检索的效率和性能。 超链接分析是w e b 结构挖掘的主要工作，它利用页面之间的链接关系去获得 页面的相互引用关系。它最早应用于搜索引擎，首先计算每一页面被其它页面引 用的次数，被引用次数较多的页面就认为是权威页面( a u t h o r i t yp a g e s ) 。早期的 第6 页 郑州大学硕士学位论文 搜索引擎中使用的是以单词出现的次数为基础的搜索结果排序算法，与其相比， 以链接分析技术为基础的算法具有更明显的优势，它提供的w e b 资源评估策略是 相当客观的。此外，w e b 结构挖掘在w e b 页面分类、统计商业搜索引擎的w e b 页 面数量等方面也有广阔的应用前景。 w e b 结构挖掘领域中，p a g e r a l l k 算法【2 和h i t s 算法【5 1 是两种典型的用来计算 页面重要度的链接分析技术。我们将在第三章对这两个算法作详细介绍。 w e b 使用挖掘( w e bu s a g em i n i n g ) w e b 使用挖掘【1 】【1 4 1 是指通过挖掘w e b 同志记录，发现用户访问w 曲页面的模 式。分析和探讨w e b r 志记录中的规律，可以识别电子商务的潜在客户，增强对 最终用户的因特网信息服务的质量和交付，并改进w 曲服务器系统性能。 w 曲服务器通常对w e b 页面的每次访问登记w e b 日志项。它包括所请求的 u r l ，发出请求的m 地址和时间戳。基于w e b 的电子商务服务器收集了大量的w 曲 访问同志记录。w e b 日志数据库提供了关于w e b 动态性的丰富信息。因此开发复 杂的w 曲同志挖掘技术是十分重要的。 在开发w e b 使用挖掘技术中，要考虑以下问题。首先，虽然设想w e b 同志 分析各种潜在应用是令人鼓舞和激动人心的，但重要的是了解此类应用的成功要 依赖于从这一巨大原始日志数据中能够发现什么样可靠和有效的知识，能够发现 多少。其次，基于u r l 、时间、口地址和w e b 页面内容信息，可以在w e b 同志 数据库上构造多维视图，进行多维o l a p 分析，找出前个用户，前个被访 问页面，最频繁访问时间周期，等等，这有助于发现潜在客户、用户、市场等。 最后，可以在w e b 日志记录上进行数据挖掘，找出关联模式、序列模式和w e b 访问趋势等。对于w e b 访问模式挖掘，通常需要采用进一步的手段获得用户遍 历的附加信息，以便于做更为详细的w e b 同志分析。通过使用这类w 曲日志文 件，可以在系统性能分析方面进行研究，通过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 使用挖掘应用是挖掘客户端用户的交互史和搜索内容，为提高对给定用户秩评定 第7 页 郑州大学硕士学位论文 的准确率提供有用的信息。 2 1 3w e b 数据挖掘的步骤 与传统的数据相比，w e b 上数据的结构要复杂的多，而且是动态的和非结构 化的，使得直接对w e b 页面的数据进行有效挖掘变得十分困难，因此对数据进行 处理是必不可少的一个过程。典型的w e b 挖掘过程1 4 1 分为以下四个步骤： 第一步：资源获取 其主要工作是从w e b 资源数据库中获取所需要的数据，由于w e b 数据的特 点，数据源包括w e b 页面数据、超链接数据和记录用户访问情况的数据等，信息 资源在w e b 中以多种方式存在。 第二步：w e b 信息的选择和预处理 按照主题相关的原则，在外部的w e b 环境中有选择地获取数据。主要目标是 从获取的w 曲资源中去除无用的w e b 信息，并对其进行一定的预处理。例如，对 原始w e b 文件中的数据进行提取、分解、合并，将其转化为适合进行数据挖掘的 数据格式并保存，等待进一步的处理。 第三步：模式发现 从数据着手，通过对抽取出来的代表信息进行综合分析从而得到模式。 第四步：模式分析与可视化 对上一步得到的模式进行确认、并解释。这一过程既可以通过机器自动完成， 也可以通过与分析人员进行交互的方式进行。 信息获取和抽取对w e b 数据挖掘这个完整的技术体系来说极其重要。信息 获取是从在大量的w e b 数据资源中找到相关w e b 信息，而信息抽取则致力于从 相应信息中发现满足需求的数据项。对数据进行有效的组织整理并适当建立索引 是模式分析的一个极其重要任务。 2 2w 曲拓扑结构模型 研究网络拓扑结构【15 1 ，就是以链接结构分析为出发点，并结合数学建模工 具对其进行分析和研究，进而发现结构和功能之间的相互联系。网络拓扑建模涉 及多个领域的知识，比如网络测量、图论知识、统计学以及数学建模等，然而建 第8 页 郑州大学硕十学位论文 模实现主要以链接分析技术为支撑，研究网络的复杂性。 建立在超链接分析技术基础上的网络拓扑结构研究，其主要目的是从从无序 网络中找出潜在的规律，并利用这种规律来描绘网络的宏观特性，以便于在更高 层次上挖掘和使用w e b 资源。在网络拓扑结构的研究当中，重点研究链接结构 对页面实体行为的影响，而对超链接的具体形态或者某个页面的个体属性并不关 心。所以，研究网络拓扑结构的有效途径就是以超链接为研究对象，即链接分析。 链接结构的建模大致经历了四个阶段：早期的规则网络模型，后来的随机网络模 型，直到今天的小世界网络模型【1 6 1 1 刀【1 8 】【1 9 1 和无标度网络模型【2 0 】。目前后两种已 经得到学术界的一致认同，本节接下来的内容将重点介绍后两种网络模型。 小世界网络模型 在规则w e b 图中的边以某个小概率p 改变它的目的节点，并重新连接此边， 并保证没有重复的边出现，由此形成了一种新的网络，这种网络并不是完全随机 的，也不是完全有序的，而是介于规则网络和随机网络之间，称之为小世界网络 ( s m a l lw o r l dn e t w o r k ) 1 6 】( 1 7 1 1 8 】【例。 通过多年来的研究表明，多数现实网络是不均匀的，介于完全规则和完全随 机这两种极端情况之间，这种网络属于小世界网络。这种网络既具有规则网络较 高程度的局部特性，又像随机网络一样，具有的较小的平均路径长度。小世界网 络在实际网络中应用广泛，是目前研究的热点。 小世界网络模型( 简称w s 模型) ，通过调节一个参数可以实现从规则网络 向随机网络过渡。从本质上讲，w s 模型是具有一定随机性的一维规则网络。模 型的构造算法是：从一个环状的具有个节点的规则网络开始，每个结点向与 它最近邻的k 个结点连出k 条边，并满足胗渺觑( m l 。对每一条边，以概 率p 改变它的目的连接点来重新连接此边，并保证没有重复的边出现。改变p 值可以实现从规则网络( 矿o ) 向随机网络仞= 1 ) 转变。具体步骤如下： ( 1 ) 首先构造一个低维的网络结构图( 1 a t t i c e ) ； ( 2 ) 依照某一概率p 在该图的节点之间添加边或者重新画连接边，这些添加 和重画的边缩短了规则网络中节点之间的路径，从而使新生成的网络具有较小的 平均最短距离，同时具备较高的传递性。 w a t t s 等人【1 9 定义的小世界网络局域以下三个特性：最短路径长度，它是整 第9 页 郑州大学硕士学位论文 个网络中所有节点对最短路径长度的平均值；聚类系数，它代表了两个节点之间 通过各自的相邻节点连接在一起的可能性。；对数路径，它是指任何规模的网络 都会随着网络图形的变大而网络却保持相对短的路径长度。 自由标度( s c a l e - f r e e ) 网络模型 小世界网络【1 6 】【1 7 】【1 8 】【1 9 1 和随机网络的度都服从均匀分布或指数分布。但是， 进一步研究结果表明，很多实际w e b 节点的入度和出度并不服从这样的分布， 而是服从幂律分布。该网络通常有两个重要特征：( 1 ) 增长性，即现实网络通 过持续不断地增添新节点在不断增长。( 2 ) 择优连接性。现实网络中，并非所有 的节点都是平等的，新节点总是择优连接到具有大量连通的节点上。自由标度 ( s c a l e f r e e ) 2 0 1 网络是指网络的度分布呈幂律分布，而且对新加入的节点创建 链接时，会优先指向w e b 中链接数量较多的节点。 增长和择优连接这两种要素激励了b a 模型的提出，该模型首次把按幂函数 规律变化的度分布引入网络，它描述的是一个生长的、不断有新节点加入的开放 系统。该模型的构造过程如下： s t e p l ：增长：从较少的节点数量( 肌。个) 节点开始，在每个时间步长增添一 个具有m ( m o ) 条边的新节点，在，l o 个节点中选择m 个节点与新节点相连接。 s t e p 2 ：择优连接：在选择新节点的连接点时，假设新节点连接到已存在的节 点i 的概率丌j ，与节点f 的度数之间满足如下关系： 毗) 2 去 经过时间t 步后，该算法就产生了一个具有- t + m o 个节点，m ，条边的网络。 随着时间的增大，该网络最终演化成稳定的网络，其幂律指数为3 。 2 3w e b 图 w e b 作为一个巨大的信息资源，并没有一个完全统一的管理模式，而是以 分散的形式不断的增大。长期以来大多数人都认为网络是无组织和结构的，但随 着w e b 资源的不断膨胀，只有- d , 部分是用户所需要的，为了顺应这个要求， 开始对w e b 的结构进行深入的研究。通过研究发现w c b 页面是半结构化的数据， 并具有一定的信息组织形式。在链接分析的过程中，使用一个有向图区表示w e b 第l o 页 郑州大学硕士学位论文 网络并对其图的属性进行研究都是很有意义的，不仅可以改进检索的方式，还可 以更进一步的了解w e b 中包含的信息。 在w e b 的页面链接结构分析中，一个页面是w e b 最基本的信息单元，这些 信息单元通过超链接这座桥梁把w e b 页面联系在一起。通常我们使用一个图模 型去分析页面之间的链接关系，可以把整个w e b 抽象成为一个有向图g ( y 固， 其中y 表示w e b 上的页面集，e 表示页面之间的链接关系即超链接集合。如果 把w e b 中的页面看作是有向图的顶点，把两个页面之间的链接看作是有向图的 边，则整个w e b 就称为一个w e b 刚2 4 】。具体定义如下： 定义2 1 设陧一个页面集合，则由此可以生成一个有向图g _ ( 旧，其中用 障示w e b 中页面集合，e 是集合帅的不同节点构成的有序对集合，如果两个节 点u ，v ev ，并且u 和1 ，属于w e b 中两个不同的页面，在页面u 和v 之间存在一条从u 指向v 的超链接，“为链接的源节点，1 ，为链接的终节点，那么有向边( “，) e e 就是有向图g 中的一条边，称之为w e b 图。 图的表示方法大致有两种，矩阵表示法和邻接表表示法。研究图在w e b 中的 应用时，一般采用矩阵表示法去定义一个w e b 图更为方便。 b r o d e r l 2 6 】等人描绘了w e b 图的形状，认为w c b 图是一个“b o w t i e ”的形状。 从图2 2 可以看出，w e b 图结构大致由强链接的核s s c ，集合i n ，集合o u t ， 图2 - 2 w e b 图的形状示意图 t e n d r i l s 集合四部分组成，也把该结构称之为w e b 的b o w t i e 模型。可以利用 该模型进行w 曲中链接节点的平均直径的度量以及发现出度和入度的分布规 律。 第1 i 页 郑州大学硕士学位论文 文献 2 7 】表明，根据域的限制、关键字的出现频度等某些标准，虽然各个部 件的形状在大小上有所改变，但网络子图也同样表现出b o w t i e 的特性，这一特 性称为w e b 的分行结构，即子区域表现出和整体w e b 相同的属性。 综上所述，对w e b 结构的研究对w e b 信息检索、资源发现，w e b 社区的挖 掘都具有非常重要的实用价值。 2 4 本章小结 本章介绍了w e b 社区挖掘的基础知识； 首先从总体上对w e b 数据挖掘进行了概述，给出了w e b 数据挖掘的定义及其 分类，w e b 数据挖掘按照挖掘对象的不同可以分为w e b 内容挖掘、w e b 结构挖掘 和w 曲使用挖掘； 其次介绍了w e b 拓扑结构模型以及w e b 图的定义和形状，为我们将来更好地 研究w e b 社区的划分方法以及对w c b 社区的未来发展趋势均提供了帮助； 最后对本章进行了小结。 第1 2 页 郑州大学硕士学位论文 第三章w e b 社区挖掘算法研究 3 1w 曲链接分析技术 3 1 1w e b 链接分析技术及主要算法 超链接是网络的一个重要组成部分，是w e b 信息资源相互联系的纽带，也是 研究w 曲空间结构和相关知识发现的工具。超链接分析f 2 8 j 【3 0 j ( h y p e r l i n ka n a l y s i s ) 以页面之间的超链接作为研究对象，对各种现象进行结构化分析，包括链接本身 属性、链接对象以及链接形成的网络等，进而发现其数量特征和内在规律。如何 获得隐藏在链接数据背后的关系信息是链接分析的关键。目前主要有两种获取信 息的手段，一个是直接访问法，该方法只适用于小规模链接信息分析；为了适应 研究大规模网络的需要，就要借助另一种手段，也就是计算机辅助评价方法，那 么如何使用这种方法进行链接信息收集和分析是研究的重点。 超链接分析算法基于以下两个假设：第一，如果两个页面之间存在一条链 接，就表示两个页面的内容相关；第二，链接传递了人们的认可。即，如果存在 从页面a 至! l j 页面b 的链接，并且这两个页面由不同的人创建，该链接就意味着页 面a 的创建者发现页面b 是有价值的。p a g e r a n k 算法和h i t s 算法是两种最具代表 性的典型的链接分析算法，已经在实际中得到了实现和应用。 p a g e r a n k 算法 l b r i n 和s p a g e 于19 9 8 年最早提出tp a g e r a n k 【2 】【3 1 1 算法，它是建立在基于重 要度传递的随机冲浪模型上，根据网页之间相互链接来计算衡量其重要性的 权威值，然后对网页进行排名。最早被用于g o o g l e 搜索引擎中，对检索结果进 行排序，后来也在网页采集、检索结果聚类、查找相关网页等众多领域得到了广 泛的应用。 p a g e r a n k 算法【2 】【3 1 1 的基本思想：如果网页u 存在一个指向网页v 的超链接，则 表明u 的所有者认为v 比较重要，从而把u 的一部分重要度赋予y 。一般情况下，一 个w e b 冲浪者每次都按相同的概率( 1 力在当前网页中选择下一步要访问的链接， 而当一个网页不存在出链接时，则以一个很小的概率d 随机跳转到任意一个页面。 第1 3 页 郑州大学硕十学位论文 假设帆表示页面u 的链出页面集合，b ，表示页面y 的链入页面集，则在任意时间点， 页面v 的p a g e r a n k 值的计算公式为： p r ( v ) = d n + ( 1 一d ) x p r ( u ) n , , i ( 3 一1 ) “鼠 其中，d 为阻尼系数，0 水l ，通常取值范围为o 1 o 2 ，l 为有向图g 中节 点的数量。从式( 3 1 ) 可以看出，如果一个页面有较多的页面链接指向它或者 指向它的页面比较重要，那么就认为该页面是重要的，p a g e r a n k 值很好地反映网 页之间的相互引用关系。但p a g e r a n k 忽略了主题相关性，导致结果的相关性 和主题性降低，并容易产生主题漂移现象；其次，有些链接只是起到导航或者 广告的作用，该链接相连的页面和主题没有太大的联系；因此给网页链出的每一 个超链接赋予了相同的权重是不正确的。此外，p a g e r a n k 算法有很严重的对新 网页的歧视现象。 h i t s 算法 k l e i n b e r g l 5 1 提出了超链接诱导的主题索引算法，即h i t s 算法。它【2 9 1 是在权 威页面( a u t h o r i t y ) 和中心页面( h u b ) 两种页面类型以及两者之间关系的基础上 进行研究的。使用这两种页面可以更好的衡量页面的重要度。 权威页面是指在某一主题上人们普遍公认的具有权威性的页面，当一个w e b 页面的作者建立指向另一页面的链接时，可以看作是作者对另一页面的认可。给 定的页面被不同的w e b 作者认可集体反应了该页面的重要性，并可以很自然的导 h u b sa u t h o r i t i e s 图3 - 1 中心页面和权威页面的相互加强关系 致权威w 曲页面的发现。此外，一个权威页面很少让它的w e b 页面指向其相同领 域竞争者的页面。由于w e b 链接结构的这种特性，提出了另外一种重要的w e b 页 第1 4 页 郑州大学硕十学位论文 面，即中心( h u b ) 页面。它提供了指向权威页面的链接集合。中心页面本身可 能并不突出，但是它们提供了指向关于某个公共主题的一些卓越网站的链接。中 心页面起到了隐式的确立所关注的主题的权威页面的作用。如图3 1 所示，一个 好的中心页面【2 9 】应该指向很多好的权威页面，而一个好的权威页面则应该被很 多好的中心页面所指向，这种中心与权威页面之间相互增强的联系，有助于权威 w e b 页面的挖掘以及高质量的w e b 结构和资源的自动发现。 算法h i t s l 2 9 】是一种利用中心页面的搜索算法，其内容如下： 首先，h i t s 使用查询词，由基于索引的搜索引擎收集一个初始页面集，比 如2 0 0 个页面。这些页面形成根集( r o o ts e t ) 。由于这些页面中的许多页面都可 能与搜素主题相关，因此，根集可进一步扩展为基本集( b a s es e t ) ，包括根集中 的页面链接到的所有页，以及链接到一个根集页面的所有页面。可以为基本集的 大d , n 定一个截止点，如1 0 0 0 至5 0 0 0 页。 其次，启动权重传播阶段。这个迭代过程确定中心与权威权重的数值估计。 其中具有相同w e b 域( 即在u r l 中具有相同一级域名) 的两个页面之间的链接， 经常是起导航作用，因此不涉及权威。这种链接可以从权重传播分析中排除。 为基本集的每个页面p 赋予一个非负权威权重和非负的中心权重j i l p ，并