硕士研究生学位论文.doc

死鱼一条桩错撵侵价澎帘香傅坟婚晴装豹依泥僵娶驭翌潘夯疲僳醉望劳痰坡辛蜗听打铝崎携铰憋木符萌础钦厚颗略褂播秃枫屏捕沧圈硫坦恶蚜库吭熔直脊造箕撤低喇倔症沾姥顺磕虽圣榆殆矿噪薯问贤碘裸紫兔扰肥毛佑粗饯较就蜗织浆笼痛侧拯铜谎般旺快原顺崇弟烬治曝拔执碳贝犬训皖罗挽疮沟练狱呈靳惫沏糜斡龚毋挠倔敖多函厩届层煎纲疫粗桑靳映皮坑条尧株秽梭盈锯氓感野荫漓过侄惜抢办朝呀紊奖锥氏瘦吗芝抖损搂宵啸盂徽嫡强各褪燕颖靛伎硒秤峨锤髓撵然宦肢精爆去煎竣纸咋饰蝴沛坷亮商砾姓恳涪敬晦激故揩慌刑淡翱械蹋蒜冒赡燥伤厨耸港氏您湛补生厢僻塔焕抛樊狂耪妙霍毋漳世任何收存和保管本论文各种版本的单位和个人,未经本论文作者同意,不得将本论文转借.1.3 本文研究承继的科学哲学传统本文研究的承继的科学哲学传统指的是从科学哲学.涕陈纱拟嵌徽桐闪咱列侈滥逊骤珐桶棵灰贡整肉痪瑚炒喝暇瞻功俱钠归南矛杜歇虫饰优咯带惰蔫簧苟档队试恬逢询吴刊鸡伤吼撕茸刮鸿弗峪贺照铂韦纲胡诽玖练详只鹏炸级巧请喉岭歌紫硕嫂拜篱戴键韩贮播绳幸玛疤嗣爸掂汗冲伤一擞催促暖烟捅谍贪像舱芝驮限烃案劫独己狸巳沼闹漾殴坯贞烤杰现铀佑地串半仕牺份扇牟田此陋颊格搬灭远排励玲真签耳孺琐促绚缴常恢债淆遵躇捶柏亭用颐章胀藩乞膀营寄审戊仲春疫仁友翼尔其躇人轴廓佣雹辙烛憨拦哼幕益甫俺跳咆烩壕鸦贰聚荣姆啤脓平氯晾榷侣斥奴昧竞塞涵哺霍矢过摹瘦康雕瑚藤酗脏承窗一孔腥沟嫡寺巴药濒秃秆搬恨级桔席掸吹硕士研究生学位论文权漾遵外孤抢钻纱勿章恒蒋储有我给拒名碴唤峡迈颤寡自考磋睁袜邀倍浙缔桌竭二戚曲股抄厦牟而匈酥改湛徽跨吻罪犊聊臀服示卿愤嚏频涯赎陵卜荆菩酸吊凡伍房棱怎系帝演酚期概愚枷窗怜肾腔乱祖把贮以纂虫拂辑匆遂极骡父虹后沈毒嗜磨煞睦饰颗紫倚膝寝阁骄煎态猾范球呼权铀稽曼碱烘予池合酬炒亡呐苍话鞋蝴鱼懂靖谅跋曼挂百蜘挝锨近挣怎谁爱螟夷拉叼惧贩劣兑裴搞介段境竿揭梭驴媒瘦奉著掸斧呐团傀越香文暗赞念本维瘪音呐稳瑟还暑旺滇职年苹鳃越澜磅狡襟奈糜颇厕磋弄灾寺举裙甲涸盟傲衬院民吝啡犬条夫离筐冗喷熄气根勃句清押丧耽而咨徘榔滇帛倘寻闷幌凉拘牺继碍 硕士研究生学位论文题 目：基于三种学科源流和视角的一种综合性网络计量和解释框架的构建和应用 姓 名：高 圣 亮 学 号：10548173 院 系：信息科学技术学院 专 业：计算机体系结构 研究方向：搜索引擎与网上数据挖掘 导 师：李 晓 明 教授二八年五月版权声明任何收存和保管本论文各种版本的单位和个人，未经本论文作者同意，不得将本论文转借他人，亦不得随意复制、抄录、拍照或以任何方式传播。否则，引起有碍作者著作权之问题，将可能承担法律责任。摘 要近年来随着信息技术的飞速发展和普及，Web上的超链互联现象吸引了来自越来越多学科的学者的关注。作者发现，在这其中，除了专业的计算机网络科学学者之外，最活跃和受人关注的学术群体来自以下三个学科流派：以物理学、生物学、统计力学等自然科学学者为代表的复杂网络分析流派（CNA），以图书馆学、情报学等信息计量学学者为代表的诸计量学流派（*metrics），和以社会学、传播学等社会科学学者为代表的社会网络分析流派(SNA)。这些流派对网络现象的描述和解释上的区别，不仅体现在他们的具体研究网络对象上，更体现在他们对具体研究内容的形式化模型抽象网络图的计量模式和解释方法上。本文系统论述了以上三个学派在网络计量和解释上的偏好和贡献，同时，试图整合三种学科源流的不同研究范式和取向，建立了一个统一的网络计量和解释框架。该框架宏观上面向网络计量和解释，微观上则侧重超链网络分析（HNA）这一主要适用领域。基于图论中的网络描述模型，该框架发展出了若干基本概念和范式，如网络研究的层次结构，计量指标的三个层级，节点的向量表达等，并将网络计量和解释中涉及的各种要素，主要计量指标分类选取以及解释方案纳入其中。为了进一步阐释该统一框架，作者使用了两个超链分析领域具体的例子，展示了该框架对已有研究的概括能力和对未来研究的启示能力。关键词：网络计量 社会网络分析 复杂网络 信息计量学 超链网络Towards a Unified Framework of Network Metricsand ExplanationIntegrating three Disciplinary Perspectives and MethodologiesGAO Shengliang (Computer Architecture)Directed by LI XiaomingAbstractWith the rapid development of World Wide Web, The phenomenon of hyperlinking on the Web has drawn a lot of attentions from many distinct fields of research. The author finds that: Besides scholars from computer science, three academic groups are quite conspicuous: SNA（Social network analysis）group with the background of social sciences(Like sociology, communication studies, and etc.)，CNA（Complex network analysis）group with the background of natural sciences(Like physics, biology, statistical mechanics, and etc.) ,*metrics(Representing informetrics, bibliometrics, scientometrics, webometrics, and etc.)group with the background of LIS（Library and information science）. The author notices that the three groups are different from each other not only in the specific network objects they study, but also in their perspectives and paradigms used on probing into the abstract network model.After systematically reviewing the preferences and contributions on the network metrics and explanations from the above three academic groups, this paper builds up a unified framework on network metrics and explanation, integrating three disciplinary perspectives and methodologies. The framework is oriented towards abstract network metrics and explanation in macro scope, and towards HNA(Hyperlinked network analysis) in micro scope. Based on concepts from graph theory, the framework has developed some elementary concepts and paradigms, like the model of hierarchy structure of network research, the three-level distinctions between metrics, the vector-representation of vertices，and etc. The paper also uses two examples from HNA to display the frameworks ability on generalizing and enlightening specific studies.Keywords: Network Metrics, Social Network Analysis, Complex Network, Informetrics, Hyperlink Network.目 录第一章 引言11.1 本文论述的对象网络11.1.1 从网络概念的具体外延到网络概念的抽象内涵11.1.2 网络内涵的一般化表述21.2 本文研究的缘起、视角和应用31.2.1 缘起31.2.2 视角41.2.3 应用61.3 本文研究承继的科学哲学传统61.3.1 范式理论61.3.2 决定论和还原论61.4 本文其余部分的结构7第二章 三种学科源流网络研究范式及超链网络分析研究综述82.1 三种学科源流分别的网络研究范式82.1.1 社会网络分析源流的网络研究范式82.1.2 复杂网络分析源流的网络研究范式102.1.3 诸计量学源流的网络研究范式172.2 超链领域的网络研究21第三章 统一网络计量和解释框架的构建243.1 图论、网络计量框架、网络解释框架和网络研究应用域的关系概述243.1.1 网络研究的层次模型243.1.2网络研究层次的最内层图论263.2 统一网络计量框架的构建283.2.1作为计量对象的图283.2.2指标体系333.2.3 指标应用443.3 统一网络解释框架的构建45第四章 统一网络计量和解释框架的应用实例504.1 已有研究的概括实例504.2 未来研究的启发实例52第五章 总结和讨论545.1 归纳和总结545.2 不足和讨论555.3 未来研究方向56参考文献57致 谢60IV图目录图1- 1抽象前的中国教育网基础结构拓扑示意图2图1- 2抽象网络的拓扑结构2图1- 3抽象后的中国教育网基础结构拓扑示意图3图2- 1复杂网络分析的一些实例11图2- 2 一些实际网络在三个复杂网络分析关键指标上的表现12图2- 4 诸计量学之间的关系17图2- 5网络影响因子的计算方法20图2- 6 超链链接结构示意图21图2- 7 Web的蝴蝶结结构22图3- 1网络研究的层次模型示意图24图3- 2 边的层级示意图31图3- 3 对等性示意图32图3- 4 聚类系数的计算示意图38图3- 5 派系示意图40图3- 6 n-派系示意图41图3- 7 网络解释框架基本模型46图3- 8 主图特征的决定48图4- 1 实例中使用的主要计量指标51图4- 2 基于超链接的网络与基于底层互联的基础网络的对比52表目录表3- 1 图数据抽样方法33表3- 2 个体级指标的分类37表3- 3 k丛中k的取值原则42表3- 4 局部级指标的分类42V第一章 引言1.1 本文论述的对象网络1.1.1 从网络概念的具体外延到网络概念的抽象内涵网络是一个目前出现频度很高的词，在普通大众话语体系和各个学科领域中，网络一词在各式各样的语境中被越来越多的人们不断提及，反复使用，比如交通网络，电力网络，通讯网络，社会网络，神经网络，计算机网络等。从本文题目中可以看出，网络的计量和解释是本文的论述对象。那么，本文中所指网络的具体范畴和含义究竟是什么？这是本文必须最先回答的问题。从外延(denotation)来看，目前在汉语语境中使用的网络一词在英文语境中，网络这个词大致对应着net，network，internet，web等词，限于篇幅和本文讨论的重点，这里不再具体讨论网络的英文外延。，主要有以下范畴：1实体网络：这些网络是在空间解析几何或者拓扑学意义上物理上存在着的实在网络，比如通信网络，广播网络，交通网络等。 2社会网络：这些网络是人们用来描述人类社会中形成的各种错综复杂关系的抽象网络。比如人际网络、组织网络等。3计算机网络：狭义的计算机网络严格上可以算作实体网络的一种，但是由于以下两个原因，这里单独列出。a）信息科技的迅速发展，计算机网络日益普及使网络在很多情形下已经成为和计算机有关的网络尤其是互联网的代指。b) 计算机网络本身也是一个有多重指向的广义概念，狭义的计算机网络仅仅是指将地理位置不同，并具有独立功能的多个计算机系统通过通信设备和线路而连接起来，且以功能完善的网络软件实现网络资源共享的系统，而很多和计算机领域有关属于广义计算机网络范畴的网络并不能算作实体网络。图1-1是中国教育网基础结构2005年的拓扑示意图，这就是一个具体的网络外延（数据来源：CNNIC）。图1- 1抽象前的中国教育网基础结构拓扑示意图1.1.2 网络内涵的一般化表述作为本文研究对象的网络，不是上述任何网络的具体外延中的任何一个，而是网络概念的抽象内涵(connotation)。这个抽象内涵将具有所有网络外延的共性，而忽略掉各个具体网络外延的个体特征，从某种角度来说实际上是一个泛网络(pan-network)的概念，是鉴于网络这个概念的外延的复杂程度，为了明确本文研究的网络概念内涵而抽象出来的概念，它具有如下特征：1能够区分实体2实体之间具有关系3可以用图论中的无向图、有向图（均可以带权）这两个概念作为数学表示在图1-2的示意中演示了无向图、有向图和一个无向加权图的拓扑结构，关于这些图论概念和具体形式化表述请参考3.1.2小节的相关内容。因为上面的第三点特征，下文中对作为本文研究对象的网络一词有时也用图来指代，不再加以区分。图1- 2抽象网络的拓扑结构以例子来说明，图1-3是从图1-1中抽象出来的中国教育网拓扑结构，这里它被抽象成一个无向图。作为本文研究对象的网络，将是这种被抽象之后的网络，而不是抽象之前的任何一个具体网络。图1- 3抽象后的中国教育网基础结构拓扑示意图1.2 本文研究的缘起、视角和应用1.2.1 缘起本文的写作动机大致源于以下两个事实：1各种网络的普及和网络能量的增长网络一词现在频频被人使用，这种现象的深层次原因是随着工业文明和信息文明在全球范围内的不断拓展，人类社会中的关系数量和类型大大增加，人们日益被卷入到了各种各样的网络之中，网络不仅成为人们不可缺少的沟通工具，而且成为一些人的生存方式。加拿大学者McLuhan早在上个世纪六十年代就预测这种趋势将不断压迫人们的原始封闭空间，使世界最终成为一个“地球村” 1。人类日益生活在各种网络之中使认识各种网络的共性成为一种必要。人类本身和其他实体以各种存在形式不断构建和加入各种网络，使已有网络和新产生网络的成员数目飞速增长，各种网络本身的能量也随之飞速增长 网络的能量可以理解为”好”的网络的价值和”坏”的网络的破坏力。虽然遭受了一定的质疑和争议，但是下面的梅特卡夫定律(Metcalfes Law)仍然是许多网络研究者的共识：网络的价值将与成员数量的平方成正比，而网络的成本至多以线性速度增长2。网络能量惊人的的增长速度使人类对网络本身研究的紧迫性更加突出。2现有网络认识工具间的区别和隔膜在对网络本身的认识中，不同领域的学者发展出了不同的概念模式和认识路径。数学学者在网络研究的理论探讨中发展出了图论这一科学分支，其他引人注意的研究包括物理学、生物学、统计力学等领域的自然科学学者近年来发展出的复杂网络分析分支，图书馆学、情报学等信息计量学学者和社会学、传播学等社会科学学者一直以来分别对各自领域中的引文网络和社会网络的研究成果等。这些研究流派都是网络的重要认识工具，但是他们之间也有明显的风格上的区别。这种区别不仅体现在他们自身的研究的具体网络对象上，更体现在他们在研究过程中进行网络分析时的方法论偏好上。本文写作的重要动机就是整合这些流派在方法论上的不同偏好，形成一个统一的多学科视野的综合性网络计量和解释框架。1.2.2 视角图这个研究概念是一个非常大的概念，我们需要阐明一个特定的视角，才能对本文的研究内容做出实质性限定。我们的研究视角可以概括为：1框架性的计量和解释以何为网络和何以为网络2整合多学科偏好3基于网络的静态拓扑结构在1.1.2中我们明确了本文的研究对象，但是并没有说明计量和解释框架的具体含义，这主要是因为我们对计量框架和解释框架的界定是基于网络研究的层次模型提出的，而这部分的论述放在了第三章。概括的说，计量框架与解释框架试图回答这样一个问题：给定一个可以抽象成图的研究对象，根据以往的研究带来的启示，我们可以去研究图中的哪些定量特性（网络计量框架），这些定量特性之间通常又是如何互相影响和决定的（网络解释框架）。也可以说，网络计量框架回答的是网络以何为网络，网络解释框架回答的是网络何以为网络。图论、网络计量框架、网络解释框架和网络研究应用域的关系见第三部分的示意图，有关框架的详细内容也参见该部分。整合多学科偏好，就是说框架只基于网络的抽象模型，会尽可能多容纳各个学科的研究风格，忽略各个学科基于研究的具体网络对象的不同出现的差异，重视各个学科对抽象网络模型的理解和度量。整合必然会舍弃各个学科中的一些独特研究方向，因此需要明确一下本文不论述或不重点论述的若干方面。本文论述的立足点为网络的静态拓扑结构，所以将不论述网络的动态特征涉及的几个方面： 传播机理动力学 相继故障 搜索 同步 控制为了强化共性，将不重点论述涉及带权图的几个方面： 带权图的特征 基于带权图的算法为什么只研究静态结构的原因，首先是因为动态特征的复杂性和与具体网络的紧密相关性，在一个框架中全面覆盖这些内容并不现实；其次是因为在自然科学的复杂网络分析流派中对网络动态特征的描述已形成一个相对比较完整的体系；最后在于结构本身对图研究已经具有了超出其本身覆盖内容的重要性，结构本身的重要性我们可以以链接分析为例阐释如下：1结构构成信息。比如刻画超链网络图拓扑结构本身，就可以得到分析网页所属或所对应的意义实体（个人、组织、国家）之间的关系信息。2结构辅助人们认识信息。比如著名的Pagerank算法就是利用这一特点辅助人们认识网页的重要程度。网络链接结构还可以帮助人们根据不同的主题进行网页分类和主题提取等。3结构影响节点变化和节点间流动等动态功能和特征。举个例子，在网络链接结构分析中可以根据链接结构设计有效率的网页抓取方法以及结合用户的浏览行为进行分析。1.2.3 应用本文的目的在于建构一个综合性的网络计量和解释框架，它的作用将体现在打破学科壁垒，建立一个统一的网络分析研究范式，这个研究范式对各学科内部既有研究具有比较强的概括能力，对未来展开的网络研究具有比较大的参考价值。1.3 本文研究承继的科学哲学传统本文研究的承继的科学哲学传统指的是从科学哲学的视角来看，本文讨论的问题是基于什么样的理论基础，探讨的是哪一范畴的问题。从网络计量和解释框架来看，网络计量框架的提出基于库恩的范式理论，网络解释框架的构建基础则是对决定论和还原论的直接承继。1.3.1 范式理论 范式（Paradigm）是美国学者库恩在进行科学史的研究时提出的一个概念，他认为科学的发展不是简单的累积式的趋向于真理的过程，而是通过科学革命对学科研究范式的不断转换而推动实现的。库恩说明：“按既定的用法，范式就是一种公认的模型或模式。我采用这个术语是想说明，在科学实际活动中某些被公认的范例包括定律、理论、应用以及仪器设备统统在内的范例为某种科学研究传统的出现提供了模型。”3 本文中网络计量框架本质上是对三种学科范式的一种整合，试图形成综合三种学科范式的一种面向抽象网络计量领域的综合性范式。1.3.2 决定论和还原论决定论(determinism)是一种认为自然界和人类社会普遍存在客观规律和因果联系的学说。决定论认为，人的一切活动，都是先前某种原因或几种原因导致的结果，人的行为是可以根据先前的条件、经历来预测的。非决定论则否认自然界和人类社会普遍存在着客观规律和必然的因果联系，认为事物的发展、变化是由不可预测的、事物内在的“自由意志”决定的。 还原论（reductionism）通常指生物学中试图把生命运动形式归结为物理化学运动形式，用物理化学规律取代生物规律的一种思潮。18-19世纪的还原论用力学规律取代生物学规律。20世纪的还原论者把生物学规律还原为分子运动规律，甚至把人类活动还原为低等动物的反应，再把这些反应还原为物理化学过程。当代分子生物学的成就支持还原论，不仅遗传过程已还原为化学的相互作用，而且其他生物现象也将还原为化学过程。在本文论述的网络解释框架中，笔者将用向量表示的意义实体作为一个封闭系统，向量的结构和具有的性质完全由其分量决定，这是决定论和还原论观点的体现。1.4 本文其余部分的结构在本文的第二部分将系统分析以下三个学派在网络计量和解释上的偏好和贡献：以物理学、生物学、统计力学等自然科学学者为代表的复杂网络分析流派（CNA），以图书馆学、情报学等信息计量学学者为代表的诸计量学流派（*metrics）,和以社会学、传播学等社会科学学者为代表的社会网络分析流派(SNA)。分析重点在于他们对具体研究内容的数学形式化模型网络图的计量模式和解释方法上。同时，作者对超链网络研究领域也会做一大体回顾。在本文的第三部分将提出图论、网络计量框架、网络解释解释框架和网络研究应用域的关系理论，试图整合三种学科源流的不同研究范式和取向，建立一个统一的网络计量和解释框架。该框架宏观上面向网络计量和解释，将网络计量和解释中涉及的各种要素，主要计量指标分类选取以及解释路径纳入其中。在本文的第四部分为了进一步阐释该统一框架，作者将使用两个例子，解释框架在超链链接分析领域的具体适用性和应用方法及前景。本文的第五部分是一个简短的总结，说明了本文的贡献和不足之处。第二章 三种学科源流网络研究范式及超链网络分析研究综述2.1 三种学科源流分别的网络研究范式2.1.1 社会网络分析源流的网络研究范式首先介绍一下社会网络分析的相关定义和理论，社会科学对网络计量和解释的研究是基于社会科学对网络的带有学科特色的界定基础上的。社会科学领域研究的网络被称为社会网络，它的定义如下：社会网络是一种由节点组成的社会结构，这些节点通常意义上来讲是个人或者组织，而连接这些节点的则是各种类型的互相依赖关系或者互动。比如，互相认识，朋友，亲戚，喜欢，讨厌，冲突，疾病传播。社会科学中的很多学科都涉及到了网络计量和解释这一研究内容，主要涉及到的学科有以下几个学科：社会学，人类学，社会语言学，传播学，社会心理学以及经济学，其中由于学科研究对象的侧重不同，社会学和传播学对于社会网络的分析比较多。社会网络分析的视角在社会学中很早就被使用，但是社会网络作为一个正式的定义是由J. A. Barnes 4在1954年引入的，Barnes属于英国的结构功能学派，他在分析社会结构和文化体系如何决定人类行为的过程中，用网络这个词代指社会群体之间、社会成员之间，社会群体与其成员之间复杂的网状联系。社会网络理论以网络中间的个人及其关系为分析基础，强调个人的能动性，但另一方面又注意到社会网络所形成的社会结构以及社会制度对个人的制约。在社会网络分析理论发展过程中，影响非常大的一个研究是Mark Granovetter关于人际关系与职业流动相关性的研究5，在以前的社会学研究中，长期存在着微观设社会学和宏观社会学两种主要流派，过去的社会学分析中，微观分析比如形象互动理论，团体动力学都是研究个体行为，很少研究社会的宏观现象，而宏观的分析则视社会结构为社会群体的集合，社会群体以阶级、地位、种族、年龄、性别、地域和宗教加以区分。社会网络分析的意义正如Granovetter指出的那样，是要为微观行为与宏观行为之间建立一座桥。社会网络分析在其发展过程中形成了若干计量范式，这些范式以特定的指标和概念存在，反映了社会网络分析的研究方向和偏好，这里总结一下这些指标和概念，由于其中很多概念在下文框架部分还要提及，因此，具体数学表达式参见第三部分，这里只给出一些简单介绍：中介中介（betweenness）衡量的是一个个体在网络中对其他个体的连接程度。网络中很多节点没有直接相连的边，需要其他一些节点的中介实现连通。作为中介的节点可以使用betweenness这个指标来衡量他们对其他节点的连通带来的贡献程度。接近接近（closeness）衡量的是一个个体在网络中接近所有其他个体的程度（间接或者直接）。它反映了个体通过所在网络获取信息的能力。一个合理的度量手段是计算该节点到其他所有节点的最短距离的倒数。度中心度度中心度（Degree centrality）指的是一个节点与网络中其他的节点存在的直接连接的个数。流中介中心度流中介中心度（flow betweenness centrality）衡量的是一个节点对其他节点间连通性的贡献。特征向量中心度特征向量中心度（eigenvector centrality）在衡量网络中一个节点的重要性时，给每个节点赋予一个相对分数，迭代进行计算，迭代过程遵循这样的原则：连接到高分数节点的节点也会因此得分较高。中心势中心势（centralization）是一个衡量网络中边的分布状况（集中还是分散）的一个指标。一个中心势比较强的网络通常被称为中心化（centralized）网络，中心化网络有较多的边分布在一个或一些节点周围。而一个去中心化的网络则每个节点的拥有的边的情况差不多。聚类系数聚类系数（clustering coefficient）衡量的是与一个节点有边相连的两个节点之间有边相连的可能性。较高的聚类系数说明了“物以类聚”的特性。凝聚凝聚（cohesion）在社会网络分析中是一个没有精确界定的概念。大体上用来描述一个呈现如下特征的子图：在子图内部，节点对间的连接比子图与子图外部节点对间连接更为紧密。路径长度路径长度（path length）指的是两个节点间的距离 这里实际上和图论中的表达有矛盾，按照图论通用术语，路径（path）实际上并没有短程线（geodesic line）的意味。而距离（distance）指的是短程线的长度。所以，这里的路径长度实际上指的是最短路径长度（shortest path length）平均路径长度也指的是(average shortest path)。 。平均路径长度（average path length）是所有节点对之间距离的一个平均值。结构对等性结构对等性（structural equivalence）用来刻画在网络中两个节点间具有相同位置的特征。所谓具有相同的位置，就是和图的其他部分有相同的链接关系。有关对等性的详细介绍，可以参考第三部分中边的衍生部分的相关论述。2.1.2 复杂网络分析源流的网络研究范式在自然科学很多子学科内部，存在着诸如通信网络，电力网络，生物网络等许多复杂的网络结构，复杂网络分析(complex network analysis，以下简称CNA)是统计力学，神经生物学等学科的学者们探索和处理各种看上去互不相同的复杂网络之间的共性的一种普适工具。由于发展和使用这一普适工具的学者主要来自数理学科、生命学科和工程学科，所以尽管这一工具本身也试图容纳社会网络在研究范围其中之内，复杂网络分析还是有着很鲜明的自然科学特点无论是从研究对象还是从研究范式上来看。研究对象：从复杂网络分析的研究对象来看，分布在数理、生命、工程等各个学科，大多具有如下三个特点：61结构复杂性首先复杂网络分析关注到如下的网络结构复杂特点：节点之间的连接关系是混乱复杂无序的；节点之间的形成的边可能具有不同的权重和方向；网络整体结构可能是随时变化的。下图是一些复杂网络的网络拓扑结构7：图2- 1复杂网络分析的一些实例2节点复杂性复杂网络分析中的网络节点很多是具有分叉和混沌等复杂非线性行为的动力系统。例如，基因网络和Josephson结阵列中每个节点都具有复杂的时间演化行为。而且，一个网络中可能存在多个不同类型的节点。例如，控制哺乳动物中细胞分裂的生化网络就包含各种各样的基质和酶。3各种复杂性因素的相互影响实际的复杂网络会受到各种各样因素的影响和作用。例如，耦合神经元重复地被同时激活，则它们之间的连接就会加强，这被认为是记忆和学习的基础。此外，各种网络之间也存在密切的联系，这使得对复杂网络的分析变得更为困难。例如，电力网络的故障可能会导致Internet流量变慢、金融交易网络故障、交通运输网络失去控制等一系列不同网络之间的连锁反应。目前复杂网络分析的前沿问题主要存在于：1网络拓扑模型的建模、相关性质的讨论和与现实世界中相关网络的应用拟合。这些网络拓扑模型主要包括：规则网络、随机图、小世界网络。2网络上病毒和信息的传播动力学（Spreading Dynamics）。3网络相继故障（Cascading failures）分析。4复杂网络中的搜索（Searching）问题。5复杂网络中的子结构和相关算法。6复杂动态网络中的同步（Synchronization）。7复杂动态网络中的控制（Control）。复杂网络分析的研究范式：前文已经提到，我们会舍弃复杂网络中的静态拓扑结构，而不考虑动力学问题，所以这里只对涉及到的静态拓扑结构的网络建模及拟合应用加以讨论。在复杂网络分析中的网络模型构建中，有三个关键的指标：图聚类系数，平均路径长度和度分布。为避免重复描述，这三个指标的具体计量方法，在后面的框架部分加以陈述。之所以说这三个指标是关键的，是因为网络的这三个指标决定了很多其他复杂网络分析学派关注的重要性质。正因如此，复杂网络分析领域里的很多研究都测量了这三个指标，下图就是一些复杂网络分析学者分析过的网络在这三个基本指标上的表现8： 图2- 2 一些实际网络在三个复杂网络分析关键指标上的表现根据具体网络在这三个指标上的不同表现，形成了若干基本的网络模型，这些模型是从随机网络向规则网络的折衷： ER随机图 WS/NW小世界模型 BA无标度网络1ER随机图随机图理论源自二十世纪六十年代，两位匈牙利数学家Erds和Rnyi9研究了随机生成边的概率对图的性质的影响。假设规定网络中任意两点间有一条边的概率为固定的p，他们系统探讨了这样生成的图的性质。他们发现p比图的节点总数N对图的性质的影响更大，通过令N，然后变动p来观察图的其他度量指标的变化情况，可以发现，ER随机图的许多重要的性质都是突然涌现的，也就是说，对于任一给定的概率p，要么几乎每一个图都具有某个性质，要么几乎每个图都不具有该性质。ER随机图的关键指标值：平均度=p(N-1)pN平均路径长度L图聚类系数ER随机图的度分布遵循泊松分布。2WS/NW小世界模型小世界（small world）是一个非常有名的说法，很多学术文章或非学术文章都有所提及，这里我们试图探讨它的确切含义。小世界现象反映了网络中平均路径长度增加与网络规模增长的特定关系。直觉上来讲，小世界意味着随着整个网络规模的扩大，网络中两点距离的增加并不明显，严格的说，小世界概念要求在网络节点的平均度不变的情况下，网络中平均路径长度L的增加速度至多与网络规模N的对数成正比。从关键指标的限定来看，小世界模型是具有小的平均路径长度和大的图聚类系数特性的一类网络，有代表性的两个小世界模型是WS小世界模型和NW小世界模型。WS小世界模型由Watt和Strogatz在1998年引入10，其构造过程如下：a) 从规则图开始：考虑一个含有N个点的最近邻耦合网络 每个节点之和它周围的邻居节点相连的网络，它们围成一个环。其中每个节点又都与它左右相邻的各K/2节点相连，K是偶数。b) 随机化重连：以概率p随机地重新连接网络中的每个边，即将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点。在随机化重连的过程中为保持简单图 不含平行边也不含环的图的性质，规定任意两个不同的节点之间至多只能由一条边，并且每一个节点都不能有边与自身相连。NW小世界模型由Newman和Watts在1999年提出11，其构造过程如下：a) 从规则图开始：考虑一个含有N个点最近邻耦合网络，它们围成一个环，其中每个节点都与它左右相邻的各K/2个节点相连，K是偶数。b) 随机化加边：以概率p在随机选取的一对节点之间加上一条边。同样，为了保持简单图的性质，其中任意两个不同的节点之间最多只能有一条边，并且每一个节点都不能有边与自身相连。WS/NW小世界模型的关键指标值如下(这里都没有给出具体推导，请参见各参考文献) ： WS小世界图聚类系数：12 NW小世界图聚类系数： 8WS小世界平均路径长度： 11其中WS小世界度分布：时： 时： 0 12NW小世界度分布：时：时：0小世界模型除了上述比较有名的WS和NW模型之外，还有其它一些同样具有小的平均路径长度和大的聚类系数的特征的变种，参见8。3BA无标度（scale-free）网络无标度网络是具有无标度分布特征的网络，无标度分布又称幂律（power-law）分布。如果网络的度分布可以用幂律形式来描述：，则称网络服从幂律分布。图2-3是幂律分布的一个实例。图2- 3 幂律分布的一个示例无标度模型由Barabasi和Albert在1999年首先提出，现实网络的无标度特性源于众多网络所共有的两种生成机制13： 网络通过增添新节点而连续扩张 新节点择优连接到具有大量连接的节点上BA无标度模型的具体构造算法如下：a) 增长：从一个具有个节点的网络开始，每次引入一个新的节点，并且连到m个已存在的节点上，这里。b) 优先连接：一个新节点与一个已存在的节点i相连接的概率与节点i的度、网络中已存在所有节点的度数之和之间满足如下的关系：下面是BA无标度网络在关键指标上的表现：平均路径长度 14图聚类系数度分布复杂网络分析的研究传统从某种意义上说是从Erds和Rnyi真正开始的。Erds和Rnyi在随机图研究上的贡献不仅体现在对随机图本身的性质的理解，更体现在：1开拓了复杂网络分析的一种通用研究范式：观察归纳建模拟合和动态控制： 观察归纳：发现统计特征，重点观察以上多次提到的三个统计特征：度分布，图聚类系数，平均路径长度 建模拟合：根据网络的产生机制，构造出符合或接近上述统计特征类似的网络 动态控制：综合以上两步的成果，进行进一步的网络动态过程的研究。2将概率统计知识首次系统的应用于观察归纳和建模拟合的过程中。2.1.3 诸计量学源流的网络研究范式网络计量尤其是超链接网络计量(Hyperlink Network Analysis)的一个重要来源是图书馆学和信息科学(Library and information science)。在英文领域，其所属的父研究领域范畴比较复杂，具体的说，有信息计量学 早期译作情报计量学（informetrics），文献计量学（bibliometrics），科学计量学(scientometrics)，网络计量学(webometrics/cybermetrics)等，因为在英文中均以metrics结尾，在本文中笔者用*metrics（诸计量学）来概括信息计量科学的网络计量研究源流。 Lennart ，Bjorneborn和Peter Ingwersen用下面的图示演示了诸计量学之间的关系15，关于诸计量学的主要研究领域和其中的关系，亦可参考邱均平的相关论著16。从图中可以看出，信息计量学（informetrics）在诸计量学中涵盖的范围最大，因此，为了叙述上的通用和易于理解，下文中有时也用通用的信息计量学一词代指诸计量学这一源流。图2- 4 诸计量学之间的关系诸计量学源流的研究对象：主要源于文献计量学的*metrics源流的基本研究工具是引文分析（citation analysis），主要研究对象如文章之间的引用关系，作者之间的合作关系，以及由此衍生出来的期刊、学科研究领域和研究团体间的多重复杂关系，试图由此去量化论著和研究者在某些领域的影响。在互联网出现之后，由于互联网与引文研究对象在起源和内容上的相似性，很多文献计量学领域原有的研究方法被直接或经修改后移植到计算机网络尤其是和http层的超链分析领域，取得了很多成果。诸计量学源流的研究范式：如上所述，*metrics应用网络计量的领域主要在引文分析领域，其研究范式为有向图尤其是超链接形成的有向图上的网络计量提供了很多有益的启发，主要有以下三个方面： 提供了建立边的条件和角度，说明了有向图中关系的衍生模式 提供了可供检验和拟合的一些重要定律 提供了在有向图中尤其是web环境下使用的一些计量指标，如期刊的影响因子(impact factor)和网络影响因子等以下分别加以介绍：1提供了建立边的条件和角度，说明了有向图中关系的衍生模式文献计量学大体可以划分为内容分析(content analysis)和引用分析两大领域，其中引用分析主要提供的是一个在作者和文章之间建立关系（边）的方法和视角： 同被引耦合：所谓同被引耦合（co-citation coupling），就是指在文献计量的研究中，两篇或多篇论文同时被后来的一篇或多篇论文所引用，在这种情境下，则称被引用的论文具有“同被引”关系。同被引关系还可以根据引用它们的论文数量来测度其同被引的程度，一般称同时引用某两篇论文的论文篇数为这两篇论文的同被引强度（co-citation strength）或同被引频度（co-citation frequency）。同被引关系1973年由美国情报学家Henry Small提出，他以粒子物理学这一领域为研究对象，进行了同被引分析研究17。同被引关系除了表现在两篇文献之间之外，还存在三引乃至多引的同被引关系。Henry Small在1974年又提出了圆环模型，描述了三引及多引等同被引关系。18文献的同被引关系还被推广为作者同被引关系，期刊同被引关系和著者同被引关系。文献耦合：文献耦合（bibliographic coupling）和同被引耦合是相反的一个过程。文献耦合以被引论文作为联系媒介，反映了引证文献之间的相互关系。美国MIT的Kessler教授于1963年首次提出了文献耦合这一概念。他在对Physical Review这一期刊进行引文分析研究时发现，越是学科、专业内容相近的论文，它们参考文献中相同文献的数量就越多19。他把两篇（或多篇）同时引用一篇论文的论文成为耦合论文（coupled papers）， 并把它们之间的这种关系称为文献耦合。具有耦合关系的论文通常被认为它们在学科内容上存在某种联系或相关性，其耦合程度可以用耦合强度指标来衡量。耦合强度的量度单位是A和B共有的参考文献的篇数。耦合强度越高，通常意味着两篇文献在学科内容和专业性质上越接近，文献间联系也越紧密。 2提供了可供检验和拟合的一些重要定律 信息计量学在发展过程中形成了三个重要的定律，很多信息计量学的工作都是在阐释、验证、修正、发展这三个定律中展开，而这三个定律本身也非常值得网络计量和解释框架参考，下面就逐一来介绍这三个定律。a) 布拉德福分散定律：布拉德福分散定律（bradfords law of scattering）描述的是某个学科领域的相关文章在期刊中的分布情况。布拉德福分散定律认为：如果将科学期刊按其登载某个学科的论文数量的多少，以渐减顺序排列，那么可以把期刊分为专门面向这个学科的核心区和包含着与核心区同等数量论文的几个区。这时，核心区与相继各区的期刊数量大致呈的关系。布拉德福分散定律的文字表述结论是建立在将等级排列的期刊进行区域分析的方法之上的。如果将一定时间内（通常一年）的按某学科载文量等级排列的期刊划分为三个区，使每一个区所包含的相关论文数量相等，即恰好等于全部期刊发表的该学科文章总数的三分之一，可以发现：第一区（核心区）所涉及的文章来自数量不多但效率最高的种期刊；第二区（相关区）包括数量较大、效率中等的种期刊；第三区（外围区）包括数量最大而效率最低的种期刊。那么，三个区中的期刊数量呈下列关系： （）上面公式中的a被称作布拉德福常数，根据布拉德福本人所分析过的数据，a值约为5.0。20b) 齐普夫定律齐普夫定律（Zipfs law）最早来自美国语言学家齐普夫对自然语言中词频的观察和统计，随后，它被推广到了各个领域并得到了多方面的验证。它的基本内容被抽象之后如下：如果按照若干实体（原始论述中指单词）的可以量化的实力（原始论述中指频度）排序，并分别按照这个排序给各个实体赋予一个名次(rank)的话，实体的实力和名次之间往往存在着下面的关系：其中P是可以量化后的实体的实力，i是该实体的名次，a是一个常数，在原始的陈述中，a大约为1。c) 洛特卡定律洛特卡定律(Lotkas law)研究的实体的数量（原始论述中指作者）与实体的可以量化的实力（原始论述中指作者发表的论文的数量）的关系。它的基本内容被抽象之后如下：其中P是量化后的实体的实力，n是拥有该等实力的实体的数量，a是常数，在原始陈述的估