（计算机应用技术专业论文）基于链接分析的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 社区发现典 型算法并提出了改进算法，同时在现有搜索软件及其工具包基础上构建了其应用系统原型。 探讨了如何根据w e b 社区发现算法对w e b 信息集合进行有效的聚类划分和直观易懂的描述， 对改善搜索引擎的搜索结果有一定的理论及应用价值。 关键词：链接分析；w e b 建模；w e b 信息检索；聚类；w e b 社区发现 西安理工大学硕士学位论文 t i t l e ：r e s e a r c ha n da p p l i c a t l o no fw e bc o m m u n i t y d i s c o v e r yb a s e do nh y p e r l i n ka n a l - y s i s m a i o r - c o m p u t e ra p p l i c a t i o nt e c h n o l o g y n a m e ：c u il i s u p e r v i s o r ：p r o f l i n t a ol i j a b s t r a c t s i g n a t u r e ：& ! s i g n a t u r e ：z 囱丝鱼 w i t ht h er a p i dg r o w t ho fw e bj n f o r m a t i o n i tb e c o m e sm o r ea n dm o r ei m p o r t a n ta n d c h a l l e n g i n gr e s e a r c hp r o b l e mt h a th o wt or e t r i e v el a t e n ta n du s e f u ii n f o r m a t i o na m o n gt h e g i g a n t i ca m o u n to fw 曲i n f o r m a t i o n ，a n du t i l i z ew e bi n f o r m a t i o na d e q u a t e l ya n de f f e c t i v e l yo n i n f o r m a t i o nd o m a i n i ti sv e r yv a l u a b l et os e a r c hw e bc o m m u n i t yd i s c o v e r yi np r a c t i c ea n d a c a d e m i cs t u d y , w e bc o m m u n i t yi sv e r yi m p o r t a n tw e bi n f o r m a t i o n 。i tc a np a r t i t i o nw e b i n f o r m a t i o nv a l u a b l y , i tr e f l e c t sp r e v a l e n ta n dc o m p l i c a t e dc l u s t e r i n gr e l a t i o na n dh i e r a r c h i c a l r e l a t i o no nw e b m o s ta b u n d a n ti n f o r m a t i o nc l u eh a sb e e np r o v i d e df o rw e bc o m m u n i t yd i s c o v e r y r e s e a r c h i n gi n t h er e l a t i o no fw e bp a g e l i n k s ，w e bc o m m u n i t yd i s c o v e r yw a sb a s e do n h y p e r l i n ka n a l y s i st e c h n o l o g y w ec a ng a i nu s e f u lt o p o l o g i c a lr e l a t i o nf r o mw e bp a g el i n k s s t r u c t u r e w ec a na n a l y z ec o r r e s p o n d i n gf u n c t i o n a la n ds e m a n t i cm e a n i n gf u r t h e r , a n df i l t r a t e u s e l e s si n f o r m a t i o n i tw i l lb er e d o u n dt oe n h a n c ew e bi n f o r n l a t i o nr e t r i e v a lp e r f o r m a n c ea n d p r e c i s i o nt h a tw 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 mi su s e dt os e m c he n g i n e ，a n dc a l li m p l e m e n t w e bi n f o r m a t i o nc l u s t e r i n gi ns o m ew a y s b a s e do nt h ea n a l y s i so fc u r r e n tw e ba n di t sd a t ac h a r a c t e r , t h em o d e l i n gm e t h o d so fw e b t o p o l o g i c a ls t r u c t u r e ，w e bt o p o l o g i c a ls t r u c t u r em o d e l ，w e bi n f o r m a t i o nr e t r i e v a lm o d e la n dt h e a r c h i t e c t u r eo fs e a r c he n g i n e ，t h ec l a s s i c 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 mw a sr e s e a r c h e d o nt h eb a s i so fw e b h y p e r l i n ka n a l y s i st e c h n o l o g yi nt h i sp a p e r , a n d i t si m p r o v e da l g o r i t h mw a s p r o p o s e d a n dw e bc o m m u n i t yd i s c o v e r ya p p l i c a t i o ns y s t e mw a sc o n s t r u c t e db a s e do nc u r r e n t s e a r c hs o f t w a r ea n dt o o lp a c k a g e t h ei n t u i t i o n i s t i cm e t h o dt h a th o wt oc l u s t e r i n gp a r t i t i o nw e b i n f o r m a t i o ns e tb yw 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 mw a sd i s c u s s e d ，a si sv e r yv a l u a b l ei n p r a c t i c ea n da c a d e m i cs t u d yt oi m p r o v er e t r i e v a lr e s u l t so fs e a r c he n g i n e k e yw o r d s ：h y p e r l i n ka n a l y s i s ；w e bm o d e l i n g ；w e bi n f o r m a t i o nr e t r i e v a l ；c l u s t e r i n g ；w e b c o m m u n i t yd i s c o v e r y i i 独创性声明 秉承祖国优良道德传统和学校的严谨学风郑重申明：本人所呈交的学位论文是我个 人在导师指导下进行的研究工作及取得的成果。尽我所知，除特别加以标注和致谢的地 方外，论文中不包含其他人的研究成果。与我一同工作的同志对本文所论述的工作和成 果的任何贡献均已在论文中作了明确的说明并已致谢。 本论文及其相关资料若有不实之处，由本人承担一切相关责任 论文作者签名：塑兰p 译3 月盈瑁 学位论文使用授权声明 本人：醒在导师的指导下创作完成毕业论文。本人已通过论文的答辩，并 已经在西安理工大学申请博士硕士学位。本人作为学位论文著作权拥有者，同意授权 西安理工大学拥有学位论文的部分使用权，即：1 ) 已获学位的研究生按学校规定提交 印刷版和电子版学位论文，学校可以采用影印、缩印或其他复制手段保存研究生上交的 学位论文，可以将学位论文的全部或部分内容编人有关数据库迸行检索；2 ) 为教学和 科研目的，学校可以将公开的学位论文或解密后的学位论文作为资料在图书馆、资料室 等场所或在校园网上供校内师生阅读、浏览。 本人学位论文全部或部分内容的公布( 包括刊登) 授权西安理工大学研究生部办 理。 ( 保密的学位论文在解密后，适用本授权说明) 一徽：年一名：弊m 绪论 1 绪论 1 1w e b 数据特征及w e b 社区 1 1 1 当前w e b 及其数据特征 随着全球网络化、信息化的发展，w e b 已成为人们获取信息的主要手段，它是一个复 杂超文本所组成的巨大的信息源，且其规模仍在迅速增长： ( 1 ) 1 9 9 8 年7 月i n t e r n e t 协会( h t t p ：w n v i s o c o r g ) 年会报告称，世界上2 5 0 个国 家中有2 4 0 个提供i n t e r n e t 上网服务。 ( 2 ) 来自互联网名字与编号管理机构( i c a n n ) 罗马会议的一份全球域名产业报告显示， 2 0 0 3 年全球域名注册量已经突破6 千万个，较上年度增长率为1 6 。 ( 3 ) 2 0 0 3 年7 月9 日，国务院信息化工作办公室发布的( 2 0 0 2 年中国互联网信息资源 数量调查报告显示，截止到2 0 0 2 年1 2 月3 1 日，全国域名数为9 4 0 3 2 9 个，网站数为 3 7 1 6 0 0 个，网页总数达2 2 4 4 2 万个，网页总字节数达3 8 6 0 6 。 ( 4 ) 2 0 0 4 年1 月1 5 日，中国互联网络信息中心( c n n i c ) 在北京发布了第十三次中 国互联网络发展状况统计报告，报告显示，截止到2 0 0 3 年1 2 月3 1 日，我国w w w 站点数 为5 9 5 5 5 0 个，半年内增加1 2 1 6 5 0 个，增长率为2 5 7 ，和上年同期相比增长6 0 3 。 ( 5 ) i n t e r n e t 软件协会( h t t p ：w w w i s c o r g ) 的最新统计表明，到2 0 0 4 年1 月，w e b 主机的数量已超过一亿五千万台。据c o m s c o r e ( h t t p ：删c o m s c o r e c o m ) 的最新统计 报告，截至2 0 0 4 年5 月1 4 日，全球已逾3 亿5 千万用户使用i n t e r n e t 。 ( 6 ) 目前，g o o g l e 搜索引擎索引的网页数为4 2 8 亿张，而调查显示，没有一个搜索引 擎的网页索引超过总网页的六分之一。 随着w e b 的不断发展及人们对w e b 依赖程度的不断加深，w e b 数据资源也在多元化、 复杂化发展。图1 - 1 描述了全世界w e b 文件的格式分布“2 1 ： 图1 - 1w e b 数据格式分布 f i g 1 1 d i s t r j b u l i o no fw e bd a t af o r m a t 西安理工大学硕士擘位论文 w e b 数据的复杂性主要表现在如下几个方面“1 1 ： ( 1 ) 分布式的数据：由于物理结构上分布的拓扑结构，使得数据分散在不同的爿算平台 上，而且w e b 上的有效带宽经常发生变化。 ( 2 ) 不稳定的数据：由于w e b 的动态性，其信息在不断地发生着更新。新闻、股票市场、 公司广告和w e b 服务中心都在不断地更新各自的页面，链接信息和访问记录也在频繁地更 新之中。 ( 3 ) 规模巨大：目前w e b 上的信息已经非常多，而且还在爆炸性地增长。 ( 4 ) 半结构或无结构的数据以及冗余数据：以h t m l 形式存在的w e b 页面，没有统一的 格式，包括镜像和重复页面，内容的重复率大约有3 0 ，语义的重复率可能会更高。 ( 5 ) 信息质量没有保证：若把w e b 看成是一种新兴的出版媒体。它与传统的出版媒体不 同，其大部分出版过程不包括编辑的过程。所以难免会有各种各样的编辑错误的发生和存 在。 ( 6 ) w e b 包含了大量不同的用户衽区：网络用户具有不同的背景、兴趣、目的。 ( 7 ) 异构的数据：w e b 几乎覆盖了全球所有国家，内容基本上包括全部的学科、领域、 语言、跨越不同的政治派别、宗教信仰。w e b 上的各网站、页面分属不同的组织机构，使 用w e b 的目的从严肃的科学研究到政治宣传、谋求商业利润、娱乐消遣无所不有。w e b 页 面的风格、创作方式也是五花八门。这些异构数据的类型还在不断地增加，而每一种数据 类型需要不同的方法来处理。 ( 8 ) w e b 上的信息对用户而言，只有很小的一部分是相关的或有用的。据说9 9 的w e b 信息对于9 9 的用户是无用的。虽然这看起来不是很明显，但一个人只是关心w e b 上非常 小的一部分信息确是事实，w e b 所包含的其余信息对用户来说是不感兴趣的，而且会淹没 所希望得到的搜索结果。 w e b 数据的特点和它的快速增长，以及謦来的挑战，加上现有醪e b 搜索系统在信息覆 盖率、及时性、个性化、可扩展性等方面存在的问题慨”，构成了如w e b 数据挖掘与发现、 w e b 社区研究、智能信息检索等信息领域的新兴学科及技术的形成与发展的动机。 1 1 2 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 页面集。 2 绪论 从w e b 拓扑结构分析角度看，一个社区就是指一个w e b 图的子集，在这个子集内的 节点之间连接密度高于子集内部节点与外部节点的连接密度，可见w e b 拓扑结构社区是 一个层次化的概念，即一个大的社区可能包含了若干的小社区。主题相同或相似的页面常 常相互稠密链接在一起，本身呈现出社区现象，反映了w e b 中普遍存在的、复杂的聚团 关系和层次关系。无论具体的社区定义如何，社区结构都反映了w e b 中存在的层次现象， 所以对w e b 社区的层次分析相当于从不同的颗粒度来分析w e b 的性质。 w 曲社区是自i n t e r n e t 诞生以来就客观存在的一些w e b 群体，它们在内容上一般都是 围绕某一主题具有一定的相关性，或者具有某一相似特性，即w e b 社区内容具有初步的 自组织性，如何发现这些潜在的w e b 社区是近几年来引起众多研究者关注的研究领域。 1 1 3 w 曲挖掘 对w e b 社区发现的研究是w e b 挖掘的一个研究方向。w e b 挖掘( w e bm i n i n g ) 就是 数据挖掘在w e b 上的应用，它是一项综合技术，是从与w w w 相关的资源与行为中抽取 感兴趣的、潜在的有用模式和隐含信息伽。w 曲挖掘包括w 曲内容挖掘( w 曲c o n t e n tm i n i n g w c m ) 、结构挖掘( w e bs t r u c t u r em i n i n g w s m ) 和使用挖掘( w e bu s a g em i n i n g w u m ) ，如图1 - 2 所示。 图1 - 2w e b 挖掘 f i g 1 2w e bm i n i n g 在图1 2 中：( 1 ) w c m 可以看作对基本搜索引擎所完成工作的扩展，它超出了基本信 息检索的范围，可以使用像概念层次、同义词、用户信息以及分析网页之间的链接等技术 改进搜索引擎的效果；( 2 ) w s m 可以看作是为w e b 组织建立一个模型，该模型是通过分析 不同网页之间的超链接结构等建立的，进而发现许多蕴涵在w e b 内容之外的对我们有潜 在价值的模式和知识；( 3 ) w u m 的研究对象是w e b 使用数据或者w e b 日志，当从服务器 的观点分析时，挖掘发现的是提供服务的网站的信息，挖掘的结果可以帮助改善网站的设 计，通过分析客户的点击序列，可以发现一个或一组用户的信息，可以帮助实现网页的预 存取和缓存。 同时，数据挖掘是k d d ( k n o w l e d g ed i s c o v e r yi nd a t a b a s e s ) 过程的一个步骤”1 ，所 以w e b 社区发现的研究也是k d d 的一个研究方向，k d d 的过程模型如图1 3 所示。 3 西安理工大学硕士学位论文 跏p 7 ：采取行计 图1 - 3k d d 过程模型 f i g 1 - 3 p r o c e d u r em o d e lo fk d d 在图1 3 中：( 1 ) 目标定义的主要目的是清楚地说明需要完成什么，应将总目标以具体 的小目标的形式陈述出来；( 2 ) 一组可行的资源数据对任何一个成功的数据挖掘项目来说都 是最重要的；( 3 ) 数据预处理是数据清理的一种形式，它包括解决噪声问题和处理缺失的信 息；( 4 ) 由于诸多原因，数据转换是非常必要的，它可以采用多种形式；( 5 ) 知识发现的实验 性和迭代性在知识发现过程中表现得非常明显，数据挖掘完成后，就会对模型进行评估； ( 6 ) 解释和评估的目的是确定学习者模型是否是可接受的，而且可以用于解决检验环境领域 以外的难题，如果取得了可接受的结果，就到了将所获得知识转换为用户可以理解的术语 的阶段；( 7 ) 数据挖掘的最终目标是应用所学到的东西，由知识挖掘过程的成功应用而可以 采取的一组可能的行动，用在知识发现过程中学习到的知识推动新的科学研究。 1 1 4 链接分析的应用 链接分析技术在w e b 信息发现与挖掘中有着广泛的应用： ( 1 ) 链接分析技术有助于改进网络信息检索质量 以网页为检索对象，以链接分析为核心算法的网络信息检索，打破了线性存储的限制， 为用户提供了比传统的信息检索范围更广泛的检索空间。在搜索引擎的网页爬行方面，超 链分析方法可以优化爬行策略，在搜索引擎检索结果的评价和排序方面也是超链分析方法 的重要应用领域，如百度、y a h o o ，g o o g l c 等搜索引擎就采用了链接分析技术来对检索结 果排序。 ( 2 ) 链接分析技术有助于扩大网络主题和社区发现空间 网页作者在创建链接的过程中并不是随意和无序的，通常会对自身的主题内容和链接 需求进行评价，以其通过信息流动来获得网络的认可。他们通常会有选择地优先考虑那些 他们认为是重要性或是权威性较高的网页。因此具有相近社会背景或是学科背景的网页会 通过超链接逐渐聚集在一起，形成个个的主题集合。通过网页和超链接可以方便地扩展 4 绪论 主题空间，从而使用户就某一主题形成具有社会学属性的社区提供了平台。 ( 3 ) 链接分析技术有助于提高网络资源的评价质量 受欢迎的网页点击率一般较高，从直观上看，链接分析可以作为判断网页重要性和网 络生命力的重要因素之一，这些在超链分析算法产生和改进方面都产生了深刻的影响。以 网络社会学为基础的超链接网络理论，立足于网页作者的社会学属性，将作者的主观判断 和理性选择作为评价网络资源的基础。通过评价有助于优化网页设计，尤其是通过提高链 接的有效性，如减少悬空链接或死链接来提升自身的认可程度。此外，还可以根据网络链 接结构，来分析站点的联系程度、集中度，通过网络结构的布局分析合理配置资源，以保 证信息传输的顺畅和用户期望的实现。 另外，网络计量学在网络资源评价研究领域占有十分重要地位，而超链分析也是其重 要研究工具之一，以用来发现核心网站。用链接分析法进行统计网站被链接和访问次数， 可以作为评价网站和网络信息资源质量的一个指标，再加上相应的链接文字分析，就可以 脱离对词频统计的依赖对搜索结果进行的按相关性排序。链接关系直观地反映了全球范围 内的同一主题类属的影响力，可以说，超链分析为网络资源评价提供了一个自然实用、易 于操作的方法，并在一定程度上可以弥补诸如同行评议等定性方法的缺陷。 ( 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 社区发现研究提供了基础，即研究w e b 社区发现的一个首要问题就是要为w e b 的链 接结构给出一种合理的描述。 1 2 课题研究现状及意义 1 2 1 国内外研究现状 w e b 社区发现研究是近几年众多研究者关注的研究领域，许多研究还处于起步阶段， 还需研究者更加深入地认识和探讨。 人们对于w e b 社区的认识来自于对w w w 结构的分析，在w e b 拓扑结构特征和建模 方面，经历了从经验假设到客观分析，从单纯的计算机网络研究到复杂系统特征化研究的 5 西安理工大学硕士学位论文 过程。1 9 9 6 年d o a r 提出了等级模型，刻画了互联网所具有的层次特性：w a t t s 和s t r o g a t z 于1 9 9 8 年提出了小l 兰界网络w s 模型，比较合理地反映了既不完全规则也不完全随机的 w e b 网络的统计特性；1 9 9 9 年f a l o u t s o s 等人发现了w e b 拓扑结构中度的幂定律分布现象； 随后b r o d e r 等人对w e b 图的连通性进行了研究，提出了“蝴蝶结”状的w e b 连通域结构 图，并指出这些连通域的规模同样服从幂数定律分布；k u m a r 等人基于互联网拓扑特征 就w e b 图进行了数学建模研究，并提出了一种随机拷贝的机制来模拟w e b 超链接的创建 过程；此外，h u b e r m a n 和a d a m i c 提出了网站规模分布服从幂数定律的h a 模型，b a r a b a s i 等人提出了网页节点的度分布服从幂数定律的b a 模型，并用偏好性依附解释了幂数分布 形成的机制等，为人们对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 a r r yp a g e 和s e r g e yb r i n 在1 9 9 6 年发明了p a g e r a n k ，是一项利用威 望值改善w e b 搜索结果的技术。华盛顿大学计算机科学与工程系的m a t t h e wr i c h a r d s o n 和p e d r od o m i n g g o s 提出了结合链接和内容信息的p a g e r a n k 算法，增加考虑了用户从一 个网页直接跳转到非直接相邻的但是内容相关的另外一个网页的情况。斯坦福大学计算机 科学系t a h e rh a v e l i w a l a 提出了主题敏感( t o p i c s e n s i t i v e ) p a g e r a n k 算法【1 0 1 ，这些改进 的p a g e r a n k 算法可以用来发现与主题相关的w e b 社区，但在发现社区数量上还需进一步 研究。 美国康奈尔大学教授k l e i n b e r g 和g i b s o n 等人提出的h i t s 算法模型提供了一种很自 然的方式【1 1 l ，将链接的结构用一组中心性网页和权威性网页展现出来，尽管这些中心性 网页和权威性网页之间并不知道相互的存在，但是可以将这一组中心性网页和权威性网页 理解为一个w e b 社区。由于这种w e b 社区的定义是完全基于结构的，可以在不知道特定 主题的情况下发现它们，并不是说将整个w e b 分割成许许多多个这样的社区。k l e i n b e r g 等人认为需要通过用一小部分高权威性的相关网页来表示社区的主题。利用h i t s 算法除 了依赖于主题的广泛性之外，同时还依赖于w e b 知识结构，那些在w e b 上存在更多甚至 更合理链接的主题，利用h i t s 具有较好的结果。针对那些在w e b 中体现较少链接的主 题，h i t s 的效果便不令人满意。所以此方法缺乏对w e b 社区的一种清晰描述，使得在没 有给出特定主题描述时，无法从w e b 中有效地抽取潜在的社区。 k u m a r 等人从二分有向图的角度对w e b 社区给出了一种明确的定义描述【1 2 j 。根据随 机二分图的理论，一个足够大而稠密的随机二分图将以很高的概率包含一个完全二分有向 图。如果将某个社区的链接结构看作一个大而稠密的二分有向图，则社区的核就可以用一 个完全二分有向图来表示。即如果在w e b 上存在一个某种主题的社区，那么这种二分的 核必包含在其中，即指出w e b 的创建过程虽然是分布的、无计划的过程，但决不是随机 6 绪论 的过程，新超链接的创建与w e b 中已存在的超链接具有某种依赖关系。但对于如何确定 核的参数，以及采用怎样的方法从整个w e b 结构图中枚举出所有社区的核，k u m a r 等人 并没有为核参数声明特定的值。 g f l a k e “”最先提出通过最大流算法来抽取w e b 社团，采用分配给各边一个相同 的容量值的办法来解决h i t s 算法存在的主题飘移问题，但对社区的质量和数量也会带来 许多不利的影响。而且随着w e b 图的增加。噪音页面也会增加。文献“5 。对最大流算法 发现w e b 社团进行了试验评价及分析。i b ma l m a d e n 实验室在w e b 社区研究方面取得了 一些重要的进展“”，开发了a r c 系统和c l e v e r 系统，其研究的基础仍然起源于链接分 析算法h i t s 。 近年来，国内许多研究学者对w e b 社区发现进行了研究。中国人民大学信息学院对 w e b 社区发现技术进行了综述“”，对社区的发现技术做了较为全面的分析，并提出了w e b 社区未来的研究趋势。复旦大学计算机与信息技术系，提出基于图论的频繁模式挖掘w e b 权威页面和社区“”，选择了惟一标号图进行分析，集图论和频集生成a m g m 算法和s f p 算法，有效地挖掘简单图中连通频繁子图，但在如何从惟一标号图中产生连通频繁图方面 还需要更进一步的研究。复旦大学还运用s f p 算法构造了e s f p 算法，完成从复杂的网络 拓扑结构中提取权威的页面和社区啪1 ，该算法减轻了用户需要花费大量时间过滤搜索引擎 返回的不满意的结果问题，但在具有相同结点的权重处理上还需要更加数学化或接近实际 含义的计算方式。中南大学信息科学与工程学院也开展了w e b 社区的相关研究o ”，指出 了基于链接结构的社区发现算法的缺陷和改进方向。中科院计算技术研究所对文本聚类及 其在w e b 社区搜索中的应用进行了研究o ”，利用文本聚类重新组织搜索结果以提高w e b 社区信息检索效率，并且利用聚类验证评估了文本聚类算法的性能。 上述研究必将丰富和进一步推动国内外关于w e b 社区发现及相关技术的研究与发 展，也会引起更多研究者的关注和参与。 1 2 2 课题研究意义 w e b 社区可以对互联网进行各种意义上的划分，反映w e b 中普遍存在的、复杂的聚 团关系和层次关系，将其应用到搜索引擎中可减少搜索引擎在需要处理的信息量方面的负 荷，从而使其在处理信息搜索请求时可以在一个较小的范围内对信息进行更加深入的分析 匹配。因此，通过合理的策略快速发现海量w e b 页面中的w e b 社区，已成为近年来信息 检索及搜索引擎研究中的一个热点问题。 w e b 社区是w e b 组织中非常重要的信息，从w e b 中系统地抽取社区或者发现隐式的、 动态自发形成的w e b 社区具有重要的理论和应用价值： ( i ) 可以更清楚地理解w e b 的拓扑关系，迸一步分析w e b 拓扑所对应的功畿或语义内涵， 进一步挖掘出个体之间的交流关系； 7 西安理工大学硕士学位论文 ( 2 ) 提高w e b 搜索的性能和精确性； ( 3 ) 实现更有效的w e b 路由、研究w e b 的鲁棒性、发现隐藏在大规模空问中的功能和规 则化的知识； ( 4 ) 可以进一步分析网络话题的生成与大规模传播及话题内涵演化的各种规律： ( 5 ) w e b 社区可以引导用户找到感兴趣的、有价值的，甚至是最及时、可靠的信息； ( 6 ) 门户网站通过识别和区分w e b 社区，可以有效地组织它们的目录层次，使得互联 网的信息聚类成为可能； ( 7 ) 可以帮助制造商准确地找到消费者； ( 8 ) 可以帮助我们纵观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 社区所 表现的新型社会关系正逐渐改变着人类的真实世界。 1 3 本文主要研究内容 本论文通过分析w e b 数据特征、w e b 超链接和w e b 社区结构的特点，围绕链接分析及 w e b 信息搜索等技术，对基于链接分析的w e b 社区发现及其应用进行了具体深入的研究， 本论文的主要研究内容包括： ( 1 ) 分析了w e b 数据特征及分布，总结了国内外对w e b 社区发现的研究成果； ( 2 ) 研究了w e b 拓扑结构建模方法、w e b 拓扑结构模型和w e b 信息检索模型； ( 3 ) 深入研究和探讨了基于链接分析的w e b 社区发现典型算法及改进算法，并对各种方 法进行了评价和总结； ( 4 ) 在现有检索软件工具包的基础上，构建了基于链接分析的w e b 社区发现应用系统， 完成了应用系统的设计流程及实现方案。 8 基于链接分析的w e b 拓扑结构建模及信息检索 2 基于链接分析的w e b 拓扑结构建模及信息检索 2 1 链接分析的理论基础 超链接是w e b 的重要元素，它将分布的网络信息有机地联系起来。链接分析 ( h y p e r l i n ka n a l y s i s ) 也称结构分析( s t r u c t u r ea n a l y s i s ) ，它是以超链接为主要输入， 对网络链接的自身属性、链接对象、链接网络等各种现象进行分析，以便揭示其数量特征 和内在规律的一种研究方法。 基于链接分析的算法，提供了衡量网页质量的客观方法，独立于语言，独立于内容， 不需人工干预就能自动发现w e b 上重要的资源，挖掘出w e b 上重要的社区，自动实现文档 聚类。 2 1 1 链接分析的来源 链接分析的思想来源于引文分析理论。科学计量学认为科学文献之间并不是孤立的， 而是通过参考文献存在着相互引证的关系。引文分析是科学计量学用来研究这种引证关系 的方法，通过各种数学方法对科学期刊、论文、著作等各种分析对象的引用或被引用现象 进行分析研究，以便揭示其数量特征的内在规律，达到评价、预测科学发展趋势的目的”1 。 如图2 - i 说明了文献引用关系。 一 图2 - 1 文献引用 f i g 2 - 1 t h el i t e r a t u r ec i t a t i o n 在图2 - 1 中，论文尺参考了论文c ，论文尺就有了一篇参考文献c ，而论文c 则有了 一篇引文r ，如果将所有具有引用关系的论文连接起来，就形成了引文网络。在该网络中， 存在两种主要的引用关系，如图2 2 ( a ) 为文献耦合，即同时引用同一篇文献，图2 - 2 ( b ) 为文献同引，即被别的文献共同引用。 绢飙 ( a ) 文献耦合关系( b ) 文献同引关系 ( a ) t h er e l a t i o n s h i po fl i t e r a t u r ec o u p l i n g ( b ) t h er e l a t i o n s h i p o f l i t e r a t u r ec i t a t i o n t o g e i h e r 图2 2 文献引用关系 f i g 2 2 t h er e l a t i o n s h i po fl i t e r a t u r ec i t a t i o n 9 西安理工大学硕士学位论文 文献耦合和文献同引可以有效揭示科学文献之自j 的某利i 内在联系，可以客观反映科学 活动过程中的许多隐减在深层次的相关关系。 在w e b 出现后，人们将这一理论应用到了w e b 链接结构分析中，用来挖掘w e b 中所隐 藏的信息。有人研究w e b 链接结构把它作为发现含有有用资源的工具。还有人研究网页的 链接结构对网页进行聚类和分类，及利用w e b 链接结构来改进基于关键词的搜索引擎的结 果。尽管链接分析方法的理论还不是非常成熟，在很多应用领域仍是尝试性的，但在w e b 信息领域中链接分析技术对于扩大网络知识发现空间、以及发现有价值的结构信息等方 面，具有极为重要的意义。 2 1 2 链接分析与引文分析的异同 引文分析的方法和思路被广泛应用于w e b 链接分析研究中，并产生了深刻的影响，但 两者之间存在着不同： ( 1 ) 链接分析中的数据已经数字化、分析的范围更广、指向的对象是超媒体的、动态 性强，而引文分析中的关系是静态的、单一的。 ( 2 ) 引文关系的建立是基于一定的规范性约束，引文分析只统计参考文献数据就可完 成引文分析的任务，体现科学文献的学术价值关系，而链接分析在操作上更加复杂，因为 w e b 网页的发布缺乏合理的组织和程序约束，使得w e b 信息过载和信息污染现象严重。 ( 3 ) w e b 的商业化营运，使得网站被链接数量往往具有不可忽视的商业背景，使网页 之间的超链接关系变得十分复杂。 2 2w e b 超链接 2 2 1w e b 超链接目的性研究和类型划分 a w e b 超链接目的性研究 w e b 信息的发布和超链接的使用既无统一的标准，也没有权威机构审查，带有极大的 主观性和随意性。其目的可分为四类：第一类是基于学术的目的。第二类是基于社会的目 的。第三类是基于技术的目的。第四类是将链接作为价值增值的手段。多数链接行为的产 生是多种动机共同驱动的结果。 b w e b 超链接的类型划分 对于w e b 超链接的类型，研究角度不同而结论各异。 根据功能不同，可分为基本结构链接、组织和推理链接以及导航链接；根据链接的方 式可分为实链接和虚链接；根据链接的端点，可分为双端点链接、多端点链接、单端点链 接和无端点链接；根据链接的存在范围，可分为网页内链接、站内链接和站间及站外链接 1 0 基于链接分析的w e b 拓扑结构建模及信息检索 等；根据超链接的方向可分为向上链接、向下链接、交叉链接和向外链接。 2 2 2w e b 超链接的特征 w e b 链接特征是w e b 链接属性的总和。w e b 链接具有形式、数量、分稚规律、作用等 多方面的属性。虽然w e b 中的链接数量巨大，形式复杂，分布情况各异，但在数量、分布 方面的信息能依靠程序自动分析，并获取较精确的结果。所以可从w e b 超链接数量特征、 分布特征及链接对w e b 的影响力等几大方面加以研究。 2 2 3w e b 超链接与w e b 信息内容的关系 超链接结构由信息节点和链接组成。节点是围绕某一特殊主题组织起来的数据信息单 元；链接是将不同的节点联系起来的工具，是表现节点之间关系的实体。在w e b 中，网页 都不是孤立的，它们之间的超链接关系也不是任意和无序的，而是存在某种内容关系： a 内容关联 如果节点p q ，则p 和q 之间在内容上往往存在较大的相似性。可以将w e b 中两个 节点之间的属性相关度看成它们所包含内容的相似度。即存在链接关系的网页问，其描述 的主题一般都具有较为相似的背景。 b 内容群集 如果节点p 、q 、s 的信息内容相似，节点u 的内容与p 、q 、5 的信息内容不同，则 p 、q 、s 之间存在超链接的机会将远大于它们同“的链接。即在w e b 中相似主题的节点 间一般都存在着大量的链接，形成多个核心集合。核心集合中的节点之间的链接关系最为 密切，内容也最为相近。随着内容相似度的降低，相互间的链接也会逐渐减少。 c 内容的可见度 如果节点p 的入链数量为个，节点口的入链数量为m ，且a 、b 描述相同主题， 如果，n ，材，贝q 节点p 被用户发现和访闯的可能性就要比q 大，即p 比露更具权威性。 d 质量递推 如果节点p g ，且p 质量较高，那么口的信息质量也相应较高。因为节点不会选择 质量较低劣的目的节点进行链接的，另外，如果一个节点有很多高质量的节点指向它，则 该节点质量更具权威性。 2 2 4w e b 超链接信息获取 w e b 超链接是网络信息之间联系的桥梁，是探索网络空间结构和进行网络知识挖掘的 工具。在研究实践中首要解决的问题就是如何结合定量、定性方法来获取和描述链接信息， 西安理工大学硕士学位论文 超链接数据信息的获取途径等研究仍是链接分析研究者们关注的话题。 超链接数据的收集可以通过访问搜索引擎或使用w e b 爬行工具来获德。为了提高超链 接提取的质量和效率，可对链接信息进行深层次的研究，对网页进行分析并准确提取出其 中有价值的u r i 信息，最终将所有满足条件的链接信息提取出来，将不满足条件的结果过 滤掉。 链接分析的重点在于获取蕴藏在链接数据背后的关系信息，这些信息的获取有两种途 径：直接访问法和计算机辅助评价方法。赢接访问法只适用于小规模的链接信息分析。为 了研究大规模w e b 的需要，如何借助计算机程序进行链接信息收集和分析是重点。利用计 算机辅助软件进行定量分析虽然可以提高研究分析的效率，但在应用中仍有局限性，因此 在理论上应实现定量分析和定性分析的结合，在实践中如何实现这种思想，则需随着研究 的深入不断发展和完善。 2 3w e b 拓扑结构建模 “结构决定功能”，即一个复杂系统的拓扑结构往往决定了该系统所具有的功能及相 关分布特性。因此，人们对w e b 的研究更多立足于对其宏观和微观拓扑结构及相关规则进 行分析而获取对w e b 系统化认识。 人们研究w e b 建模的目的，就是如何建立一种模型，展示微观的相互作用的w e b 的动 态增长过程，并能够模拟出真实w e b 拓扑结构的统计特征。 w e b