（应用数学专业论文）web社区中话题的发现与排序.pdf

摘要 随着w e b 社区的蓬勃发展，互联网正逐步跨入社区时代。w e b 社区以其开 放性、互动性和共享性深得广大网民的喜爱，成为网民表达思想、获取信息、互 相交流以及建立社交圈的主要平台。如何对社区中的资源进行分类、整理、排序， 将优质、有效的资源推荐给用户，以有效地提高社区资源的分享和利用，具有重 要的意义。 本文面向虚拟社区领域，使用话题发现技术和话题排序技术对其话题信息进 行挖掘。在话题发现中，本文通过选择合适的话题发现模型对从w e b 页面中提 取的与话题相关的主题进行分析，然后运用单遍聚类算法实现了话题发现；在话 题排序中，本文根据社区网页特点建立了话题排序特征模型，然后根据话题排序 得分实现了话题排序。通过话题发现和话题排序，本文实现了将社区中的信息按 照所表达的主题进行归类和组织，并以有序的形式展现给用户，从而有效地管理 和组织了社区中的信息，可方便用户在动态变化的社区环境下查看自己感兴趣或 需要的信息。 本文的创新点如下： ( 1 ) 在话题发现和建立话题模型时，将主题与评论相结合，从而使获得的 话题信息更为全面。 ( 2 ) 在话题排序时，本文通过对w e b 社区网页进行分析，选出话题的最近 发布时间、最远发布时间、主要发布时间、被点击次数、被评论次数、当前评论 增长速度，平均评论数和当前评论数作为排序特征，从而解决了传统话题排序 中使用单一的点击数或更新时间来进行话题排序的不足。 ( 3 ) 在确定权重向量时，结合用户参与评判的方法提出了一种新的确定排 序特征向量权重的方法，实验证明，通过该方法得到的权重向量使本文得到了较 好的排序结果。 本文的实验对象为国内最大的三个社区网站：猫扑大杂烩、天涯社区和腾讯 社区。实验证明，本文所提出的社区话题发现和排序方法是可行的，且排序 结果良好。 关键词：w e b 社区；主题信息提取；主题分析；话题发现；话题排序 a b s t r a c t w i t ht h ev i g o r o u sd e v e l o p m e n to fw e b c o m m u n i t i e s ，t h eh a t e i t i e ti sg r a d u a l l v e n t e r i n gt h ee r ao ft h ec o m m u n i t y w e bc o m m u n i t yi s b e c o m i n gm o r ea n dm o r e p o p u l a rw i t ht h em a j o r i t yo fi n t e r n e tu s e r s i t so p e n n e s s ，i n t e r a c t i o na n ds h a r i n gh a s m a d et h e mb e c o m eam a i np l a t f o r mf o ri n t e r n e tu s e r st o e x p r e s si d e a s ，a c e e s st o m f o r m a t i o n ，m u t u a le x c h a n g e ，a sw e l la se s t a b l i s h t h e i rs o c i a lc i r c l e s h o wt o c l a s s i f y , a r r a n g ea n dr a n kt h er e s o u r c ei nc o m m u n i t yt or e c o m m e n dt h ee f f i c i e n t r e s o u r c et ou s e r sa n di m p r o v et h e s h a r i n ga n du s i n go fc o m m u n i t yr e s o u r c e e f f e c t i v e l yh a si m p o r t a n ts i g n i f i c a n c e t h i sp a p e ru s e st o p i cd e t e c t i o na n d t o p i cr a n k i n gt e c h n i q u e st om i n et o p i c k n o w l e d g ef r o mt h ec o m m u n i t y i nt o p i cd e t e c t i o n ，t h i sp a p e ra n a l v z et h et h e m e w h i c hi sr e l a t e dt ot h et o p i ci nt h ew e b p a g eb ys e l e c t i n gaa p p r o p r i a t et o p i cd e t e c t i o n m o d e l ，t h e nu s e ss i n g l e 。p a s sc l u s t e r i n ga l g o r i t h mt od i s c o v e r yt h et o p i c ；h a t o p i c r a n k i n g ，t h i sp a p e ra c c o r d i n gt ot h ec h a r a c t e r i s t i c so fw e b p a g et oe s t a b l i s ht h et o p i c r a n k i n gf e a t u r em o d e l ，t h e na c h i e v e dt or a n k i n gt h et o p i c sb yt h et o p i cr a n k i n g s c o r e a f t e rt o p i cd e t e c t i n ga n d t o p i cr a n k i n g ，t h i sp a p e ra c h i e v e dt oo r g a n i z et h e c o m m u n i t yi n f o r m a t i o nb ys u b j e c ta n dd i s p l a yt h e mi na no r d e r e df o r m ，s oi tc a nh e l p u s e r se x a m i n et h e i ri n t e r e s t e do rn e e d e di n f o r m a t i o n t h ei n n o v a t i o no ft h i sp a p e ri sa sf o l l o w s ： ( 1 ) c o m b i n et h e m ew i t hc o m m e n ti nt o p i cd e t e c t i o na n dt o p i cm o d e l t h i s m a k e st h et o p i ci n f o r m a t i o nm o r e c o m p r e h e n s i v e ( 2 ) i nt h et o p i cr a n k i n gt e c h n i q u e ，a f t e rt h ea n a l y s i so fw e bc o m m u n i t i e s p a g e , t h i sp a p e rs e l e c t st h el a s t ，t h ef i r s ta n dt h em a j o rt i m et h a tt h e t o p i cw a sr e l e a s e d c l i c k s ，t h en u m b e ro fc o m m e n t s ，t h eg r o w t hr a t eo ft h ec u r r e n tc o m m e n t s ，t h ea v e r a g e n u m b e ro fc o m m e n t sa n dt h ec u r r e n tn u m b e ro fc o m m e n t sa st h es o r tf e a t u r e s n i s w o r ks o l v e st h ed e f i c i e n c yo f r a n k i n gt o p i c so n l yb yu s i n gc l i c k sa n du p d a t e dt i m e ( 3 ) i nd e t e r m i n i n gt h ew e i g h tv e c t o r s ，b a s e do nt h eu s e ri n v o l v e m e n te v a l u a t i o n m e t h o d ，t h i sp a p e rp r e s e n t san e wm e t h o dt od e t e r m i n et h er a n k i n gf e a t u r ev e c t o r w e i g h t s - t h ee x p e r i m e n ts h o w st h a tt h ew e i g h tv e c t o r st h a to b t a i n e db vt h em e t h o d m a k e st h ep a p e r g e tg o o dr a n k i n gr e s u l t t h ee x p e r i m e n t a ls u b j e c t so ft h i sp a p e ra r et h el a r g e s tt h r e ec o m m u n i t vs i t e s ： m o ph o d g e p o d g e ，t i a n y ac o m m u n i t ya n dt e n c e n tc o m m u n i t y t h ee x p e r i m e n t i l r e s u l t ss h o wt h a tt h em e t h o do ft o p i cd e t e c t i o na n dt o p i cr a n k i n gf o rc o m m u n i t yi n t h i sp a p e ri sf e a s i b l ea n dt h i sr a n k i n gm e t h o dw o r k sw e l l k e yw o r d s ：w e bc o m m u n i t y ；s u b j e c ti n f o r m a t i o ne x t r a c t i o n ；s u b j e c ta n a l y s i s ；t o p i c d e t e c t i o n ；t o p i cr a n k i n g i i i 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 武汉理工大学或其他教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示了谢意。 签名：主奎2 盔置 日期： 2 丝z 望：望 学位论文使用授权书 本人完全了解武汉理工大学有关保留、使用学位论文的规定， 即学校有权保留并向国家有关部门或机构送交论文的复印件和电 子版，允许论文被查阅和借阅。本人授权武汉理工大学可以将本 学位论文的全部内容编入有关数据库进行检索，可以采用影印、 缩印或其他复制手段保存或汇编本学位论文。同时授权经武汉理 工大学认可的国家有关机构或论文数据库使用或收录本学位论 文，并向社会公众提供信息服务。 ( 保密的论文在解密后应遵守此规定) 研究生( 签名) ：受辛? 搦 导师( 日期? 群j 2 j 2 武汉理t 大学硕二e 学位论文 1 1 研究目的和意义 第1 章引言 随着计算机尤其是网络技术的发展，在线社区或者称之为虚拟社区( v i r t u a l c o m m u n i t y ) 的应用形式在互联网上蓬勃发展。虚拟社区这种新的电子社会行为 越来越显著的影响着传统社会中的每一个成员，虚拟社区可以给成员带来新的 交流方式、工作方式、协同合作方式，甚至是影响到生活的每一个角落如购物， 交友等。虚拟社区在互联网上以前所未有的速度增长，以至于理论研究远远 落后于应用实践，这为我们提供了许多值得研究的课题。这些研究课题涉及信 息技术、社会学、心理学、经济学、管理学等等各个方面。 最早的关于虚拟社区的定义由瑞格尔德( r h e i n g o l d ) 做出，他将其定义为 “一群主要籍由计算机网络彼此沟通的人们，他们彼此有某种程度的认识、分 享某种程度的知识和信息、在很大程度上如同对待朋友般彼此关怀，从而所形 成的团体。 国外分别有“v i r t u a lc o m m u n i t y 、“o n l i n ec o m m u n i t y 、“e l e c t r o n i c c o m m u n i t y 、“c y b e r s p a c ec o m m u n i t y 、“c o m p u t e r m e d i a t e dc o m m u n i t y ”和“w e b c o m m u n i t y 等名称，而我国则有“在线社区 、“网上社区 、“网络社区 、“虚 拟社区 、“虚拟社群 等不同叫法。 随着社区技术的高速发展和社区应用的普及成熟，互联网正逐步跨入社区 时代。从论坛b b s 、校友录、博客( b l o g ) 、个人空间、s n s 交友等新旧社区应 用，到社区搜索、社区聚合、社区营销、社区资源共享等话题，都是业界关注 的热点。互联网社区在2 0 0 8 年取得了高速的发展，中国网民对论坛b b s 讨论组 论坛社区等的应用已经超过即时通讯，成为仅次于搜索引擎的互联网基本应用。 以b b s 、新闻组为基础应用的论坛类网络社区在中国历经1 0 余年的发展， 拥有了比较庞大的用户群体。根据“中国互联网络信息中心 统计数据【l 】，截至 2 0 0 8 年6 月，中国有1 9 1 万家( c n n l c ) 独立网站，从门户到行业网站，从地 区门户到个人站点，8 0 以上网站均拥有独立社区。社区类网站月度覆盖人数上 升迅速，社区用户月覆盖人数超过1 4 亿。网络社区的开放性、互动性和共享 性深得广大网民的喜爱，网络社区作为广大普通网民发表自身言论和思想的有 效载体和平台，代表着草根文化潜在的巨大价值和影响力，成为网民表达思想、 武汉理工大学硕士学位论文 展示自我、获取信息、与其他网民互动互通以及建立社交圈子的主要平台，在 中国的发展十分迅速。网络社区用户覆盖人数的稳定增长，表明其已经成为主 流网络应用之一。 w e b 社区成为社会舆论最重要的传播载体。调查显示1 1 1 ，中国网民的主体是 3 0 岁及以下的年轻群体，这一群体占到网民总数的6 8 6 ，他们更加习惯通过 互联网获取新闻信息、表达意见。2 0 0 8 年以来，由于互联网的影响，有些地方 性、局部性的事件一夜之间被放大，成为全国关注的话题。以拉萨“3 1 4 ”事件 和汶川“5 1 2 地震为标志，网络社区已经成为社会舆论最重要的策源地。网络 社区正在全面渗透到社会生活的每个方面，并成为社会舆论最重要的传播载体。 网络社区的迅速发展弱化了政府对社会信息的控制力，如何有效的监控、引导、 管理网络社区的舆论发布和传播，如何整治互联网低俗信息的传播【到，具有重要 的研究意义和应用价值。 w e b 社区中包含了丰富的资源和知识。用户的相互交流、话题和资源的发 布、相互的咨询和帮助、问题的讨论形成了丰富的知识网络，基于w e b 社区的 讨论有助于提高组织中的协作、知识创新和知识传播。对w e b 社区内的知识进 行结构化、有序的分析和整理，有效的对w e b 社区知识进行分享具有重要的意 义。在用户浏览社区资源时，“推荐”、“t o p ”、“精华类型的社区资源受到用 户浏览频次最高，占6 6 2 1 3 1 。如何对社区中的资源进行分类、整理、排序，将 优质、有效的资源推荐给用户，以有效地提高社区资源的分享和利用，具有重 要的意义。 w e b 社区中包含了丰富的用户资源。用户是社区的主体，2 0 0 8 年调查显示 【3 】：用户访问社区网站时间在在6 小时以下居多，占7 8 5 ，社区的深度用户占 比例也较高，每天访问时间在6 小时以上的达到了3 0 5 。用户在社区种的参 与程度也比较高，其中平均几天参与交流的占2 4 5 ，平均每天交流1 5 次以上 的有1 6 6 ，从来不参与的比例非常低，仅占2 7 。 社区用户根据不同的价值取向和喜好聚集成为圈子或群落，使得在社区中 的广告投放与传统网络广告相比更为精准；社区用户将社区作为发表自己思想、 见解的平台，具有较强的参与性和信息分享性，网民使用产品后在社区中分享 体验己成为其习惯性行为，其发表的观点和经验，j 下自觉不自觉地影响着圈子 中其他社区用户的消费理念、消费行为和消费决策【4 1 ，具有一定“社区知名度 的活跃用户，这种影响力更为明显。对社区中的用户进行t o p k 排序，从社区 中找到关键用户具有良好的商业价值。 2 武汉理工大学硕十学位论文 社区用户在网络交流、资源发布、情绪宣泄时，会表现出一些具有个人特 征的信息。通过对用户的言论、行为、记录、关系网络进行分析，来得到一些 用户的特征和信息，如：兴趣、特长、领域、性格、地理、年龄、性别、职业、 资产等。这些特征对识别用户需求、用户精准定位，具有广泛的商业价值。 w e b 社区数量庞大、良莠不齐。根据调查显示，截止2 0 0 8 年，社区应用的 主要方式论坛数量已经达到1 3 0 万个i 引，b l o g 空间数达到1 0 7 亿【2 1 。社区涉及 的领域也比较广阔，其中排名第一的是门户类，占比达1 6 9 ，其次是互动娱乐 类，为1 2 5 ；i t 产业和教育类也都在1 0 以上。社区的新生和消亡也比较普 遍，2 0 0 8 年成立的网络社区占最大比重，为4 6 3 ，其次为2 0 0 7 年，这两年成 立的社区比重达7 4 7 。社区的差异主要表现在社区内容数量和质量、社区中用 户状况、社区的结构组成等多个方面，用户在从社区中获取资源和信息时，会 存在难以抉择的问题，如何找到本领域中最优质的网络社区推荐给用户使用， 具有重要的应用价值。 本文重点研究从w e b 社区中挖掘不同时期的热点话题并对之进行排序的理 论和方法，方便社区用户分享、浏览社区资源，促进w e b 社区的建设和繁荣。 这对于政府有关部门有效的监控、引导、管理w e b 社区的舆论发布和传播，整 治互联网低俗信息的传播，具有重要的研究意义和应用价值。 1 2 国内外研究现状 1 2 1 社区研究现状 目前，w e b 社区研究，已成为互联网领域的研究热点，国内外学者和产业 界对w e b 社区的多个方面都展开了研究： 在社区发现方面，目前绝大多数的社区发现研究项目是基于w e b 页面之间 的链接结构进行的爬行、抽取、挖掘而进行的。y i n gz h o u ，j o s e p hd a v i s 【5 j 提出 了一个在b l o g 中发现社区的方法。他们将整个w e b 视为一个有向图，每一个节 点代表一个页面，每个超级链接代表一条边；通过爬行得到w e b 图的结构，他 们首先从一个种子( s e e d ) b l o g 的所有页面中找到一个超级链接的候选集合，然 后从候选集合中去掉链回种子或者没有指向b l o g 的链接，剩下的链接集合指向 了其他的b l o g 。然后再去掉有向图顶点之间的重复链接，保留重复链接的数量 作为链接权重，并使用i s l a n dp a r t i t i o n i n ga l g o r i t h m 分析方法挖掘出网络中存在的 3 武汉理：【大学硕士学位论文 虚拟社区【酣，比较典型的相关分析方法包括改进的p a g e r a n k 算法i7 1 。此外，还 有基于h i t s i 引、二分有向图和流量的技术用来挖掘潜在的社区。 在社区搜索方面，是通过集成社区资源形成索引，从而对领域内的所有社 区进行资源检索的功能。目前已有较为成熟的产品。n i l e s hb i n s a l 和n i c kk o u d a s 1 9 j 提出了一个基于文本文档( b l o g ) 的爬取、过滤、索引和搜索的方法。通过维 护r s s 信息来实现信息的集成。刘务华，罗铁坚，王文杰等【1 0 l 在分析w e b 社区 搜索资源分散特点的基础上，运用w e b 抓取器、向量空间模型和相关性排序等 技术设计了w e b 社区搜索引擎的体系结构，实现了一个w e b 社区搜索引擎系统 c h i n a l a b s e a r c h 。 在社区分析方面，包括社区中人和人关系的分析，主题和内容的分析，个 人爱好和信息的分析，组成结构分析等。分析方法包括使用图论来对基于链接 网络的社会关系分析，j u r el e s k o v e c 等人【1 1 】利用s u b m o d u l a r i t y 算法构造突发事 件预警模型，能够低成本的快速发现社区中的突发热门事件；p a r a gs i n g l a l l 2 l 研 究了利用1 m 进行交流的群体的关联性和兴趣分享，从而实现个人行为的分析； j i a w e ih a n 等人建立了一种基于最优线性组合的学习方法，来对多关联复杂社会 网络中的隐藏信息进行挖掘【1 3 j 以及对异构社会网络进行挖掘【1 4 】；r o l fa e m u e l l e r 等人利用供应链模型对社会网络进行分析【1 5 】。还一种分析是使用语义模 型对人们之间的主题和内容进行分析，p e t e rm i k a 构建了基于语义w e b 技术的 f l i n k 社会网络抽取和分析系统【1 6 】，以及统一的社会网络语义模型o n t o l o g i e s l l 7 1 。 另外还有利用潜在空间模型对动态社区进行分析【1 8 】，有对社区网络的演变进行 实证分析1 1 9 】，以及不确定性社区分析【2 0 】等。国内有牛军钰等人对社区用户进行 特征时空建模和挖掘1 2 ，徐从富等对异构关系的社区挖掘1 2 2 1 。 在社区评价方面，主要是通过用户的反馈和关系密集度来对社区进行评价。 y i w e ic a o ，a n n ag l u k h o v a i 冽等以游戏社区为例子，分析了社区成功的因素，提 出了社区评价的统计方法。r o b e r tm c c a n n ，a n h a id o a n l 2 4 j 等利用在线问答形式 获得用户的反馈，并利用用户反馈的质量对用户进行评价，获得用户的权重。 gv e l a y a t h a n 和s y a m a d a l 2 5 j 给出了一个基于用户行为的方法用于评价网页的 质量。 与本文相关的研究内容主要包括w e b 社区中的话题发现和排序两个方面， 下面将进行概述。 4 武汉理j 二人学硕十学位论文 1 2 2 社区中的话题发现与排序 话题发现源自t d t 领域，t d t 技术( t o p i cd e t e c t i o na n dt r a c k i n g ，话题识 别与跟踪) 是由美国国防高级研究计划署( d a r p a ) 倡导的一项研究，涉及到 网络形式的新闻报道，并取得了一定成果【孤捌。话题识别是指自动识别信息片 断集合中的各个未知话题，并能在线检测出新话题。话题跟踪是指在各种信息 来源中追踪那些讨论目标话题的相关信息片段1 2 引。 自1 9 9 6 年t d t 概念提出以来，国内外许多研究机构都参与了这一技术的研 究，大大地推动了相关技术的发展。 j u r el e s k o v e c 等人【1 l l 利用s u bm o d u l a r i t y 算法构造突发事件预警模型，能够 低成本的快速发现社区中的突发热门事件；多伦多大学的n i l e s hb a n s a l 等人【3 0 j ， 通过追踪b l o g 中发表的文章，发现出流行的或者最新的话题、用户组群以及相 关地理信息。r 本东京大学的n a o h i r om a t s u m u r a 教授等人 3 1 】提出影响力传播模 型i d m ，该模型利用帖子中的关键词反映人物的观点，在帖子线索中关键词传 递的多少反映其影响程度的特点，实现了对b b s 上有影响力的人物及其话题的 发现。i d m 模型的着眼点在于用户间的交互模式，通过分析帖子或用户所传递 的影响力来发现热门话题或焦点人物。后来国内蒋儿等人利用i d m 模型设计并 实现了一个主题发现原型系统【3 2 j ，该模型所使用的方法需要反复计算词语以及 词语问的影响力，并重新构造词语结构图，使得计算复杂度较大，不适合大规 模的文本计算。 在国内，邱立坤等人【3 3 】在考虑在b b s 的标题、j 下文、首帖、回帖中出现的 词分别有着不同的重要性的基础上，改进了传统的向量空间模型，即在聚类时 采用非增量的s i n g l e p a s s 算法，以各话题中平均相似度最高的帖子线索的标题 作为该话题的标题，然后应用b b s 特有的点击数、回复数进行热度排序，再采 用基于标题特征词提取的话题归并方法，归并同一主题而不同视角的话题；针 对b l o g 文本的特点，丁伟莉等人【3 4 】提出了一种应用于中文b l o g 的热门话题检 测与排序技术，通过对基于词条的向量空问模型以及词条间相似度的计算方法 的改进，节省了存储空间，减少了相似度的计算量；同时考虑到同义词和近义 词的存在问题，采用了词形和词频相结合的方法进行聚类结束，然后在每个话 题的标题中心向量中选取权重最大的两个词作为最后的话题名；最后选取话题 中的文章数、话题中文章所对应的评论条数之和、话题中的文章所对应的评论 人数之和作为话题排序的特征向量，进行线性加权组合后得到了话题的综合排 5 武汉理t 大学硕十学位论文 序。 总的来说，国外对w e b 社区的研究工作起步不久，国内才刚刚起步，有待 研究的地方还很多。在话题发现和排序的研究中已有的算法在应用到实际中时 还存在很多的不足之处，需要对聚类方法以及排序技术等加以改进。 1 3 论文组织结构 本文主要由两部分研究内容构成：第一部分研究如何从信息量庞大的w e b 社区实时、动态地发现有意义的话题；第二部分在第一部分研究的基础上设计 合理的排序模型对已发现的话题进行排序，并将排序结果展示给用户。通过对 这两部分内容的研究，力求达到将社区中当前最热门的话题展示给用户，方便 用户浏览的目的。 本文组织结构如下： 第一章是引言，概述了w e b 社区中的话题发现与话题排序的研究背景和意 义，并介绍了国内外关于w e b 社区、话题发现和话题排序的研究现状。 第二章介绍了搜集w e b 社区资源的三个关键技术，即w e b 资源发现技术、 w e b 页面净化技术和w e b 文本处理技术。 第三章主要介绍了本文的话题发现方法，即通过选择合适的话题发现模型 对从w e b 页面中提取的与话题相关的主题进行特征分析，然后运用单遍聚类算 法实现话题发现。 第四章主要介绍了本文的话题排序方法：首先根据社区网页特点建立话题 排序特征模型，然后对话题排序特征进行标准化处理，并结合用户参与评判的 方法提出了一种新的确定权重向量的方法，最后根据话题排序得分实现话题排 序。 第五章主要是对本文提出的话题发现和话题排序方法进行了实验。实验结 果表明，本文所提出的方法具有可行性，排序结果良好。 第六章总结与展望。 6 武汉理下大学硕士学位论文 第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 文本处理技术。下面分别对这些技术进行说明。 2 1w e b 社区资源的发现技术 w e b 资源主要有规模大、更新快、内容丰富、信息类型多样、信息寿命短暂、 资源价值不一和资源分布广泛无序这几个特点，这些特点使得w e b 社区成为一个 巨大而复杂的信息源。如何使用户在w e b 社区的海洋中找到所需的信息就是w e b 资源发现要解决的问题。本文将主要介绍基于链接分析的w e b 资源发现技术。 为了获取相关主题的w e b 社区资源，用户希望能够查到与给定主题相关的 w e b 页面，并且该页面具有较高的质量，称为最具权威的( a u t h o r i t a t i v e ) 页面。 有意思的是权威性通常隐藏在页面的链接之中，它们不仅由页面组成，还包括页 面之间的超链接。这些超链接包含了大量潜在的人为认可的信息，有助于确定权 威性。当个页面的作者建立指向另外一个页面的一个链接时，可认为是该作者 对另一个页面的认可。如果将每个网页看作是一个节点，每一个链接看作是一条 有向边，那么整个w e b 就构成了一个巨大的有向图。通过分析w e b 图链接结构以 确定页面重要程度的技术被称为链接分析技术。下面，介绍基于链接分析的两个 典型算法：p a g e r a n k 算法和h i t s 算法。 2 1 1p a g e r a n k 算法 p a g e r a n k 算法由s t a n f o r d 大学的b r i n 和p a g e 提出的1 3 引，是w 曲超链接结 构分析中最早、最成功的算法之一，也是最早并且最成功地将链接接分析技术应 用到商业搜索引擎中的算法。g o o g l e 搜索引擎就是通过将该算法和链接文本标 记、词频统计等因素相结合的方法对检索出的大量结果进行相关度排序，将价值 度高的网页尽量排在前面。 7 武汉理工大学硕士学位论文 p a g e r a n k 算法的基本思想是试图为搜索引擎所涵盖的所有网页赋予一个量 化的价值度，每个页面被量化的价值以一种递归方式来定义，由所有链接向它的 网页的价值度所决定，即被大量高价值网页引用( 链接)的网页也是具有很高 价值的网页。其理论基础如下： 忽略掉w e b 页面上的文本和其它内容，只考虑页面间的超链接，构造有向 w e b 图g = ，e ) ，其中顶点y 表示所有网页集合，边e 表示网页间的链接集合， 网页f 中有指向网页j 的链接表示节点f 和f 之间存在一条边。节点f 的出度是指 从页面i 出发的所有超链接( o u t l i n k ) 的总数，而入度则是指所有指向节点f 的超 链接( i n l i n k ) 的总数。假设f 。是被网页“链接的网页集合，巨。为链接网页“的 网页集合，令n ( u ) = i e i ，则网页u 的权值袱似) 为： d 、 p n ( u ) ；d d ( u ) + ( 1 一d ) y 二盟 ( 2 1 ) 。、 。魁n o ) 上式可以用一种随机网上冲浪者( t h es u r f e r s ) 模型来描述，假设冲浪者跟 随链接进行了若干步的浏览后又转向一个随机网页重新跟随链接浏览，那么一个 网页的价值度就由该网页被这个随机冲浪者所访问的频率所决定。 对于随机访问模型，存在另外两种情况，一是存在这样一类网页，它们没有 指向其它网页的链接，仅在一定范围内相互链接；另一种是出度为零的一类网页。 当用户访问到这两类网页时，按照上述模型进行访问，访问将终止或仅在某一类 网页上徘徊，它们在算法迭代过程中会不断地吸收权值，直到所有的权值都沉积 到它们上面，这种现象被称为权值沉积( r a n ks i n k i n g ) 。对于这种情况，当一个 随机冲浪者遇到了这种沉积网页时，他可以随机地挑选另一个网页并继续浏览。 为了对所有的网页一视同仁，这种类型的随机访问可以相同的概率在任何一个网 页上发生。从而得到p a g e r a n k 算法的修正形式如下： n ，、 p r ( u ) ；扣 ) + ( 1 一d ) 罗掣 ( 2 2 ) 矿邕v 吖 其中d 为跳转概率，通常被置为o 1 5 。上式表明冲浪者以概率d 不再跟随链 接浏览而是重新以分布d ) ( 一般取d 似) = 1 1 1 ) 随机地挑选一个网页进行浏览， 以概率1 一d 继续跟随当前网页中一个链接进行浏览。 p a g e r a n k 算法实现过程：将网页的u r l 对应成唯一的整数，然后把每一个 超链接用其整数l d 存放到索引数据库中，经过预处理之后，设每个网页的初始 p a g e r a n k 值为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 值作为搜索引擎结 果排序的一个参考，值越高的页面排序越靠前。 8 武汉理丁大学硕士学位论文 p a g e r a n k 算法通过分析w e b 超链接关系可大大提高w e b 检索的准确性，克 服了基于内容匹配方法的不足。p a g e r a n k 算法本身是一个著名的页面排序算法， 且与主题无关。t a h e rh h a v e l i w a l a 【3 6 j 认为用户浏览的网上冲浪者模型是基于主 题的，他们任意选择一个与自己感兴趣的主题相关的页面进行浏览，然后沿着其 链接到达与该主题相关的其他页面。根据这一思想，他将p a g e r a n k 算法改造为 与主题相关的算法，运用该算法可以发现与主题相关的社区： 艘o ) = ( 州p + ( 1 一占) t v , 毛p r ( j ) 万 2 - 3 ) 其中p ( f ，丁) 表示i 与主题r 的相关度，是衰减因子，一般取0 1 加2 ，力为 有向图g 中节点的数量，o u t l i n k ( j ) 为节点_ 包含的超链接数量。通过判断p r ( i ) 是否大于阈值来确定是否为主题的社区成员。 2 1 2h i t s 算法 h i t s 算法是由k l e i n b e r g l 3 8 j 在9 0 年代末提出的一种链接分析算法，与前面 介绍的p a g e r a n k 算法相比，h i t s 算法提供了一种更加完善的衡量网页重要程度 的度量。h 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 c s e a r c h ) 中，k l e i n b e r g 将页面分为两种类型：一种为描述某一主题的权威页面，称为 a u t h o r i t y 页面；另一种为能把这些a u t h o r i t y 页面联结在一起的页面，称为h u b 页面。h i t s 算法涉及两个重要的权值概念： a u t h o r i t y ：表示一个权威网页被其它网页所引用的加权次数，即该权威网页 的加权入度值。某一网页被引用的次数越多，则该网页的加权入度值越大，即 a u t h o r i t y 越大。 h u b ：表示一个w e b 页面指向其它网页的加权数量，即该w e b 页的加权出 度值，它提供了指向权威页面的链接集合。某一网页的加权出度值越大，则该网 页的h u b 值越大。h u b 起到了隐含说明某话题权威页面的作用。 h i t s 算法具体过程：根据用户查询请求，首先用一个现有的商业搜索引擎 进行查询，取约2 0 0 个查询结果作为算法的根集( r o o ts e t ) ，记为r q 。由于这 些页面中的许多页面被假定为与搜索内容相关，因此它们中应包含指向最权威页 面的指针。然后，对r q 中每一个节点，将所有指向该节点或该节点所指向的网 页补充进来形成基集( b a s es e t ) ，记为b q 。计算b q 中每一个网页的a u t h o r i t y 权重和h u b 权重，这是一个递归的过程。 h i t s 算法如下： ( 1 ) 为基集的每个页面赋予一个非负的a u t h o r i t y 权重和非负的h u b 权重， 9 武汉理t 大学硕士学位论文 如对任意一个网页p 可令其a u t h o r i t y 权重为a ，h u b 权重为h p ，并将所有的a p 和h ，值初始化为同一个常数，如令口，= l h p = 1 。 ( 2 ) a u t h o r i t y 与h u b 的权重可按下式计算： 口p h q ( 2 4 ) i q ：q - p ， h p 口。 ( 2 - 5 ) i q ：q p j 其中p ，q 代表网页，q p 表示网页g 通过链接指向网页p ，a ，和a 。分别表 示网页p 和q 的a u t h o r i t y 权重， 和h ，分别表示网页p 和口的h u b 权重。 ( 3 ) 每次迭代后进行规范化处理保证不变性，处理公式如下： 罗( 口吁) 2 1 ( 2 6 ) 仍 罗啦) 2 1 ( 2 7 ) 仍 其中p 代表网页， 口。表示网页q 的a u t h o r i t y 权重，h q 表示网页q 的h u b 权重。 ( 4 ) 当口，和i l l ，没有收敛时，转到公式( 2 4 ) 、( 2 - 5 ) 。 ( 5 ) 大量实验证明，经过大约1 0 - 1 5 次迭代计算，a ，和h ，的值将趋于稳定， 即迭代结束。此时，可设置阀值丁，将所有口，和h ，大于r 的网页挑选出来，排 序并输出查询结果。 k l e i n b e r g 等人通过大量的实验发现h i t s 算法对于许多查询具有良好的查准 率和查全率，且通过它所发现的社区主题和h i t s 算法根基的选择几乎无关。尽 管h i t s 算法取得了较大的成功，但由于h i t s 构造的子图通常会包含一些和主 题无关的页面，因此会存在以下一些问题： ( 1 ) 主题漂移。所谓主题漂移就是给定一个宽主题查询，主题精选算法分 析出的最好的几个权威中心信息源与用户查询相关度较低或不相关，或者仅包 涵查询宽主题的一个很“偏 的主题。由于h i t s 算法仅局限于w e b 页面之间的 链接关系，而没有考虑页面的内容，因而在应用过程中表现出不稳定性，有时会 出现主题漂移问题。 ( 2 ) 无关链接的影响。在w e b 中，一个页面上的所有链接并不都与主题相 关，它们包括站点内的导航链接，广告链接等，这些链接会极大地影响h i t s 算 法的运算效果。站点内的导航链接很好清除，但是有些链接就不那么好过滤了， 需要用到许多其他的技术。 ( 3 ) 无关页面的影响。无关页面被引入的途径有两个：一是基于相似度的 搜索引擎返回的根集中本身就包含无关页面：二是根据链接关系生成基本集时引 入的。由于h i t s 算法只是简单地根据链接关系确定权重，缺乏对页面有效性的 1 0 武汉理上人学硕士学位论文 判断，容易产生无关页面获得较大的h u b 权重和a u t h o r i t y 权重的结果，从而导 致输出的h u b 页面和a u t h o r i t y 页面与查询主题无关。 对于主题漂移问题，i b ma l m a d e n 研究中心c l e v e r 搜索引擎对h i t s 算法进 行了一些改进，提出了a r c ( a u t o m a t i cr e s o u r c ec o m p i l a t i o n ) 算法【3 9 j 。c l e v e r 考虑到两点：第一，降低无关网页的影响，这就需要对不同的链接赋予不同的权 重。第二，在算法中加入内容控制信息，根据内容的相关性调节链接的权值，使 权值的计算具有一定的偏向性。基于这两点，c l e v e r 在h i t s 算法的基础上考虑 了网页超链接的锚( a n c h o r ) 文本信息对网页排序的影响，利用链接的锚文本及 上下文信息与检索主题的相关程度来确定链接的重要性。c l e v e r 认为如果一个链 接的前后文本中都出现了关于主题的描述，则可认为当前网页和目的网页都与主 题相关，应相应地增加这个链接的权重。据此c l e v e r 构建了一个新的矩阵，在 计算网页a u t h o r i t y h u b 值时用该矩阵取代原有的网页链接子图的邻接矩阵。 为了减少无关页面的影响，j g e v r e y 和s r u g e r 于2 0 0 2 年提出了两个基于 超链接和内容的网页排序算法，即a v e r a g e 算法和s i m 算法1 4 0 1 。这两个算法与 h i t s 算法的主要区别在于：向基于内容排序的搜索引擎提交查询主题，获取根 集网页的过程中，会返回每个页面与查询主题的相似度( s i m i l a r i t y ) 值，h i t s 算法没有考虑该项信息，仅利用网页间的链接结构来计算网页的a u t h o r i t y h u b 值，而a v e r a g e 算