已阅读5页,还剩131页未读, 继续免费阅读
(计算机系统结构专业论文)信息网络拓扑结构与内容相关性研究.pdf.pdf 免费下载
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
信息网络拓扑结构与内容相关性研究:摘要 摘要 互联网的普及大大推动了社会信息的网络化进程,包括w e b 、博客( b l o g ) 、 即时通信( i n s t a n tm e s s a g e ) 、p 2 p 资源共享等各种信息网络正在迅速发展。继w a t t s 等人于1 9 9 8 年提出小世界网络模型和b a r a b i s i 等人于1 9 9 9 年提出了自由标度网络演化 过程中的两条基本规则之后,复杂网络研究的蓬勃发展推动了真实大规模网络的各 种网络性质研究。在互联网环境下,信息网络的拓扑结构与内容分布之间的相互关 系是网络内容计算和社会计算领域的一个基础而有本质的问题。这一问题对大规模 信息网络的规律性特征发现、信息网络建模、信息社区分析、高效率信息搜索与定 位、信息内容的深度挖掘以及信息传播与扩散机制的研究等都具有重要意义。本文 在详细分析了w e b 网络的拓扑结构与内容分布之间的规律性特征基础上,以信息网 络的物理连接拓扑结构与节点内容分布之间的相互关系为主线,对信息网络基本特 征、网络建模、社区分析及相关应用方面问题进行了深入细致地分析研究。 论文主要包括三部分成果: 首先,近几年人们研究发现连接度的幂律分布、局部的强聚团性等现象是大规 模稀疏化信息网络的共性拓扑结构特征。但是,信息网络的拓扑结构与内容分布之 间的量化关系却鲜为人所知。本文发现了信息网络中一些新的新特征:1 ) 网络微观 层面的拓扑结构与内容分布存在明显的映射关系,具体包括节点之间的物理连边概 率与节点之间的内容相关度成指数比例关系、节点形成三角形拓扑结构的概率与节 点内容相关紧密程度之间同样具有一种指数比例关系;2 ) 网络节点连接度整体分布 与节点内容相关度整体分布是线性无关的。这些发现揭示出“结构”与“内容”是 信息网络中两个截然不同而又相互依存的基本要素。 进一步,为了解释拓扑与内容( 功能) 之间的关系,本文提出了一种融合节点 知名度和节点相关度的w e b 网络演化模型( p r c pm o d e l ) 。从模型的理论推导、 演化学习验证以及大规模实验验证表明,该模型既能解释网络节点连接度的幂律分 布规律,又能产生与真实网络相类似的微观拓扑集聚现象;而更重要的是,p r c p 模型能够很好地拟合真实网络中存在的网络微观粒度拓扑聚团与内容聚团之问的映 射关系。由此,我们可以进一步推测信息网络中“微观层次的结构与内容构造规则 共同决定了网络整体的物理结构、内容分布以及两者之间的相互映射关系”这一新 信息网络拓扑结构与内容相关性研究:摘要 的论点。p r c p 模型能够比前人更好地解释信息网络中微观与宏观行为之间的关 系。 最后针对纯粹基于物理连边聚集程度划分的社区研究的不足,提出了一种多 尺度、动态化的信息社区概念。新的社区概念综合考虑了物理连边密度和节点之间 差异性的属性相关等多种尺度,以连边和消息转移概率来定义信息网络中的社区, 并在此基础上提出了相应的社区发现算法。实验表明该方法可以发现更有实际价值 的网络信息社区。 关键词:复杂网络、信息网络、自由标度网络、小世界效应、w e b 网络演化模 型、节点知名度、节点相关度、网络内敛度、信息社区、网络集聚性、连边概率、 成三角概率、三角相关度、拓扑结构 信息网络拓扑结构与内容相关性研究:摘要 a n a l y s i n gt h et o p o l o g i c a ls t r u c t u r ea n d t h ec o n t e n tr e l a v e n c eo ft h ei n f o r m a t i o nn e t w o r k s x u e q ic h e n g ( c o m p u t e ra r c h i t e c t u r e ) d i r e c t e db yp r o f e s s o rl ig u o j i e t h ep o p u l a r i z a t i o no fi n t e r u e tp r o m o t e st h ed e v e l o p m e n to ft h en e t w o r k si nd i v e r s e s o c i a li n f o r m a t i o n a f t e rw a t t sa n ds t r o g a t zp u tf o r w a r das m a l l w o r l dm o d e li n1 9 9 8a n d b a r a b d s ia n da l b e r tg a v eas c a l e f r e em o d e li n1 9 9 9 ,r e s e a r c h e r sa r ee n g a g e di na n a l y z i n g t h e c h a r a c t e r i s t i c so ft o p o l o g i c a ls t r u c t u r eo fr e a l i t yc o m p l e xn e t w o r k s i nt h ei n t e r n e t e n v i r o n m e n t ,i ti sb a s i ca n dk e yi s s u et oa n a l y z et h er e l a t i o n s h i pb e t w e e nt h et o p o l o g i c a l s t r u c t u r ea n dc o n t e n td i s t r i b u t i o no ft h ei n f o r m a t i o nn e t w o r k s i ti sac h a l l e n g i n gp r o b l e m f o rm a n yo t h e rp r a c t i c a lr e s e a r c hw o r k s ,s u c ha sh o wt om o d e lt h ed i v e r s ea n dc o m p l e x i n f o r m a t i o nn e t w o r k s ,h o wt o g e th i g he f f i c i e n tr e s u l t si nl a r g en e t w o r ki n f o r m a t i o n r e t r i e v a l ,h o wt om i n i n gd e e p e rc o n t e n tf r o mt h en e t w o r k s ,h o wt of i n dt h ee s s e n t i a lr u l e s o ft o p i cp r o p o g a t i o ni ni n f o r m a t i o nn e t w o r k sa n dh o wt op r e d i c tt h es p r e a d i n gb e h a v i o ri n t h en e t w o r k se t c a f t e ra n a l y s i n gt h et r a d i t i o n a lt o p o l o g i c a lc h a r a c t e r i s t i c so ft h ew e b ,w e f i n dt h a tt h e r ee x i s t sak i n do fh i g hc o h e r e n tr e l a t i o n s h i pb e t w e e nt h et o p o l o g i c a l c l u s t e r i n ga n dt h ec o n t e n tc l u s t e r i n gi nt h ei n f o r m a t i o nn e t w o r kb a s e do nm i c r o v i e w b a s e do nt h i sk i n do fr e l a t i o n sb e t w e e nt h et o p o l o g i c a ls t r u c t u r e sa n dt h ec o n t e n t d i s t r i b u t i o n sw es t u d yt h ew e bm o d e l i n g ,c o m m u n i t yi d e n t i f i c a t i o na n ds o m er e l a t e d p r o b l e m si nd e t a i l t h i sw o r kc o n t a i n st h r e em a i ns i g n i f i c a n tr e s u l t sa sf o l l o w s : f i r s t ,a f t e rs o m ee x i s t e dc h a r a c t e r i s t i c so ft h ew e bt o p o l o g ya r ev e r i f i e d ,s o m en e w c h a r a c t e r i s t i c sa r ed i s c o v e r e d :1 ) t h e r ee x i s t sa no b v i o u sm a p p i n gr e l a t i o nb e t w e e nt h e t o p o l o g i c a ls t r u c t u r ea n dc o n t e n td i s t r i b u t i o ni nt h ew e b e g t h el i n k a g ep r o b a b i l i t y b e t w e e nt w on o d e si se x p o n e n t i a l l ys c a l e dt ot h en o d e - n o d er e l e v a n c eo ft h e s et w on o d e t h et r i a n g u l a r i z a t i o np r o b a b i l i t yi se x p o n e n t i a l l ys c a l e dt oc o n t e n tt i g h t n e s sa m o n gt h r e e n o d e s 2 ) t h ed i s t r i b u t i o no fd e g r e ea n dt h ed i s t r i b u t i o no fn o d e n o d er e l e v a n c ea r e i n d e p e n d e n ti ng l o b a lv i e wi nt h ew e b i no r d e rt of i n do u tw h yt h e r ee x i s t ss u c hk i n do fr e l a t i o nb e t w e e nt h et o p o l o g i c a l s t r u c t u r ea n dc o n t e n td i s t r i b u t i o n ,w ec r e a t ean e we v o l v i n gm o d e lf o rt h ew e b i nt h i s n e wm o d e l ,t h ep o p u l a r i t y ( c o n n e c t i v i t y ) a n dn o d e n o d er e l e v a n c ea r ec o u p l e di n t o i i i 信息网络拓扑结构与内容相关性研究:摘要 p r e f e r e n t i a la t t a c h m e n td u r i n gt h ee v o l u t i o no ft h ew e b w ec a l li ta sp r c p m o d e l b o t ho f t h e o r e t i c a l l ya n a l y s i sa n de x p e r i m e n t ss h o wt h ep r c pm o d e lc a ns i m u l a t ea n dp r e d i c t m a n yt o p o l o g i c a lc h a r a c t e r i s t i c sa n dc o n t e n td i s t r i b u t i o n s ,e s p e c i a l l yi tc a ns i m u l a t et h e c o r r e l a t i o nb e t w e e nt h es t r u c t u r ea n dt h ec o n t e n ti nt h ew e b t h e s er e s u l t sa l s os u g g e s ta c o n c l u s i o nt h a tt h em i c r o - t o p o l o g i c a lr u l ea n dm i c r o - v i e wc o n t e n td i s t r i b u t i o nb r i n gt h e g l o b a ls t a t i s t i c a lc h a r a c t e r i s t i c so ft o p o l o g y ,c o n t e n ta n dc o r r e l a t e dm a p p i n gb e t w e e nt h e m a tl a s t ,am u l t i d i m e n s i o n a la n dp r o b a b i l i s t i cc o m m u n i t yi sp r o p o s e db a s e do nt h e c o n n e c t i o n ( e d g e s ) d e n s i t ya n dm e s s a g et r a n s f e r r i n gp r o b a b i l i t ya m o n gd i v e r s en o d e s a c c o r d i n gt or a n d o mw a l ka n dd e l t a c l o s u r em e c h a n i s m ,w ec a l lt h en e wc o m m u n i t ya s d e l t a c l o s u r ec o m m u n i t y m a x i m a lv a l u ec o n s t r a i nb a s e dd e l t a c l o s u r ea l g o r i t h mi sv a l i d f o rd e l t a - c l o s u r e c o m m u n i t yi d e n t i f i c a t i o n e x p e r i m e n t s s h o wt h ed e l t a - c l o s u r e c o m m u n i t i e sa r em o r es u i t a b l ef o ri n f o r m a t i o nn e t w o r k s k e y w o r d s :c o m p l e xn e t w o r k s ,i n f o r m a t i o nn e t w o r k s ,s c a l e f r e en e t w o r k ,s m a l l w o r l de f f e c t ,e v o l v i n gm o d e l ,n o d ep o p u l a r i t y ,n o d e - n o d er e l e v a n c e ,i n n e rc o n v e r g e n c e , c o m m u n i t y ,c l u s t e r i n gc o e f f i c i e n t ,l i n k a g ep r o b a b i l i t y ,t r i a n g u l a r i z a t i o np r o b a b i l i t y , t r i a n g l er e l e v a n c e ,t o p o l o g i c a ls t r u c t u r e 中国科学院博士学位论文信息网络拓扑结构与内容相关性研究 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得 的研究成果就我所知,除了文中特别加以标注和致谢的地方外,论文 中不包含其他人已经发表或撰写过的研究成果与我一同工作的同志对 本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意 作者签名:苷争参凑日期:二口一f 彳g l 关于论文使用授权的说明 中国科学院计算技术研究所有权处理、保留送交论文的复印件,允许 论文被查阅和借阅;并可以公布论文的全部或部分内容,可以采用影 印、缩印或其它复制手段保存该论文 作者签名:辛学旅导师签名: 日期:二口口丘占 第一章引言 第一章引言 n o ww ea r ec l o s et ok n o w i n g j u s ta b o u te v e r y t h i n gt h e r ei st ok n o wa b o u tt h e p i e c e s b u t w ea r e 和a sw eh a v ee v e rb e e n f r o mu n d e r s t a n d i n gn a t u r ea saw h o l e 。- b a r a b d s i 1 1 网络效应 我们生活在一个网络世界里。从生物学领域来看,网络关系从微观到宏观无所 不在,例如基因表达结构网络、蛋白质相互作用网络、新陈代谢网络、生物群体网 络、生态网络( 食物链、水循环等) 等等;人类构造的各类物理技术网络,包括人 们日常生活中水电煤气网络、通讯网络( 包括,电话、电视、广播、i n t e r n e t 等多类 技术网络) 、交通网络等是人类现代社会的无法或缺的支撑环境;在物理网络之上 的各类信息网络,例如:w e b 网络、电子邮件网络、电子金融交易网络、短信网络 以及与社会经济、政治、文化、军事等活动密切相关的领域信息网络等植根于我们 工作,学习、生活的每一个角落中。同样,人类社会中的任何交往活动以及各种有 形无形的社会关系本身就是各类不同层次的、交叉重叠的的社会网络。 不仅仅单个网络无所不在,异构网络之间存在不同层次的相互依赖关系也是无 所不在的。而这种依赖关系的本质是不同网络节点之间存在多样性的相互作用或者 连边关系。例如w e b 网络主要以i n t e m e t 网络为基础、人类学习网络则架构在不同类 别的类通信网络、信息网络和社会网络之上的。可以说,如果没有网络,没有网络 中大量存在的连边( c o n n e c t i o n ) ,就无法讨论生命的进化,也无法研究或者推动文 明的持续发展。 需要注意到的是,对人类来讲,尽管网络的存在是有重要意义的,但是网络的 有益效应和有害效应往往是同时存在的比较常见的有害效应就是疾病的传播、网 络安全问题等相对于静态的存在网络,具有有害效应的网络往往是具有很强动态 性和时效性的逻辑网络例如,当年s a r s 的大范围感染、当前持续了几年的全球禽 流感扩散、前赴后继的网络流行病毒、或大或小的网络舆论扩散、网络谣言的传播 等等。这些网络产生明显影响的时候人们往往无法追查到源头、影响消失的时候又 无法知道其未来的发展轨迹。类似这种动态传播的网络效应,常常被人们归之为网 络的一种动力学现象。 还有一个现象是大部分真实网络是不可逆的,是非对称的。以我们的生态环境 网络为例,一旦一个区域遭受到类似乱砍乱伐、围湖造田等破坏性活动的时候,这 个区域几千年形成的良好生态环境几年内将被完全摧毁而当人们认识到问题严重 性的时候,尽管通过大量的退耕还林、植树种草等补救措施,往往是有了8 0 投入 却难以获得2 0 的效果,而真正能够复原到原来状态几乎是没有先例的出现这种 现象的原因是人们对网络的认识还处于表面层次,而表面特征往往是内在因素演化 中国科学院博士学位论文信息网络拓扑结构与内容相关性研究 后的一些突变效果。认识上的困难包括两个方面,其一是网络系统的内在因素往往 难以识别;其二是人们对突变( 涌现) 规律还无法量化分析。 虽然目前还没有一个清晰的定义,我们还是可以将这些规模巨大、结构与关联 关系复杂、存在大量动力学现象以及非线性不可逆的涌现特征的网络系统统称为复 杂网络系统。 无论我们喜欢还是不喜欢,网络是客观存在的,也是无所不在的。人们对网络 科学的研究还处于萌芽阶段,目前还没有一个非常清晰成型的研究理论体系和一套 有效的定量分析工具而一个可喜的现象是,无论这些网络以及网络现象的差异性 有多大,科学家们已经发现了复杂网络的一些有趣的规律性特征,而且人们越来越 相信有可能会发现一些共性的基本规律而把握了这些基本规律后,我们有理由相 信对认识网络、很好得利用网络将具有重要价值。 1 2 复杂网络研究的基本问题 “拓扑结构决定系统功能”是人们一开始研究利用网络来描述真实系统的一个 潜在假设。根据这个假设,如果我们将系统内部的各个元素作为节点,元素之问的关 系视为连接,那么一个系统就构成了一个网络。而对一个系统的网络拓扑结构的有效 模拟以及对相关拓扑结构特征的准确预测就成为衡量网络研究成功与否的重要标 志。 人们早期的工作主要是面向经典的规则图研究。1 9 5 9 年,两位匈牙利数学家 e r d o s 和r 6 n y i 为了描述通信和生命科学中的网络,提出了随机网络模型。其基本思 路是通过在网络节点问随机地布置连结,就可以有效地模拟出真实系统的拓扑结 构这种方法及相关定理的简明扼要,导致了图论的复兴,数学界也因此出现了研 究随机网络的新领域。而在过去的4 0 多年里,科学家惯于将所有真实复杂网络都看 作是随机网络 随机网络理论有一项重要预测:尽管连结是随机安置的,但由此形成的网络却 是高度民主的。也就是说,绝大部分节点的连结数目会大致相同。实际上,随机网 络中节点的分布方式将遵循钟形的泊松分布。连接数目比平均数高许多或低许多的 节点,都十分罕见。有时随机网络也称作指数网络,因为一个节点连接k 个其它节点 的概率,会随着k 值的增大而呈指数递减。 随机网络理论另一个预测:网络的成团性是均匀的。随即产生的连边使得网络 中的节点聚成三角形或者其它全连接子图的机会是均等的由此可以预测在一个连 接稀疏的大规模随机网络里面,网络节点局部成三角的密度比较低。从而导致网络 的传递性比较低,网络节点之间的平均最小路径相对比较远。 然而,随机网络模型的这两种预测在大量真实网络中都是不准确的。上个世纪 9 0 年代末,两篇著名的文章使得人们重新认识了这两种网络特性。w a t t s 和s t r o g a t z 第一章引言 于1 9 9 8 年在 n a t u r e 上发表的论文表明能够产生高聚团性和短路径的网络模型既 不是规则网络模型也不是随机网络模型,而是介于两者之间的一种新模型。b a r a b :i s i 和a l b e g 于1 9 9 9 年在 s c i e n c e 发表的论文表明大规模真实稀疏网络的节点连接度 分布是幂函数形式,他们提出的一种自由标度网络模型能够预测这种规律 区别于随机网络模型的复杂网络研究引起了科研人员的广泛关注。迄今,包括 小世界效应、连接度的幂律分布以及高集聚性等成为大部分复杂网络的共性特征 最近5 、6 年以来,大规模复杂网络的研究成果、影响范围、参与人的数量等都出现 了“涌现”现象。目前,复杂网络研究涉及到的范围超过了我们在上面提到的所有 真实网络研究领域。大量关于复杂网络的文章在s c i e n c e 、n a t u r e 、p n a s 、p r l 等国 际一流的刊物上发表,从一个侧面反映了复杂网络已经成为国际学术界一个新兴的 研究热点。一个明显的例子是,如果我们通过g o o g l es c h o l a r 搜索的话,上述两篇文 章被人们引用的次数已经超过了1 5 0 0 次。图1 1 给出最近几年与复杂网络研究相关论 文的增长情况。 包括: 图1 1 题目中出现复杂网络( c o m p l c x n e t w o f k ) 的论文增长情况统计 从复杂网络研究的效用目的来看,复杂网络的研究问题可以细化为如下四类, 1 ) 复杂网络到底具有什么样的拓扑结构? 其基本特征是什么? 有什么价值? 2 ) 复杂网络的拓扑结构与网络所承载的功能、语义之间存在什么样的关系? 如何发现? 如何度量? 3 ) 网络中非线性涌现现象以及其它动力学特征是什么? 如何度量? 4 ) 网络的鲁棒性和安全性什么特征? 如何控制? 1 来源:i n t r o d u e t l o nt oc o m p l e xn e t w o r k s :m o d e l i n g , c o n t i 柚ds y n c h f o n i z a t i o i lb r l e f m gb yg i l 柚m n gc h c n c i t y u n i v e r s i t y o f h o n g k o n g , t o t h c f i r s t c h l n e s c o n f e r e n c e o l l c o m p l e x n e t w o r k s , w u l u m ,c h i n a , a p r i l 2 0 0 5 3 中国科学院博士学位论文信息网络拓扑结构与内容相关性研究 绍。 关于复杂网络的研究内容和挑战性问题介绍将在第二章综述中作相对详细地介 1 3 信息网络研究背景 互联网的普及大大推动了社会信息的网络化进程包括w e b 网络、即时通讯系 统、p 2 p 信息共享网络、博客群落、邮件网络、短信网络以及与各类专业、垂直性质 的信息网络已经成为人们工作、生活、学习等各类活动的重要组成部分,已经成为信 息社会的基础环境。这些信息网络其节点规模从数千万到上百亿,其消息传播模式 复杂多样,信息内容分布复杂。不失一般性,对如此大规模异构信息网络的规律性 特征发现、高效率信息搜索与信息定位、信息内容的深度挖掘以及信息动态传播机 制和信息扩散行为的分析是信息网络研究的现实需求,也是极具挑战性的研究问 题 针对信息网络发展的现状,对复杂信息网络研究尤其需要关注如下一些具体问 题: 信息网络越来越社会化、多样化、个性化,网络节点之问的关系非常复杂,交 叉重叠的虚拟社区大量存在。由此,信息网络的建模除了关注其物理连接拓扑结 构,更需要关注内容分布等其它相关属性特征第一个例子是,目前以w e b 论坛、 博客群落、即时通信以及各类门户系统为代表的信息网络正面临着一场世界性的升 级,人们称之为从互联网1 0 逐步迈入互联网2 0 时代。互联网2 0 发展受到信息技 术、经济学理论和社会学等综合因素的影响其中包含了复杂网络的多种统计特 征,例如满足个性化条件和社会网络建立基础的小世界效应、社会资本驱动、长尾 理论、去中心化、弱纽带( 弱链接) 等等;互联网2 0 之所以是一次重要的变革。因 为互联网2 o 完全改变了生产关系,解放了生产力。互联网2 0 让每一个人能够真正完 全参与到互联网的共同创作中来,相对于互联网1 0 时代网络中被动地参与和缺乏深 层联系的简单页面跳转,互联网2 0 是在实现让每一个人成为网络社会的真正主体, 从而彻底释放网民创造潜能,带来一种全新的自主信息交互方式。第二个例子是基 于p 2 p 模式的信息网络发展势不可挡。2 0 0 2 年,当尼古拉斯曾斯特姆( n i k l a s z e n n s t r o m ) 把p 2 p 音乐下载软件k a z a a 卖给一家小公司时,得到了5 0 万美元;而2 0 0 5 年,他把p 2 p 通信软件s k y p e 丑售给e b a y l l ;j ,赚到了2 1 亿美金有运营商统计,目前 类似b f 下载这样的p 2 p 软件占去互联网总流量的4 0 以上。无论足w e b 2 0 还是p 2 p 信 息网络,信息网络内部存在大量的逻辑结构和虚拟社区现象,而这些逻辑结构和虚 拟社区的形成与信息节点之问的物理联系( 连边) 、信息节点的内容属性、信息传 第一章引言 播的历史行为、信息主体的兴趣相似性等多种因素密切相关。由此,对信息网络的 研究再也不能仅仅依赖于对网络节点之问的物理连边拓扑结构分析 网络信息的深度内容分析需要考虑多尺度特征空间的融合计算问题基于 w e b 2 0 和p 2 p 网络的上述特征,单纯基于内容特征空间或者连接拓扑特征空问的网 络信息搜索、信息浏览定位服务往往效果不会很好面向多层次、个性化、社会化 网络信息挖掘需要综合考察网络节点的内容特征、社区环境、时序特征,网络行为 特征、网络信息的增长变化特征等多尺度空间融合的信息挖掘技术,在此基础上探 讨更精确、更个性化、更深层的网络信息发现、搜索与定位技术 另外:网络舆论的蝴蝶效应使得人们越发关注对信息网络中的消息扩散规律以 及热点话题涌现相关特征的分析一般情况下,随着互联网的普及,信息受众对网 上良莠不齐的信息已经形成了自我甄别能力由此,网络信息的产生、传递、扩散 直至达到一个稳定状态是一个相对平稳的过程然而,我们经常看到网上一个不经 意的谣言往往会使得股价崩盘;一篇平常的报道往往会在网上像雪崩一样急遽扩 大,由此会造成强大的舆论压力或者正面的重大社会影响。而这种现象的产生的机 制目前看还是非常不清楚的而大规模网络病毒扩散、d d o s 攻击、垃圾信息泛滥等 网络安全事件使得人们更加关注信息网络的鲁棒性、安全性等问题 1 4 本文主要贡献与组织 本论文基于上述的背景,在详细观察信息网络的拓扑结构特征以及拓扑聚团性 和内容聚团性之间的映射关系基础上,从模型、算法和应用三个层次上在信息网络 拓扑结构与内容的相关性上进行了深入细致的探讨,研究工作主要包括以下几个方 面: 1 ) 在验证了前人提出的w e b 网络拓扑结构特征基础上,进一步发现了一些新的特 征;微观拓扑结构中的强集聚性( 平均聚团系数很高) 、微观层面拓扑结构与 内容相关性存在明显的映射关系、网络节点连接度分布与节点内容相关度整体 分布是线性无关的等 2 ) 通过对复杂网络的拓扑结构分析及网络建模相关的研究进行细致的探讨,提出 了多尺度综合决定论,特别针对信息网络提出一种融合节点知名度和节点相关 度的w e b 网络演化模型( p r c pm o d e l ) 。从模型的理论推导、演化学习验证以 及大规模实验验证表明,该模型能够产生解释网络拓扑结构中明显的微观拓扑 集聚现象( 很高的聚团系数分布) ;能够很好地拟合网络连边分布与网络内容 相关分布之间的映射关系;能够很好的预测网络拓扑聚团性和内容聚团性之问 的映射关系。 3 ) 提出了基于连边密度和转移概率内敛的社区概念,同时,定义了一种消息转移 概率密度的社区定义并分析了相关社区发现算法新的社区定义可以将物理连 5 中国科学院博士学位论文吖言息网络拓扑结构与内容相关性研究 边和节点之间内容相关度综合起来从而以此发现更有实际价值的信息网络社 区结构。 4 ) 应用前景分析,对网络拓扑结构的分析以及网络建模研究主要关注的是对真实 世界的理解,而其最终目的是通过这些研究提升基于这些网络之上的应用能 力,进而预测和控制网络系统的行为等 论文内容的具体安排如下:第二章,对复杂网络研究工作做了简单的介绍尤 其是我们所关注的一些网络基本特征、度量方法和建模相关的工作与信息网络应 用相关的研究也是我们考察的重点容;第三章对w e b 网络的拓扑结构特性和拓扑结 构与内容分布之间的映射关系进行了详细地观察和分析:在第三章观察到的w e b 网 络基本特征基础上,本文在第四章提出了一种节点知名度与节点相关度融合得w e b 网络演化模型;随后,基于物理连边和内容属性等多尺度判定前提,本文在第五章 提出了一种多尺度、概率化的信息社区概念,并提出了针对性的社区发现算法。论 文最后作了一个简单的总结。 第二章复杂网络研究概述 第二章复杂网络研究概述 最近几年复杂网络成为人们广泛关注的交叉学科研究的热点包括物理学、数 学、生物学、经济学、社会学以及信息科学等领域的众多科学家从不同角度对复杂 网络的特性进行了分析,相关的工作涉及复杂网络的功能与拓扑结构分析、复杂网 络的建模、复杂网络动力学特性分析以及基于复杂网络的各种应用研究等。本章综 合介绍了与复杂网络的拓扑结构分析及网络建模相关的研究工作,着重论述复杂信 息网络相关的研究进展。 2 1 基本概念与研究背景 2 1 1 基本概念 从数学上看,一个网络就是一个图,它包含节点集合和边集合。在介绍网络与 图的研究背景之前,我们先统一一下本文涉及到的与图理论相关的基本概念定义 定义2 1 :图的定义 一个图g 定义为一个( v ,e ) ,记作g = ( v ,e ) ,其中 ( 1 ) v 是顶点的集合,其中的元素称为节点( n o d e o r v e r t e x ) ; ( 2 ) e 是无序积矿矿中的一个子集合,其元素称为边倒g e ) 。边是两个节点之 间的连线。 ,;0 、j v e r t e x i 久一以嚣 翘。j 。 图2 1 图定义的示例上图中,左图为含有8 个节点和1 0 条边的简单 图。右图为含5 个节点和5 条边的简单图。右图中的左边三个节点连 接形成一个三角形子图。 定义2 2 :子图与完全图 当矿( h ) 矿( 回,且且旧) _ c e ( c ) ,我们称图h 是图g 的子图,记作日g 每一对不同节点均有一条边相连的简单图被称为完全图( c o m p l e t eg r a p h ) 节点的个数称为完全图的阶。一般地,我们将一个图中的一个3 阶完全子图称为一个 三角形( t r i a n g l e ) 。 定义2 3 :图的基本分类 当图g 中的边是有向边的时候,一条边在图中对应的两个关联节点分别为该条 边的起始点和终止点,图g 称为有向图当图g 中的边是无向边的时候,图g 称为无 7 中国科学院博士学位论文信息网络拓扑结构与内容相关性研究 向图。设 o c v ,e ) 中,如果对g 中的每一条边( 屹,v ,) ,相应的有一个权重h ,。则 g 及其权重集合统称为赋权图。同样,赋权图也可以分有向赋权图和无向赋权图。 定义2 4 :连接度 一个图中,节点的连接度为与该节点相连的边的数量。对于有向图,一个节点 的连接度包括指向该节点的边数( 入度) 和从该点指出的边数( 出度) 。 数学家和物理学家在研究网络属性的时候,往往只关心节点之间有没有边相 连,至于节点到底在什么位置,节点具有什么自有属性,边是长还是短,是弯曲还 是平直等等这些因素都是他们不在意的。即网络模型中的节点和边是抽象的概念。 定义2 5 :网络的拓扑结构 我们把网络中不依赖于节点的具体位置与属性以及边的具体形态就能表现出来 的性质叫做网络的拓扑性质,相应的结构叫做网络的拓扑结构。 在科学研究界。大部分的网络研究工作关注于网络拓扑结构相关的性质分析。 而其中最重要的当是如何提出一种有效的网络模型来描述和分析真实系统的拓扑结 构。 2 1 2 从规则网络、随机网络到复杂网络 最早的网络与图的研究起源于1 7 3 5 年德国数学家欧拉解决哥尼斯堡七桥 ( k f n i g s b e r gb r i d g e ) 问题随后,网络研究逐步发展成为系统化的科学理论。早 期,网络研究大多应用于社会科学领域,例如社会关系的建模等此时的网络模型 大多具有规则化的结构,例如一维链、二维晶格、完全图,二部图等。到了2 0 世纪 5 0 年代末,两位匈牙利科学家e r d o s 和r r n y i 提出了一种随机网络模型( e rm o d e l ) l “”9 1 在e r 模型中,两个节点之问的连边根据一个概率来生成随着e r 提出随 机网络模型之后,面向真实网络的建模以及网络理论方面的研究取得了很大进展。 在随后的很长一段时间以来,人们一直想当然地认为随机网络模型是现实系统的理 想模型 然而到了上个世纪9 0 年代,随着计算机处理能力的提高以及可以获得计算的数 据规模空前增大,人们发现传统的网络模型在处理大规模网络的时候出现了很大的 问题。首先,由于网络研究由原来的针对几百个节点的小网络,转向了研究规模更 大的、结构更加复杂的网络系统。以前一些方法和问题在处理大规模的复杂网络系 统时变得无能为力例如,传统图论里面对单4 z , j 点、单个节点对网络连通性的影 响等研究,在千万级以上节点规模的网络中类似的评价几乎没有意义,因为在如此 大规模的网络里面,单个节点对网络整体的连通性和鲁棒性几乎没有任何影响。其 次,通过对大规模真实系统的统计分析,人们发现很多真实网络所展现出来的大量 特性都无法用随机网络模型来解释这些问题使得人们研究复杂网络时需要更加复 第二章复杂网络研究概述 杂的统计工具来刻画其本身的特征,也需要新的理论模型来描述整个复杂网络,以 及对其行为作出分析和预测。 我们知道,现实生活中的网络无所不在,而且大部分现实网络无论是节点和连 边的规模还是网络的结构来看,都是复杂网络。当前虽然复杂网络研究已经成为热 点,然而目前人们还没有给出复杂网络的精确定义。比较公认的大部分真实复杂网 络具有三个主要特征:小世界效应、自由标度性( 也称无尺度性) 和高聚团性从 系统科学来看,复杂网络是典型的复杂系统。此处,我们借用复杂系统领域科学家 对复杂网络的特征进行了一些归纳i 抽“2 0 0 4 1 ,具体如下: 1 ) 网络行为的统计性:网络节点数可以有成百上千万,甚至更多,从而使得 大规模性的网络行为具有统计特性; 2 1 网络连接的稀疏性:一个n 个节点的具有全局耦合结构的网络的连接数目为 o ( n 2 ) ,而实际大型网络的连接数目通常为o ( n ) ; 3 1 拓扑结构的复杂性:网络拓扑结构既非完全规则也非完全随机,但却有其 内在的规律; 钔节点动力学行为和网络时空演化复杂性。 以上特征,反映了实际网络的复杂性特征。一方面,它具有无序演化的特征, 另一方面,它也具有增加有序程度的演化特征。它具有分形和混沌的特征,具有自 组织演化的特征,也具有形成序参量的特征因此,复杂网络的研究可能会综合以 往的各种自组织理论、非线性和复杂性理论研究的成果,从而形成新的复杂性研究 机制的理论。 对经典的复杂系统研究,例如对宏观经济学的研究、对地球气候变化的研究 等,主要有三个学派分别为:关注非平衡统计方法,采用偏微分方程来构建复杂 系统:以圣达菲研究所( s a n t af ei n s t i t u t e ) 的科研人员为首的一些科学家提出来的 复杂适应系统( c o m p l e xa d a p t i v es y s t e m s ) 模型方法,他们采用规则和自适应计算 相结合的方法,对真实复杂系统的数据进行仿真计算,比较有代表性的方法是基于 智能主体的模型( a g e n tb a s e dm o d e l ) ;最后一类方法是纯粹的数据驱动建模方 法,这类方法主要以遗传算法的应用为代表。 实证结果表明,大多数的真实网络具有小世界效应( 较小的最短路径) 和聚集性 ( 相对较大的聚团系数) ,见表2 2 所示。然而,规则网络虽具有聚集性,平均最短路径却 较大;随机图则正好相反,具有小世界效应,但聚集系数却相当小。可见规则网络和 随机网络并不能很好地展现真实网络的性质。这说明现实世界既不是完全确定的也不 是完全随机的。 w a t t s ;f f f s t r o g a t z l w = “1 9 9 8 1 提出了一种介于规则网络和随机网络之问的小世界网络 模型( w s 模型) 该模型兼具小世界效应和高聚集性b a r a b 6 s i 和b e n i 断舢“1 9 9 9 1 指出,大量的复杂网络的连接度呈幂律分布,其分布形式与网络的规模无关,他们 9 中国科学院博士学位论文信息网络拓扑结构与内容相关性研究 提出来的网络模型被称为自由标度( s c a l ef l e e ) 的网络模型( b a 模型) 。随着w s 模型和b a 模型的提出,人们对大规模复杂系统的研究真正进入了复杂网络模型时 代。 到目前为止,针对复杂网络研究的基本问题可以简单概括为五个方面密切相关 却又依次深入的研究内容: 1 ) 通过实证方法度量和分析网络的统计性质:具体目的是发现复杂网络的一 些统计特征,例如路径长度、连接度分布、拓扑结构的层次化与聚团性特 征等,并研究相关特征的有效评价方法: 2 ) 构建相应的网络模型来理解这些统计性质何以如此:主要为复杂网络建模 研究。其目标是提出一种相对严谨、可计算的形式化模型,在此基础上分 析和解释网络所具有的拓扑与功能相关的特征; 3 ) 在己知网络模型基础上,发现或者挖掘出与功能和语义相关的深层内容。 例如针
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2026年电商行业发展趋势报告及新零售市场分析
- 2026年养老服务行业报告:市场需求与产业发展
- 2026年眼科医疗服务市场供需分析与专科连锁发展策略报告
- 2026年环保产业报告:绿色发展与循环经济模式探索
- 2026年汽车行业盈利策略与壁垒研究
- 2026年互联网企业员工心理健康报告:关注年轻一代的心理需求
- 2026年能源行业环保合规与风险评估报告
- 《乐游原》李商隐
- 结直肠肿瘤经自然腔道取标本手术专家共识(2019版)
- 高中物理力学系统平衡条件应用技巧训练试题及答案
- 2026年健康管理师职业技能等级认定(一级)操作技能考前冲刺试题
- 关键核心技术领域青年人才成长规律和培养支持的建议
- 中国国际展览中心集团笔试考点2026
- 经营主体信用监管标准体系研究报告2026蓝皮书
- 发展对象入党答辩常见问题与参考答案
- 2026油田化学品行业市场发展分析及前景趋势与勘探开发投资研究
- 外墙真石漆施工安全
- 高空拆除作业安全技术交底指南
- 三年级英语课标解读课件
- 护士职业安全防护ppt课件(图文)
- 住宅小区安全技术防范系统建设技术规范
评论
0/150
提交评论