（管理科学与工程专业论文）复杂网络模型构建及其在知识系统中的应用.pdf

人连理工大学博士学位论文 摘要 复杂网络作为新兴的对复杂系统进行定量描述的工具，可以对复杂自适应系统进 行建模和分析。如果把知识系统中的“要素”和“关系”分别抽象成节点和边那么 可以利用复杂网络理论对知识系统进行建模与分析。知识管理具有高度复杂性以及跨 学科的特点，兼有自然与人文科学两种属性。我们从系统科学的角度从整体上对其进 行分析。由于知识的高度抽象性，知识的拥有者和知识的载体之间有着错综复杂的联 系，构成了各种类型的知识系统。知识系统是以网络的结构形式存在的复杂自适应系 统。本文从系统结构与系统功能的角度，对复杂网络理论中的演化机制及若干动力学 行为进行了理论研究。并利用复杂网络对某一微观知识系统进行了实证研究，对这一 系统中的知识进行表示，分类以及聚类等分析，分别对宏观层次的整体学科发展趋 势，中观层次的学科代码调整和微观层次的学科领域知识的发展进行了分析。 首先，分别从拓扑网络和加权网络的角度对无尺度网络的演化机制进行了研究， 重点研究了正负匹配度可调的网络演化机制。提出了多步连接的无尺度网络增长模 型，正负匹配度可调模型以及自学习双向选择加权网络模型；从宏观角度研究了平均 距离约束下的无尺度网络演化模型。通过细致地研究有向无尺度网络中出度和入度的 关系，发现入度的度分布指数由出度的平均度决定。 其次，从结构决定功能，功能影响结构的角度，对复杂网络上的鲁棒性、同步能 力以及传播行为等动力学性质进行了研究。利用最优化方法，优化某一动力学指标， 观察优化过程中和最优状态下网络的结构特性，研究动力学与结构之间的关系。并提 出了s i 模型中新的传播机制：定向传播机制。并对意见之间的传播进行了研究发现在 考虑人员可移动的情况下，达成共识所需要的阈值比经典模型要低。 最后，把复杂网络理论应用于知识系统模型的构建与分析当中。把某组织知识系 统中的知识点抽象成节点，它们之间的关系抽象成边，对这一组织中的知识进行了宏 观发展趋势预测。具体为，分别从拓扑网络和加权网络的角度，分析了我国自然科学 基础研究申报体系中自1 9 9 9 年n 2 0 0 4 年的宏观发展趋势，发现项目关联网络具有平均 直径逐年下降，集聚系数逐年上升的特性，并对研究热点等问题进行了分析。我们建 立了基于自学习和双向选择机制的小世界网络增长模型，模型的各统计指标与实证结 果相吻合。最后，对微观领域的学科知识进行了进一步分析。研究了聚类产生的领域 知识的关系。并分析了领域知识内容的客观性。 关键词：知识管理，系统工程，复杂网络，无尺度网络，网络动力学 复杂网络模俐构建及其在如识系统中的麻用 a b s t r a c t c o m p l e xn e t w o r k sc a l ln o to n l yd e s c r i b et h ec o m p l e xs e l f - o r g a n i z e ds y s t e m ，b u ta l s oc a l l b eu s e dt om o d e la n da n a l y z ei t i ft h e “e l e m e n t a n d r e l a t i o n s h i p a r ea b s t r a c t e db yt h en o d e a n d e d g er e s p e c t i v e l y , w ec a l ls t u d yt e x tk n o w l e d g em i n i n gf r o mt h ep o i n tv i e wo fc o m p l e x n e t w o r k s b e c a u s ek n o w l e d g em a n a g e m e n ti sv e r yc o m p l e x i t ya n di n t e r d i s c i p l i n a r y , w h i c h c o m b i n i n gt e c h n o l o g ya n dl i t t e r a eh u m a n i o r e s ，w es t u d i e dt h ek n o w l e d g es y s t e mi n t e g r a l l y f r o mt h ep o i n to fs y s t e ms c i e n c ea n ds y s t e me n g i n e e r i n g b e c a u s ek n o w l e d g ei sv e r ya b s t r a c t a n dt h e r ea r ec o m p l e xr e l a t i o n s h i pb e t w e e nt h eo w n e ra n dc a r r i e ro f k n o w l e d g e ，k n o w l e d g es y s t e mi sc o n s i d e r e da sa c o m p l e xs e l f - o r g a n i z e ds y s t e m i nt h i sp a p e r , t h ee v o l v i n gm e c h a n i s m a n ds o m ed y n a m i cc h a r a c t e r i s t i c sf r o mt h ep o i n to fs y s t e ms t r u c t u r ed e t e r m i n es y s t e mf u n c t i o n sa n ds y s t e mf u n c t i o n si n f l u e n c es y s t e ms t r u c t u r ei ss t u d i e d u s i n gt h ec o m p l e xn e t w o r k t h e o r y , am i c r o k n o w l e d g es y s t e mo fa ne n t e r p r i s ei sp r e s e n t e d t h em a c r o s c o p i cd e v e l o p m e n t t e n d e n c y , m i d d l ec o d es y s t e ma d j u s t m e n ta n dm i c r o s c o p i cf i e l dk n o w l e d g ee v o l u t i o nu s i n g c o m p l e xn e t w o r kt h e o r yi ss t u d i e d f i r s t l y , t h ee v o l u t i o nm e c h a n i s m , w h i c hc a l lp r o d u c ed i f f e r e n ta s s o r t a t i v ec o e f f i c i e n tr o f c o m p l e xn e t w o r k sf r o mt h ep o i n tv i e wo ft o p o l o g ya n dw e i g h t e da r cs t u d i e d t h em u l t i s t a g e r a n d o mg r o w i n gs c a l e f r e en e t w o r km o d e l g r o w i n gs c a l e - f r e en e t w o r k sw i t ht u n a b l ea s s o r - t a t i v ec o e f f i c i e n ta n ds e l f - l e a r n i n gm u t u a ls e l e c t i o nw e i g h t e dn e t w o r km o d e la r ep r e s e n t e d u n d e rt h ee x o g e n o u sp r e s s u r e ，w h i c hi sr e p r e s e n t e db yt h ed i a m e t e rc o n s t r a i n t ，w es t u d i e d s c a l e f r e en e t w o r ke v o l v i n gm o d e l t ot h ed i r e c t e do n e ，t h er e l a t i o n s h i pb e t w e e ni n d e g r e ea n d o u t - d e g r e ei ss t u d i e da n df o u n dt h a tt h ee x p o n e n to fi n - d e g r e ed i s t r i b u t i o ni sd e t e r m i n e db yt h e a v e r a g eo u t d e g r e e s e c o n d l y , t h er o b u s t n e s s ，s y n c h r o n i z a t i o na n ds p r e a d i n gc h a r a c t e r i s t i c so fn e t w o r kf r o m t h ep o i n to f “t h es t r u c t u r ed e t e r m i n e st h ed y n a m i c ，w h i l et h ed y n a m i ch a ss o m ef u n c t i o no n s t r u c t u r e ”a r es t u d i e d u s i n gt h eo p t i m i z a t i o na l g o r i t h m ，w eo p t i m i z e do n ed y n a m i cc h a r a c t e r a n df o u n dt h er e l a t i o n s h i pb e t w e e nt h ed y n a m i ca n dn e t w o r ks t r u c t u r e t h er e s e a r c hw o r ko f o p i n i o ns p r e a d i n ga n dc o n s e n s u sf o r m a t i o no ns q u a r el a t t i c eh a v ef o u n dt h a tt h eb o u n d a r yi s s m a l lt h a nt l l et r a d i t i o n a lm o d e l f i n a l l y , t h ec o m p l e xn e t w o r kt h e o r yi sa p p l i e dt oa ne n t e r p r i s em i c r o s c o p i ck n o w l e d g e s y s t e m b yc o n s t r u c t i n gt o p o l o g ya n dw e i g h t e dn e t w o r k s ( r a n ) ，t h em a c r o s c o p i cd e v e l o p m e n t t r e n da n dt h eh o t s p o tf i e l d sf r o m19 9 9t o2 0 0 4a r ea n a l y z e d b a s e do nt h et e x tc o n t e n lt h e i i 大连理工大学博士学位论文 c o n t e n tn e t w o r ki sc o n s t r u c t e da n dt h ec l a s s i f i c a t i o na n dc l u s t e r i n gs y s t e mc h a r a c t e r i s t i c si s s t u d i e d u s i n ga f a s t e rc l u s t e r i n ga l g o r i t h m p r e s e n t e db yo u r s e l v e s ，o n ec a nf i n dt h ec o m m u n i t y s l r t l c t u r ei ne a c hy e a r , w h i c hm a yg i v eat h e o r e t i c a lf o u n d a t i o nt oa d j u s tt h er e s e a r c hc o d e s y s t e m n en o d ei sd e f i n e da so n er e s e a r c hf i e l d 。w h i c hi sp r e s e n t e db yo n ec o d e i ft h e r ei s a tl e a s to n ep r o p o s a lf i l l e dt w oc o d e s 。t h e r ei so n ee d g eb e t w e e nt h e s et w of i e l d s u s i n gt h i s d e f i n i t i o n ，o n ec a nf i n dt h a t ，t h ea v e r a g ed i s t a n c ed e c r e a s e sdw i t ht i m e ，w h i l et h ec l u s t e r i n g c o e f f i c i e n tci n c r e a s e sw i t ht i m e i nt h ew e i g h t e dn e t w o r k s ，w ep r e s e n t e dt h ed e f i n i t i o no f “n o d ef i t n e s s ”。w h i c hm e a n st h en u m b e ro fp r o p o s a l sw h i c hh a v ef i l l e do n l yo n ec o d e n 圮 a n a l y s i so ft h ew e i g h t e dn e t w o r ki n d i c a t e st h a tt h el o c a lc l u s t e r i n gs c a l e sa sq 一是，w h i c h h a sb e e nf o u n di nh i e r a r c h i c a ln e t w o r k s c o n s i d e r i n gt h et e x tc o n t e n t , w ec o n s t r u c t e dt h e c o n t e n tn e t w o r k w eu s et h ev e c t o rs p a c em o d e l ( v s m ) t oe x p r e s st h et e x tc o n t e n t ，a n dd e f i n e t h et e x ts i m i l a r i t yu s i n gt h ec o s i n ed e f i n i t i o n 1 1 1 er e s e a r c ho nt h ec o n t e n tn e t w o r km a yb e h e l p f u lt os t u d yt h er e a ld e v e l o p m e n tt e n d e n c yf r o mt h ec o n t e n tp o i n to fv i e w i na d d i t i o n ，a n e w c l u s t e r i n ga l g o r i t h mi sd e v e l o p e df o r t h ew e i g h t e dn e t w o r ka n da p p l i e di tt or a n t of i n d t h ec o m m u n i t ys t r u c t u r ei ne a c hy e a r f u r t h e r m o r e ，w h e t h e rt h ec o m m u n i t yi sr e a s o n a b l ei x n o ti ss t u d i e d t h e s ew o r k sm a yb eh e l p f u lt ou n d e r s t a n dt h ed e v e l o p m e n tt r e n do fc h i n e s e n a t u r es c i e n c eb a s i cr e s e a r c ha n dt oa d j u s tt h ec o d es y s t e m k e yw o r d s ：k n o w l e d g em a n a g e m e n t , s y s t e me n g i n e e r i n g ，c o m p l e xn e t w o r k s ，s c a l e f r e e n e t w o r k s ，d y n a m i cc h a r a c t e r i s t i c s ， 独创性说明 作者郑重声明：本博士学位论文是我个人在导师指导下进行的研究 工作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 大连理工大学或其他单位的学位或证书所使用过的材料。与我一同工作 的同志对本研究所做的贡献均已在论文中做了明确的说明并表示了谢 意。 大连理工大学学位论文版权使用授权书 本学位论文作者及导师完全了解“大连理工大学硕士、博士学位论文版权使用规 定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学将本学位论文的全部或部分内容 编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文。 作者签名：墨娃 导师签名： e t 期：兰21 2 ：日期：习堕 人连理工人学博士学位论文 1 1 问题的研究背景和意义 第一章绪论 世纪之交的一项重大科研发现是观察到复杂系统受简单规则驱动f 1 - 1 2 。通过对大 量复杂系统，例如，技术系统中的互联网【1 3 ，1 4 】，社会系统中的人际关系网【1 5 】，生物 系统中的蛋白质相互作用网【1 6 的实证研究和建模分析，发现这些网络的演化规则可以 概括为：随机性、适应性、遗传性0 0 。所谓网络是由结点和连线组成，这里结点和 连线是广义的，其中结点表示系统的元素，两结点的连线表示元素之间的相互作用。 尽管这个定义极其简单，但是所构建的网络能够高度复杂。复杂阿络可以作为描述从 技术到生物直至社会各类系统的骨架，而且是研究系统拓扑结构和动力学性质的强有 力工具。因此人们致力于揭示复杂网络的形成机制，演化规律，涌现临界和动力学过 程。这时人们看到的是错综复杂的系统，它受某些简单规则所驱动自组织而形成。这 是复杂性更重要的一种形式。 无尺度网络 2 的发现，不但开创了复杂网络研究的新局面，而且对于系统科学的 研究也有重要的意义。无尺度网络的发现是一个极好的契机，有可能以复杂网络的拓 扑特性研究为切入点，深入开展知识网络系统结构的研究。结构是客观事物的基本属 性，也是各个学科领域的基本问题，如物质科学研究物质的结构和性质，生命科学研 究生物的结构和功能，社会科学研究社会的结构及其功能。知识系统科学研究知识系 统的结构和功能。可以说，每一门学科对其研究对象的结构都有非常丰富的研究成 果。但是从系统学层面的成果还不是很多。无尺度网络的发现，为我们开拓了新的 视野。系统结构可以描述成网络结构。但是研究网络图的经典规则图和随机网络理 论【1 7 ，1 8 】距离现实的复杂系统有一定的距离，大多数复杂系统是动态演化的，是开放 自组织的，是规则和随机相伴而行的。单纯应用规则图和随机网络理论对这些普遍存 在的复杂系统不能进行实质性的分析。无尺度网络的研究成果反映了大多数复杂系统 的这些基本特性，使得对于这些系统的研究取得了实质性的突破。以无尺度网络为起 点的复杂网络的研究开启了以统计性的实证方法研究网络的拓扑结构及其基本属性， 为基于系统结构的系统功能的研究及系统动态行为研究，从基础的层面上建立了客观 的经验基础。 自然界中存在的大晕复杂系统都可以通过形形色色的网络加以描述。从细菌、细 复杂网络模犁构建及其在知识系统中的应用 胞和蛋白质系统【1 6 】，到人类性关系b 9 ，甚至到科学家之间的合作 1 5 】，论文之间的 引用联系【2 0 】，大型的i n t e m e t 网【1 3 等，它们都构成某种网络系统，也构成某种复杂网 络系统。因此，如若发现一种囊括它们的共同特性的观点和方法，则能够抓住这类网 络的关键，形成深入的认识。一个典型的网络是由许多节点与连接两个节点之间的一 些边组成的，其中节点用来代表真实系统中不同的个体，而边则用来表示个体间的关 系，规则是两个节点之间具有某种特定的关系则连一条边，反之则不连边，有边相连 的两个节点在网络中被看作是相邻的。例如，神经系统可以看作大量神经细胞通过神 经纤维相互连接形成的网络；计算机网络可以看作是自主工作的计算机通过通信介质 如光缆、双绞线、同轴电缆等相互连接形成的网络。我们把网络不依赖于节点的具体 位置和边的具体形态就能表现出来的性质叫做网络的拓扑性质，相应的结构叫做网络 的拓扑结构。那么，什么样的拓扑结构比较适合用来描述真实的系统呢? 两百多年 来，对这个问题的研究经历了三个阶段。在最初的一百多年里，科学家们认为真实系 统各因素之间的关系可以用一些规则的结构表示，例如二维平面上的欧几里德格网， 它看起来像是格子t 恤衫上的花纹；又或者最近邻环网。到了二十世纪五十年代末， 数学家们想出了一种新的构造网络的方法，在这种方法下，两个节点之间连边与否 不再是确定的事情，而是依据一个概率决定。数学家把这样生成的网络叫做随机网 络 1 7 ，1 8 ，它在接下来的四十年里一直被很多科学家认为是描述真实系统最适宜的 网络。直到近几年，由于计算机数据处理和运算能力的飞速发展，科学家们发现大量 的真实网络既不是规则网络，也不是随机网络，而是具有与前两者皆不同的统计特征 的网络。这样的网络被科学家们称做复杂网络，对于它们的研究标志着第三阶段的到 来。 遗憾的是，就目前而言，科学家们还没有给出复杂网络精确严格的定义。从这几 年的研究来看，之所以稼其为复杂网络，大致上包含以下几层意思：首先，它是大量 真实复杂系统的拓扑抽象；其次，它至少在感觉上比规则网络和随机网络复杂，因为 我们可以很容易地生成规则和随机网络，但就目前而言，还没有一种能够生成完全符 合真实网络统计特征的简单方法；最后，由于复杂网络是大量复杂系统得以存在的拓 扑基础，因此对它的研究被认为有助于理解“复杂系统之所以复杂”这一至关重要的问 题。 1 9 9 7 年，经济与合作发展组织( o e c d ) 发表了题为以知识为基础的经济的报 告【2 l 】，在国内外引起了研究知识经济的兴趣。所谓知识经济，根据当前比较一致的理 解，是指建立在知识的创新、传播和使用基础上的经济 2 2 】。 一2 一 人连理工人学博士学位论文 上世纪末，软件产业等知识密集型企业迅猛发展和美国经济的持续高速增长，一 度把知识经济的讨论推向高潮，随着美国经济增长速度的降低和网络企业泡沫的破 灭，人们开始从理性角度对知识的作用，如何对知识进行有效的管理等问题进行全面 的审视和思考。随着科技和现代化管理对经济的贡献日益增大，知识将逐步成为促进 经济增长的关键因索。知识的有效应用可以提高企业等组织的创新能力，适应环境能 力和成员素质。因此，知识已经成为企业的核心竞争力。 知识作为一种资源，作为一种生产要素和资本，对于它的管理要专门加以研究。 国外从上世纪7 0 年代结合技术创新的研究开始关注知识管理。8 0 年代后期正式出现了 知识管理这一名词 2 3 1 。人们在研究以企业为中心的知识管理的过程中，对知识管理做 出了很多定义 2 4 。从知识管理的具体任务的角度，对一个企业或组织来说，知识管理 涉及到如下问题 2 2 1 ： 本组织中需要的知识是什么? 现有的知识在哪里? 可以从哪里获取? 如何传播? 如何生成新的知识? 如何有效利用? 知识如何存储更新，如何保护? 等等。 由于知识管理的高度复杂性，它兼有自然科学和人文科学两种属性。具有跨学科 的特点，其涉及的学科有：管理科学，认知科学，心理学，社会学和信息科学，系统科 学与系统工程等。知识管理又有宏观和微观两个层次。宏观知识管理是国家层次的； 企业或组织中的知识管理是微观层次的。本文主要对微观层次的知识管理工作进行研 究。 近年来，关于知识管理的研究主要沿着两条路线进行的。一条路线的重点是信息 管理。走知识工程，人工智能的道路。因为信息是知识的载体，通过对信息内容和信 息工具的管理来实现知识管理。这条线致力于信息系统，人工智能工具的开发研究。 另一条主线把人的管理摆在十分重要的位置上，研究着重于人的行为，技巧和思维方 式，以及组织行为等。上述两条路线的研究人员分别具有理工科和人文学科专业背 景。然而，单独走其中哪一条路线都缺少对知识总体上的把握。应该从系统的角度， 从整体上对知识管理加以分析和整理。利用现代系统科学与系统工程对复杂系统的研 究思路和方法，可以从系统的高度对知识管理中的各种要素及其相互之间的关系进行 一3 一 复杂网络模钽构建及其在知识系统中的廊用 深入分析。我们可以从系统的结构和功能的角度对知识系统加以考察。这里所说的知 识系统，不同于人工智能中基于知识的系统( k n o w l e d g e b a s e ds y s t e m ) ，后者可以看作是 前者的特例【2 5 】。2 0 0 0 年，王众托【2 5 提出了用系统工程的方法对知识系统进行研究。 知识系统工程指的是对知识迸行组织管理的技术学科。 由于知识的高度抽象性，人们更容易从知识的拥有者或者知识的载体这样一些看 得见的实物，人员或组织机构来辩识知识的存在。知识的存在形式有书刊，文件，数 据载体以及与知识密切相关的人员或组织。这些知识按照来源和用途有着各种各样的 有机联系，构成了复杂的知识系统。知识系统不像一般的实物系统或信息系统。由于 知识的生成是人的复杂脑力活动以及人与人之间互动的产物，而每个人以及每个团 队，组织都有一定的自主性，所处的环境还有一定的不确定性，所以知识系统是一类 复杂的组织系统。 系统的结构与系统的功能密不可分，一个好的结构可以起到强化和扩充系统功能 的作用。知识系统是以网络的结构形式存在和运行的。网络的一部分是有形的，如信 息网。也有一部分是无形的，例如人与人之间的关系网络，知识点与知识点之间的关 系网络，组织内部的知识关系网络等等。知识网络系统就是从整体上对不同层次和部 门的有形的技术性的网络和无形的网络加以集成。复杂网络是近年来快速兴起的对复 杂系统进行结构分析的研究工具。复杂网络可以作为描述复杂系统的有力工具，而且 可以对复杂系统进行建模和分析。我们可以把复杂网络理论应用到知识网络系统中， 对系统中不同层次的网络进行挖掘和分析，为对决策者的知识管理工作提供帮助。 1 2 复杂网络在知识管理和其它领域的应用 知识管理研究开始向更深的层次发展，一些基础性的问题开始受到关注。例如， 基于本体论( o n t o l o g y ) 嗍建模问题、文档自动分类问题等。此外，还有其他的一些 关于知识建模的研究，例如产生式系统及框架、语义网络、面向对象的知识模型等。 这些研究将为知识管理学科打下坚实的基础。知识管理同其他学科领域的交叉、融合 方兴未艾，许多研究者借鉴其他学科，不断完善知识管理研究思路、方法和工具等。 最近，有些科学家开始把复杂网络方法引入到知识管理的研究当中，具体的工作如 下。 一4 一 人连邓工人学博士学位论文 1 - 2 1 复杂网络在知识表示与建模方面的应用 b a r t h 6 1 e m y 等人首次提出了基于语义关系和复杂网络的知识表示方法 2 6 3 。算法利 用复杂网络中的传递性等概念对语义网络中的关系类别进行识别，并且引入了新的统 计指标对语义网络中的知识进行表示。c o s t a l 2 7 基于层次网络模型对知识学习和知识 传播模型进行了研究，提出了基于复杂网络的知识学习算法。o l i n 等 2 8 】细致地研究了 企业联盟中多级企业之间的知识管理，从定性的角度对多级企业之间数据通讯等问题 进行了研究。w a k e f i e l d 2 9 】详细地研究了知识管理策略中知识a g e n t 的结构对知识管理 的影响。 席运、7 1 - 3 0 - 3 5 对组织中的知识进行了相似的研究。主要工作如下：基于复杂网络 的组织知识结构建模；在对组织知识结构及构成进行分析的基础上，并结合组织知识 的存储情况，提出了组织知识的知识网络( k - k 网络) 模型和知识超网络( k s n ) 模 型；基于加权网络的组织知识存量建模；在k - k 网络模型及k s n 模型基础上，提出了组 织知识存量表示的w k n 模型及w i 【s n 模型；基于w k n 模型的个人及群体知识结构分析 方法；基于w k s n 模型的组织知识安全问题分析方法；和基于w k s n 模型的组织知识定 位搜索方法等工作。 1 2 - 2 科研合作网络与语义网络 科研合作网络的研究是我们能够更好地理解科学家之间合作的社会学机制。通 过对不同数据库的分析发现，科研合作网络具有小世界效应和高度倾斜的度分布 3 6 3 8 。在引文网络中同样发现了相似的结论。人类语言通过定义音节或单词为点，同义 或近义为边建立网络进行分析 3 9 】，发现语义网络具有小世界效应和负的正负匹配度， 研究对象包括葡萄牙语，英语，德语和罗马语。 1 2 3 集团结构的发现算法研究 发现实际系统中的集团结构对于许多问题都非常重要。例如社会网络中合作关系 的发现，知识网络中领域知识的识别，以及大脑功能模块的发现等等。通常的集团结 构发现方法都是分裂方法，即从一个集团中分出两个小的集团。这里我们主要介绍图 谱分析方法 4 0 - 4 3 】和g i r v a i l 、n e w m a n ( g n ) 4 4 算法。 一5 一 复杂网络模掣构建及其在知识系统中的应用 图谱分裂算法提出于二十世纪七十年代【4 嘣3 】，盛行于九十年4 - t 4 5 1 ，图 谱分裂算法比其它随机自适应算法都要好，例如k e r n i g h a n l i n 算法【4 6 和f i d u c c i a - m a t t h e y s e s 4 7 。拉普拉斯图谱( l a p l a c i a ns p e c t r u m ) 有许多很吸引人的性质【4 8 ，4 9 。因为 它的最小特征值a l = 0 ，对应的特征向量是v 1 = ( 1 ，1 ，1 ) t 。当图中包含九个互不重 叠的集团时，零空间的维数就等j ：n 4 2 1 。当图中的n 个集团结构不是很清晰的时候， 图的拉普拉斯矩阵只有一个零特征值，n 一1 个略微大于0 的特征值，其它特征值都远 离0 。f i e l d e r 4 3 ，5 0 在1 9 7 5 年首次提出用第二小特征值a 2 和对应的特征向量v 2 来得到图 分裂的近似解。如果图的集团结构比较好的时候，图谱分裂算法的结果很好而且速度 也很快。对一个n n 的矩阵，算法需要时间复杂度为o ( n 3 1 的时间计算特征向量。因 为实际计算的时候只需要计算少量的特征向量，所以需要的计算量并不大。而计算第 二大特征值需要( b a 2 ) 5 1 1 ，所以算法近似地有的线性复杂度。 g i l l ，a l l 和n e w m a n 利用删除网络中介数最大边的方法提出了一种计算网络集团结构 的迭代算法。由于介数最大的边在通讯当中最为重要，那么它两侧的节点对也就最 多。算法的思想为： 步1 ：计算每一条边的介数并进行排序； 步2 ：删除介数最大的边； 步3 ：分析网络的集团。转到步l ，直到所有的边都被删除( 网络变成个离散节 点) 。 为了衡量算法所得到集团的好坏，他们引入了模块性定义 q = ( e “一霹) = n e l i e 2 t 其中矩阵e 的元素8 旬表示网络中连接集团i 和集团j 的边占所有边的比例，c t i 一j e i j 。 使q 达到最大的集团个数变为最佳的集团分类。算法对计算机构造的网络和经典的数据 的结果都很好。 1 2 4 信息检索与导航 m i l g r a i n 的社会学实验不仅说明了社会网络中存在相对短的路径，同时也说明人们 在不知道全局信息的情况下有办法发现这些距离很短的路径。但是它的机制目前却不 是很明了。这种在不知道全局信息的信息检索能力不仅在社会网络当中非常重要，而 一6 一 人连即工人学博士学位论文 且对于w o r l d w i d ew e b 中的信息检索，优化城市交通网络的吞吐能力，i n t e m e t 网络中 的信息包的传输等问题都十分重要。 广度优先搜索算法【3 8 是我们最常用到的寻找两个节点之间最短路径的方法。当网 络中任何信息都不确定的情况下，n o h 和r i e g e r 研究了用网络中随机游走的方法，并且 给出了任何两点首次碰面平均时间的精确表达式。为了设计点对点( p e e r - t o - p e e r ) 网络中 的高效搜索算法，a d a m i c 等人提出了基于最大节点度的搜索策略【5 2 】，即假设每个节点 都知道自己邻居节点的信息。a i e l l o 等 5 3 1 研究了无尺度网络中最大度策略下的信息检 索，发现最大度策略下的搜索成本比随机游走要小。目前，最大度策略已经被应用于 实际网络中。k i m 等细致地对比了无尺度网络中由随机游走，最大度策略和择优连接策 略测量出来的实际的最短距离 5 4 】。择优选择策略指的是每个点根据自己邻居的信息， 按照邻居节点的度择优选择下一个节点。由于网络的整体信息不知道，所以也无法得 到网络中按式( 1 5 ) 得到的最短距离。我们依据搜索策略得到的最短距离定义扩展的最短 距离见。研究发现，最大度策略的扩展最短距离与m ( ) 成正比，而由随机游走和择优 策略得到的扩展最短距离与网络规模成幂律关系。 我们已经讨论了不知道网络全局信息下的有效搜索算法。现在考虑另一个问题， 即如何在特定的搜索算法下构建最优的网络结构。克莱伯格( k l e i n b e r g ) 首次研究了对具 有小世界结构的网络进行有效导航 5 6 ，5 7 。他构建了一个w s 模型的变形模型，模型的 构造思想如下：在一个二维格子上，任意两个节点对以概率严，其中r 为这两个点之间 的距离，口为可调参数。克莱伯格证明了在这样的网络里随机选择一个目标节点的传输 时间存在一个下界s c n b ，其中p = ( 2 一o t ) 3 。2 0 0 6 年，国际数学家大会将奈望林纳 奖颁发给了乔恩克莱伯格( k l e i n b e r g ) ，奖励他的工作为重要的实际问题带来了深刻的 理论见解。这些理论已成为认识和管理今天日益增多的网络世界的核心。g u i m e r i 等研 究了避免拥塞问题最好的网络结构 5 8 】。拥塞问题是并行计算和城市交通中非常重要的 问题。如果只是对于信息检索最有效的网络结构，那么一定是一个极化的星状网络。 这样的结构很有效是因为达到一个随机目标节点的步数是非常有限的。然而，当面对 多个搜索过程的时候，因为中心节点路由能力的限制，极化星状网络的效率却很低。 1 2 5 社会网络中的应用 社会网络由人和他们之间的各种关系构成 5 9 ，6 0 ，例如友谊关系，合作关系，性 关系，交易关系等等。社会网络的研究最早要追溯到1 9 2 6 年w e l l m a n 研究儿童选择伙伴 的研究【6 l 】。复杂网络研究中的许多概念都源于社会网络，例如节点的中心性，集聚 一7 一 复杂网络模呷j 构建及其在知识系统中的应用 系数，等等。社会网络中把度最大的节点称为局部中心，而介数最大的点称为全局中 心。节点的等价性等概念表示社会网络中两个人社会关系的等价性。 实际友谊网络的统计分析已经揭示了友谊和青少年犯罪之间的重要关系 6 2 】。复杂 网络的研究促使人们开始研究动物的社会关系特性 6 3 ，6 4 ，以及音乐家，演员，小说 人物之间的关联关系。通讯系统的迅猛发展使得我们建立了新的社会关系t 6 5 ，6 6 1 ，复 杂网络理论不仅可以使我们了解其宏观的统计特性，而且可以更深入地了解这些关联 关系建立的过程。例如对电话网络和e m a i l 网络的研究 6 7 - 6 9 1 。通过对人们处理电话 和e - m a i l 的习惯的分析，b a r a b 缸i 7 0 71 发现我们处理e - m a i l 的时间符合幂律分布，而不 是原先排队论中提出的p o s s i o n 分布，这将为排队论的研究提供新的契机。 不同的研究还发现了性关系网络的无尺度分布【7 l - 7 4 】。这个结果说明择优连接模 型或许可以解释隐藏在性关系网络后的结构。这些结果的发现对于进一步的社会学研 究提供了有力的保障。 1 2 6 大脑网络研究 脑是人体结构和功能最为复杂和精密的器官，它在根本上控制着人类的各种行 为，揭示脑的奥秘是自古以来人们一直孜孜以求的追求与梦想。大脑是生物体中 结构和功能最复杂的组织，大脑的神经细胞总数约为1 0 1 2 的数量级，相当于整个银 河系星体的总数。尽管大脑中的神经元和大脑皮层之间的连接数如此之大，但是它 被认为是在最小的约束下实现资源的最优分配和整合 7 5 。在结构角度，大脑之间 的关联有如下三种定义：神经解剖学关联，功能性关联和有效关联 7 6 - 7 8 1 。在这里 我们重点介绍功能性关联。功能性关联指的是在某项神经生理实验下，大脑中不同 空间距离上的瞬间关联 7 9 1 。我们可以通过脑电图( e l e c t r o e n c e p h a l o g r a p h i c ) ( e e g ) ，磁 电 ( m a g n e t o e n c e p h a l o g r a p h i c ) ( m e g ) ，磁功能成像( f u n c t i o n a lm a g n e t i cr e s o n a n c a ：i m a g - i n g ) ( f m p d ) 和正电子穿透( p o s i t r o ne m i s s i o nt o m o g r a p h ) ( p e t ) 等技术记录大脑完成某项任 务是各个区块之间的活动情况。通过把不同任务下大脑的激活区重叠分析的方法，已 经构造出了大脑功能图【8 0 】。s p o r n s 和k 6 t t e r 8 1 细致地分析了大脑各区块之间的结构性 和功能性m o t i f ，通过构建网络的拓扑结构，通过优化方法分析网络的m o t i f 和小世界等 特性，发现大脑会最大化功熊性模块的数量和种类，但却始终保持结构性模块的数量 很小。这可能与网络需要进行高效的信息整合有关。e g u f l u z 等 8 2 】通过分析f m i u 中大 脑个脑区信号的相关系数，构建了脑功能网络，发现了无尺度特性，并对其进行了细 致的分析。但是大脑网络的构建仍然面临许多问题，例如如何用加权有向网络在空间 一s 一 人连卿工人学博士学位论文 上构建大脑网络就是一个极其有意义的工作。进一步，大脑网络中的小世界效应对大 脑功能的影响，以及大脑当中众多动力学行为对于揭示大脑的奥秘都十分有意义。 1 3 复杂网络研究综述 数学中以图论形式开展的网络研究是离散数学的基柱之一。1 7 3 5 年e u l e r 提出的著 名的葛底斯堡七桥问题解是网络理论首个真正的证明，在此之后网络理论得到了快速 的发展。二十世纪期间，网络发展为一个重要的知识实体。在过去几年里，现实世界 网络的很多很有趣的特征引起了科学家们的关注。这些特征表明现实中的网络不同于 规则图，也不同于随机图。现实世界网络是介于规则图和随机图之间的一种网络，这 些逐渐凸现出来的事实表明这些现实网络背后存在特殊的生成机制。这些生成机制的 发现将有助于人们开发具有特定目标的网络结构。 首先，简单介绍有关图的基本知识。图g 可以表示为集合f 矿e ， v ( g ) = 1 ，2 ， 表示图g 的顶点集合，表示网络的顶点总数，e ( g ) = ( n ，j 1 ) ，( i 2 , 如) ，( i n ，如) ) 代表边的集合，e 表示总边数。如果( t ，j ) = ( j ，t ) ，则图 是无向图，否则为有向图。当网络是无向无权的时侯，邻接矩阵a = f 吼f 1 是一 个0 1 对称矩阵，表示图中顶点之间的连接关系，具体形式为： = 薯翥t j 之间有边 当网络是有向图时，邻接矩阵a 是非