关键词：复杂网络；城市交通网络；Hub节点
中图分类号：TP316.8 文献标识码：A 文章编号：1672-7800（2013）005-0070-02
0、引言
随着当今社会科学的不断发展和进步，各学科的发展都需要与周围的众多学科产生关系，因此复杂性学科应运而生。复杂性学科的引入能够更加充分、全面地对事物进行研究。复杂性学科是系统学科和非线性学科相结合的产物，其不仅具有两者身上的优点，更是对两者的补充和发展，因此复杂性学科已经成为了现代科学研究中最有效和常用的研究领域。而在上世纪末小世界效应和无标度特性的发现，为人们提供了一个新的研究复杂性学科的角度，让复杂网络在更多的领域里得到了应用，并取得了不错的效果。随着城市的不断发展，城市交通网络也成为了越来越重要的问题。近年来，复杂网络在城市交通网络领域中的不断应用，大大提高了城市交通网络的分析准度率和效率，也让人们看到了复杂网络在城市交通网络应用的光明前景。
1、复杂网络在城市交通网络分析中应用的可行性
关于复杂网络在城市交通网络中的应用，各方观点不一，很多人认为由于城市交通规模不足，城市交通网络的研究条件距离复杂网络研究还有很大差距，复杂网络不能够准确地在城市交通网络分析中进行应用。而另一些人则认为，随着城市交通网络的不断发展，城市交通网络已经成为了一个复杂的、庞大的网络系统，因此在某些研究上能够完全遵循复杂网络的研究方向。虽然城市交通网络在很多方面还不能完全符合复杂网络的研究标准，但是在很多方面具有较大的相似性，并且相关实验数据也能够证实复杂网络所描述的城市交通网络与实际相符，因此复杂网络能够在城市交通系统中应用。
在笔者看来，复杂网络在城市交通网络上的应用是可行的，主要因为以下3点内容：
（1）虽然城市交通网络在某些方面具有规则网络的某些特征，因此具有拓扑统计的相关性质。但在研究城市交通问题时可以对简单的拓扑进行抽象研究，这样就能够将城市交通网络中复杂的拓扑现象展现出来，从而反应出城市交通网络其它方面的重要特征。
（2）由于城市交通在不断地流动和变化过程中，因此在特征上具有明显的复杂性。例如：在每个路口处，即复杂网络中的每个节点处，都会有不同的变化，这些变化并不能确定其变化的方向，因此能够采用复杂网络对其进行研究。
（3）在交通网络的不断演变过程中，拓扑在交通网络上的应用对交通网络的分布和发展起到了重要的推动作用，因此将复杂网络应用在城市交通中对城市交通意义重大，符合城市网络交通的发展规律。
2、复杂网络在城市交通系统中的相关应用
2.1 复杂网络对城市交通网络的描述
由于城市内部交通复杂，交通模式不同，因此在复杂网络上会产生很大的不同。当今社会发展迅速，交通网络也随着社会的发展而不断变化，在交通网络的变化过程中，受到了包括地理、经济、规划等多种因素的影响，而复杂网络对于这些复杂因素的问题有着极强的处理能力。在研究城市交通网络时，只需要将城市网络抽象成复杂网络，然后对其进行研究。一般理论上对城市交通的抽象方法有两种：第一种是原始法，只需要简单地将交叉路口视为节点，并将连接这些节点的马路当做边，这种方法较为直观，容易理解；而第二种方法和第一种完全相反，其将交叉路口当作边，而把连接的马路当作节点，这样的方式虽然不直白，但在很多研究中有着第一种方法所没有的好处。
2.2 研究中面临的问题
目前，复杂网络理论已经在多个领域内取得了不错的发展，但是在城市交通网络上并没有太长时间的研究，在与城市交通网络的融合和描述上还有出入。但随着复杂网络在城市交通网络中的不断运用，会有更多的相关研究成果，这样能够促进两者更好地融合，从而为城市交通网络的发展做出更大的贡献。笔者分别从网络实证研究和网络演化机制两个方面来对城市交通网络复杂性进行阐述。
2.2.1 网络实证研究
网络实证研究能够有效地确定每个参数的基本意义，对一些忽略的系统宏观性质进行探寻。从目前的情况来看，网络的实证研究主要在于城市的网络道路建设和城市的公共交通网络建设。
（1）城市的网络道路。有关城市的网络道路建设早在十多年前就进行了研究，科学家通过对不同国家城市道路网络的研究得出，一般的道路交通量服从幂律分布，并且通过进一步研究发现，这些研究中的城市网络均为无标度网络，这就体现出了复杂网络中小世界的特征。
（2）城市的公共交通网络。相比于城市的道路交通网络，城市的公共交通网络的数据更加准确，研究起来也相对简单。根据中国相关城市的公共交通网络进行分析，公共汽车网络的分布呈指数分布。在此基础上对公共汽车网络的演化过程进行了模拟，结果与理论符合情况良好。此外，据国外文献记载，在对国外众多城市的公共交通网络进行研究后可以看到，这些网络都存在小世界的特性，城市交通网络均符合幂律分布或指数分布。上文已经介绍了城市交通网络的描述方法及一些常用的统计参数，但仅有这些还不够，还需要寻找更好的描述方法和更为有效的统计参数来刻画、分析城市交通网络的复杂性。
2.2.2 网络演化机制
网络演化机制研究是探索具有特定统计性质的网络形成机理的重要手段，主要涉及网络演化中的5类事件：加点、加边、重连、去边、去点。此后，涌现了大量关于网络演化机制的研究，为发现复杂网络形成机理以及进一步研究复杂网络上的动力学行为奠定了坚实的基础。就城市交通网络而言，主要研究网络无标度性和流量集中性两个方面。
（1）网络无标度性。目前，对无标度网络的演化机制研究主要集中在优先连接和Hub节点形成这两个方面，这些研究大多是对抽象的网络进行研究，而对于实体城市交通网络的研究并不常见。文献通过建立模型将优先连接和距离选择联系起来，从而搭建了无标度性与空间网络的桥梁。文献提出了一种基于预期效用最大的加点模型，并深入分析了地理信息的引入对网络度分布、聚类系数和匹配方式的影响。此外，对于无标度网络的演化机制研究，文献的部分研究结果也可借鉴。
（2）流量集中性。对城市交通网络的实证分析发现，小部分的主干路承担了路网中大部分的交通量，文献在进行了大量路网演化模拟实验后指出，交通网络中道路等级的涌现是路网本身固有的性质。这一发现打破了交通网络研究的传统观念，同时也带来了一系列疑问，如：是什么原因导致了交通网络道路等级的涌现？对于一个特定的城市交通网络而言，是否存在特定时期内的最优等级结构？这些问题还有待进一步研究。相信通过不断的实验与实践，这些疑问会逐步得到解决，这样复杂网络就能够在城市交通网络的建设中起到更重要的作用。
关键词：复杂网络理论;网络拓扑;应用分析;计算机网络
一、引言
随着计算机网络的飞速发展，传统的网络模型已经很难对计算机网络拓扑特性做出客观的描述和研究。针对这个现象，复杂网络理论的产生和应用，为计算机网络的拓扑发展带来了新的平台和思路。对于复杂网络理论在计算机网络拓扑中的分析已经成为计算机网络领域研究的重要课题。
二、复杂网络和计算机网络拓扑的基本理论
（一）复杂网络理论的含义及其复杂性
复杂网络是指具有内部相似、自行组织、吸引因子、小区域、无标度中的一部分或者全部的网络。其复杂性主要体现在以下六个方面：①结构的复杂性，表现在网络的节点数量较大。②节点的多样性，网络中的所有组成部分，代表的各种事物均为复杂网络理论中的节点。③连接的多样性，指的是网络中节点的连接方式不一致。④动力学的复杂性，指的是节点之间的复杂性，能够产生多样的结构特征。⑤网络结构的变化性，指的是网络节点之间消失和连接产生就像网页随时断开和连接一样，使得网络结构不断的发生变化。⑥多重复杂性的融合，指的是上述所有复杂性的结合表现出的复杂性。此外，复杂网络理论有小世界、集团集聚程度更加密集和幂律的度及介数涵盖的范围不断扩大等三种特性。
（二）计算机网络拓扑技术及分类
计算机网络拓扑最早是由瑞士数学家欧拉在1736年提出的，主要是用于连接计算机网络和传输不同设备之间数据的一种方式。不同的网络设计要选择适合的网络拓扑方式，在网络拓扑结构中，拓扑技术是以图像的方式来表示多种设备之间的相互关系。计算机网络拓扑的主要类型有星行结构、环形结构、总线型结构、混合拓扑结构、分布式结构等。由于计算机的分布和数据传输电缆的布置存在很大的差异性，每一种网络拓扑结构都有其相应的优缺点，因此在计算机网络拓扑形式的使用上，要具体问题具体分析。
三、复杂网络理论在计算机网络拓扑中的具体应用分析
（一）计算机网络的同步行为现象分析
这主要是指计算机各个网络节点之间的同步行为，在复杂网络理论中，网络节点之间的同步是较为常见的一种现象，主要是受网络拓扑和各节点之间的动力学性质决定的。但是值得注意的是，这种同步行为并不都是有益的，如由多个路由器发出路由信息的网络，其同步行为包括了发出同一种路由信息和同时不发送信息，这就很有可能会使得网络出现拥挤或者瘫痪的现象。从计算机网络技术的发展来看，人们采取避免计算机网络出现同步行为的措施并没能完全奏效，经常会出现一种同步行为结束，另一种同步行为又产生的现象。因此，如何有效杜绝计算机网络的同步行为现象仍然是人们研究的课题。
（二）计算机网络拓扑行为的演化模型
计算机网络拓扑行为的演化模型由复杂网络演化模型逐步转变为了局部演化模型，这两种演化模型都是从路由器和自治域两个不同的层次来描述计算机网络的拓扑结构的。从路由器上看，各个路由器相当于各个网络节点，而路由器之间的物理连接相当于边。从自治域上看，在边界网关协议的基础上，如果两个自治域之间对等连接的话，就说明这两个节点之间是有一条边相连的。复杂网络演化模型演化出的结果很大程度上出现“富者更富，穷着更穷”的现象，即那些新加入的用户会倾向于那些品牌好、质量好、连接数量多的网络服务商。该模型遵循的“偏好连接”原则是基于整个网络上的，与优先考虑连接到本地区的服务器或路由器的实际不符。而局部演化模型的偏好连接倾向性是在局部信息的基础上形成的，一定程度上克服了复杂网络演化模型的缺陷。
（三）计算机网络脆弱性和鲁棒性的动力学模型
1.计算机网络的鲁棒性。计算机网络的原始功能是保证军事资料的安全性，这样的保证就是所谓的鲁棒性。鲁棒性是指在计算机网络中的某个区域或节点中出现问题或故障时，不会扩散到整个计算机网络系统，计算机还能保持正常的运行。相关研究表明，一般在一个网络系统中，只要有百分之二十左右的正常区域和政策阶段就能够保障计算机网络的正常运行。
2.计算机网络的脆弱性。虽然计算机网络有鲁棒性的动力学模型，但是一旦计算机网络系统中的重要区域或节点受到破坏时，整个计算机网络将会异常脆弱。更有甚者，如果计算机网络中一小部分的中心阶段被破坏后，整个网络就会陷入瘫痪的境地，计算机网络也无法保障正常运行。
（四）计算机网络病毒扩散模型和病毒防治的方法
网络安全影响了计算机网络的日常运行，而影响网络安全的因素主要是病毒的袭击和扩散。因此，复杂网络理论在计算机网络拓扑中的应用，应该采取有效的措施来抑制计算机网络病毒的扩散，减少病毒的传播，避免病毒对计算机网络损害后带来的计算机网络安全问题。复杂网络理论开始应用于计算机网络拓扑行为中时，人们开始以复杂网络为基础不断研究和探索出新的防御病毒的方法，且取得了一定的进展。比如在规则网络中，人们经过研究发现计算机网络病毒只有在小世界中才能轻易的传播，在复杂网络理论里，计算机网络感染病毒的可能性较小，一旦感染的话，网络系统将会受到大面积病毒的袭击，这对预防计算机病毒的入侵技术而言是一大挑战。防御计算机网络病毒工作的开展，必须建立一个科学系统的防御病毒扩散模型，模型需要遵循的原则有网络的拓扑结构形式、知晓病毒的传播原理、网络拓扑结构形式和知晓病毒传播原理之间的关系和作用。此外，在计算机网络病毒扩散模型的构建和病毒防治的过程中，要格外注重预防网络病毒的产生和传播的速度，通过网络的拓扑结构和复杂网络理论来做好计算机网络的抗病毒工作。
四、结语
总之，基于复杂网络理论的计算机网络拓扑分析是一项专业的、复杂的、系统的步骤程序化工程。复杂网络理论能保障了人们实现对计算机网络拓扑行为的要求，促使了计算机网络拓扑研究的发展，给我国现代化网络的发展提供了可靠的保障。
【参考文献】
随着计算机网络的飞速发展，传统的网络模型已经很难对计算机网络拓扑特性做出客观的描述和研究。针对这个现象，复杂网络理论的产生和应用，为计算机网络的拓扑发展带来了新的平台和思路。对于复杂网络理论在计算机网络拓扑中的分析已经成为计算机网络领域研究的重要课题。
二、复杂网络和计算机网络拓扑的基本理论
（一）复杂网络理论的含义及其复杂性
复杂网络是指具有内部相似、自行组织、吸引因子、小区域、无标度中的一部分或者全部的网络。其复杂性主要体现在以下六个方面：①结构的复杂性，表现在网络的节点数量较大。②节点的多样性，网络中的所有组成部分，代表的各种事物均为复杂网络理论中的节点。③连接的多样性，指的是网络中节点的连接方式不一致。④动力学的复杂性，指的是节点之间的复杂性，能够产生多样的结构特征。⑤网络结构的变化性，指的是网络节点之间消失和连接产生就像网页随时断开和连接一样，使得网络结构不断的发生变化。⑥多重复杂性的融合，指的是上述所有复杂性的结合表现出的复杂性。此外，复杂网络理论有小世界、集团集聚程度更加密集和幂律的度及介数涵盖的范围不断扩大等三种特性。
（二）计算机网络拓扑技术及分类
计算机网络拓扑最早是由瑞士数学家欧拉在1736年提出的，主要是用于连接计算机网络和传输不同设备之间数据的一种方式。不同的网络设计要选择适合的网络拓扑方式，在网络拓扑结构中，拓扑技术是以图像的方式来表示多种设备之间的相互关系。计算机网络拓扑的主要类型有星行结构、环形结构、总线型结构、混合拓扑结构、分布式结构等。由于计算机的分布和数据传输电缆的布置存在很大的差异性，每一种网络拓扑结构都有其相应的优缺点，因此在计算机网络拓扑形式的使用上，要具体问题具体分析。
三、复杂网络理论在计算机网络拓扑中的具体应用分析
（一）计算机网络的同步行为现象分析
这主要是指计算机各个网络节点之间的同步行为，在复杂网络理论中，网络节点之间的同步是较为常见的一种现象，主要是受网络拓扑和各节点之间的动力学性质决定的。但是值得注意的是，这种同步行为并不都是有益的，如由多个路由器发出路由信息的网络，其同步行为包括了发出同一种路由信息和同时不发送信息，这就很有可能会使得网络出现拥挤或者瘫痪的现象。从计算机网络技术的发展来看，人们采取避免计算机网络出现同步行为的措施并没能完全奏效，经常会出现一种同步行为结束，另一种同步行为又产生的现象。因此，如何有效杜绝计算机网络的同步行为现象仍然是人们研究的课题。
（二）计算机网络拓扑行为的演化模型
计算机网络拓扑行为的演化模型由复杂网络演化模型逐步转变为了局部演化模型，这两种演化模型都是从路由器和自治域两个不同的层次来描述计算机网络的拓扑结构的。从路由器上看，各个路由器相当于各个网络节点，而路由器之间的物理连接相当于边。从自治域上看，在边界网关协议的基础上，如果两个自治域之间对等连接的话，就说明这两个节点之间是有一条边相连的。复杂网络演化模型演化出的结果很大程度上出现富者更富，穷着更穷的现象，即那些新加入的用户会倾向于那些品牌好、质量好、连接数量多的网络服务商。该模型遵循的偏好连接原则是基于整个网络上的，与优先考虑连接到本地区的服务器或路由器的实际不符。而局部演化模型的偏好连接倾向性是在局部信息的基础上形成的，一定程度上克服了复杂网络演化模型的缺陷。
（三）计算机网络脆弱性和鲁棒性的动力学模型
1.计算机网络的鲁棒性。计算机网络的原始功能是保证军事资料的安全性，这样的保证就是所谓的鲁棒性。鲁棒性是指在计算机网络中的某个区域或节点中出现问题或故障时，不会扩散到整个计算机网络系统，计算机还能保持正常的运行。相关研究表明，一般在一个网络系统中，只要有百分之二十左右的正常区域和政策阶段就能够保障计算机网络的正常运行。
2.计算机网络的脆弱性。虽然计算机网络有鲁棒性的动力学模型，但是一旦计算机网络系统中的重要区域或节点受到破坏时，整个计算机网络将会异常脆弱。更有甚者，如果计算机网络中一小部分的中心阶段被破坏后，整个网络就会陷入瘫痪的境地，计算机网络也无法保障正常运行。
（四）计算机网络病毒扩散模型和病毒防治的方法
网络安全影响了计算机网络的日常运行，而影响网络安全的因素主要是病毒的袭击和扩散。因此，复杂网络理论在计算机网络拓扑中的应用，应该采取有效的措施来抑制计算机网络病毒的扩散，减少病毒的传播，避免病毒对计算机网络损害后带来的计算机网络安全问题。复杂网络理论开始应用于计算机网络拓扑行为中时，人们开始以复杂网络为基础不断研究和探索出新的防御病毒的方法，且取得了一定的进展。比如在规则网络中，人们经过研究发现计算机网络病毒只有在小世界中才能轻易的传播，在复杂网络理论里，计算机网络感染病毒的可能性较小，一旦感染的话，网络系统将会受到大面积病毒的袭击，这对预防计算机病毒的入侵技术而言是一大挑战。防御计算机网络病毒工作的开展，必须建立一个科学系统的防御病毒扩散模型，模型需要遵循的原则有网络的拓扑结构形式、知晓病毒的传播原理、网络拓扑结构形式和知晓病毒传播原理之间的关系和作用。此外，在计算机网络病毒扩散模型的构建和病毒防治的过程中，要格外注重预防网络病毒的产生和传播的速度，通过网络的拓扑结构和复杂网络理论来做好计算机网络的抗病毒工作。
【关键词】产业集群 复杂网络 介数
一、引 言
产业集群指同一产业的企业以及该产业的相关产业和支持产业的企业在地理位置上集中[1]。产业集群中上下游企业之间是一种需求与供应关系。
随着复杂网络理论和方法的不断发展，国内外很多学者开始把产业集群与复杂网络结合起来进行研究。当前基于复杂网络的产业集群研究主要集中在对产业集群网络整体模型及其演化，缺少对其抵御风险能力的分析，本文设计了一个产业集群复杂网络模型，针对不同类型节点退出网络时分析该产业集群网络模型抵御风险能力的变化情况。
二、产业集群复杂网络模型
（一）模型概述
在产业集群复杂网络模型中，首先根据企业在产业链中的位置把产业集群中的企业抽象为上游、中游和下游企业三类。设定三类企业的连接方式为：上游企业和下游企业只能与中游企业连接，中游企业可以与上游和下游连接。节点间的连接用有向边表示。
（二） 产业集群网络模型构建与演化过程
产业集群网络模型以BA网络模型和LC局域世界演化模型为基础，具体构建过程如下：1.在产业集群复杂网络模型中，网络中初始状态为m0个节点，e0条连边。把m0个节点随机分配给三种不同节点，网络中节点间的连边为随机生成。2.每隔一个时间间隔t向网络中引入一个新节点i，如果新节点为分别为上游企业、下游企业和中游企业，则携带边数为m1、m2和m3，局域世界分别为中游企业、中游企业、上游与下游企业。3.当新节点i与网络中的相应节点连接时，其连接概率按照以下公式择优进行：
其中为网络中的节点j获取新节点i连边的概率，为节点j的度。4.根据新节点i的类型不同，在局域世界中选择m（m
三、产业集群网络模型风险衡量指标
产业集群网络中的企业节点退出网络后会使整个产业集群网络的功能受到影响，当退出企业较多时，会使整个网络失效。本文中选取产业集群网络受到节点退出影响后产销链条能否保持完整作为产业集群网络抵御风险能力的度量指标。产业集群网络中的某些企业节点由于政策、经营等风险因素退出后，会形成互不连通的多个子产业集群。其中规模最大的称为最大有效子子产业集群。通过统计由于攻击被去除的企业数占原产业集群网络总企业数的比例与最大有效子产业集群的规模S的关系来衡量产业集群网络的风险抵御能力。
四、产业集群网络节点风险衡量指标
产业集群网络中一个企业的退出，如果严重影响了该网络的产销功能或物流能力，则称该企业节点为高风险节点。本文中我们使用度和介数指标来区分不同的节点，其中产业集群网络中节点企业的度指一个产业集群节点企业所连接的其他节点企业的个数，介数为通过该节点的最短有效路径的条数，度量这两种节点退出网络后产业集群网络抵御风险的能力。
五、 仿真模拟与讨论
图1 产业集群网络最大有效子产业集群的规模变化情况
产业集群网络模型的初始节点企业数均设为30个，上游企业、中游企业和下游企业加入产业集群网络时所带的边数分别设定为6、10、6。网络加入的上游企业、中游企业和下游企业的个数分别为480、800和1280。从图1中可以看出，随机退出和高风险节点退出造成的产业集群网络最大有效子产业集群规模的变化趋势是相同的，均呈现逐渐下降的趋势。随机退出的方式下产业集群网络最大有效子产业集群规模随着去除节点企业比例的增加下降相对比较缓慢，而采用高风险节点退出的方式时，产业集群网络最大有效子产业集群规模随着去除节点企业比例的增加下降非常迅速。
六、结束语
针对复杂网络交叠团的聚类与模糊剖析办法设计Issue(问题)，给出一种新的模糊度量及对应的模糊聚类办法，并以新度量为根底，设计出两种发掘网络模糊拓扑特征的新目标:团间衔接严密水平和模糊点对交叠团的衔接奉献度，并将其用于网络交叠模块拓扑构造微观剖析和团间关键点提取。实验后果标明，运用该聚类与剖析办法不只能够取得模糊勾结构，并且可以提醒出新的网络特征。该办法为复杂网络聚类后剖析提供了新的视角。
关键词:网络模糊聚类;团—点相似度;团间连接紧密度;团间连接贡献度;对称非负矩阵分解;网络宏观拓扑
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.
[14]LUSSEAU D，SCHNEIDER K，BOISSEAU O J，et al.The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations:can geographic isolation explain this unique trait?[J].Behavioral Ecology and Sociobiology，2003，54(4):396-405.
针对复杂网络交叠团的聚类与模糊剖析办法设计issue(问题),给出一种新的模糊度量及对应的模糊聚类办法,并以新度量为根底,设计出两种发掘网络模糊拓扑特征的新目标:团间衔接严密水平和模糊点对交叠团的衔接奉献度,并将其用于网络交叠模块拓扑构造微观剖析和团间关键点提取。实验后果标明,运用该聚类与剖析办法不只能够取得模糊勾结构,并且可以提醒出新的网络特征。该办法为复杂网络聚类后剖析提供了新的视角。
关键词:网络模糊聚类;团—点相似度;团间连接紧密度;团间连接贡献度;对称非负矩阵分解;网络宏观拓扑
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.
[14]lusseau d,schneider k,boisseau o j,et al.the bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations:can geographic isolation explain this unique trait?[j].behavioral ecology and sociobiology,2003,54(4):396-405.
[关键词]股票；相关性；复杂网络；GN算法
[DOI] 10.13939/ki.zgsc.2015.22.042
1 引 言
股票间的相关性对于风险管理、投资决策具有重要影响。对于股票相关性的研究，现代金融理论主要基于经济基本面进行解释，即认为相关性来源于影响资产现金流和影响资产折现率的基本面因素。已有研究表明，股票间相关程度远超出了经济基本面因素的影响，股票市场作为复杂系统日益受到人们的关注。近年来，经济、数学、社会等领域的学者都开始用复杂网络及其相关概念来研究股票市场，进而研究股票间相关性。
2 股票间的相关性
研究股票间的相关性对股民来说至关重要。现随机选取沪市A股、沪市B股、深市A股、深市B股、创业板这五类市场中各20只股票在2013年1月1日至2013年8月31日的周开盘价、收盘价和周个股回报卒作为量化指标，进行相关性分析。
2.1 单个指标的相关系数
选取周开盘价，周收盘价与考虑现金红利再投资的周个股回报率，并用k=l，2，3表示。
Ai（k）表示股票代码为i，指标为k的时间序列矩阵
设随机变量Ai（k）与Aj（k），则协方差为：
Cov（Ai（k），Aj（k））=E（Ai（k）- EAj（k）） -EAj（k）
相关系数为：
2.2指标权重的设立――变异系数法
其中 为第i项指标的平均值，=是第i项指标值的方差，对vij（k）（k）进行归一化，即得到各项指标的权数：
2.3 综合指标的相关系数
设运用股票i与股票j之间的综合相关系数值为
2.4模型的求解
对原题附件中数据进行处理，依据五类不同的股票市场，依次随机选取20只股票在2013年1月至2013年9月共36周内的周开盘价、收盘价和考虑现金红利再投资的周个股回报率数据。基于模型Ⅱ，运用Matlah编程求解，见表1。
3 股票板块的划分
股票板块的划分存在很多依据，常见的有按地域、按行业、按概念等，但这些都是从定性的角度去考察股票与股票内在联系，而通过相关性构建的股票网络，能依据股票与股票间时间序列数据的相关性，从定量角度去划分股票板块。这样的量化处理使得板块内部的波动性更加一致，更利于我们的投资决策。
3.1 股票相关性网络模型
①相关系数构成。网络的节点代表股票，边代表股票之间的相关性。任意两只股票i和j的综合相关系数为：
Pij（k）= pij（k）w（k）
其中i和j表股票代码，pij的取值范围为[-1，1]。若pij=-1，则表示两只股票完全负先关；若pij=1，则表示两只股票完全正相关。
②阈值的设定。股票代表网络中的点，如果相关系数|pij|≥θ（θ∈[-1，1]），就认为节点i和j之间有连边，这里的θ即阈值点。通过计算对比得知，当θ=0.05时其到达最佳阈值，股票网络的拓扑性质最稳定，更有利于对股票网络的研究。
③社团结构的构建。由模块度评价函数来衡量社团结构划分好坏，将其推广至加权的模块度评价函数Q定义为：
其中wsub>ij为网路中节点i和节点j之间的权重，ssub>i= 为节点i的权重，m=
为网络中所有边的总权重，ci为节点i被划人的社团编号，对于函数δ（ci，c）有：当u=v是，δ（ci，c）=1，当u≠v时，δ（ci，c）=0。
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 结论分析与投资建议
现实中的板块划分主要分为两类，一类是地域板块，按照上市公司的所在地划分股票；一类是概念板块，如金融与银行业、化工业等；同时也会有依据股票的表现划分为蓝筹股、垃圾股等。而上述划分是依据时间序列数据的相关性程度划分的，与现实的板块划分有相同也有不同的地方。
相同点：与主流的两类划分的依据相同，其划分主要依据都是因为这类股票有着很强的相关性，在整体系统性风险一定的情况下，局部的系统性风险类似，如银行与金融板块，当央行上调法定存款准备金率时，其板块的股票整体呈下降趋势。
不同点：本文的股票网络模型比较接近与现实生活中的依据股票表现划分的类型，但这不是主流的划分，与按照概念划分和地域划分的板块在度量相关性的指标上有一定的差距。
一是多样化选股。投资股票种类多样化，板块多样化根据社团结构的股票网络图知，当购买股票时，切勿全部购买相同板块的股票，要综合考虑，分散风险。相同板块的股票相关程度高，波动的趋势相同，从一方面来看，若全部购买同一类型股票，将会使板块的非系统性无法避免，提高投资的风险率；从另一方面来看，虽然同一板块股票上涨具有传递效应，但其效应大小远远小于下跌时的连带效应，及时此板块的某些股票暴涨也不一定能带动整个板块所有股票上涨。所以，即使是风险偏好者也应慎重考虑。
二是综合投资与投机，确保利益最大化。作为投资者，在股票市场的最终目的是利益最大化。那么在选股时，不仅要考虑短线低买高卖的投机操作，也要有长期持仓的投资计划。对于投机类股票，结合板块分析可知，应选取处于萌芽期或成长期的股票，这些股票的波动性大，只要能把握好趋势，在短线操作的收益率较高。对于那些风险偏好更高的投资者来说，可以考虑处于衰落期的股票。这类股票，一旦有公司借壳上市，其市值会翻倍的增长；对于投资类股票，可以选取成熟类板块的股票，这类股票波动程度小，股盘大，价格相对稳定，每年会有固定的分红股利，这类股票适合长线持有。
三是选股重看基本面。股票的基本面的好坏是一只股票有没有操盘意义的前提，一般的我们通过分析其每股净收益，单日成交量等基本财务指标来判断其基本面情况。如果一只股票的基本面不好，再多的技术分析也只是空中楼阁。所以对于选股来说，先看基本面，再看技术指标。
（安徽财经大学，安徽蚌埠233000）
［摘要］传统股票板块的划分缺乏精确的逻辑推理和数理分析。本文基于复杂网络和社团理论，通过构建数量模型，选取时间序列数据对股票与股票之间的相关性进行分析，依据相关性大小对股票进行板块的划分，并依据划分结果，为投资者提供政策建议和技术支持。
［
关键词 ］股票；相关性；复杂网络；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）.
［2］ 潘令希.关于IPO发售机制的探析［J］.中国市场，2014（43）.
购物车(0)
