关闭

关闭

关闭

封号提示

内容

首页 复杂网络研究进展_模型与应用

复杂网络研究进展_模型与应用.pdf

复杂网络研究进展_模型与应用

李茜 2012-12-16 评分 0 浏览量 0 0 0 0 暂无简介 简介 举报

简介:本文档为《复杂网络研究进展_模型与应用pdf》,可适用于经济金融领域,主题内容包含小型微型计算机系统JournalofChineseComputerSystems年月第期VolNo收稿日期:基金项目:国家自然科学基金项目(,)资助符等。

小型微型计算机系统JournalofChineseComputerSystems年月第期VolNo收稿日期:基金项目:国家自然科学基金项目(,)资助作者简介:詹卫华,男,年生,博士研究生,研究方向为复杂网络理论及应用关佶红,女,年生,教授,博士生导师,研究方向为地理信息系统,复杂网络和生物信息学章忠志,男,年生,博士后,副教授,研究方向为复杂网络理论复杂网络研究进展:模型与应用詹卫华,关佶红,章忠志(同济大学计算机科学与技术系,上海)(复旦大学计算机学院,上海)Emai:lzhanwhtongjieducn摘要:作为研究各种复杂系统的一种通用工具,复杂网络已经在许多学科中产生了深刻地影响,引起了各领域学者的广泛关注本文全面地介绍复杂网络的各种主要统计特性和最具有代表性的网络模型,并且对计算机科学中关注的语言网络,Internet和PP这些现实网络,从复杂网络的角度进行分析,展示了复杂网络理论和方法在这些领域中的应用和得到的重要结果关键词:小世界网络无标度网络度分布聚类系数中图分类号:TP文献标识码:A文章编号:()AdvanceintheResearchofComplexNetwork:ModelandApplicationZHANWeihua,GUANJihong,ZHANGZhongzhi(DepartmentofComputerScienceandEngineering,TongjiUniversity,Shanhai,China)(SchoolofComputerScience,FudanUniversity,Shanhai,China)Abstract:Asancommontoolforstudyingvariouscomplexsystems,complexnetworkhasmadedeeplyeffectonmanydiscipline,andhasattractedwideattentionsVariousimportantstatisticalpropertiesofcomplexnetworkanddominantnetworkmodelsareaddressedMoreover,weanalysesomereallifenetworkssuchaslanguagenetworks,WWWandInternetthatareofinterestincomputerscience,andshowtheapplicationoftheoryandmethodsofcomplexnetworktothesefieldsKeywords:smallworldnetworkscalefreenetworkdegreedistributionclusteringcoefficient引言自然界和人类社会中存在各种各样的复杂系统这些系统由许多相互联系的单元构成,网络是描述复杂系统最自然的工具)))节点表示系统组成单元,边表示单元间的联系在我们周围环绕着形形色色的网络:节点表示web页面,边来表示页面间的链接,这就形成了www网络节点表示作者,边表示两人在同一篇科学文献中合作,就形成了合著者网络节点表示底物,边表示底物间发生的生化反应,就形成了代谢网络网络在数学上用图来表示,因此网络的研究源于对图的研究年,著名的瑞士数学家欧拉为了解决KÊnigsberg七桥问题,发表了第一篇图论文章图(Graph)这个词第一次出现在Nature期刊上进入世纪年代,出现了一大批精彩的关于图的新理论和结果除了在数学上图论方面的发展,网络在社会科学中也受到了广泛的研究社会网络分析在十九世纪年代早期就开始发展,当时研究者把目光投向了社会实体间的关系,如组织成员间的通信、国家间的贸易、公司间的经济事务等年Watts和Strogaz发表在Nature上的小世界网络(SmallWorldNetworks)与一年后Albert和Barab‚si在Science上发表的无标度网络(ScalefreeNetworks)直接推动了人们对从简单规则网络转向了复杂网络的研究,并进而掀起了复杂网络研究的空前的浪潮复杂网络已经成为系统科学,复杂性科学和统计物理学研究的中心和焦点它作为一种研究模式或者手段,已经渗透到生物学、医学、计算机科学、社会学和管理学等众多领域,并成为研究热点复杂网络的结构特性简单地说,复杂网络就是比规则网络具有更复杂拓扑特性的网络具体地,这些特性包括:平均距离、度分布、簇系数、度度相关性、社区结构和层次性等度、度分布和度相关性(DegreeCorrelation)无向网络的节点的度(Degree)是指与节点连接的边数而有向网络的节点的度分为入度(Indegree)和出度(Outdegree)网络中所有节点度的列表称为度序列(DegreeSequence),度序列的平均值称为网络的平均度,记为<k>给定了网络的度序列就确定了该网络的度分布(DegreeDistribution)度分布是指从图中随机选择一个节点其度为k的概率,记为P(k)度分布是网络的最基本的拓扑特性根据度分布,可以将网络分为随机图,无标度网络和指数网络等度分布一个非常有用的表示(生成函数表示法)为:小型微型计算机系统年G=Ek=pkxk()其中pk表示度为k的节点在网络中的比例在随机图模型中,任意两个节点间相连的概率为p,换句话说,任意节点连接到任意的其它节点的概率都是相同的但在许多现实网络中,存在着一定的混合模式(MixingPattern),即一个节点倾向于连接到某一些节点例如在社会网络中,一个节点连接到另一个节点与代表它们的个体的种族、语言和年龄等有关研究者也发现,许多网络边的两节点间的度也存在依赖关系,即度度相关性(DegreeDegreeCorrelation)如果度高的节点倾向于连接其它度高的节点,称为同配混合(AssortativeMixing)如果度高的节点倾向于连接其它度低的节点称为异配混合(DisassortativeMixing)为了对不同网络进行比较,文献中提出了利用Pearson相关系数(PearsonCorrelationcoefficient)r来作为网络同配性的度量,r的取值范围是,,大于为同配,小于为异配许多社会网络是同配的,而一些技术网络如Internet和蛋白质网络是异配的文献进一步发现,网络的同配性(异配性)影响网络的结构和行为按照度同配混合的网络比对应的异配网络更利于渗流(Percolation)对于节点删除,同配混合的网络要比异配和中性的网络更具有鲁棒性最短路径长度、平均最短路径长度、介数(Betweenness)对于无权网络,网络中任意两点间的最短路径(ShortestPathLength)是从一个节点到另一个节点的最少边数对于有权网络,两点间的最短路径是指权值之和为最小的路径两节点间的最短路径长度具有重要的实际意义例如,在信息传输中,沿着最短路径意味着耗费最小网络中任意两个节点之间的最短路径长度的最大值称为网络的直径(Diameter)平均最短路径长度(MeanShortestPathLength)是网络中所有节点对之间的最短路径长度的平均值平均路径长度是网络的一个重要的统计特征,它确定了网络中节点对的平均分离度Milgram著名的小世界实验得出了六度分离的推断,即地球上任意两个人之间的平均距离是,平均路径长度可以做为网络信息传递效率的度量,文献,将网络的效率定义为:E=n(n)EiXjdij()这里,n表示节点数,dij为两个节点i和j之间的最短路径长度网络的平均最短路径长度较小的现象称为小世界效应(smallworldeffect)许多现实网络具有小世界效应,如电影演员网络(平均最短路径为),对等网络(平均最短路径为),代谢网络(平均最短路径是)为了度量节点在网络中的重要性)))中心性(Centrality),引进了节点介数(NodeBetweeness)概念,它的定义如下:bi=Ej,kIG,jXk从j到k的经过i的最短路径数从j到k的所有最短路径数()边介数(EdgeBetweenness)是经过这条边的节点对的最短路径数,它在社区发现中为区分一个社区的内部边和社区之间的边提供了一种有效的度量标准聚类系数(ClusteringCoefficient)二元关系R,如果aRb,bRc,那么aRc,则称R是传递的熟人网络中,也有类似的特性,即拥有一个共同朋友的两个人他们也彼此熟悉,这种性质称为网络的聚类性(Clustering),也称为传递性(Transitivity)传递性意味着出现三角形,定义节点i聚类系数如下:Ci=与点i相连的三角形的数量与点i相连的三元组的数量()整个网络的聚类系数C就是所有节点i的聚类系数Ci的平均值,且有C对于一些无标度网络,局部聚类系数Ci随着节点i的度下降而下降,随机网络的聚类系数为O(n),当网络规模极大时,趋于零,而多数现实网络的聚类系数显著大于零,即具有明显的聚类特性社区结构(CommunityStructure)社区结构是许多现实网络具有的一个共同的特征,即网络的节点可以分成几个组,每个组内部的节点连接稠密,而组之间的节点连接稀疏,图是一个包含三个社区的一个简单网络图三个社区的网络FigAnetworkwiththreecommunities社区结构的发现具有重要的意义,例如在WWW中的社区对应着一组关于某个主题的网页社会网络中的社区对应着有着共同爱好或背景的一群人生化网络中的社区则对应着某个复合体或某种功能因此,社区发现是当前复杂网络研究的一个热点方向,并且已经提出了各种方法,如基于介数度量的方法、随机游走方法,、电阻网络方法、拉普拉斯特征值方法,、极值优化方法、派系过滤算法等一个广泛使用的度量网络的社区结构的量是模块度(Modularity),它定义为:设网络分为n个社区,则定义一个nn的矩阵e,每一行和每一列都代表一个社区,矩阵元素eij表示社区i和j间的边数占网络总边数的比例,eii就表示社区i内部边所占的比例,ai=Eeij表示第i行或第i列元素之和,即与第i个社区的节点相连的边的总比例,则模块度定义为Q=Eieiiai=Trace(e)e()即社区内部边的比例减去具有同样社区划分但节点间是随机连接的网络的这一值的期望Q的值在与之间,Q越接近(这是最大值)预示着具有越强的社区结构层次性(Hierarchy)按层次组织是许多复杂系统的一个共同特征文献揭示了在代谢网络中,有许多小的连接密集的簇,它们会相互期詹卫华等:复杂网络研究进展:模型与应用结合形成较大较稀疏的簇,而这些簇又可能进一步形成更大更稀疏的簇这种自相似地嵌套形成了我们现实网络的严格而又精细的结构有趣地是,网络的层次性特性,可以通过简单的量来捕获,即C(k)曲线满足C(k)~kClauset等人建立了一种层次随机图模型,利用该模型对现实网络进行拟合,发现网络的层次结构可以解释网络的许多其它特征,如平均度、聚类系数和最短路径等发现网络中的连接往往需要在实验室或现场付出高昂的费用,这就使得许多现实网络是不完备的,在这种情形下预测网络中丢失的连接具有重要的意义Clauset进一步利用建立的模型设计了一个丢失连接的预测器,它与传统的方法相比,能够应用于更广泛类型的网络结构复杂网络的典型模型随机图(RandomGraph)随机图是图论中最年轻的分支之一,对它的系统研究起始于年ErdÊs和R†nyi的工作,他们发表了一系列的论文,建立了丰富的随机图理论的基础现实网络具有复杂的拓扑结构和未知的组织原理,总是呈献出某种随机性,因此用随机图作为网络的模型是最直接的一种选择ErdÊs和R†nyi中,定义了网络的一个极其简单的模型常称为ER模型,记为Gn,m,它是一个有n个节点m条边的随机图,这m条边随机放置在这n个节点间,也就是说它是具有n个节点m条边的所有可能的图的系综(Ensembles)另外一种替代的模型是有n个节点,节点间以概率p相连,记为Gn,p,它同样是一个系综,具有m条边的图出现的概率是pm(p)Mm,其中M=n(n)用z表示网络的平均度,则当n极大时,z=p(n)Upn,则度分布为pk=nkpk(p)nkUzkezk!()可见当n极大时,度分布近似为泊松分布,因此这种随机图也常称为泊松随机图(PoissionRandomGraph)随机图的结构性质随着p的变化而变化,当p=时是离散的N个点,当p=时是全耦合的完全图在p的变化过程中,存在一个从连接稀疏、只有少数边、所有的连通分量都较小而且尺寸分布符合指数分布的状态变化为连接密集、多数节点形成一个巨连通分量、剩余节点形成一些小连通分量而且它们尺寸依然保持指数分布的状态的相变当p=n时相变发生(此时z=),最大分量尺寸为O(n),在相变点之上,巨分量尺寸为O(n),在相变点之下,不存在尺寸大于O(logn)的分量,Newman用生成函数的方法得到了同样的结论网络的典型距离是L=lognlogz,这表明随机图具有小世界效应在随机图中,两节点间的边存在与否独立于其它边,因此不存在聚类性、度相关性,也不具有社区结构随机图模型与现实网络的许多特征并不相符,因而很少用于现实复杂系统的建模,但我们可以对随机图模型进行各种扩展度分布是网络最基本的拓扑特征,将现实网络的度分布与随机图模型相结合,就得到了配置模型(ConfigurationModel)给定度序列,生成具有给定度序列的所有的可能的网络,而且这些网络的权是相同的,这样的网络的系综就是配置模型自年代以来,许多学者对配置模型作了研究,如文献得到了具有巨分量的用pk表达的精确条件,文献给出了巨分量尺寸的期望,文献给出了相变点上下的非巨分量的平均尺寸,文献则给出了平均路径长度等配置模型在研究网络特征和行为中,具有重要的意义我们可以把配置模型作为一个空模型,观察到某个具体网络的某些特征对相应的配置模型的偏差,往往预示着新的发现小世界网络(SmallworldNetwork)根据人们的经验,通常,许多现实网络如技术网络、生物网络和社会网络等,既不是完全规则的,也不是完全随机的,而是介于两者之间Watts和Stroogatz基于这些观察,提出了WS模型,是指对一个具有n个节点的环格,初始时每个节点有k个邻居,将每条边以概率p进行随机重绕的过程(参见图)由于该模型生成的网络具有较短的特征路径,即网络具有小世界效应,故称为小世界网络,WS模型也因此常称图从规则的环格到随机网络的随机重绕过程FigRandomrewiringprocedureforinterpolatingbetweenaregularringlatticeandarandomnetwork为小世界网络(模型)上述的构造过程有可能破坏网络的连通,因此Newman和Watts稍后提出了通过随机化加边的方法构造小世界网络的模型,即NW模型还有许多改进的模型:加点、加边、去点、去边以及不同形式的交叉,产生多种形式的小世界模型小世界网络具有高的聚类系数,WS小世界网络的聚类系数为:C(p)=(k)(k)(p)()而NW小世界网络的聚类系数为:C(p)=(k)(k)kp(p)()小世界网络的典型特征是平均最短路径满足对数标度,但是到目前为止,还没有精确的解析表达式小世界网络的度分布与多数现实网络并不能很好匹配,对于NW模型和WS模型,其表达式都比较复杂,具体形式参见文献,无标度网络(Scalefreenetwork)节点度服从幂律分布,是指具有某个特定度的节点数目与这个特定的度之间的关系可以用一个幂函数近似地表示,幂函数曲线是一条下降相对缓慢的曲线,这使得度很大的节点可以在网络中存在对于随机网络和规则网络,度分布区间非常狭窄,几乎找不到偏离节点度均值较大的点,故其平均度可以被看作其节点度的一个特征标度在这个意义上,我们把小型微型计算机系统年节点度服从幂律分布的网络叫做无标度网络BA模型年,Barab‚si和Albert受WWW形成的启发,提出了构造无标度网络的演化模型,常称为BA模型该模型考虑了现实网络的两个重要特性:增长(growth)特性和择优连接(preferentialattachment)特性具体地说,该模型的构成过程如下:初始时刻有m个孤立的节点,在每一个时间步t=,,,,,nm加上一个新的节点,j同时加上从此节点出发的m条边,将新节点j连接到网络中已经存在的节点i是按照正比于i的度的规律来选择边的另一端节点:Fjyi=kiElkl()这样经过nm步后就生成了具有n个节点、m(nm)条边的网络当nm足够大时,所形成的网络的各节点的度满足幂律分布p(k)~k(C)而且,指数C=与模型的参数m和m无关BA无标度网络的聚类系数为C=m(m)(m)ln(mm)mlntt()可见,BA无标度网络不具有高的聚类系数BA无标度网络具有小世界特性,其平均路径长度为Wlognloglogn()BA无标度网络的度分布当网络规模极大时,可以用主方程法进行精确求解Krapivsky,Redner,Leyvraz与Dorogovtsev,Mendes,Samukhin独立地求出度分布:P(k)=m(m)k(k)(k)Wmk()显然,BA网络的度分布指数为一个不变量BA模型的变形由于典型的BA无标度网络并不具有高的聚类系数Holme与Kim提出了一种可调簇系数模型,称为HK模型在一些实际网络中,网络节点的存在老化现象,如在科学引用网络中,发表很久的论文很少引用,WWW中新的页面也很少链接到很久以前的页面Dorogovtsev等人提出的模型考虑了这一效应另外在电力网络和Internet等网络中,节点间的物理距离或者欧氏距离经常扮演着重要角色Manna和Sen研究了定义在欧氏空间上的无标度网络当标准的BA连接概率用距离因子lA调整后的行为语言网络语言是一个复杂的动态系统,它在各个层次(词汇、语法、语义)上显示出极其复杂的网络结构,而且它的结构不断地进行着演化认识和理解语言的共同的网络拓扑和演化的一般规律,无论是对于语言学研究本身,还是对于认知科学和信息处理以及其它一些领域都具有重要的意义语言网络的类型目前研究的较多的有以下种类型的语言网络词同现网络(Cooccurrencenetwork)在一个句中一起出现的两个词的关系就是词同现关系,许多词同现是由于词间的语法关系,有一些是习惯用语或固定搭配许多词同现的距离是,如redflower,stayhere等,也有许多词同现的距离是,如hittheball,Maryusuallycries在建立词同现网络时,词作为网络中的节点,同现关系作为网络中的边,一般只考虑距离为和的同现关系Ferrer和Sol†以英国国家语料库中的个词的四分之三的词为对象,考察了两种方法下构建的同现网络,一种方法是按照基本的方法建立的,称为无约束词网络(UWN),另一种方法是过滤掉了虚假的关联,只有超过随机同现概率的一对词才认为是词同现关系,这种方法建立的网络称为约束词网络(RWN)他们发现这两种网络具有与许多现实网络如生化网络和社会网络等相近的拓扑性质:小世界效应和较高的聚类系数,表列出了与对应的随机网络的比较结果在度分布方面,这两种网络同样具有BA网络类似的幂律性质,但值得关注的是它们的具有分为两段的幂指数,它们的第一段幂指数是,第二段指数是表词网络模式TabelWorldnetworkpatterngraphCCrandomddrandomUWNXRWNX句法网络(Syntacticnetwork)句法网络是由词和表示词之间的句法依赖关系构成,句法网络是有向的,一般规定弧的方向是由修饰语(modifier)指向中心词(headword)语句的句法依赖结构可以看作是全局网络包含的所有可能的句法连接的子集Ferrer和Sol†等人研究了三种欧洲语言:捷克语、德语和罗马语的三个全局句法依赖网络,它们分别是由三个文集中出现的所有词和句法依赖连接构成研究发现,这三个网络有相似的统计特征,从而揭示了一般句法网络的组织特征:平均路径都较短,而且平均路径长度的频率分布也大致相同聚类系数大大高于随机网络的聚类系数,表明句法网络的组织显著不同于随机网络度分布呈幂律分布,这为语言的发展是自组织的过程的观点提供了一个证据连通性强的节点彼此之间有互不相连的倾向,即句法网络具有异配性另外句法网络也呈献出明显的层次性语义网络(Semanticnetwork)语义网络中,节点是表示概念的词,边表示ISA,部分整体等概念间的关系语义网络可以由文档集中自动建立Sigmen和Cecchi专门研究了由Wordnet中名词构成的语义网络他们发现:所有的语义关系是标度不变的具有高的聚类系数类别型的概念在语义网络中居于主导地位,它们形成了树状,是整个网络的骨架内含的多义词(Polysemy)对网络起着重要的作用,它们的存在使得网络成为一个小世界Motter等人基于概念间的相似建立了一个语义网络,他们发现了网络有利于联想的高聚类性,同时网络的任意两词的期詹卫华等:复杂网络研究进展:模型与应用距离较短,而这使得搜索能更快找到目标到目前为止,我国学者已经对汉语言网络做了些基础性研究韦洛霞等人,首先发表了汉语词网络及词组网络的特性的实证结果,他们以汉语词词组代表网络节点,如果两个词词语有公共的汉字,则连一条边他们计算表明:这样构成的语言网络具有小世界网络和无尺度网络特性最近,Li和Zhou对汉字网络特性进行了研究他们用组成汉字的基本元素――偏旁部首来构成网络的节点如果两个偏旁部首构成一个字,则在它们之间有一条边他们的统计分析表明,这种汉字网络具有小世界和非泊松(nonPoisson)分布特性刘知远等基于大规模语料库,建立了汉语依存句法网络,并从复杂网络的角度对该网络进行了系统的实验考察他们的实验结果表明汉语依存句法网络具有复杂网络的两个基本性质:小世界效应和无标度特性汉语的这些句法上的统计特性,与捷克语、德语和罗马尼亚语等极为相似语言网络的模型Dorogovtsev和Mendes等人提出了一种语言演化的理论模型,将语言看作是一种由相互作用的词构成的增长网络网络的增长按照下述的规则进行:在每个时间步,t一个新的节点(词)加入到网络中,这个新节点以与旧节点的度ki成正比的概率连接到节点,i同时在旧节点间出现ct条边,这ct条边是按照两节点度之积成正比的概率出现,c是个与具体语言有关的常量图中描述了词网络的每一个时间步的演化规则该模型很好地解释了Ferrer和Sol†发现的词网络的度分布的幂指数分为两段的特点,图中的空心圆和实心圆分别表示Ferrer和Sol†按照两种不同的建立网络的方法得到的度分布,实线表示是利用模型计算的结果图词网络增长模式FigSchemeofthewordwebgrowth可以看出在k的整个范围内,在个数量级上惊人地一致利用该模型也可以得出结论,英国英语中大约有多个重要的核心词汇,而且核心词汇量由具体语言的c决定,并不会随着网络的演化而变化Steyvers和Tenenbaum遵循语言学家的建议,认为语义结构的增长主要通过分化过程(ProcessofDifferentiation):新词的意义或表达的概念来自于对已经存在的词或概念的某种变化一个加入到网络的新词,它和已经存在的节点区别在于它所具有的连接模式他们提出了语义网络增长的有向的和无向的两个版本的模型无向增长网络模型,初始时是一个具有M个节点的全连接网络在每一个时间步,将一个新节点和M条边加入到网络中,这M条边是通过首先选择要分化的结点,i然后选择i的邻域Hi(注意包括节点i本身及其邻居)中的M个与之相连分化节点i是根据词或概念的复杂性成正比的概率P(i)选择:Pi(t)=ki(t)En(t)l=kl(t)()其中,ki(t)是节点i在时间差t时的度,n(t)是t时网络的节点数节点i的M个邻域节点j是按照对应节点的实用性uj成正比的概率Pij:Pij(t)=ujElIHiul()可以将词的使用频率作为词的实用性对于有向增长网络模型,初始时是M个有向的全连接图,从每一个节点到其它任一节点都有一条弧在选择i节点时,相应结点的度是入度和出度之和,在加边时需要考虑边的方向:从新节点指向旧节点还是从旧节点指向新节点这两个版本的网络模型都能与已经考察过的语义网络的如平均最短路径、网络直径、聚类系数、度分布等统计特征一致图词网络度分布FigDistributionofthenumbersofconnections语言网络在自然语言处理中的应用随着在线信息的剧增,在最短的时间内从文档集中获取最重要的信息越来越成为人们迫切的需要从而文本的自动处理成为当前自然语言处理领域中的一重要的研究热点将语言网络应用于文本处理已经取得了一些引人注目的成果抽取式摘要(ExtractiveSummarization)是从原始文档中选择一些句子而生成的摘要方式,而抽象式摘要(AbstractSummarization)是在对文本中的信息进行理解的基础上对其进行的重新表达相对于句子抽取这种数据驱动的方法,抽象摘要需要解决的语义表示、推理和自然语言生成等问题则要困难得多从而现在自动摘要研究得最多的是抽取式摘要Erkan和Radev将文档簇看成是一个由彼此相关的句子构成的网络,与簇中许多其他的句子相似的句子更接近主题的中心,因此他们提出了基于中心的抽取式摘要方法每个句子表示为N维空间中的一个向量,N是目标语言中的总词汇量,句子中的每一个词在向量中对应的分量的值为该词在句中的出现频率tf乘以逆文档频率idf,从而两句子中的相似性定义为对应两向量的内积将文档簇表示为一个相似性矩阵,Erkan和Radev首先提出了一种基于度中心的方法:设置一个阈值,在网络中去掉低于该值的边,然后选择网络中度小型微型计算机系统年最大的m个节点所代表的句子在这种方法中,节点的每一条边相当于对它的中心性同等地进行平等地投票,这就会产生一个副效应,即无关的文档包含一些句子,如果仅考虑来自于该文档的投票,这些句子是被认为是权威的,从而错误地被抽取出来Erkan和Radev为克服这个问题,接着提出了另外一种更为复杂的基于特征向量中心的方法该方法的主要思想是考虑投票的来源,对投票节点按其中心性加权Mihalcea也提出了一种类似的与语言无关的自动文摘算法,紧接着Mihalcea和PTarau将这种方法推广到多文档情形文档自动摘要领域的研究者不可回避的一个困难问题是摘要的评价,一般而言总要由人涉入到摘要质量的评价目前,已经有些学者提出了文摘的自动评价的几种模型和方法,摘要的质量评价中两个广泛使用的两个指标是:句子的精确度(sentenceprecision),度量摘要中包含的与理想摘要匹配的句子所占的比例回召率(recall)度量摘要中回召的理想摘要中的句子所占的比例值得注意的是这两个指标在用于自动评价时,仅适用于理想摘要也是抽取式摘要的情形Santos等人将每一个文档和摘要都表示为一个文档图(documentnetwork),它是一个由概念和概念间关系构成的有向图他们首先利用LinkPaser工具将句子分解,然后抽取出名词短语和相互关系,这样就可以生成相应的文档图两个文档图的相似度定义为:sim(DG,DG)=nNmM()其中N是DG的概念数,M是DG的关系数,n是两个文档图的匹配的概念数,m是匹配的关系数另外,文本处理还有一些工作值得注意,如Veronis利用语言网络的小世界特性,把网络中的密集hub节点所代表的词取作关键词,用于信息检索Zhu等人利用语言网络的小世界特性来提取关键词,基本思路是:以文档中的词为节点,将处于同一句子的相邻的词连成一条边,如此构建网络然后,考察把每个词从网络中去掉前后网络平均最短路径长度的变化,变化大的词选为关键词Huan等人通过利用类似的原理,提出了从文本中提取关键词列表的算法Internet通常,Internet以两个不同的尺度来描述:自治系统(Autonomoussystem,AS)层和路由器(Router)层在AS层,网络的每个节点表示AS(也常称为域),一个AS典型地是由一个单独的机构管理,相邻的AS通过边界网关协议BGP交换信息在路由器层,每个节点表示路由器,一个AS内部通常有多个路由器Internet大约有个AS,它们是如何组织的,有什么拓扑特性,这些问题对于设计有效的通信和安全协议都是至关重要的,因此探索Internet拓扑是Internet研究的一个重要问题在这一节中我们将首先介绍Internet的拓扑特性,然后介绍Internet的模型和拓扑生成器关于Internet的交通动力学,可以参考综述,Internet的弹性可参考文献,Internet的拓扑特性年,Faloustsos等人根据美国应用网络研究国家实验室(NLANR)提供的年底至年底的AS层的数据,发现了Internet的AS层的拓扑满足一些幂律特性随后在年,Siganos和Faloustsos等人根据年至年的数据,在工作的基础上,总结出如下条幂律特性:()将节点按度数从大到小排列,节点在这个排列中的位置称为该节点的秩,则节点的度数与节点的秩数的常量幂成比例:dvWrRv()度大于d的节点在整个网络中所占的比例Dd与d的常量幂成比例:DdWdD()将邻接矩阵的特征值按从大到小排列,第i个特征值满足幂律关系:KiWiE()距离在跳数为h内的节点对,满足幂律关系:P(h)=chH,h<DN,hD其中,c=NM,N、M和D分别是网络节点数、边数和直径AS可以分为Stub域和Transit域,一个域是Stub域如果连接任意两点u和v的路径通过这个域仅当u或v在这个域中,Transit域则没有这个限制Stub域又可进一步分为MultihomeStub(与多个Transit域相连)和SinglehomedStub(与一个Transit域相连),Stub域之间在一些情形下也可以相连Transit域由一些连接紧密的骨干节点构成,每个骨干节点与多个Stub域相连,有些骨干节点还与其它的Transit域相连图显示一个域结构的例子基于这种结构使得任意两图Internet域结构的例子FigExampleofinternetdomainstructure节点间的路径具有这样的特征:如果两节点在同一个域中,它们间的路径S则在同一个域中如果在不同域中,则它们间的路径要通过一个或多个Transit域这就使得连接位于两个不同Stub域的节点的路径不会经过其它的Stub域因此,每一个AS可以认为属于一个特定的层(Tier)Subramanian等人根据域之间存在的客户供应商(CustomerProvider)关系和对等(PeerPeer)关系探索Internet的层次拓扑他们发现Internet可以分解为个层次:稠密核(Densecore)、传递核(Transitcore)、外层核(Outercore)、小的区域性ISP、客户稠密核由诸如Genuity、Sprint、ATT和UUNET等个大的ISP构成,它的连通性非常强,有个对等连接此外,稠密核有条边与客户AS相连,有条边与小区域提供者相连传递核包含个AS,个对等连接,欧洲和亚洲的顶级供应商都在该层中Cai等观察到各个层次的度分布期詹卫华等:复杂网络研究进展:模型与应用的幂律关系幂律网络的一个主要特点是存在少量度很大的节点,Zhou和MondragŽn将这类节点称为富节点(Richnode)富节点之间倾向于彼此相连,形成了连接紧密的富人俱乐部(Richclub)如果其中两个节点不相连,则它们极其可能有一个共同成员,这就使得任意两成员间的平均距离在到之间将网络的节点的度按逆序排列,则富人俱乐部的连通性可以定量表示为:U(rN)=Lr(r)=Lr(r)其意义是网络中前r个度最大的节点之间实际边数占可能的最多边数的比例富人俱乐部为网络核心层提供一种定量的描述Internet是增长的网络的典型例子,分析动态系统时识别它是否处于稳定状态很重要PastorSatorras等人根据NLANR收集的年至年的数据,考察了连通性k、平均聚类系数和平均最短距离这几个平均量的行为,结果如表所示可以看出,前两个量随着时间变化缓慢地增长,而平均距离随着时间缓慢地减少度分布的行为在时间上一致地符合幂律关系:P(k)=kC,C=,这与的结果相一致对年月的Internet数据的统计发现,度小于等于的节点占了网络的,度数大的节点的邻居多数为这些度小的节点,即总体上度相关是负相关的,或者说Internet是异配的Maslov等的解释是两节点间至多只有一条边,Park等用解析的方法证实了这一机制表AS的三个不同年份的平均性质TabelAveragepropertiesofthreedifferentyearsofAS年<k><C><d>Internet的拓扑建模与拓扑生成器拓扑建模是通过已经获得的关于Internet的经验数据,分析真实Internet可能具有的重要的拓扑特性,从而建立能够再现这些特性的模型拓扑生成器旨在根据建立的模型生成用于模拟现实Internet的网络到目前为止,已经出现了许多的Internet的AS层模型和拓扑生成器,年,Waxman设计了第一个拓扑生成器,它是一个随机图生成器考虑到Internet结构的层次性,Doar基于现实网络按广域网、城域网和局域网的组织特点,提出了相应的三层模型,建立了Tiers生成器随后Doar与Calvert和Zegura基于TransitStub模型建立了另外一个更为著名的GTITM生成器年Faloustsos等人揭示了Internet度分布满足幂律关系,而Tiers生成器和GTITM生成器生成的网络不满足这一特性,为此人们提出了基于度的拓扑生成器,这些生成器的共同特点是:生成的网络度分布和Internet的度分布匹配而不考虑Internet拓扑的层次性Brite,是一个通用的生成器,它定义了两个参数:IG(增量式生长)和PC(优先连通性)当这两个参数均为时,生成的拓扑与Waxmen的拓扑一致当这两个参数均为时,该生成器实现的实际上就是BA模型Tangmunarunkit等人将基于度和基于(层次)结构的生成器作了比较,发现基于度的生成器能够更精确地捕获所测量拓扑的大尺度结构,而且基于度的生成器能够产生类似于Internet的层次结构的形式层次性和度分布都是Internet的重要拓扑特征,Cai等人提出了一种机制,同时对Internet的层次和各层上的幂律分布建模Zhou和MondragŽn观察到Internet具有富人俱乐部特性,而已有的模型都不能产生这一性质,他们提出了PFP(positivefeedbackpreference)模型在该模型中,新节点和新边交互增长,选择节点时采用非线性优先连接PFP模型能够精确地再现许多拓扑性质,包括度分布、富人俱乐部、最大度和异配混合等PP网络PP网络又称为对等网络,它的特点是网络中的每个节点处于平等地位,同时扮演着客户和服务器的双重角色由于这种网络技术克服了传统的基于客户服务器的集中式共享资源模式所存在的明显的缺陷,它已经广泛应用于对等计算、协同工作、搜索引擎和文件共享等领域PP网络大致可以分为两种类型:结构化PP网络(例如Chord、CAN、Typestry和Pastry)、非结构化PP网络(例如Gnutella、eDonkey等)结构化的PP网络节点按照某种方式整齐地进行组织,而非结构化的PP网络的节点是随机分布的由于非结构化的PP网络有上百万的用户,它能够提供关键字查询,拓扑结构更为灵活,并且由于其节点间的交互更为复杂,是复杂网络理论研究和应用的更为合适的载体,因此我们将集中介绍非结构化PP网络的拓扑特性及其进行搜索的策略和算法PP网络的拓扑特性结构化的PP网络中的节点是按照一定的规则整齐地排列,在数学上可以用规则网络来表示,它们的拓扑特性很容易得到但非结构化的PP网络则是一个结构极其复杂的动态网络,PP网络的拓扑研究大多集中在非结构化PP网络上Gnutella是最流行的PP文件共享系统,具有大量的且不断增长的用户群体,它作为典型地非结构PP网络吸引了众多的研究者关注探索网络拓扑常用的方法是将一些称为爬虫(Crawler)的程序分布到网络中,每个爬虫利用PingPong机制并行收集拓扑信息,最后由一个中心节点将这些爬虫发现的拓扑汇集成整个网络的拓扑结构由于不断地有节点的加入和离开而引发网络的动态性,使得获得的网络拓扑实际上是某个时间点网络的快照Jovanovic收集了年月到月期间数据,发现Gnutella拓扑具有较短的平均路径(大约在~之间)和较高的聚类系数(与间,比随机网络高几十倍)并且具有Siganos和

用户评论(0)

0/200

精彩专题

上传我的资料

每篇奖励 +1积分

资料评分:

/10
2下载券 下载 加入VIP, 送下载券

意见
反馈

立即扫码关注

爱问共享资料微信公众号

返回
顶部

举报
资料