论文部分内容阅读
随着互联网的日益普及,网络在人们交流和经济活动中的地位越来越重要,人们发现自然界和人类社会到处都充斥着形形色色的复杂系统,大多数的复杂系统能够采用适当的网络来表示。复杂网络是近年来的一个新课题,它已渗透到许多不同的领域中,对复杂网络的深入研究有助于人们理解网络的功能、探索复杂网络中的潜规律,使网络更好地为人类服务。首先,对K-means算法的初始中心进行优化改进。传统K-means算法的初始中心是任意选择的,造成划分结果不稳定,极易陷进局部最优。针对这个问题,本文设计了一种新的算法来优化初始中心,即在高密度区域中以距离最远的两点作为初始中心,接着找距离这两点的中点最远的点作为第三个初始中心,然后再将到这三个初始中心距离和最大的点作为第四个初始中心,依此类推,直到找到k个初始中心。在算法过程中通过自动调节参数的取值,增强了算法的鲁棒性。实验结果证实,改进的K-means算法具有较好的精度,降低了算法对初始中心的依赖,增强了算法的自适应能力,提高了聚类效果,为复杂网络社团划分提供了思路。其次,复杂网络有着比较明显的社团结构,为了找出网络中的社团结构,在分析K-means的基础上,设计了一种基于K-means的社团划分算法。引入节点重要度系数,根据节点重要度系数寻找合适的初始中心,然后根据K-means算法将网络聚成k个社团,最后选出模块度高的社团结构。借助经典网络进行仿真实验,分析发现该算法的社团划分准确率比较高,验证了这种算法的合理性。最后,应用复杂网络建模和分析方法探索城市公交网络,通过引入节点度、平均距离、聚类系数对青岛市公交站点网络、公交换乘网络和公交线路网络进行分析。研究表明这三种网络模型都是无标度网络,公交换乘和公交线路网络还具备小世界特性。为了进一步研究站点之间的相互作用强度,构造了以车流量为权重的加权网络,加权后的网络仍然是无标度网络,但它的加权距离和加权聚类系数都比较小,不具备小世界特性。最后在拓扑特性的基础上设计一种新的度量指标即重要度D(i)来挖掘网络中的重要节点,并对公交线路优化提出建议。本文主要对K-means算法进行改进,改进算法表现出更高的准确率和稳定性,提高了聚类质量。然后通过借鉴K-means算法思想,设计了一种基于K-means的社团划分算法,仿真实验表明该算法的社团划分准确率比较高,是有效算法。将复杂网络应用到青岛市公交网络中,分析青岛市公交网络的拓扑特征,为优化城市公交线路提出可供参考的建议。