复杂网络分析篇（1）

复杂网络理论已经广泛应用于人们的日常信息生活中，本文将对复杂网络的研究进展与基础知识进行介绍。复杂网络理论的研究工作自身则具有比较鲜明的跨学科特色，在研究过程中会遇到许多难点，本文重点探讨在网络拓扑应用中，复杂网络理论的模型与特性。

1复杂网络理论

复杂网络即是一种具有内部相似性、有组织的网络形式。复杂网络的复杂性体现在以下六个方面:第一，结构复杂，复杂网络内部包含了数量巨大的网络节点，对各个网络节点进行排列与组合可以形成不同类型的网络结构，不同结构所体现出来的特征也是多种多样的;第二，网络进化。网络进行即网络节点消失或产生的过程，比如链接或网页可能随时出现或消失，其根本目则在于提高复杂网络的实用性，体现出网络进化的特点;第三，连接多样性。复杂网络中由于不同节点的特点不同，所采用的连接形式也存在较大的差异;第四，动力学复杂性。在不同结构特征的表现下，不同节点之间会体现出一定的复杂性特点;第五，节点多样性。节点作为网络中十分重要的组成部分是网络不中同事物的一个具体体现，由于不同计算机设备之间存在着巨大的差异，这就造成节点的差异，体现出节点多样性的特点;第六，多重复杂性融合。这种表现就是以上五点综合起来所形成的特点，这种综合性的特点直接决定了拓扑结构的特点。

2复杂网络理论的应用

2．1计算机网络同步行为研究

复杂网络中最常见的现象是同步行为，不同节点与网络拓扑之间在内部关系上也存在着比较明显的同步性倾向，然而对于部分特殊情况来说，同步行为可能并不利于提升用户的使用体验，甚至会对数据的储存与计算造成干扰。随着当前我国无线通信技术的不断发展，许多网络内部的信息需要由同一台路由器进行传送，不可避免地出现同步现象，所产生的同步行为包含两种，其中一种是路由信息同时生成，另一种是路由信息同时中止，第一种同步行为可能造成局域网络拥堵，另一种行为而会造成局域网络瘫痪。随着各大通信企业已经会对这方面的问题提出了大量的解决方案，但到日前为止，还能够哪一种方法能够彻底纠正同步行为所造成了危害。

2．2计算机网络拓扑行为的演化模型

当前世界范围内所广泛应用的网络拓扑模型主要包含两种，其中一种是局部演化模模型，另一种是复杂网络演化模式。通过自治域与路由器两个层面对拓扑结构进行刻画。在路由器层面，不同网络节点通过路由器体现出来，路由器设备的连接即是网络边际。在自治域层面，不同节点之间的连接通过边界网关体现出来。

2．3计算机网络拓扑模型的架设基础

计算机网络拓扑形态结构当中所具有的各种形态结构都需要图2拓扑结构在单独的搭建标准与适用环境中才能够发挥作用，在传输技术方面，网络拓扑结构主要包含两大类，分别是广泛散播方式与点对点传播方式，这两种传播方式都一定程度会干扰至计算机网络拓扑行为，即使要对网络形态与结构进行改良，也需要在数据资源充足的条件下才能够发挥出网络协议分析技术的调整作用，只有在数据库能够采集至网际间信息数据时，网络分析技术才能够投入应用。

2．4病毒防治方法

做好网络安全工作本质上就是综合运用各种手段解除病毒或是抵抗病毒，最大程度上将病毒对于网络的破坏降到最低限度。已往所采用的防毒措施是在特定网络病毒传播模型的基础上，平等对待全部网络节点，对网络内部的各个节点进行随机选取，然而这种防毒方法所体现出来的局限性是十分明显的，无法防止病毒进一步的蔓延。而单位计算机出现病毒感染的概率比较低，一旦发生感染，病毒侵犯的面积则可能会十分庞大，防御计算机病毒工作即是挑战也是机遇。利用复杂网络理论，程序设计人员可以制作一个病毒传播模型，依照人们对于病毒传播原理的有关见解，产生专门的拓扑结构，使网络拓扑结构与病毒传播原理相互作用，对病毒的蔓延起到阻止作用，其中重点的研究内容是延缓病毒传播速度与防御病毒两个方面。

3复杂网络理论的应用前景

复杂网络理论需要仍处于比较初级的发展阶段，但在人类对于网络世界的理解与认识上，复杂网络起到了理论丰富与知识拓展的作用。可以预见的是，在当前社会全面进行信息化时间的大背景下，复杂网络理论所发挥出来的重要作用是其他理论与技术不可替代的，计算机网络拓扑与复杂网络理论相结合，可以在未来一段时间内形成一套固定的规律并投入到技术应用中，在有关研究成果与应用经验的不断积累下，能够对现有的网络结构进行进一步的优化，提高网络信息传递效率，改善用户的网络信息应用体验。

4结语

计算机网络具有系统复杂性与规模庞大性两方面的特点，通过已往所采用的排列与组织方法很难理清庞大且复杂的网络拓扑结构。这就需要针对计算机网络的复杂性特点专门形成一套理论体系，即复杂网络理论，通过这种理论，人们可以通过一种更加快捷、更加简单的方式来刻画出计算机拓扑行为，使人们能够发现优化网络拓扑行为的方法，推动网络信息的合理化发展。

参考文献:

复杂网络分析篇（2）

一、引言

随着计算机网络的飞速发展，传统的网络模型已经很难对计算机网络拓扑特性做出客观的描述和研究。针对这个现象，复杂网络理论的产生和应用，为计算机网络的拓扑发展带来了新的平台和思路。对于复杂网络理论在计算机网络拓扑中的分析已经成为计算机网络领域研究的重要课题。

二、复杂网络和计算机网络拓扑的基本理论

（一）复杂网络理论的含义及其复杂性

复杂网络是指具有内部相似、自行组织、吸引因子、小区域、无标度中的一部分或者全部的网络。其复杂性主要体现在以下六个方面：①结构的复杂性，表现在网络的节点数量较大。②节点的多样性，网络中的所有组成部分，代表的各种事物均为复杂网络理论中的节点。③连接的多样性，指的是网络中节点的连接方式不一致。④动力学的复杂性，指的是节点之间的复杂性，能够产生多样的结构特征。⑤网络结构的变化性，指的是网络节点之间消失和连接产生就像网页随时断开和连接一样，使得网络结构不断的发生变化。⑥多重复杂性的融合，指的是上述所有复杂性的结合表现出的复杂性。此外，复杂网络理论有小世界、集团集聚程度更加密集和幂律的度及介数涵盖的范围不断扩大等三种特性。

（二）计算机网络拓扑技术及分类

计算机网络拓扑最早是由瑞士数学家欧拉在1736年提出的，主要是用于连接计算机网络和传输不同设备之间数据的一种方式。不同的网络设计要选择适合的网络拓扑方式，在网络拓扑结构中，拓扑技术是以图像的方式来表示多种设备之间的相互关系。计算机网络拓扑的主要类型有星行结构、环形结构、总线型结构、混合拓扑结构、分布式结构等。由于计算机的分布和数据传输电缆的布置存在很大的差异性，每一种网络拓扑结构都有其相应的优缺点，因此在计算机网络拓扑形式的使用上，要具体问题具体分析。

三、复杂网络理论在计算机网络拓扑中的具体应用分析

（一）计算机网络的同步行为现象分析

这主要是指计算机各个网络节点之间的同步行为，在复杂网络理论中，网络节点之间的同步是较为常见的一种现象，主要是受网络拓扑和各节点之间的动力学性质决定的。但是值得注意的是，这种同步行为并不都是有益的，如由多个路由器发出路由信息的网络，其同步行为包括了发出同一种路由信息和同时不发送信息，这就很有可能会使得网络出现拥挤或者瘫痪的现象。从计算机网络技术的发展来看，人们采取避免计算机网络出现同步行为的措施并没能完全奏效，经常会出现一种同步行为结束，另一种同步行为又产生的现象。因此，如何有效杜绝计算机网络的同步行为现象仍然是人们研究的课题。

（二）计算机网络拓扑行为的演化模型

计算机网络拓扑行为的演化模型由复杂网络演化模型逐步转变为了局部演化模型，这两种演化模型都是从路由器和自治域两个不同的层次来描述计算机网络的拓扑结构的。从路由器上看，各个路由器相当于各个网络节点，而路由器之间的物理连接相当于边。从自治域上看，在边界网关协议的基础上，如果两个自治域之间对等连接的话，就说明这两个节点之间是有一条边相连的。复杂网络演化模型演化出的结果很大程度上出现“富者更富，穷着更穷”的现象，即那些新加入的用户会倾向于那些品牌好、质量好、连接数量多的网络服务商。该模型遵循的“偏好连接”原则是基于整个网络上的，与优先考虑连接到本地区的服务器或路由器的实际不符。而局部演化模型的偏好连接倾向性是在局部信息的基础上形成的，一定程度上克服了复杂网络演化模型的缺陷。

（三）计算机网络脆弱性和鲁棒性的动力学模型

1.计算机网络的鲁棒性。计算机网络的原始功能是保证军事资料的安全性，这样的保证就是所谓的鲁棒性。鲁棒性是指在计算机网络中的某个区域或节点中出现问题或故障时，不会扩散到整个计算机网络系统，计算机还能保持正常的运行。相关研究表明，一般在一个网络系统中，只要有百分之二十左右的正常区域和政策阶段就能够保障计算机网络的正常运行。

2.计算机网络的脆弱性。虽然计算机网络有鲁棒性的动力学模型，但是一旦计算机网络系统中的重要区域或节点受到破坏时，整个计算机网络将会异常脆弱。更有甚者，如果计算机网络中一小部分的中心阶段被破坏后，整个网络就会陷入瘫痪的境地，计算机网络也无法保障正常运行。

（四）计算机网络病毒扩散模型和病毒防治的方法

网络安全影响了计算机网络的日常运行，而影响网络安全的因素主要是病毒的袭击和扩散。因此，复杂网络理论在计算机网络拓扑中的应用，应该采取有效的措施来抑制计算机网络病毒的扩散，减少病毒的传播，避免病毒对计算机网络损害后带来的计算机网络安全问题。复杂网络理论开始应用于计算机网络拓扑行为中时，人们开始以复杂网络为基础不断研究和探索出新的防御病毒的方法，且取得了一定的进展。比如在规则网络中，人们经过研究发现计算机网络病毒只有在小世界中才能轻易的传播，在复杂网络理论里，计算机网络感染病毒的可能性较小，一旦感染的话，网络系统将会受到大面积病毒的袭击，这对预防计算机病毒的入侵技术而言是一大挑战。防御计算机网络病毒工作的开展，必须建立一个科学系统的防御病毒扩散模型，模型需要遵循的原则有网络的拓扑结构形式、知晓病毒的传播原理、网络拓扑结构形式和知晓病毒传播原理之间的关系和作用。此外，在计算机网络病毒扩散模型的构建和病毒防治的过程中，要格外注重预防网络病毒的产生和传播的速度，通过网络的拓扑结构和复杂网络理论来做好计算机网络的抗病毒工作。

四、结语

总之，基于复杂网络理论的计算机网络拓扑分析是一项专业的、复杂的、系统的步骤程序化工程。复杂网络理论能保障了人们实现对计算机网络拓扑行为的要求，促使了计算机网络拓扑研究的发展，给我国现代化网络的发展提供了可靠的保障。

复杂网络分析篇（3）

随着科学技术的进步和生产力的发展,政治、经济、社会环境发生了巨大变化,顾客的消费水平不断提高,使得企业间的竞争日益加剧。企业为了提高竞争力而采取了许多先进的制造技术和管理方法。营销管理日益受到企业的重视,企业在全球市场中不再作为单个实体而是作为营销链的一部分参与竞争,企业之间的竞争已经转化成为营销系统之间的竞争。营销系统是在竞争、合作、动态的环境中,由厂商、各级销售和客户等成员实体构成的快速响应环境变化的动态销售网络。在竞争、合作和动态多变的市场环境下,复杂营销网络中的每一个成员都有自身的经营策略,每个成员的目标都是通过不断提高自身对市场的适应能力从而提高其竞争力来获取利润。可见,营销系统是一种复杂的自组织、自适应性网络系统,因而用复杂网络的研究方法可以发现其它方法不易揭示的该类系统的有趣而且重要的性质,而这些宏观规律对系统的运作管理和科学决策具有重要的参考价值。

一、复杂网络的统计参数

复杂系统可以被理解为一个关系网络, 这个关系网络由一个个节点所组成, 这些节点之间依据一定的规则、相互关系而维系着系统整体的存在。在社会经济系统中作为复杂系统的网络无处不在, 如人与人之间的社会网络、资源共享网络、绿色经济网络、企业之间的产品生产和销售等方面的竞争网络、国家内外之间的贸易合作网络等等。复杂网络研究是从统计角度考察网络中大规模节点及其连接之间的性质, 这些性质的不同意味着不同的网络内部结构, 而网络内部结构的不同导致系统功能有所差异。在现实的社会经济系统中,我们将每一个企业主体看做是一个节点,而企业之间的博弈规则看做是连接节点的边,于是系统中存在的主体便构成了一个网络。

1.平均路径长度(Average path length)

网络的特征路径长度 是所有节点对之间的最短路径的平均值, 表示为

(1)

其中表示节点之间的最短路径值。

研究表明,尽管许多实际网络的节点数巨大,但网络的平均路径长度L相对于N来说却很小,这种现象称之为“小世界效应”。

2.聚类系数(Clustering coefficient)

节点的聚类度的所有邻居节点之间实际的连接数与理论存在的最大连接数之比, 表示为

(2)

其中为节点的度。平均聚类系数C定义为所有节点的聚类系数的平均值, 表示为

(3)

研究表明,在大多数情况下,复杂网络的集群系数都要比随机网络和规则网络的集群系数大得多。正如常言所说的“物以类聚,人以群分”所描述的那样,社会经济网络的一个典型的特征就是小集团集群的形态。

3.度及度分布(Degree and degree distribution)

图论中节点的度定义为与该节点连接的其它节点的数目,通常用分布函数 来描述网络中节点的度分布情况, 表示一个随机选定节点的度恰好为 的概率。节点度的分布特征是网络的重要几何性质,规则网络中各节点的度值相同,符合Delta 分布,随机网络的度分布可近似为Poisson 分布,大量的实际网络存在幂律形式的度分布,称为无标度网络。无标度网络是节点与节点之间的连接分布遵循幂律分布的网络,即节点度分布服从幂律分布。在这种网络中,大部分节点只有少数连接,而某些少数节点则拥有与其他节点的大量连接,即存在一些关键的中枢节点。这种网络对于随机性错误具有较强的鲁棒性,对于人们的蓄意攻击或破坏却具有较强的脆弱性,疾病在这种网络上极易传播。

二、企业营销网络分析

企业的产品营销系统是由厂商、各级销售和客户共同构成。现实中的企业营销系统通常由于销售(制造商、商和批发商)的分布范围的不同以及它们之间存在着各种各样的联系, 往往形成一个庞大的复杂网状结构。企业产品的营销过程, 也可以看成是厂商生产出来的产品通过各级销售, 最后扩散到用户中的扩散过程, 或者说是企业产品从厂商到销售, 最后到用户的传播过程。所以厂商、各级销售和用户就构成了企业产品在营销网络中的节点,节点之间的营销关系构成了网络中的边。

三、模型的建立

分析了企业营销网络中企业之间的营销关系,提出了一种新的演化模型来模拟其网络的演化过程,该模型的基本思想源于局域世界演化模型,演化过程中考虑两种基本因素:增长和局域世界优先连接。

1.增长模型

考虑到企业营销网络的演化特点,新模型的初始条件与其他模型有些区别,它起始于个节点,条边,节点之间两两相连, ,第一次新增节点具有m条边,并且这m条边分别和每个已有节点相连。这样,在之后的每一个时刻便会添加一个新的节点,而该新节点边的条数m是从以概率选取,这里是选取边数为的概率。那么在时刻之后,该网络便有个节点,条边的网络。

2.优先连接模型

在该模型中,网络中原有的节点连接新的节点的概率与以下两个因素有关系:

(1) 与节点的度有关系,这种关系是正比关系。

(2) 与节点的局域世界也有关系,节点优先连接机制不是对整个网络,而是在每个节点各自的局域世界中有效。随机地从网络已有的节点中选取m个节点,作为新加入节点的局域世界。新加入的节点根据优先连接概率来选择与局域世界中的m个节点相连。

四、仿真分析

1.仿真设计

为了验证统计企业营销网络的统计特性,以青海省城乡私营企业所构成的批发和零售业企业营销网络为例,基于上述网络模型构造算法的描述,利用VB语言编程实现模型的构建,构建出的模型如图1所示。实现时根据网络演化模型的构造算法,初始时先确定节点的总数,然后根据构造算法得到相应网络模型的邻接矩阵,最后再依据邻接矩阵计算网络的度分布、平均最短路径和平均聚集系数。

2.数据分析

以大圆点代表批发商,小圆点代表销售商, 边代表它们之间所存在的营销关系,不同的节点代表不同的企业。 通过直观的观察可以了解到,在企业营销复杂网络中批发商和销售商的营销关系比较密切, 相对来说批发商或销售商之间的营销关系却较为缺乏。也可以看到节点之间的距离很小,是一个典型的小世界网络。各成员企业间的联系的分布是不均匀的,这主要是由于成员的地位不同造成的。与核心企业的联系密集,节点度就大;而与小的非核心企业联系稀疏,节点度就小,即存在优先连接,新加入该系统的企业会优先选择与那些在社会中影响力较大、实力雄厚的企业进行合作,表现在网络中就是首先选择与度比较大的节点进行连边。

下面的仿真图只是仿真过程中的部分结果。从仿真结果可知,网络的平均路径较小,随着网络节点数的增加呈现上升的趋势,但增加的速度较为缓慢,以网络节点数 的对数成正比。如图2所示。网络的平均聚集系数较高,随着网络节点数的增加呈现下降的趋势,但不会随着网络节点数的无限增大而趋于0,表明此网络具有小世界网络的特点,如图3所示。网络的度分布服从幂律分布,在网络中拥有少量度很大的节点,而大部分节点的却为2,相对来说,这些节点的度很小,满足无标度网络的第一个重要特性。

3.复杂网络统计特性对企业营销工作的指导意义

复杂网络的最终目的是通过对现实网络模拟,仿真得到相关数据,通过对数据的分析,更加科学合理的预测和控制相应的网络行为。本文中生成的网络模型较为真实的反应了现实网络的特性,因此在该网络模型中得到的统计参数也能反应现实网络的实际意义。

(1) 复杂系统理论中复杂网络具有自组织现象, 通过合理的运作, 企业可以扩大网络中已有节点之间的营销合作,即网络内部的演化。例如,生产商企业可以对其网络中某些中枢节点的商赋予一定权限, 使其进行低成本销售策略, 从而增加网络内部与其它节点连接比较少的节点与这些中枢节点的连接,从而使得营销网络内部边的线性增长。

(2)生产厂商或产品销售企业可以使用比竞争对手更具诱惑力的销售方式,一方面,稳定营销网络中已存在的合作节点, 增强节点构成者的满意度, 从而达到增强营销网络鲁棒性的目的;另一方面,吸引更多的新企业加入到网络中,使网络规模不断增加。

(3) 市场销售对于企业而言具有信息反馈的作用,企业应重视营销过程中所得到的反馈信息, 一方面研发能够不断满足客户需要的新产品,另一方面对现有的产品和服务进行改进, 提高客户的满意度, 从而阻止竞争对手对合作客户的争夺,防止企业的退出。

(4) 企业要想在激烈的市场竞争中长盛不衰,必须要有不断的创新(制度创新和技术创新)。创新将打破原有生产销售合作网络中的均衡。创新与竞争可能会导致网络中的某些企业破产,这些企业破产会不会导致网络的剧烈变动甚至整个结构的变更实际上依赖于这些企业在网络中的重要程度,政府应对这种核心企业采取适当的政策加以保护。

五、结束语

本文以企业营销网络为例,模拟构建了网络模型,通过对该模型的统计参数的理论描述和计算机仿真,初步探讨了统计参数对企业营销网络的指导意义。在进行仿真分析过程中也发现,由新模型所生成网络的平均最短路径和企业营销网络的真实数据还是有些差别,在上面所示的仿真结果中,平均最短路径要比真实数据大。当调整模型中的参数时,虽然能够使得平均路径趋于真实数据,但是此时,其它部分却又与实际的数据有些差别。因此,我们需要继续研究其中的原因,来改进新模型,使其更加适合企业营销工作网络的演化方式。

参考文献:

[1]侯明扬:复杂网络理论在企业营销中的应用研究[J]. 华东经济管理, 2008 (2) :1322134

[2]刘宏鲲 周涛:中国城市航空网络的实证研究与分析[J]. 物理学报,2007 (1) :1062113

[3] Watts D J, Strogatz S H. Collective dynamics of‘small-world’networks[ J ]. Nature, 1998,393 (4) : 440 - 442

复杂网络分析篇（4）

一、引言

网络可以用来描述从生物到社会的各类真实系统，其中节点表示真实系统中不同的个体或组织，而边则表示个体或组织之间的联系。近年来，国际科学界对复杂网络理论与实证的研究做了大量的工作，很多国际一流的刊物如Nature、Science等都陆续刊发了大量复杂网络的研究论文，研究所涉及的网络有：科学家合作网络、交通网络、神经网络、新陈代谢网络等。但综观这些论文，没有学者对产业结构进行分析和研究。

英国是世界经济强国之一，其国内生产总值在西方国家中居前列。2002年，英国经济规模居世界第四，是世界第二大海外投资国，同时是世界第四大贸易国。英国经济的发达与其产业结构有重要的关联。本文试图从复杂网络的角度对英国产业结构进行分析和研究。因此，本文以英国产业结构为研究对象，将产业结构抽象为由产业和产业间联系所组成的复杂网络，把产业看作是网络中的节点，将产业与产业之间的联系看作是网络中的边，计算网络的统计特征，分析其具有的复杂性，希望为我国产业结构的发展和优化提供决策依据。

二、英国产业结构网络

产业是同类企业的总和，产业结构由许多的产业部门组成，各产业部门之间相互依存、相互联系、相互作用，共同构成一个有机的整体。本文研究的英国产业结构网络由123个产业组成。所利用的数据来自英国2002年价值型投入产出表。为研究方便，对数据有以下说明：

1.不考虑本产业对本产业的中间投入，只有这样建立起来的网络才不是一个自环的网络。

2.引入消耗系数的临界值并进行无向化处理。临界值的计算过程如下：首先，计算出所有的直接消耗系数，其计算公式如下：

三、网络的相关统计特性

网络的相关统计特征有：平均最短距离、平均簇系数、度分布、度-度相关性、度-簇相关性、点介数。

1.平均最短距离

在英国产业结构网络中，最短距离表示任意两个产业之间最少的边的数目。整个网络的平均最短距离则是对所有节点对的最短距离的平均。其公式如下：

经过计算得到英国产业结构网络的簇系数为0.478，表现出聚集性。由于该网络同时具小的平均最短距离和较大的簇系数，因此可以认为它是一个小世界网络。

3.度分布

节点的度是指与此节点连接的边的数量，所有节点的度的平均值称为网络的平均度。网络中节点的度分布可以用分布函数p(k)来表示，p(k)被定义为随机地选择一个节点恰好有K条边的概率，或者等价地描述为网络中度为K的节点数占网络节点总数的比例。

根据英国产业结构网络的实际数据计算，可以得到网络的平均度为16.8，即每个产业平均连接17个其他的产业。英国产业结构网络的度分布，如图1所示。

图1为双对数坐标，横坐标表示点序号，纵坐标表示节点度。由图1可见，在这个网络中，节点度服从双段幂律分布，对所得数据进行双段拟合，得到的拟合斜率分别为-0.2778和-5.8826。

4.度-度相关性

度-度相关性表现的是节点之间相互选择的偏好性。一个节点i所有邻近节点的平均度记为

根据公式(3-7)可计算出123个节点当中的每个节点的介数Bi，点介数分布如图4所示。

由图4可知，点介数分布服从幂律分布，介数大的节点数目较少，介数小的节点数目教多，大部分节点的点介数均处在0.039832和0.01639之间，这些节点在网络中的影响较小。表中展示了介数值排名前10位的产业，由于点介数反映了其在网络中的影响力，那如果把表1中的任何几个节点或全部节点从网络中删除，则会极大地影响网络的运行。

四、结论与展望

以产业部门为节点的英国产业结构网络是一个小世界网络，具有短的平均路径长度和大的簇系数，且其度分布服从双段幂律分布。网络表现出负的度度相关性，表明度大的节点优先连接度小的节点。同时，此网络具有正的度簇相关性，说明度大的产业比度小的产业更倾向与集聚成团。

本文只是对英国产业结构网络无向性质的一个初步研究，在后续的研究工作中会深入研究边的方向及边权、点权对网络性质的影响。除此之外，还将对比各国的产业结构网络的性质，从而对各国经济的增长和同一产业的发展进行比较，进而能够采取措施促进整个经济的增长或单个产业的发展等。

参考文献：

[1]周涛柏文洁等:复杂网络研究概述[J].物理，2005，(1):31～36

[2]Newman M E J．The structure and function of complex networks[J]. SIAM Review，2003，45：167～256

[3]Wang X F．Complex networks: Topology, dynamics and synchronization[J].Int J Bifureation & Chaos, 2002,12:88～916

[4]Albert R，Barabasi A-L．Statistical mechanics of complex networks[J].Rev．Mod．PhyS，2002，74：47～97

[5]刘宏鲲周涛:中国城市航空网络的实证研究与分析[J] .物理学报，2007，(1):106～113

[6]郑金连狄增加:复杂网络研究与复杂现象[J].系统辨证学学报，2005，(4):8～13

复杂网络分析篇（5）

关键词:网络模糊聚类;团—点相似度;团间连接紧密度;团间连接贡献度;对称非负矩阵分解;网络宏观拓扑

Fuzzy clustering and information mining in complex networks

ZHAO Kun，ZHANG Shao-wu，PAN Quan

(School of Automation， Northwestern Polytechnical University， Xi’an 710072， China)

Abstract:There is seldom a method which is capable of both clustering the network and analyzing the resulted overlapping communities. To solve this problem， this paper presented a novel fuzzy metric and a soft clustering algorithm. Based on the novel metric， two topological fuzzy metric， which include clique-clique closeness degree and inter-clique connecting contribution degree， were devised and applied in the topological macro analysis and the extraction of key nodes in the overlapping communities. Experimental results indicate that， as an attempt of analysis after clustering， the new indicators and mechanics can uncover new topology features hidden in the network.

Key words:network fuzzy clustering; clique-node similarity; clique-clique closeness degree; inter-clique connection contribution degree; symmetrical nonnegative matrix factorization(s-NMF); network topology macrostructure

团结构是复杂网络普遍而又重要的拓扑属性之一，具有团内连接紧密、团间连接稀疏的特点。网络团结构提取是复杂网络分析中的一个基本步骤。揭示网络团结构的复杂网络聚类方法[1~5]对分析复杂网络拓扑结构、理解其功能、发现其隐含模式以及预测网络行为都具有十分重要的理论意义和广泛的应用前景。目前，大多数提取方法不考虑重叠网络团结构，但在多数网络应用中，重叠团结构更为普遍，也更具有实际意义。

现有的网络重叠团结构提取方法[6~10]多数只对团间模糊点进行初步分析，如Nepusz等人[9，10]的模糊点提取。针对网络交叠团结构的深入拓扑分析，本文介绍一种新的团—点相似度模糊度量。由于含有确定的物理含意和更为丰富的拓扑信息，用这种模糊度量可进一步导出团与团的连接紧密程度，以及模糊节点对两团联系的贡献程度，并设计出新指标和定量关系来深度分析网络宏观拓扑连接模式和提取关键连接节点。本文在三个实际网络上作了实验分析，其结果表明，本方法所挖掘出的网络拓扑特征信息为网络的模糊聚类后分析提供了新的视角。

1 新模糊度量和最优化逼近方法

设A=[Aij]n×n(Aij≥0)为n点权重无向网络G(V，E)的邻接矩阵，Y是由A产生的特征矩阵，表征点—点距离，Yij>0。假设图G的n个节点划分到r个交叠团中，用非负r×n维矩阵W=[Wki]r×n来表示团—点关系，Wki为节点i与第k个团的关系紧密程度或相似度。W称为团—点相似度矩阵。令

Mij=?rk=1WkiWkj(1)

若Wki能精确反映点i与团k的紧密度，则Mij可视为对点i、j间相似度Yij的一个近似。所以可用矩阵W来重构Y，视为用团—点相似度W对点—点相似度Y的估计:

W ?TWY(2)

用欧式距离构造如下目标函数:

minW≥0 F?G(Y，W)=Y-W ?TW?F=?12?ij[(Y-W ?TW)。(Y-W ?TW)]ij(3)

其中:?F为欧氏距离;A。B表示矩阵A、B的Hadamard 矩阵乘法。由此，模糊度量W的实现问题转换为一个最优化问题，即寻找合适的W使式(3)定义的目标函数达到最小值。

式(3)本质上是一种矩阵分解，被称为对称非负矩阵分解，或s-NMF (symmetrical non-negative matrix factorization)。?s-NMF的求解与非负矩阵分解NMF[11，12]的求解方法非常类似。非负矩阵分解将数据分解为两个非负矩阵的乘积，得到对原数据的简化描述，被广泛应用于各种数据分析领域。类似NMF的求解，s-NMF可视为加入限制条件(H=W)下的NMF。给出s-NMF的迭代式如下:

Wk+1=W?k。[W?kY]/[W?kW ?T?kW?k](4)

其中:[A]/[B]为矩阵A和B的Hadamard矩阵除法。

由于在NMF中引入了限制条件，s-NMF的解集是NMF的子集，即式(4)的迭代结果必落入NMF的稳定点集合中符合附加条件(H=W)的部分，由此决定s-NMF的收敛性。

在求解W之前还需要确定特征矩阵。本文选扩散核[13]为被逼近的特征矩阵。扩散核有明确的物理含义，它通过计算节点间的路径数给出任意两节点间的相似度，能描述网络节点间的大尺度范围关系，当两点间路径数增加时，其相似度也增大。扩散核矩阵被定义为

K=exp(-βL)(5)

其中:参数β用于控制相似度的扩散程度，本文取β=0.1;L是网络G的拉普拉斯矩阵:

Lij=-Aiji≠j

?kAiki=j(6)

作为相似度的特征矩阵应该是扩散核矩阵K的归一化?形式:

Yij=Kij/(KiiKjj)??1/2(7)

基于扩散核的物理含义，团—点相似度W也具有了物理含义:团到点的路径数。实际上，W就是聚类结果，对其列归一化即可得模糊隶属度，需要硬聚类结果时，则选取某点所对应列中相似度值最大的团为最终所属团。

2 团—团关系度量

团—点相似度W使得定量刻画网络中的其他拓扑关系成为可能。正如W ?TW可被用来作为点与点的相似度的一个估计，同样可用W来估计团—团关系:

Z=WW ?T(8)

其物理含义是团与团间的路径条数。很明显，Z的非对角元ZJK刻画团J与团K之间的紧密程度，或团间重叠度，对角元ZJJ则刻画团J的团内密度。?

以图1中的对称网络为例，二分团时算得

Z=WW ?T=1.337 60.035 3

0.035 31.337 6

由于图1中的网络是对称网络，两团具有同样的拓扑连接模式，它们有相同的团内密度1.337 6，而团间重叠度为?0.035 3。

3 团间连接贡献度

ZJK度量了团J与团K间的重叠程度:

ZJK=?na=1WJaWKa(9)

其中:WJaWKa是这个总量来自于点a的分量。下面定义一个新指标来量化给定点对团间连接的贡献。假设点i是同时连接J、K两团的团间某点，定义点i对团J和团K的团间连接贡献度为

B?i=[(WJiWKi)/(?na=1WJaWKa)]×100%(10)

显然，那些团间连接贡献大的点应处于网络中连接各团的关键位置，它们对团间连接的稳定性负主要责任。将这种在团与团间起关键连接作用的点称为关键连接点。为了设定合适的阈值来提取团间关键连接点，本文一律取B>10%的点为关键连接点。

4 实验与结果分析

下面将在三个实际网络上展开实验，首先根据指定分团个数计算出团—点相似度W，然后用W计算团—团关系和B值，并提取关键连接点。

4.1 海豚社会网

由Lusseau等人[14]给出的瓶鼻海豚社会网来自对一个62个成员的瓶鼻海豚社会网络长达七年的观测，节点表示海豚，连线为对某两只海豚非偶然同时出现的记录。图2(a)中名为SN100 (点36)的海豚在一段时间内消失，导致这个海豚网络分裂为两部分。

使用s-NMF算法聚类，海豚网络分为两团时，除30和39两点外，其他点的分团结果与实际观测相同，如图2(a)所示。计算B值并根据阈值提取出的五个关键连接点:1、7、28、36、40(虚线圈内)，它们对两团连接起到至关重要的作用。图2(b)为这五点的B值柱状图。该图显示，节点36(SN100)是五个关键连接点中B值最大者，对连接两团贡献最大。某种程度上，这个结果可以解释为什么海豚SN100的消失导致了整个网络最终分裂的影响。本例说明，s-NMF算法及团间连接贡献程度指标在分析、预测社会网络演化方面有着独具特色的作用。

4.2 Santa Fe 科学合作网

用本算法对Newman等人提供的Santa Fe科学合作网络[15]加以测试。271个节点表示涵盖四个学术领域的学者，学者合作发表文章产生网络连接，构成了一个加权合作网络。将本算法用于网络中一个包含118个节点的最大孤立团，如图3(a)所示。

图3(a)中，四个学科所对应的主要组成部分都被正确地分离出来，mathematical ecology(灰菱形)和agent-based models(白方块)与文献[15]的结果一致，中间的大模块statistical physics又被细分为四个小块，以不同灰度区分。计算了24个点的团间连接度贡献值B，从中分离出11个B值大于10%的点作为关键连接点:1、2、4、6、11、12、20、47、50、56、57，其标号在横轴下方标出，见图3(b)，并在图3(a)中用黑色圆圈标记，这些连接点对应那些具有多种学科兴趣、积极参与交叉研究的学者。除去这11个点时，整个网络的连接布局被完全破坏，见图3(a)下方灰色背景缩小图，可见关键连接点的确起到重要的沟通各模块的作用。

4.3 杂志索引网络

在Rosvall等人[16]建立的2004年杂志索引网络上进行测试。网络节点代表杂志，分为物理学(方形)、化学(方形)、生物学(菱形)、生态学(三角形)四个学科领域，每个学科中各选10份影响因子最高的刊物，共40个节点，若某刊物文章引用了另一刊物文章，则两刊间有一条连线，形成189条连接。使用s-NMF对该网4分团时，聚类结果与实际分团情况完全一致，如图4(a)所示。

由本算法得出的团—点相似度W在网络宏观拓扑结构的挖掘方面有非常有趣的应用，如第2章所述，用W计算团—团相似度矩阵Z=WW?T，其对角元是团内连接密度，非对角元表征团与团的连接紧密程度，故Z可被视为对原网络的一种“压缩表示”。如果将团换成“点”，将团与团之间的连接换成“边”，利用Z的非对角元，就能构造出原网络的一个压缩投影网络，如图4(b)所示。这是原网络的一个降维示意图，也是团与团之间关系定量刻画的形象表述，定量地反映了原网络在特定分团数下的“宏观(全局)拓扑轮廓”，图上团间连线色深和粗细表示连接紧密程度。由图4(b)可以看到，physics和chemistry连接最紧密，而chemistry与biology和biology与?ecology次之。由此推测，如果减少分团数，将相邻两团合并，连接最紧密的两团必首先合并为一个团。实际情况正是如此:分团数为3时，biology和ecology各自独立成团，physics 和?chemistry合并为一个大团，这与文献[11]结果一致。

5 讨论

网络模糊聚类能帮助研究者进一步对团间的一些特殊点进行定量分析，如Nepusz等人[9]用一种桥值公式来刻画节点在多个团间的共享程度，即节点从属度的模糊程度。而本文的团间连接贡献度B反映出节点在团间连接中所起的作用大小。本质上它们是完全不同的两种概念，同时它们也都是网络模糊分析中所特有的。团间连接贡献度指标的提出，将研究引向对节点在网络宏观拓扑模式中的影响力的关注，是本方法的一个独特贡献。无疑，关键连接点对团间连接的稳定性起到很大作用，如果要迅速切断团间联系，改变网络的宏观拓扑格局，首先攻击关键连接点(如海豚网中的SD100)是最有效的方法。团间连接贡献度这一定义的基础来自于对团与团连接关系(Z)的定量刻画，这个定量关系用以往的模糊隶属度概念无法得到。由于W有明确的物理含义，使得由W导出的团—团关系Z也具有了物理含义，这对网络的宏观拓扑分析非常?有利。

6 结束语

针对复杂网络交叠团现象，本文给出了一个新的聚类后模糊分析框架。它不仅能对网络进行模糊聚类，而且支持对交叠结构的模糊分析，如关键点的识别和网络宏观拓扑图的提取。使用这些新方法、新指标能够深入挖掘潜藏于网络的拓扑信息。从本文的聚类后分析不难看出，网络模糊聚类的作用不仅在于聚类本身，还在于模糊聚类结果能够为网络拓扑深入分析和信息挖掘提供支持，而硬聚类则不能。今后将致力于对团间连接贡献度指标进行更为深入的统计研究。

参考文献

[1]

赵凤霞，谢福鼎.基于K-means聚类算法的复杂网络社团发现新方法[J].计算机应用研究，2009，26(6):2041-2043，2049.

[2]汪小帆，刘亚冰.复杂网络中的社团结构算法综述[J].电子科技大学学报，2009，38(5):537-543.

[3]NEWMAN M E J.Modularity and community structure in networks[J].Proceedings of the National Academy of Sciences of the United States of America，2006，103(23):8577-8582.

[4]WHITE S，SMYTH P.A spectral clustering approach to finding communities in graphs[C]//Proc of SIAM International Conference on Data Mining.2005.

[5]ENRIGHT A J，DONGEN S V，OUZOUNIS C A.An efficient algorithm for large-scale detection of protein families[J].Nucleic Acids Research，2002，30(7):1575-1584.

[6]BEZDEK J C.Pattern recognition with fuzzy objective function algorithms[M].New York:Plenum Press，1981.

[7]PALLA G，DERENYI I，FARKAS I，et al.Uncovering the overlapping community structures of complex networks in nature and society[J].Nature，2005，435(7043):814-818.

?[8]REICHARDT J，BORNHOLDT S.Detecting fuzzy community structures in complex networks with a potts model[J].Physical Review Letters，2004，93(21):218701.

?[9]NEPUSZ T，PETROCZI A，N?GYESSY L，et al.Fuzzy communities and the concept of bridgeness in complex networks[J].Physical Review E，2008，77(1):016107.

[10]ZHANG Shi-hua，WANG Rui-sheng，ZHANG Xiang-sun.Identification of overlapping community structure in complex networks using fuzzy C-means clustering[J].Physical Review A:Statistical Mechanics and Its Applications，2007，374(1):483-490.

[11]PAATERO P，TAPPER U.Positive matrix factorization:a non-negative factor model with optimal utilization of error estimates of data values[J].Environmetrics，1994，5(2):111-126.

[12]ANTTILA P，PAATERO P，TAPPER U，et al.Source identification of bulk wet deposition in Finland by positive matrix factorization[J].Atmospheric Environment，1995，29(14):1705-1718.

[13]KONDOR R I，LAFFERTY J.Diffusion kernels on graphs and other discrete structures[C]//Proc of the 19th International Conference on Machine Learning.San Francisco:Morgan Kaufmann，2002.

复杂网络分析篇（6）

关键词:网络模糊聚类;团—点相似度;团间连接紧密度;团间连接贡献度;对称非负矩阵分解;网络宏观拓扑

fuzzy clustering and information mining in complex networks

zhao kun,zhang shao-wu,pan quan

(school of automation, northwestern polytechnical university, xi’an 710072, china)

abstract:there is seldom a method which is capable of both clustering the network and analyzing the resulted overlapping communities. to solve this problem, this paper presented a novel fuzzy metric and a soft clustering algorithm. based on the novel metric, two topological fuzzy metric, which include clique-clique closeness degree and inter-clique connecting contribution degree, were devised and applied in the topological macro analysis and the extraction of key nodes in the overlapping communities. experimental results indicate that, as an attempt of analysis after clustering, the new indicators and mechanics can uncover new topology features hidden in the network.

key words:network fuzzy clustering; clique-node similarity; clique-clique closeness degree; inter-clique connection contribution degree; symmetrical nonnegative matrix factorization(s-nmf); network topology macrostructure

团结构是复杂网络普遍而又重要的拓扑属性之一,具有团内连接紧密、团间连接稀疏的特点。网络团结构提取是复杂网络分析中的一个基本步骤。揭示网络团结构的复杂网络聚类方法[1~5]对分析复杂网络拓扑结构、理解其功能、发现其隐含模式以及预测网络行为都具有十分重要的理论意义和广泛的应用前景。目前,大多数提取方法不考虑重叠网络团结构,但在多数网络应用中,重叠团结构更为普遍,也更具有实际意义。

现有的网络重叠团结构提取方法[6~10]多数只对团间模糊点进行初步分析,如nepusz等人[9,10]的模糊点提取。针对网络交叠团结构的深入拓扑分析,本文介绍一种新的团—点相似度模糊度量。由于含有确定的物理含意和更为丰富的拓扑信息,用这种模糊度量可进一步导出团与团的连接紧密程度,以及模糊节点对两团联系的贡献程度,并设计出新指标和定量关系来深度分析网络宏观拓扑连接模式和提取关键连接节点。本文在三个实际网络上作了实验分析,其结果表明,本方法所挖掘出的网络拓扑特征信息为网络的模糊聚类后分析提供了新的视角。

1 新模糊度量和最优化逼近方法

设a=[aij]n×n(aij≥0)为n点权重无向网络g(v,e)的邻接矩阵,y是由a产生的特征矩阵,表征点—点距离,yij>0。假设图g的n个节点划分到r个交叠团中,用非负r×n维矩阵w=[wki]r×n来表示团—点关系,wki为节点i与第k个团的关系紧密程度或相似度。w称为团—点相似度矩阵。令

mij=?rk=1wkiwkj(1)

若wki能精确反映点i与团k的紧密度,则mij可视为对点i、j间相似度yij的一个近似。所以可用矩阵w来重构y,视为用团—点相似度w对点—点相似度y的估计:

w ?twy(2)

用欧式距离构造如下目标函数:

minw≥0 f?g(y,w)=y-w ?tw?f=?12?ij[(y-w ?tw)。(y-w ?tw)]ij(3)

其中:•?f为欧氏距离;a。b表示矩阵a、b的hadamard 矩阵乘法。由此,模糊度量w的实现问题转换为一个最优化问题,即寻找合适的w使式(3)定义的目标函数达到最小值。

式(3)本质上是一种矩阵分解,被称为对称非负矩阵分解,或s-nmf (symmetrical non-negative matrix factorization)。?s-nmf的求解与非负矩阵分解nmf[11,12]的求解方法非常类似。非负矩阵分解将数据分解为两个非负矩阵的乘积,得到对原数据的简化描述,被广泛应用于各种数据分析领域。类似nmf的求解,s-nmf可视为加入限制条件(h=w)下的nmf。给出s-nmf的迭代式如下:

wk+1=w?k。[w?ky]/[w?kw ?t?kw?k](4)

其中:[a]/[b]为矩阵a和b的hadamard矩阵除法。

由于在nmf中引入了限制条件,s-nmf的解集是nmf的子集,即式(4)的迭代结果必落入nmf的稳定点集合中符合附加条件(h=w)的部分,由此决定s-nmf的收敛性。

在求解w之前还需要确定特征矩阵。本文选扩散核[13]为被逼近的特征矩阵。扩散核有明确的物理含义,它通过计算节点间的路径数给出任意两节点间的相似度,能描述网络节点间的大尺度范围关系,当两点间路径数增加时,其相似度也增大。扩散核矩阵被定义为

k=exp(-βl)(5)

其中:参数β用于控制相似度的扩散程度,本文取β=0.1;l是网络g的拉普拉斯矩阵:

lij=-aiji≠j

?kaiki=j(6)

作为相似度的特征矩阵应该是扩散核矩阵k的归一化?形式:

yij=kij/(kiikjj)??1/2(7)

基于扩散核的物理含义,团—点相似度w也具有了物理含义:团到点的路径数。实际上,w就是聚类结果,对其列归一化即可得模糊隶属度,需要硬聚类结果时,则选取某点所对应列中相似度值最大的团为最终所属团。

2 团—团关系度量

团—点相似度w使得定量刻画网络中的其他拓扑关系成为可能。正如w ?tw可被用来作为点与点的相似度的一个估计,同样可用w来估计团—团关系:

z=ww ?t(8)

其物理含义是团与团间的路径条数。很明显,z的非对角元zjk刻画团j与团k之间的紧密程度,或团间重叠度,对角元zjj则刻画团j的团内密度。?

以图1中的对称网络为例,二分团时算得

z=ww ?t=1.337 60.035 3

0.035 31.337 6

由于图1中的网络是对称网络,两团具有同样的拓扑连接模式,它们有相同的团内密度1.337 6,而团间重叠度为?0.035 3。

3 团间连接贡献度

zjk度量了团j与团k间的重叠程度:

zjk=?na=1wjawka(9)

其中:wjawka是这个总量来自于点a的分量。下面定义一个新指标来量化给定点对团间连接的贡献。假设点i是同时连接j、k两团的团间某点,定义点i对团j和团k的团间连接贡献度为

b?i=[(wjiwki)/(?na=1wjawka)]×100%(10)

显然,那些团间连接贡献大的点应处于网络中连接各团的关键位置,它们对团间连接的稳定性负主要责任。将这种在团与团间起关键连接作用的点称为关键连接点。为了设定合适的阈值来提取团间关键连接点,本文一律取b>10%的点为关键连接点。

4 实验与结果分析

下面将在三个实际网络上展开实验,首先根据指定分团个数计算出团—点相似度w,然后用w计算团—团关系和b值,并提取关键连接点。

4.1 海豚社会网

由lusseau等人[14]给出的瓶鼻海豚社会网来自对一个62个成员的瓶鼻海豚社会网络长达七年的观测,节点表示海豚,连线为对某两只海豚非偶然同时出现的记录。图2(a)中名为sn100 (点36)的海豚在一段时间内消失,导致这个海豚网络分裂为两部分。

使用s-nmf算法聚类,海豚网络分为两团时,除30和39两点外,其他点的分团结果与实际观测相同,如图2(a)所示。计算b值并根据阈值提取出的五个关键连接点:1、7、28、36、40(虚线圈内),它们对两团连接起到至关重要的作用。图2(b)为这五点的b值柱状图。该图显示,节点36(sn100)是五个关键连接点中b值最大者,对连接两团贡献最大。某种程度上,这个结果可以解释为什么海豚sn100的消失导致了整个网络最终分裂的影响。本例说明,s-nmf算法及团间连接贡献程度指标在分析、预测社会网络演化方面有着独具特色的作用。

4.2 santa fe 科学合作网

用本算法对newman等人提供的santa fe科学合作网络[15]加以测试。271个节点表示涵盖四个学术领域的学者,学者合作发表文章产生网络连接,构成了一个加权合作网络。将本算法用于网络中一个包含118个节点的最大孤立团,如图3(a)所示。

图3(a)中,四个学科所对应的主要组成部分都被正确地分离出来,mathematical ecology(灰菱形)和agent-based models(白方块)与文献[15]的结果一致,中间的大模块statistical physics又被细分为四个小块,以不同灰度区分。计算了24个点的团间连接度贡献值b,从中分离出11个b值大于10%的点作为关键连接点:1、2、4、6、11、12、20、47、50、56、57,其标号在横轴下方标出,见图3(b),并在图3(a)中用黑色圆圈标记,这些连接点对应那些具有多种学科兴趣、积极参与交叉研究的学者。除去这11个点时,整个网络的连接布局被完全破坏,见图3(a)下方灰色背景缩小图,可见关键连接点的确起到重要的沟通各模块的作用。

4.3 杂志索引网络

在rosvall等人[16]建立的2004年杂志索引网络上进行测试。网络节点代表杂志,分为物理学(方形)、化学(方形)、生物学(菱形)、生态学(三角形)四个学科领域,每个学科中各选10份影响因子最高的刊物,共40个节点,若某刊物文章引用了另一刊物文章,则两刊间有一条连线,形成189条连接。使用s-nmf对该网4分团时,聚类结果与实际分团情况完全一致,如图4(a)所示。

由本算法得出的团—点相似度w在网络宏观拓扑结构的挖掘方面有非常有趣的应用,如第2章所述,用w计算团—团相似度矩阵z=ww?t,其对角元是团内连接密度,非对角元表征团与团的连接紧密程度,故z可被视为对原网络的一种“压缩表示”。如果将团换成“点”,将团与团之间的连接换成“边”,利用z的非对角元,就能构造出原网络的一个压缩投影网络,如图4(b)所示。这是原网络的一个降维示意图,也是团与团之间关系定量刻画的形象表述,定量地反映了原网络在特定分团数下的“宏观(全局)拓扑轮廓”,图上团间连线色深和粗细表示连接紧密程度。由图4(b)可以看到,physics和chemistry连接最紧密,而chemistry与biology和biology与?ecology次之。由此推测,如果减少分团数,将相邻两团合并,连接最紧密的两团必首先合并为一个团。实际情况正是如此:分团数为3时,biology和ecology各自独立成团,physics 和?chemistry合并为一个大团,这与文献[11]结果一致。

5 讨论

网络模糊聚类能帮助研究者进一步对团间的一些特殊点进行定量分析,如nepusz等人[9]用一种桥值公式来刻画节点在多个团间的共享程度,即节点从属度的模糊程度。而本文的团间连接贡献度b反映出节点在团间连接中所起的作用大小。本质上它们是完全不同的两种概念,同时它们也都是网络模糊分析中所特有的。团间连接贡献度指标的提出,将研究引向对节点在网络宏观拓扑模式中的影响力的关注,是本方法的一个独特贡献。无疑,关键连接点对团间连接的稳定性起到很大作用,如果要迅速切断团间联系,改变网络的宏观拓扑格局,首先攻击关键连接点(如海豚网中的sd100)是最有效的方法。团间连接贡献度这一定义的基础来自于对团与团连接关系(z)的定量刻画,这个定量关系用以往的模糊隶属度概念无法得到。由于w有明确的物理含义,使得由w导出的团—团关系z也具有了物理含义,这对网络的宏观拓扑分析非常?有利。

6 结束语

针对复杂网络交叠团现象,本文给出了一个新的聚类后模糊分析框架。它不仅能对网络进行模糊聚类,而且支持对交叠结构的模糊分析,如关键点的识别和网络宏观拓扑图的提取。使用这些新方法、新指标能够深入挖掘潜藏于网络的拓扑信息。从本文的聚类后分析不难看出,网络模糊聚类的作用不仅在于聚类本身,还在于模糊聚类结果能够为网络拓扑深入分析和信息挖掘提供支持,而硬聚类则不能。今后将致力于对团间连接贡献度指标进行更为深入的统计研究。

参考文献:

[1]

赵凤霞,谢福鼎.基于k-means聚类算法的复杂网络社团发现新方法[j].计算机应用研究,2009,26(6):2041-2043,2049.

[2]汪小帆,刘亚冰.复杂网络中的社团结构算法综述[j].电子科技大学学报,2009,38(5):537-543.

[3]newman m e j.modularity and community structure in networks[j].proceedings of the national academy of sciences of the united states of america,2006,103(23):8577-8582.

[4]white s,smyth p.a spectral clustering approach to finding communities in graphs[c]//proc of siam international conference on data mining.2005.

[5]enright a j,dongen s v,ouzounis c a.an efficient algorithm for large-scale detection of protein families[j].nucleic acids research,2002,30(7):1575-1584.

[6]bezdek j c.pattern recognition with fuzzy objective function algorithms[m].new york:plenum press,1981.

[7]palla g,derenyi i,farkas i,et al.uncovering the overlapping community structures of complex networks in nature and society[j].nature,2005,435(7043):814-818.

?[8]reichardt j,bornholdt s.detecting fuzzy community structures in complex networks with a potts model[j].physical review letters,2004,93(21):218701.

?[9]nepusz t,petroczi a,n?gyessy l,et al.fuzzy communities and the concept of bridgeness in complex networks[j].physical review e,2008,77(1):016107.

[10]zhang shi-hua,wang rui-sheng,zhang xiang-sun.identification of overlapping community structure in complex networks using fuzzy c-means clustering[j].physical review a:statistical mechanics and its applications,2007,374(1):483-490.

[11]paatero p,tapper u.positive matrix factorization:a non-negative factor model with optimal utilization of error estimates of data values[j].environmetrics,1994,5(2):111-126.

[12]anttila p,paatero p,tapper u,et al.source identification of bulk wet deposition in finland by positive matrix factorization[j].atmospheric environment,1995,29(14):1705-1718.

[13]kondor r i,lafferty j.diffusion kernels on graphs and other discrete structures[c]//proc of the 19th international conference on machine learning.san francisco:morgan kaufmann,2002.

复杂网络分析篇（7）

在Internet中，新增加的服务器在进行选择连接时不仅要考虑当时网络的繁忙情况（网络的流量）以及节点的处理能力（点权），还要考虑到与服务器所在地区的物理距离，为此提出了一种基于流量和距离的Internet加权网络结构。在Internet网络中，每台服务器都看作是一个节点，服务器之间的流量看作是边权。在Internet中，不断有新的服务器加入的同时，增加一些新的连接，提高节点的服务能力。基于这些情况，笔者给出了一个Internet 网络演化模型。网络模型的构建过程如下：

1.初始设定

网络为给定no个节点，e0条边的网络，初始的e0条边没有重连。其中每条边的权值为wo。

2.增长过程

每一步向网络中增加一个节点k以及m（≤no）条新边。

3.偏好连接

连接节点的选择按照如下的偏好选择规则进行。

这里 ； ，α是一个参数；τ（i）表示的是节点i的邻居的集合；距离L（u,v）用Kleinberg网络模型中的网格距离 来定义。依据“就近原则”，选择距离新增节点k较近的节点进行连接的可能较大。随着α值的增加，新产生的节点与较近的节点之间相连的概率就会越来越大。设新生成边的边权固定为w0。

4．边权值的动态演化

每个时间步网络中各节点的强度与边权值动态演化特征与BBV模型的边权值动态演化特征一致。节点 增加一条新连接后，节点与其邻居连边的权重受到影响，权值变化为：

重复以上过程，直到网络达到要求的规模。

二、基于复杂网络的Internet流量分析

1.FDM模型与BBV模型比较

按照FDM模型的生成方法，选择初始参数mo=eo=10，生成1000个节点的网络模型。选取50个具有较大度的节点作为模型中的中心节点，其余节点作为普通节点。每一次产生N=500个数据包，这些数据包的源节点和目标节点都在普通节点中随机选取，且保证源节点和目标节点不同。数据包允许在网络中传递的最大步数为T，循环产生10次不同的随机数据包，并将Dt的结果取平均后作为网络中数据流量变化的指标。

首先，假设网络中的每一个节点都具有任意的容量和处理速度，即每个节点队列都可以存储所有到达的数据包且可以一次处理完所有的数据包。从中可以知道，就整体而言，模型FDM中的丢包率要明显低于BBV中的丢包率。在BBV模型中，当T=4时，Dt；在FDM模型中，根据仿真结果表明，在T=4时，Dt=0.0020。与上面的数据相比，有大约3%的数据包将不能到达目标节点而被丢弃，这将直接影响到网络的数据包。这表明，在新模型FDM中数据传递比在BBV模型中更流畅。

2.节点的容量和处理速度对网络丢包率的影响

假设Internet网络中路由器的容量和处理速度都是有限制的，所以，在下面的仿真中给节点赋予了特定的值。

复杂网络分析篇（8）

［摘要］传统股票板块的划分缺乏精确的逻辑推理和数理分析。本文基于复杂网络和社团理论，通过构建数量模型，选取时间序列数据对股票与股票之间的相关性进行分析，依据相关性大小对股票进行板块的划分，并依据划分结果，为投资者提供政策建议和技术支持。

［

关键词 ］股票；相关性；复杂网络；GN算法

［DOI］10.13939/j.cnki.zgsc.2015.22.042

1引言

股票间的相关性对于风险管理、投资决策具有重要影响。对于股票相关性的研究，现代金融理论主要基于经济基本面进行解释，即认为相关性来源于影响资产现金流和影响资产折现率的基本面因素。已有研究表明，股票间相关程度远超出了经济基本面因素的影响，股票市场作为复杂系统日益受到人们的关注。近年来，经济、数学、社会等领域的学者都开始用复杂网络及其相关概念来研究股票市场，进而研究股票间相关性。

2股票间的相关性

研究股票间的相关性对股民来说至关重要。现随机选取沪市A股、沪市B股、深市A股、深市B股、创业板这五类市场中各20只股票在2013年1月1日至2013年8月31日的周开盘价、收盘价和周个股回报率作为量化指标，进行相关性分析。

2.1单个指标的相关系数

选取周开盘价，周收盘价与考虑现金红利再投资的周个股回报率，并用k=1，2，3表示。

Ai（k）表示股票代码为i，指标为k的时间序列矩阵

设随机变量Ai（k）与Aj（k），则协方差为：

Cov（Ai（k），Aj（k））=E（Ai（k）-EAi（k））E（Aj（k）-EAj（k））

相关系数为：

2.2指标权重的设立——变异系数法

2.3综合指标的相关系数

设运用股票i与股票j之间的综合相关系数值为

2.4模型的求解

对原题附件中数据进行处理，依据五类不同的股票市场，依次随机选取20只股票在2013年1月至2013年9月共36周内的周开盘价、收盘价和考虑现金红利再投资的周个股回报率数据。基于模型Ⅱ，运用Matlab编程求解，见表1。

3股票板块的划分

股票板块的划分存在很多依据，常见的有按地域、按行业、按概念等，但这些都是从定性的角度去考察股票与股票内在联系，而通过相关性构建的股票网络，能依据股票与股票间时间序列数据的相关性，从定量角度去划分股票板块。这样的量化处理使得板块内部的波动性更加一致，更利于我们的投资决策。

3.1股票相关性网络模型

①相关系数构成。网络的节点代表股票，边代表股票之间的相关性。任意两只股票i和j的综合相关系数为：

其中i和j代表股票代码，ρij的取值范围为-1，1。若ρij=-1，则表示两只股票完全负先关；若ρij=1，则表示两只股票完全正相关。

②阈值的设定。股票代表网络中的点，如果相关系数ρij≥θ（θ∈-1，1），就认为节点i和j之间有连边，这里的θ即阈值点。通过计算对比得知，当θ=0.05时其到达最佳阈值，股票网络的拓扑性质最稳定，更有利于对股票网络的研究。

③社团结构的构建。由模块度评价函数来衡量社团结构划分好坏，将其推广至加权的模块度评价函数Q定义为：

3.2股票板块划分

（1）基本分块情况。依据社团结构理论，结合GN算法和NetDrew绘图软件见图1。

由图1可知，图像在经过重新排列后，明显呈现出四个板块，说明在这四大板块中，板块内的股票在长期的波动趋势与波动幅度具有较高的一致性。图1的股票来源为沪市A股、沪市B股、深市A股、深市B股、创业板这五类市场中各随机选取的20只股票共100只股票，范围覆盖了中国内地全部股票市场，具有较高的准确性。

（2）找寻关键节点。为了更方便寻找最关键节点，运用Ucinet软件对图形进行处理如图2所示。

每个模块的内部相关性程度很高，那么选取每个模块中最重要节点，用它的性质来近似描述该模块的整体性质。通过软件处理后，使得节点的重要程度与图形的大小成反比，这样更易比较，也更易选出最关键的节点。

依据此，分别取900930（沪普天B）、300120（华测检测）、900951（*ST大化B）002630（华西能源）这四只股票代表图2正上方，左方，正下方，右方区域。

（3）关键节点股票单个股分析。图2区域正上方的板块选取股票900930（沪普天B），观察其2013年1月至9月的周开盘价走势，其一直处在0.6元上下波动，说明其已为成熟期股票，特点为股价稳定，波动幅度小，发展前景较弱。依据此，对图2正上方区域股票归类为成熟板块股票。

图2区域左方的板块选取股票300012（华测检测），观测其走势，其2013年1月至9月的周开盘价曲线，其上涨幅度较快，在第17周的骤降是因为上市公司因为股价

过高或想要再融资，进行增资扩股的情况而非下跌。在短短的几个月内，其股价从第18周的10元附近上涨到15元附近，是一只处于上升期的股票，说明其为成长期的股票，特点为股价不稳定，波动幅度大，发展前景较强。依据此，对图2正上方区域股票归类为成长板块股票。

图2区域正下方的板块选取股票900951（*ST大化B），观测其2013年1月至9月的周开盘价曲走势，其波动幅度一般，股票价格持续低位，在第一周到第八周小幅上涨后，连续几十周的持续下跌，且通过查询股票代码发现其中文名称前标记着*ST，意味着此股票有即将下市的风险，警告投资者谨慎投资。所以这是一直处于衰落期的股票，特征为股票价格低，下跌趋势强，波动程度较大。依据此，对图2正下方区域股票归类为衰落板块股票。

图2区域右方的板块选取股票002630（华西能源），观测其2013年1月至9月的周开盘价曲线走势，其整体趋势是上升的，但上升的比例较小，而且不断波动，在一个个涨跌幅中前进，明显是一只处于萌芽期的股票，其特点为股价不稳定，波动幅度大，处于大幅度震荡上涨的趋势。依据此，对图2右方区域股票归类为萌芽板块股票。

4结论分析与投资建议

现实中的板块划分主要分为两类，一类是地域板块，按照上市公司的所在地划分股票；一类是概念板块，如金融与银行业、化工业等；同时也会有依据股票的表现划分为蓝筹股、垃圾股等。而上述划分是依据时间序列数据的相关性程度划分的，与现实的板块划分有相同也有不同的地方。

相同点：与主流的两类划分的依据相同，其划分主要依据都是因为这类股票有着很强的相关性，在整体系统性风险一定的情况下，局部的系统性风险类似，如银行与金融板块，当央行上调法定存款准备金率时，其板块的股票整体呈下降趋势。

不同点：本文的股票网络模型比较接近与现实生活中的依据股票表现划分的类型，但这不是主流的划分，与按照概念划分和地域划分的板块在度量相关性的指标上有一定的差距。

一是多样化选股。投资股票种类多样化，板块多样化根据社团结构的股票网络图知，当购买股票时，切勿全部购买相同板块的股票，要综合考虑，分散风险。相同板块的股票相关程度高，波动的趋势相同，从一方面来看，若全部购买同一类型股票，将会使板块的非系统性无法避免，提高投资的风险率；从另一方面来看，虽然同一板块股票上涨具有传递效应，但其效应大小远远小于下跌时的连带效应，及时此板块的某些股票暴涨也不一定能带动整个板块所有股票上涨。所以，即使是风险偏好者也应慎重考虑。

二是综合投资与投机，确保利益最大化。作为投资者，在股票市场的最终目的是利益最大化。那么在选股时，不仅要考虑短线低买高卖的投机操作，也要有长期持仓的投资计划。对于投机类股票，结合板块分析可知，应选取处于萌芽期或成长期的股票，这些股票的波动性大，只要能把握好趋势，在短线操作的收益率较高。对于那些风险偏好更高的投资者来说，可以考虑处于衰落期的股票。这类股票，一旦有公司借壳上市，其市值会翻倍的增长；对于投资类股票，可以选取成熟类板块的股票，这类股票波动程度小，股盘大，价格相对稳定，每年会有固定的分红股利，这类股票适合长线持有。

三是选股重看基本面。股票的基本面的好坏是一只股票有没有操盘意义的前提，一般的我们通过分析其每股净收益，单日成交量等基本财务指标来判断其基本面情况。如果一只股票的基本面不好，再多的技术分析也只是空中楼阁。所以对于选股来说，先看基本面，再看技术指标。

四是把握宏观经济基本面，紧跟时事动态。在尚不完善的中国股票市场，投机和跟风是市场普遍的特点。拥有敏锐的宏观经济嗅觉，能够更好地提高投资者对所持股票的掌控度，更有利于投资者资本收益最大化的实现。

引用一句股票市场最流行的一句话，股市有风险，入市需谨慎，在进行投资决策前，一定要量力而行，切忌盲目盲从，要理性判断，做出最优的理财规划，让你和你爱的人过上更加幸福美好的生活。

参考文献：

［1］ 康桥，田新民.沪市主板与深市创业板相关性研究及实证分析［J］.中国市场，2014（36）.

复杂网络分析篇（9）

1.前言

金融系统作为现代化经济发展的重要核心，而银行系统作为金融系统的重要组成部分，对金融系统稳定运行起着关键性作用。当银行爆发危机时，若不能妥善处理，将传染给其他银行，从而使银行系统安全运行受到严重影响，甚至引发货币危机。同时银行危机嫩能够跨国传染，进而引发全球性金融危机。因此，如果防止银行危机的扩散，使银行系统得到有效恢复，成为现阶段研究的重要课题。

2.银行危机传染含义与形式

2.1传染含义

从广义角度来看，银行危机传染主要是指跨国国界性的传播效应或者溢出效应。从狭义角度来看，银行危机传染含义主要分为三点：其一，银行危机传染主要指某个国家出现爆发性危机时，会导致其他国家也可能爆发危机的一种现象；其二，银行危机传染主要是处于危机状态的国家出现溢出效应，并对其他国家银行、金融业造成影响的一个过程；其三，银行危机传染主要是指某个金融市场爆发危机，并影响到其他金融市场交易量及价格，并产生联合波动效应。

2.2传染性形式

2.2.1内部传染形式

主要指当某个银行失去清偿能力时，将爆发清偿危机，并通过银行与银行间的往来业务将危机传染到其他银行。内部传染形式主要有：其一，信息路径。当信息失真或者不对称时，银行责权者将难以对银行经营情况进行识别，在银行危机爆发时，受到外部信息影响，导致存款者与银行间出现挤兑，并扩大危机传染范围。其二，信用路径。随着银行与银行间往来业务与交易量不断增加，银行与银行间形成的在全关系，不仅不能抵押，也无任何保险，当某个银行爆发危机时，容易引发连锁反应，进而扩散至与其往来的银行。其三，支付清算。随着支付清算系统在银行中的应用，虽然加快了资金清算效率，但是也扩大了危机传染范围。某家银行爆发危机时，若无法清偿债务，将产生连锁反应，不仅影响到银行支付清算工作，同时导致银行出现信任危机[1]。

2.2.2外部传染形式

主要指企业与银行间存在业务往来，从而受到银行危机的影响，并将危机传染给其他社会经济部门。外部传染形式主要有：其一，企业传染路径。当银行爆发危机时，首先会将危机传染给企业，然后再由企业将危机传染至与企业有业务往来的银行，从而引发大范围的银行危机。当银行爆发严重性危机时，受到危机传染的银行，由于将危机传染至其他企业，导致企业面临生存危机，而银行危机传染范围也日益扩大。其二，跨国传染路径。将国家银行作为独立系统，由于我国银行与其他国家银行存在业务往来，所以当某个国家银行爆发危机时，危机也将传染至我国银行，甚至引发全球性的金融危机[2]。

3.银行危机传染应对措施

3.1银行网络宏微观环境优化策略

首先，同业存款的调整。通过对银行危机爆发原因进行分析发现，同业存款存在比例问题，同业存款处于最优状态时，其比例与经济环境密切相关。所以，为了确保银行系统稳定运行，必须对同业存款进行有效调整，以提高资金效率，确保银行系统稳定性。其次，规范投资行为。通过对股市案件进行分析发现，投资行为缺乏规范性，是引发金融风险的重要因素。而资本市场发展与金融业密切相关，若资本市场发生动荡，将严重影响到银行系统的安全运行。所以，规范投资行为，对银行危机阻断具有重要意义。再者，加大信息披露力度。由于信息失真或者不对称，给金融市场带来很大的冲击，同时信息可作为危机传染渠道，扩大危机范围。所以，加大信息披露力度，确保信息准确性，是确保金融系统稳定运行，化解银行系统危机的关键。

3.2确保银行系统的稳定性

首先，优化网络结构，保证网络稳定运行。在复杂网络条件下，对银行危机进行深入分析，以掌握网络结构，针对不同网络危机情况，采取针对性的应对措施，以实现银行网络自治化管理，改善银行网络管理机制，确保银行网络系统安全运行。其次，充分节点作用，缩小危机范围。银行网络中有很多大节点，是危机传染重要因素。因此，通过对银行网络节点进行适当调整，以优化银行负债结构，增强银行的风险抵抗能力。

3.3做好危机公关工作

首先，掌握舆论的主导权。当银行爆发危机时，必须通过媒体将银行真实情况及时披露出来，并向人们传达积极性的信息，以避免危机严重化。其次，保证披露信息真实性。当银行出现危机时，使公众内心受到很大冲击，这时银行必须实事求是，确保披露信息的真实性，以阻断谣言。再者，沟通路径要通畅。银行必须与债权者、投资人、重要组织、内部人员及受害者等进行积极沟通。最后，全面做好危机评估工作。当银行爆发危机时，必须对危机实际情况进行准确评估，以避免危机严重化。同时政府机构及监管部门，必须积极介入，以确保信息的准确性，提高公众信任度。（作者单位：灵武市农业银行）

复杂网络分析篇（10）

中图分类号：TP302

文献标识码：A 文章编号文章编号：16727800（2013）007002303

0 引言

具有自组织、自相似、吸引子、小世界、无标度中部分或全部性质的网络称为复杂网络[1]。自然界与社会生活中众多复杂系统都可用复杂网络来描述。近年来，关于复杂网络的研究正处于蓬勃发展阶段，其中复杂网络的传输能力与人们的工作生活关系密切，在现代社会中占据了非常重要的地位。因此，发生在复杂网络拓扑之上的各种动力学过程，如改善复杂网络路由效率以提高网络容量等问题，越来越多地受到统计物理学界和工程界的关注[1]。

1 相关研究

随着网络规模和信息量的大幅增加，拥塞现象成为现实网络中常见的动态特性之一。许多实际网络，如因特网、交通网络等经常发生拥塞，由此导致网络整体性能下降，甚至瘫痪。导致网络拥塞的主要原因有两方面：一是网络中传输的大量数据流（特别是并发数据）；二是网络本身的特性，包括节点容量、节点转发数据包能力、网络拓扑结构、通信链路带宽等。

目前，学者们通常用3种方式缓解网络拥塞的问题：一是使用特定的网络拓扑结构；二是提高单个节点转发数据包的能力；三是改进路由策略。第一种方法需要改变现有的拓扑结构，和第二种方法一样都存在成本高、资源浪费等问题。当网络规模较大时这些改变较难实现，单靠升级硬件能带来的改善效果也有限。因此，许多研究人员在改进复杂网络路由策略方面做出了很多有影响力的工作[1]。

广度优先[2]和随机游走[3]是复杂网络中最简单的路由策略，但它们没有考虑网络的拓扑结构，随着网络规模的扩大，网络中会产生大量的重复数据包，从而导致网络拥塞。因此，尽管它们在路由效率的理论分析中被广泛采用，在实际中却难以应用。目前，现实网络中的路由算法多采用基于最短路径路由算法[4]，但该算法要求所有节点都知道全局信息，只考虑了网络结构属性而忽略了网络中负载的动态特性。另外，上述研究都基于一种假设，即复杂网络的结构是单层的，所有节点在处理数据包能力等方面一致且每个节点等待队列的长度无限。但实际通信网络中，这些假设很难成立，需要依照实际设计综合考虑网络拓扑和负载动态等问题的更优化的路由策略[5]。另外，在网络的动态演进过程中，由于网络规模大，要每个节点都知道全局信息并不现实。因此，基于局部信息比基于全局信息的动态路由策略更易于部署实施。

在综合考虑网络中节点处理能力、空闲队列长度、聚类性、度等网络拓扑和动态负载参数的基础上，引入层次分析法[6]建模，提出了复杂网络中基于层次分析法的路由策略（Routing Strategy in Complex Network based on Analytic Hierarchy Process，简称RSAHP）。算法利用若干权重因子的组合来选取下一跳转发节点，其中权重因子的组合综合地反映了网络的拓扑属性和动态负载等当前状态。理论分析和实验证明，RSAHP具有如下良好性质：①分布式的网络路由策略在实际网络中易于实现；②具有自适应性，每个接收到数据包的节点在系统的观点下综合判断、决定下一跳转发点，通过合理选择下一跳有效地提高网络通信能力。理论分析和仿真实验表明，RSAHP比最短路径算法更能有效避免拥塞，并能进一步增强复杂网络的网络容量。

造成上述问题的主要原因是SPRS只考虑了网络拓扑结构属性而没有考虑网络中负载的动态特性，要传送的数据包也无法选择其它的路由路径，当最短路径中的节点发生拥塞时，SPRS会使拥塞节点更拥塞，从而进一步降低网络性能，甚至加速网络崩溃。而RSAHP在综合考虑网络中节点处理能力、空闲队列长度、聚类性、度等网络拓扑和动态负载参数的基础上，利用若干权重因子的组合来选取下一跳转发节点，综合地反映了网络的拓扑结构属性和动态负载等当前状态。理论分析和仿真实验表明，RSAHP比SPRS更适合大规模网络，更能有效避免拥塞，并进一步增加了复杂网络的网络容量。

参考文献：

[1] 臧海娟，任彦，薛小平等.复杂网络环境下的路由方法研究[J].计算机应用，2010（8）.

[2] SHARMA G，MAZUMDAR R R. Hybrid sensor networks： a small world[C].Proceedings of 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing， 2005.

[3] 席峰. 基于复杂网络理论的无线传感器网络地理路由和信息融合.[D].南京：南京理工大学，2010.