（计算机软件与理论专业论文）基于swn理论的文本复合关键字提取算法的研究.pdf

摘要 捅要 小世界模型( s m a l lw o r l dn e t w o r k ) 因具有高度的局部聚类性和较小的全局平均 路径长度而在许多应用领域得到广泛应用。在前人证明人类语言中也存在s m a l l w o r l d 现象的基础上，本文提出了一种基于s m a l lw o d d 模型的复合关键字提取方 法。首先，根据文档中句子的结构，以分词为节点，建立分词间的关联关系，通 过合并相关句子中相同的分词，构造文档关联( 语义) 结构图，通过必要的计算， 确定具有s m a l lw o r l d 模型特性的文档结构图。其次，引入平均最短路径变化量和 簇数变化量，计算分词在文档中的重要性，以确定单个关键字候选集。最后，综 合考虑侯选关键字集中分词间的关联关系、分词的两个变化量间相互影响的特点 及文档领域的特定需求，按相对位置合并相关分词，即提取出复合关键词。另外， 还给出了算法的复杂度的分析。实验结果表明该方法是正确的和有效的，与人为 提取的单个关键字集相比，其提取精度为8 8 3 5 。利用该方法所获得复合关键所 表达的文档的主题比单个关键字的语义来的更加清晰、准确，从而有助于我们在 更高一层对文档内容语义的理解。 关键宇：小世界模型文档语义结构 平均最短路径长度变化量簇系数变化量 复合关键词 a b s t r a c t - - _ _ _ _ _ _ _ _ _ h _ _ _ _ _ - _ _ _ _ _ _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - _ a b s t r a c t s m a l lw o r l dn e t w o r kc h a r a c t e r i z e db ys h o nc h a r a c t e r i s t i cp a t hl e n g _ 1 la 1 1 dh i 曲 c l u s t e r n gc o e m c i e n ti sw i d e l yo b s e r v e di nm a n yr e a l w o r l dn e t w o r k se s p e c i a l l yi n h u m a nl a n g u a g e i nm i sp 印e r ，w ec o n s t n l c tan e wk i n do fa l g o r i t h me x a c t i n g c o m p o l l n dk e y w o r d sf r o mac h i n e s ed o c u m e n ta s as m a uw o r l d f i r s t l y ，ac h i n e s e d o c u i n e n tw i 】lb er e p r e s e n t e db yan e t w o r k ：m en o d e sr e p r e s e n tt e m s ，a n dm ee d g e s r e d r e s e n tm ec o o c c u r r e n c eo ft e 册s ，w h i c hc a nd e s c r i b e t 1 1 es e m a n t i ca s s o c i a t i o n r e l a t i o nb e t w e e ns i n g l ew o r d so f 幽ed o c u m e n ta n dw i l lb es h o 、v nt oh a v et h e c h a 眦t e r i s t i co f b e i n gas m a uw o r l dn c t w o r kb ys o m en e c e s s a r ya c c o u n t s e c o n d l y ，t 、v o v a r i a b e s t h ec h a r a c t e r i s t i c s p a t hl e n g 饿 i n c r e m e n l a la i l d c l u s t e r i n g c o e 踊c i e n t i n c r e m e n t a l w i l lb ei n 加d d u c e ds om a tw ec a ng e t 血ec a n d i d a t ek e y w o r d ss e tb y n u m b e r i n gt h et e r m si m p o n a n c et ot h es e m a n t i co ft h ed o c u m e n t f i n a u y ，c o n s i d e r i n g c o m p r e h e n s i v e l ym a r l yf a c t o r s ，s u c ha st h es e m a n t i ca s s o c i a t i o nr c l a t i o nb e “，e e ns i n g l e w o r d si nt l cc a n d i d a t es e t ，t h er e l a t i o nb e t 、e e nt 、v ov a r i a b l ei n c r e m e n t a l sn u n l e r i c a l v a l u ea s 、v e l la s s p e c i a lf i e l dr e q l l i r e m e m ，w ec o m b i n es o m er e l a t e dw o r d si nt h e c a r l d i d a t cs e ta n dg e ts o m ec o m p o u n dk e y w o r d s ha d d i t i o n ，w ea l s om a k eab r i e f a n a l y s i so nt l l es p a c ea i l dt i m ec o m p l e x i t yo f 也ea l g o r i t l l m t h er e s u l to fe x p e r i m e n t s s h o w st l l a tm ea l g o r i t h mi se f f e c t i v ea n da c c u r a t e ，t l l ea c c u r a c yo fw i l i c hi sa sh i 曲a s 9 1 ，c o m p a r e d 、v i 山t h ek e y w o r d sb ya na r t m c i a la b s 打犯t i o nf r o mt 1 1 es a m ed o c u m e n t t h es e m a 商cr e p r e s e n t e db yt h ec o m p o u n dk e ) w o r d st oad o c 岫e n t ， u s i n g 山i s a l g o r i 山m ，i sf a rm o r ec l e a r e ra n da c c u r a t cm a n t h a to fs i n g l ek e y w o r d ss e t ，w h i c hh e l p s u sh a v eab e t t e ru n d e r s t a n do f t l l ed o c u m e n ts e m a n t i ci nh i 曲l e v e l k e y w o r d ：s w n ( s m a nw o r l dn e t w o r k ) d o c u m e n t ss e m a n t j cs t r u c t u r ef i g u e t h ec h a r a c t e r i s t i cp a t hl e n g t hi n c r e m e n t a lt h ec l u s t e rc o e m c i e n t i n c r e m e n t a l c o m p o u n dk e y w o r d s 主塑 擎璺墨璺墅! 量 独创- 生声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。 尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已 经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其他教育机构的学位 或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中做 了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名董渣墨日期l 口口f ，2 、矽 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校 攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业离校后，发 表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学校有权保留送交论 文的复印件，允许查阅和借阅论文：学校可以公布论文的全部或部分内容，可以允许采 用影印、缩印或其它复制手段保存论文。( 保密的论文在解密后遵守此规定) 本学位论文属于保密，在年解密后适用本授权书。 本人签名 导师签名： 董洛导 数 日期2 的6 q 日期抽f 2 z - j 第一章绪论 第一章绪论 1 1s w n 问题的产生、发展及研究现状 小世界网络是指具有高度的局部集团化和较短的全局平均路径长度的网络， 它是介于高度有序和高度随机之间的一种抽象图。从2 0 世纪2 0 年代由 k a r i n 协y ( 1 9 2 0 s ) 【1 l 提出以来，经过长期的研究( k a r i n t l l y1 9 2 0 s ，p 0 0 1 和k o c h e n 1 9 5 0 s ，s 协l e ym i l g r 锄1 9 6 7 ，s t e v es t r o g 砒z 和d u n c a nw a n s1 9 9 0 s ) 逐渐形成 一种新的网络结构理论，并被广泛应用于各个科研领域，如：数学( w a t t s1 9 9 8 ) 、生 物( s 髓o g 如和s t e w a r t1 9 9 3 ) 、医学( c r i c k 和k o c h l 9 9 8 ，k a u 髓l a n1 9 6 9 ，h e s s1 9 9 6 ， k r c t z s c l 吼a r 和m o r r i s19 9 6 1 等领域。 1 1 1s w n 问题的产生 上世纪6 0 年代，美国社会心理学家米尔格伦( s t a i l l e ym i l g r a m ) 在今日心 理学杂志上提出了他的“六级分离”( s i xd e 掣e e so fs e p a r a t i o n ) 的理论。他认 为，任何两个陌生人都可以通过“亲友的亲友”建立联系，而这两个人之间的亲 友数量大约是5 。 为了证明这个假说，米尔格伦做了一个实验：让志愿者传递包裹。他随机选择 了内布拉斯加州和堪萨斯州的三百人，让他们把包裹送交波士顿的两个“目标” 之一。当然，几乎可以肯定包裹不会直接到达目标，米尔格伦就让志愿者把包裹 送给他们认为最有可能与目标建立联系的亲友。实验中最终有3 0 0 个包裹传到了 “目标”手中，总共建立了6 4 条连接，平均每个包裹要经过5 次传递才能到达目 标。m i l g r 啪认为该实验结果证实了他之前所作的假设。然而，由于实验规模太小 以及实验规则过于简单等原因，很多人都开始怀疑其结果的价值。甚至j u d 淌 k 1 e i n f e l d 在查看了m i l g r a m 存放在耶路档案馆的实验数据发现：很多未公开的实验 数据是和他的结论相违背的。于是人们做了大量相关的实验，由于这些实验同样 存在着规模小( 参与者太少) 、实验参与者的背景不够复杂( 如：仅限于某个大学内部) 等缺点，该理论一直没有进一步的发展。 在米尔格伦的实验之后，有人使用了其他的替代方法检验“六级分离”的假 说。其中最著名的一个是所谓“凯文培根游戏”。这个游戏的主角是美国电影演 员培根( k e v i nb a c o n ) 。游戏的目的是把培根和另外任意一个演员联系起来。借 助这个游戏进行研究有一个很大的优势，那就是人们拥有非常完整的电影演职员 表。弗吉尼亚大学计算机系的科学家花了一番力气建立起了这样一个电影演员的 数据库，放在网上供人们随意查询。例如，葛优在电影大腕里与萨瑟兰( d o n a l d s u t l l e r l a i l d ) 合作，而后者于1 9 9 1 年与墙根演出了刺杀肯尼迪( j f k ) 。这样， 基于s 1 】n 理论的文本复合关键字提取算法的研究 葛优就与培根建立了一个距离相当短的联系。如果你乐意，还可以找出葛优与摇 滚歌星“猫王”埃尔维斯，或者“终结者”施瓦辛格的联系。事实上，这个数据 库表明电影界确实是一个小世界。通常只须通过几个中间环节，就可以把任意两 个演员连接在一起。 另一个类似的验证实验则利用了数学家爱多士( p a u le r d o e s ) 。爱多士是一位 高产的匈牙利犹太裔数学家，一生与别人合作撰写了5 0 0 篇以上的数学论文。如 果把一篇论文的共同作者视作一种联系，那么某位数学家离爱多士有多远呢? 奥 克兰大学的格罗斯曼( j e n yg r o s s m a l l ) 建立了一个数学评论杂志的作者数据 库，剔除那些“孤立”的数学家( 没有共同作者) ，结果发现其中任一位数学家与 爱多士之间平均只隔了4 人。 然而，尽管这些实验看上去非常精巧而且很容易检验，它们有一个最大的缺 点，那就是范围太小，同属于“小圈子”。电影界或者数学界的“小世界现象”， 不能直接推广到整个真实世界。这就是w a t t s 进行大规模实验的原因之一。 3 0 年后，s t e v es t r d g a t z 和d u n c a i lw a t t s 利用互联网做了一个新的实验：建立 一个实验网站( s m a l l w o r l d c o l 啪b i a e d u ) ，每一个参与实验的志愿者在网站上注册， 然而通过这个网站把电子邮件发给最可能实现任务的亲友。该实验在几个不同的 国家内选择1 8 个“目标”( 包括：纽约上层社会的一个大学教授，澳大利亚佩思的 一名警察，巴黎的一名图书管理员等) ，通过1 6 6 个国家6 1 1 6 8 个人经过2 4 1 6 3 封 电子邮件完成实验任务，并且记录了每个参与者的姓名、住址、职业、性别、宗 教、经济状况等基本信息。统计实验数据可知，任意两个参与者之间平均要经过4 个人才能建立连接。这充分证明了米尔格伦“六度分离”假设( 或称卟世界现象) 的正确性。经过6 年的研究， s t e v es t r 0 2 a t z 和d u n c a nw a t t s 把社会网络抽象为一 种介于规则网络和随机网络两者之间的一种新型网络1 2 】= 小世界网络f s m a l lw o r l d n e t w o r k 可简写为s w n ) ，并给出了小世界模型的构造方法以及s w n 理论的几个 基本参数的定义。由于研究小世界模型有助于理解大型系统的动态属性和其结构 特征之间的关系，s w n 理论一经提出就引起了研究人员的兴趣，经过大家的共同 努力，该理论逐渐趋于完善，并被广泛应用于各个科研领域，如：数学( w a t t s1 9 9 8 ) 、 生物( s t r o g a t z 和s t e w a r t1 9 9 3 ) 、医学( c r i c k 和k o c h l 9 9 8 ，k a u f h n a n1 9 6 9 ，h e s s1 9 9 6 ， k r e t z s c l r i l a r 和m o r r i s1 9 9 6 ) 等领域。 1 1 2s w n 问题的研究现状 s w n 一经提出，就得到各学科研究者的兴趣，并将其应用到各个学科中的大 型动态系统的研究之中，下边分别介绍一下目前较成功几个应用实例。 w a t t s 和s t r o g a t z ( 1 9 9 8 ，w a t t s1 9 9 9 ) 将s w n 模型引入细胞自动机、简单游戏 第一章绪论 以及耦合振荡器网络的研究中口1 ，并将其与基于规则网络的相应研究进行对比，发 现当基于s w n 来构造这几个系统时，它们会表现出更优越的特性。他们发现：用 s w n 结构实现的细胞自动机更容易进行密度分类任务；在“囚犯两难”的多人游戏 模式下，基于s w n 时合作发生的可能性更小；使用s w n 拓扑结构的振荡器网络更 容易实现同步。 m o n a s s o nf 1 9 9 9 1 在s m a l lw o r l d 图上用一个传输矩阵来研究拉普拉斯算子的 特征值【3 】o 利用这个特征值可以使我们理解一个基于s w n 拓扑的质量弹簧系统的 工作模式。或许更有用的是：它能告诉我们扩散动力学怎样作用于一个基于s w n 的网络；扩散域的任何初始状态都可以被分解为每次衰减都独立于且指数倍于一 个与相应的特征值相关联的衰减常数的特征向量。利用上述结论，可以为某种信 息在一些社会网络中的扩散提供研究模型。 b a m t 和w e i 昏( 2 0 0 0 ) 用一种复制方法给出了s w n 上的铁磁体的伊辛模型吐 因为伊辛模型有一个较低的临界维数2 ，我们认为当p = o 并且图是一维的时候它没 有出现相位的跃迁。另外，当p 大于0 时，图的有效维数将大于l ，并随着系统规 模的增长而增长。因此，我们可以认为在一个大型系统界线内，对于任何的d 值 都能在某个有限的温度下看到一个相位跃迁。b a m t 和w 戡g t 分析并用数学方法 证明了确实是这样子的。 n e w m a l la j l dw a n s ( 1 9 9 9 b ) 致力于基于s m a l lw o r l d 图的疾病传播问题的研究 口】。他们首先认为：疾病只是易于在人群的q 部分被感染；在s w n 中通过邻居结点 互相传染并假设它只能感染那些易于感染的人然后通过这些人继续传播。在这个 模型中，疾病只会在它最初所处的连通的易感人群中传播，当q 很小时它的规模 也很小，会随着q 的增大而增大，并最终达到无穷大。这个无穷值产生的点( 流行 病产生的点) 正是在s w n 图中以概率q 进行区域渗透的渗点。n e w m a na n dw a t t s ( 1 9 9 9 b ) 给出了流行病形成点的计算结果( 较他们数字仿真的结果更优) 。m o o r ea n d n e w m a n ( 2 0 0 0 a ，2 0 0 0 b ) 后来给出了更加精确的结果。 l a g o f e m a i l d e ze ta l ( 2 0 0 0 ) 利用包括规则网格，随即图，小世界图在内的多 种图研究了基于h o d g k i n h u x l e y 模型的神经网络的行为1 3 | d 他们发现：网络中高度 聚集性的出现使得网络产生共振；同时，小的点到点间的平均距离使得网络能够对 外部刺激作出快速反应。小世界网络因为同时具有高度的局部聚集性和较小的平 均最短路径两个特点，成为唯一能够同时产生共振并作出快速反应的网络。 k u l k a n l ie ta 1 ( 1 9 9 9 ) 用数学方法研究了在s w n 中物种协同进化的 b a k s n e p p e n 模型的行为l j 】。这是一种模拟大规模物种间协同进化的模型，这种模 型的行为依赖于它所处的网络的拓扑结构，k u l k a m i 及其合作者认为小世界图较之 于通常所用的低维图更接近于现实生态系统的拓扑结构。仿真结果是，在小世界 图中的任意结点的进化行为的发生数量随着该结点的邻居的个数而变化，邻居多 4 基于s w n 理论的文本复合关键字提取算法的研究 的点的进化概率大，邻居少的结点进化概率小。 近几年，从1 9 9 9 年l a d a a a d 锄i c 证明了w e b 中存在s m a l l w o r l d 现象1 4 j 以来， s w n 理论在计算机理论研究领域得到广泛关注。并分别被引入i n t e m e t 结构研究 【5 1 、p 2 p ( p e e r t o p e e r ) 网络【6 】的d h t ( d e c e n t r a l i z e ds n u c t u r e dt o p o l o g y ) 发现算法、 搜索引擎技术等领域。另外以微软w a l l o p 项目( 以研究人们在社会网络中如何分享 媒介和建立社交联系为目的社会计算项目) 代表的s s ( s o c i a ls o 尚a r e ) 软件研发也开 始兴起。 虽然s w n 理论已经在各个研究领域得到广泛的应用，但是由于现有的计算方 法的局限性使得该理论的数学证明一直没有大的突破，s w n 理论的完备性和充分 性一直没有得到证明。 1 - 2 论文的主要研究工作 概括起来，本文主要有以下几个方面的工作： 1 系统的介绍了s w n 理论： 2 详细的阐述了现有的基于s w n 理论的文档关键字挖掘算法，并对其进行了 详细的分析，指出它们存在的不足： 3 在理论分析和实际观察的基础上，给出了一种新的文档总体结构图构造算 法和文档复合关键字挖掘算法 4 设计出实验原型系统，并用该系统对我们提出的两个新算法进行验证，把 实验结果和人工提取结果以及几种已有算法的提取结果进行比较，经分析比较， 证明了我们提出的新算法的正确性。 1 3 论文的章节安排 论文一共分6 个章节，下边分别说明各个章节的内容： 第一章：本章前半部分系统的阐述了s w n 理论的产生、发展过程，以及该理 论的应用现状；本章后半部分说明了论文的主要工作以及章节安排。 第二章：本章从复杂网络理论的研究现状开始系统的介绍了规则网络、随机 网络、小世界网络理论，并给出了几种典型的小世界网络的构造模型以及现实世 界中小世界网络的例子 第三章：本章给出了s w n 理论在自然语言处理中的应用现状，并分别介绍了 人类语言中的s w n 、文档中的s w n 以及s w n 理论在文档关键字挖掘中的应用。 第四章：本章先是介绍了z c c 构造算法和s i m p l el 算法，并在分析了两种算 法的不足之后，对他们进行改造，提出改进的z c c 构造算法似一z c c 算法、和 c o m p l e x i t yl c 算法，并在对算法时间复杂度的分析的基础上对c o m p l e x i t yl c 算 第一章绪论 法进行了改进，在后续章节中将通过具体实验证实a z c c 算法和c o m p l e x i t yl c 算法的正确性。 第五章：本章说明了实验原型系统的设计原则、设计思想，同时还给出了系统 的功能结构设计以及各个核心处理过程的实现方法。 第六章：本章根据实际情况选择合适的测试用例并用我们的实验原型系统进 行处理，验证论文中两个新算法的正确性。通过把实验结果和人工提取结果以及 几个已有算法的处理结果进行比较、分析，最终证明我们的算法有较高的精确度 和较好的可扩展性。 6 基于s l i l n 理论的文本复合关键字提取算法的研究 第二章s 洲理论 自然界中存在的大量复杂系统都可阱通过形形色色的网络加以描述。一个典 型的网络是由许多节点与连接两个节点之间的一些边组成的，其中节点用来代表 真实系统中不同的个体，而边则用来表示个体间的关系，往往是两个节点之间具 有某种特定的关系则连一条边，反之则不连边，有边相连的两个节点在网络中被 看作是相邻的。例如，神经系统可以看作大量神经细胞通过神经纤维相互连接形 成的网络；计算机网络可以看作是自主工作的计算机通过通信介质如光缆、双绞 线、同轴电缆等相互连接形成的网络。类似的还有电力网络、社会关系网络、交 通网络等等。 数学家和物理学家在考虑网络的时候，往往只关心节点之间有没有边相连， 至于节点到底在什么位置，边是长还是短，是弯曲还是平直，有没有相交等等都 是他们不在意的。在这里，我们把网络不依赖于节点的具体位置和边的具体形态 就能表现出来的性质叫做网络的拓扑性质，相应的结构叫做网络的拓扑结构。那 么，什么样的拓扑结构比较适合用来描述真实的系统呢? 两百多年来，对这个问 题的研究经历了三个阶段。在最初的一百多年里，科学家们认为真实系统各因素 之间的关系可以用一些规则的结构表示，例如二维平面上的欧几里德格网，它看 起来像是格子体恤衫上的花纹：又或者最近邻环网，它总是会让你想到一群手牵 着手围着篝火跳圆圈舞的姑娘。到了二十世纪五十年代末，数学家们想出了一种 新的构造网络的方法，在这种方法下，两个节点之间连边与否不再是确定的事情， 而是根据一个概率决定。数学家把这样生成的网络叫做随机网络，它在接下来的 四十年里一直被很多科学家认为是描述真实系统最适宜的网络。直到最近几年， 由于计算机数据处理和运算能力的飞速发展，科学家们发现大量的真实网络既不 是规则网络，也不是随机网络，而是具有与前两者皆不同的统计特征的网络。这 样的一些网络被科学家们叫做复杂网络( c o m p l e xn e t w o r k s ) ，对于它们的研究标 志着第三阶段的到来。 由于大量的真实网络即有较大的聚集特性，又有较短的平均最短路径长度( 信 息传递效率) ，所以复杂网络的研究逐渐集中于小世界网络( s w n ) 和无标度网络 ( s c a l e f r e en e t w o r k ) 的研究。其中s w n 理论的研究近些年来得到较大的理论突 破和世界应用，下面将详细讲解s w n 理论。 2 1 相关定义 网络的平均最短路径长度和簇系数以及规则网络和随机网络是理解s w n 理 论的基础，下面将给出它们的定义。 第二章s w n 理论 7 2 1 1 平均最短路径长度 在网络中，两点间的距离被定义为连接两点的最短路所包含的边的数目，把所 有节点对的距离求平均，就得到了网络的平均距离( a v e r a g e d i s t a n c e ，也叫平均最 短路径变化量) l 表示【7 l 。l 表示网络的有效大小，代表两个结点间的最典型的 分离距离。 例如，在一个朋友关系的网络( f r i c n d s h i pn e t 、o r k ) 中，l 表示在网络中任何两个 人间建立最短连接所要经过的人的数量的平均值。有趣的是，许多现实的复杂网 络虽然有比相同结点数的全连通图少的多的边数，但是却有较小的平均距离。上 述现象叫做小世界现象。 我们用g 表示一个网络所对应的拓扑结构图，n 和k 分别表示图中的结点总 数和边的总数，k 为从每个结点引出的平均边数。 是从第i 个结点引出的边的个 数( 第i 个结点的度) 。则： k ：土y 女f - 1 ， 式( 2 - 1 ) 2 _ t ：墨 式( 2 2 ) 为了说明图的特性，又设d 。表示点v ，和v ，之间的最短路径长度，用i e ( 6 ) i 表 示任意一个图g 中边的个数。( 注：论文后续部分出现上述变量的引用时都将采用上 述表示方法1 下边给出图的平均最短路径变化量的数学定义： 定义1我们把图g 中所有点之间的距离的平均值叫图g 的平均最短路径长 度，可表示为 耶) = 丽南。弛 却3 其中l ( g ) 表示图g 的平均最短路径变量 根据不同的网络结构，我们可以赋予平均最短路径长度l 以不同的物理意义， 如：在疾病传播模型中，可以把l 定义为疾病传播的中介人数；在公交网络模型中， l 表示从起点到终点，公交车停靠的站点的数量。 2 1 2 簇系数 另外一个叫做簇系数( c l u s t e r i n gc o e 伍c i e n t ) 的参数，专门用来衡量网络节点 聚类的情况。比如在朋友关系网中，你朋友的朋友很可能也是你的朋友；你的两 个朋友很可能彼此也是朋友。簇系数就是用来度量网络的这种性质的。用数学化 的语言来说，对于某个节点，它的簇系数被定义为它所有相邻节点之间连边的数 8 基于s w n 理论的文本复合关键字提取算法的研究 目占可能的最大连边数目的比例，网络的簇系数c 则是所有节点簇系数的平均值 【”。研究表明，规则网络具有大的簇系数和大的平均距离，随机网络具有小的簇系 数和小的平均距离。 定义2 我们把图g 中与点v 直接相邻的点叫做v 的邻居结点，则v 的所有 邻居结点组成的结点集叫v 的邻居。可表示为： r ，= f d ，。= 1 ) 式( 2 - 4 ) 定义3 从图g 中取出由l 中所有结点所组成的最大连通子图，则图g 相对 于结点v 的局部簇系数为： c ，= ie ( r v ) c j式( 2 5 ) 定义4图g 中所有的c 。的平均值叫做图的簇系数，用c ( g ) 来表示； c ( g ) = 专善c 。 式( 2 - 6 ) ， 图2 1 示例 例如，在图2 1 中：结点v 的邻居结点的个数为t ，= 6 ，le ( r 。) 4 ，所以 c 。= 4 1 5 。 2 1 3 规则网络 在最初的一百多年里，科学家们认为真实系统各因素之间的关系可以用一些 规则的结构表示( 我们称具有这种特性的网络叫规则网络1 ，例如二维平面上的欧几 里德格网，它看起来像是格子体恤衫上的花纹：又或者最近邻环网，它总是会让 你想到一群手牵着手围着篝火跳圆圈舞的姑娘。 在研究中得到普遍应用的规则网络模型是最近邻环网喁l 。它由n 个围成圈的 结点组成，每个点与它临近的k 个点相连，其中k 是偶数。当k 足够大时，它的 第二章s w n 理论 簇系数趋近于3 4 ，表现出很大的聚类特性。图2 2 给出了一个典型的规则网络的 例子。 在随机网络以及小世界网络的特性被发现以前，许多针对真实网络的研究都 是把其拓扑结构映射到一个规则网络的基础上做的，但是人们发现这种方法的研 究结果往往不尽如人意。例如，以前的基于规则网络的研究表明，疾病在网络中 的平均波及范围与疾病的传染强度正相关，而疾病的传染强度有一个阈值，只有 当其值大于这个阈值时，疾病才能在网络中长期存在，否则感染人数会指数衰减。 根据这个理论，疾病若是持久存在，则必然波及大量个体。但实证研究表明，计 算机病毒，麻疹等一般仅波及少数个体但能够长期存在。 虽然一些规则网络也具有很好的聚类特性和较小的平均最短路径长度，但是 很难在现实世界中找到拓扑结构和它完全对应的网络，所以人们不再把规则网络 作为包括疾病传播模型在内的许多现实网络研究的基础模型来研究。但是由于对 它的研究还可以对随机网络和小世界网络等其他网络特性的研究起到对比的作 用，所以规则网络 图2 2 一个典型的规则网络，n 人围成一个圈，每个人和他 最近的4 个人之间有边相连 2 ，1 4 随机网络 和规则网络相对应的是由e r d 6 sa n d 鼬n y i ( e r ) 4 0 年前首次提出的结构完全 随机的随机网络8 1 。 试想，有n ( n 1 ) 个扣子被撒在地上，用个绳子以相同的概率p 把每个扣 子串起来，将得到一个由n 个结点和p ( 一1 ) p 条边组成的e r 随机网络。随机 网络理论的主要研究目标是找到一个p ，使得按上述方法得到的网络都是连通的。 l o 基于s w n 理论的文本复合关键字提取算法的研究 对e r 模型研究发现，当p ( 1 n ) 时，形成的随机图最有可能都是连通图。 研究发现，随机网络一般都有较小的平均最短路径长度。但是它的簇系数都 比较大，也就是聚类性较差。表2 1 给出了几个现实网路及其相同规模的随机网络 的相关参数的比较。从表中可以看出，相同规模的随机网络的l 值和现实网络的l 值接近，但是c 值却有很大的差别。由此可见随机网络还不能很好的和现实系统 的网络相对应。 表2 1 相同规模的随机网络和现实网络的比较 n l 现蛮l 瞳机c 现实 c 麓帆 k 电影演员 2 2 5 2 2 63 6 52 9 90 7 9o o 0 0 2 76 1 电力系统 2 8 21 8 71 8 7o 0 8 0o 0 0 51 4 c e l e g a r i s 4 9 4 12 6 52 6 50 2 8o 0 52 6 7 2 1 ，5 其他相关定义 下面将给出s 、n 理论中的几个相关定义： 定义5 一条边的r a n g e 用月( f ) 表示，是指在图g 中去掉边e ( f ，) 后它的 两个顶点v ，和v ，之间的最短路径长度。 定义6图g 中的边e ( f ，j ) 叫作一个s h o n c u t ，当它的r ( f ，- ，) 2 时。 定义7图g 中的边e ( f ，) 叫做一个t h a d ，当它的尺( f ，) = 2 时。 如图2 3 ：a 图中的边e ( f ，) 就是一个t r i a d ，因为当把它去掉时，结点v 和v 之 间的最短路径长度d 。= 2 ；b 图中的边e ( j ，) 是一个s h o n c u t ，因为当去掉它时，结 点v 和v ，之间的最短路径长度d 。，= n l 。 姗t a f 。 ab 图2 3t r i a d 和s h o r t c u t 的示例 旷 第二章s w n 理论 2 2 小世界网络( s w n ) 如前文所述：规则网络具有明显的聚类特性，但是没有小世界效应；而随机网络 虽然有小世界效应，但是其聚类性却很差。因此，无论是规则网络还是以e r 模型 为代表的随机网络都不能战展现实网络的许多重要特性。因为，大多数真实网络 既不是完全规则的也不是完全随机构造的。如在社会网络中，人们往往会与他们 的邻居有很多的交往，但是决不是像规则网路表示的那样，只是跟自己的邻居交 往；在万维网( w w w 忡，他的结构又不是像e r 模型一样完全随机的，而是根据不 同的主题逐渐形成。 为了研究当一个网络从完全规则过渡到完全随机的过程中其主要特性的 变化情况，w a n s 和s 订o g a t z 构造了一种有趣的小世界网络模型吨也可称为w s 模 型1 。他们发现w s 模型即有较好的聚类特性，又有较小的平均最短路径长度，我 们把同时具有这两个特性的网络叫做小世界网络( s m a uw o r l dn e t w o r k ，可简写 为：s w n ) 。正因为它同时具有这两大特性，所以s w n 较之于规则网络和随机网络 更适于应用在真实系统的研究。s w n 一经提出，就引起了很多研究者的兴趣，经 过大量的研究发现，这种网络在真实系统中是普遍存在的。下面将分别介绍w s 模型的构造、w s 模型的特性以及几种典型的s w n 模型的构造方法。 2 2 1 小世界网络( s w n ) 为了研究当一个网络从完全规则过渡到完全随机的过程中其主要特性的变化 情况，w a t t s 和s t r o g a t z 构造了一种有趣的小世界网络模型( 也可称为w s 模型) 。 它的构造过程如下： 1 定义一个规则网络，其结构用图g 表示，该网络有n 个节点，每个节点和 它最临近的k 个节点连接形成k 条无向边。 2 从l 中定义的图开始，以概率p 重画原图中的每条边。并保证没有重复的 边出现，这样就会产生讣咄，2 条( 长程边把一个结点和远处的结点联系起来) ，改 变p 值可以实现从规则网络0 f 0 ) 向随机网络( p = 1 ) 转变。 图2 4 中显示了当n = 2 0 ，k = 4 ，并且p 从0 到l 变化时上述构造过程的 结果。 # 蝴曲翱触_ 瑚r - i 由m o 桊 1 2 基于s w n 理论的文本复合关键字提取算法的研究 图2 4 小世界网络的构造过程以及从规则网络向随机网络的过渡。图中有 v = 2 0 ，k = 4 。 该构造过程从一个完全规则的网络开始，该规则网络由n 个顶点和k 条边构 成，每个顶点和它最i 临近的k 个结点相连( 其中k 是一个偶数) ，所以每个结点有相 同的度数k ，另外k = 2 。图2 5 说明了当n = 2 0 ，k = 4 时该规则网络的结构。 图2 5w s 模型构在使用的规则网络，图中n = 2 0 ，k = 4 构造完规则网络之后，按相同概率p 对该规则网络中的每条边进行重画。这 里的重画是指：从图中随机抽取一个结点来代替该边的两个顶点中的个。其中， 该随机抽取的顶点要满足以下条件：该点与被重画边中未被取代的那个顶点之间没 有边相连，也就是要保证重画后网络中任何两个结点之间不能出现重边：被抽取的 结点不是被重画边的重画前的顶点，也就是要保征重画后的网络中没有连接同一 个结点的边出现：被抽取的结点能够保证重画后的网络是连通的。 图2 6 显示了随机抽选结点v 。重画图2 5 的边e ( r ，s ) 后的结果，在原图中，边 e ( r ，s ) 的r a n g e 比较小，r ( r ，s ) = 2 ，但是重画后得到的边的r a l l g e 就比较大， r ( r ，t ) = 6 。如果我们把r a i l g e 较大的边叫做长程边的话，上述重画过程会使得原 图中的长程边的数量随着重画边的数量的增加而增加。注意：这里每一次重画后得 到的边的r a n g e 的计算是基于图的原有结构的。例如：图2 6 中要计算r ( r ，t ) ，我们 认为在原有图只重画了边e ( r ，s ) 得到边e ( r ，t ) ，即认为没有任何其他的边已经被重 画过。 t 图2 6 随机抽选结点v 重画图5 的边e ( r ，s ) 后的结果 如果按照概率p 去重画原图中的每一条边，则会得到p n k 2 条长程边。 第二章s w n 理论 当p = o 时，没有任何边被重画，图将保持原有结构不燹。所以当p 2o 时w a n s 和s t r o t g a z 的方法重画后得到的图是一个规则图。 经计算，这时图的平均最短路径长度( 用l 。表示) 为【7 】= l 。：整型坠兰 式( 2 7 ) ”1 ” 2 k f n 1 ) 图的簇系数( 用c 。，。表示) 为： c 。：塾望 式( 2 8 ) k 咖2 丽 n “ w a n s 和s 订o t g a z 发现，当n k 1 n n 1 时： l * 芸 1 式( 2 _ 9 ) c 喇。“三 式( 2 当p = 1 时，原图中所有的边都会被重画，因为每一个重画后的边的顶点都是 随机抽取的，所以重画后的图和按e r 模型构造方法构造的图具有相同的特点( 都 是随机抽取k 对不重复的结点画出k 条边形成网络) ，这就说明当p = 1 时，重画后 得到的图是一个完全随机的图。 经计算，如果n k l i 悄 1 ，这时图的平均最短路径长度( 用l 。表示) 为： l 。掣 式( 2 - 1 1 ) l 2 面 武l 2 1 1 如果n k l n n 1 ，这时图的簇系数( 用c 啪d 表示) 为： c “言 式( 2 - 1 2 ) w a t t s 和s t r o t g a z 模拟了当p 从0 到l 变化时网络的平均最短路径长度( l ) 和 簇系数( c ) 的变化趋势如图2 。7 所示： 图2 7 p 从0 变到l 时，l ( g ) 和c ( g ) 的变化趋势，其中l ( o ) 和c ( o ) 分别 基于s w n 理论的文本复合关键字提取算法的研究 表示当p = 0 时l ( g ) 和c ( g ) 的值 图2 7 中l ( o ) 和c ( o ) 分别表示当p = o 时l ( g ) 和c ( g ) 的值，从图中可以看出， 随着p 的增大，l ( g ) 和c ( g ) 都会随之减小。但是当o 0 0 0 l c 。而 三z 三。所以q 。也是一个小世界网络。由于q 。有较小的l 值，所以使得任何 两个词语之间的互找的代价就较小，才使得人们能够快速的从大脑字典中选取合 适的词语来组成自己要表达的语义。 第三章s w n 理论在自然语言处理中的应用 3 2 文档中的s w n z h um e n g x i a o 、c a iz h i 和c a iq i n g s h e n g 用下述方法建立文档的结构图( 同现 图) 【1 3 1 ：首先去掉文档中无实际意义的符号，同时去掉文中的表、图以及引用，然 好用结点表示文中出现的词，若两个词在句( 文章的标题也被看作一个句子处理) 中的间距小于2 则用一条无向边把他们连起来。 图3 2 给出了人民网0 3 年7 月 1日的一篇文章： h 鲤；型竖逊p 蛐! ：q m ：型鱼旦垃鲤! 煎2 堡8 3 8 ! ：鱼地! 的结构图。 图3 2 文章：h 鲤；丛幽乜毂叠l ：q 堕：型鱼旦b a p 鲢! 2 5 2 缒8 3 8 ! ：h ! 盟! 的结构图 y u t a k am a t s u o 等人从第九界世界万维网大会( t h e9 t hi n t e m a t i o n a lw o r l dw i d e w e bc o n f e r e n c e ( w w w 9 ) ) 的会议论文中随机抽出5 7 篇，建立它们的结构图，并统 计出它们的两个参数：平均最短路径长度和簇系数的大小，具体结果见表3 2 1 1 1j 。 表3 2 y u t a k a m a t s u o 等人在w w w 9 的会议论文中任取5 7 篇论文的结构图的 统计结果，这里取j 。=