基于改进FCM聚类的复杂网络节点重要性评估方法(3)
1.3 论文内容的组织
一般研究网络节点失效的方法是通过让一些节点失效，然后判断剩余网络节点的联通情况，或者是计算通过一个节点的最短路径的数目。这些做法的一个共同的缺点是计算的复杂度太高，很难用于处理像互联网这样的大型网络。本文通过对网络进行聚类分析，然后再研究每个节点与聚类中心的关系，从而得出其复杂度。
本文的结构如下：
复杂网络部分介绍复杂网络以及几种有代表性的网络的特征和构造方法；
聚类算法部分介绍聚类算法的原理及常见的几种方法；
网络重要性分析方法部分介绍几种目前研究网络节点重要性的方法以及各自的优点和缺点；
改进的FCM计算节点重要性部分描述本文实现聚类算法的原理及代码；总结部分对研究结果进行概括。
2 复杂网络综述
复杂网络无所不在，比如互联网、生物的神经网络、人类的食品供应网络、细胞新陈代谢系统、飞机航班的时刻表、公司之间的合作管子、人们参加相同社会活动的网络，甚至语言中词与词之间的语法联系等等。
复杂网络并没有精确严格的定义，它可以看作是大量真实复杂系统的拓扑抽象。它既不是规则网络，也不是随机网络，而是具有与两者皆不相同的统计特征的网络。
结构决定功能是系统科学的基本观点，近年来的大量研究表明，网络的拓扑结构决定了网络的特性，复杂网络表现出了与经典随机网络模型理论不同的特性。
一般使用两个特征来衡量网络：
特征路径长度：在网络中，任选两个节点，连同这两个节点的最少边数，定义为这两个节点的路径长度。网络中所有节点的路径长度的平均值定义为网络的特征路径长度。
聚合系数：假设某个节点有K个边，则这K条边连接的节点之间最多可能存在的边个数为（K-1）*K/2，用实际存在的边数除以最多可能存在的边数得到的分数值，定义为这个节点的聚合系数。所有节点的聚合系数的平均值定义为网络的聚合系数。
节点的度是指该节点与其它节点相关联的边数。节点的聚类系数是指与该节点相连的近邻节点之间互连的比例。
聚集度和聚集系数反映了网络的模块性质。同一模块内部节点互连度高，聚集性强，而处于模块之间的节点聚集系数较弱。节点的聚集度和聚集系数体现了此节点局部范围内的互连密度，而对很多网络，例如蛋白质相互作用网络其节点的连接代表节点属性上的某种相似性，因此可以利用聚集度和聚集系数为特征，对网络节点进行聚类。
2.1 小世界网络
小世界网络模型是一类具有较短的平均路径长度又具有较高的聚类系数的网络的总称。
小世界网络模型是Watts和Strogatz在1998年提出的基于人类社会网络的网络模型，它通过调节一个参数可以从规则网络向随机网络孤独，该模型成为WS小世界模型。
由于WS小世界模型构造算法中的随机化过程有可能破坏网络的联通性，Newman和Watts提出NW小世界网络磨性能，该模型是通过用随机化加边取代WS小世界网络模型构造中的随机化重连。
WS小世界模型构造算法如下：
一个环状的规则网络开始：网络含有N个结点，每个结点向与它最近邻的K个结点连出K条边，并满足N>>K>>ln(N)>>1。
随机化重连：以概率p随机地重新连接网络中的每个边，即将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点。其中规定，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。这样就会产生pNK/2条长程的边把一个结点和远处的结点联系起来。改变p值可以实现从规则网络(p=0)向随机网络(p=1)转变。