论文部分内容阅读
20世纪90年代以来，以Internet为代表的信息技术的迅猛发展使人类社会大步迈入了网络时代。从Internet到WWW，从生态环境中的食物链网到生物体中的新陈代谢网络，从科研合作网络到各种政治、经济、社会网络，从大型电力网络到全球交通网络，人们生活在一个充满着各种各样的复杂网络的世界中。这也使得研究复杂网络成为必要。由于复杂网络节点众多，结构复杂，使得研究复杂网络非常困难。聚类分析以及在复杂网络中寻找社团结构的方法使复杂网络化为若干个节点较少，结构较简单的子网络，从而使研究较为简单。聚类分析是当今飞速发展的数据挖掘和探查性分析中的一个极为重要的技术，在数据挖掘、统计学、机器学习、空间数据库技术、生物学和市场学等领域有着广泛的应用。近年来，寻找复杂网络中的社团结构的方法已经成为复杂网络中研究的热点，本文我们将聚类分析方法应用到复杂网络中社团结构的研究。本文主要做了以下几方面的工作：(1)将模糊C-均值(FCM)聚类算法与视觉原理的密度聚类算法结合，得到一种新的聚类算法——视觉原理的FCM算法，在一定程度上解决了FCM聚类算法容易受噪声点的影响以及无法确定聚类数的问题，并将其应用于武汉市交通网，得到了较好的结果。(2)本文在分裂算法和凝聚算法的基础上也提出了一种新的算法——基于相异性指数的凝聚算法，并将它运用于经典Zachary网络，结果与现实网络完全符合。本文的创新点在于：(1)传统的FCM算法中计算两点之间的距离采用的是欧氏距离，而本文提出的视觉原理的FCM聚类算法采用的是复杂网络中常用的两点之间的最短距离。(2)视觉原理的FCM聚类算法将传统的FCM聚类算法与基于视觉原理的密度聚类算法结合，解决FCM聚类算法中常遇到的两类问题：a) FCM算法易受孤立点影响，而基于视觉原理的密度聚类算法可以通过距离剔除孤立点．b) FCM聚类算法要求事先给定参数，即所需聚类的类数．而我们通过给定的邻域半径逐渐增大得到每种情况下的聚类数，并通过最大生存区间这一概念得到最佳聚类数。(3)本文提出的基于相异性指数的凝聚算法是利用基于分裂算法中的相异性指数的概念，将原算法中的基于布朗微粒运动所得的距离用两点间的最短距离替换。另外，Newman的分裂算法中模块性的衡量标准是用社团内部边的比例减去在同样的社团结构下任意连接这两个节点的边的比例的期望值，本文采用比例的形式作为模块性的衡量标准。