许多基于互联网的研究,以及对认知网络的研究,均涉及用高速群集计算机系统并行模拟或处理大规模网络的问题。而网络拓扑图划分是处理相应计算任务分配的一种有效的技术手段。基于图划分的应用不断深入与扩展的形势,为保证划分质量的需要,对网络拓扑图划分算法进行了深入研究。本文研究工作主要包括四个方面:网络拓扑图划分的求解模式、网络模拟图的划分算法、CDN缓存服务器放置问题的图划分算法和网络拓扑图划分质量的评价方法。具体研究内容如下:第一,为了规范网络拓扑图划分问题的求解过程,从内在机制上做到保证划分质量,探索并构建一种具有循环优化调节环节的网络拓扑图划分的求解模式。该模式包含三部分内容:一是图的预处理,即权重估算,约束条件和优化目标的确定;二是图的划分,包括粗化压缩、初始划分和细化还原三个阶段;三是划分质量评价和运行参数循环优化调节。同时,为了满足图划分应用领域不断扩展的需要,在网络拓扑图划分一般定义的基础上,给出了最大化边切割的概念和网络拓扑图划分的四个扩展定义,打破了传统的图划分只为求最小化边切割,不能最大化边切割的束缚。第二,根据网络拓扑图划分求解模式,提出一种具有循环优化调节环节的网络模拟图多层k路划分算法,达到了保证划分质量的目的。在传统算法的基础上,增加预处理环节,进行权重估算,根据任务要求和实际掌握的数据情况,确定优化目标和约束条件。阐述了粗化阶段的有选择的轻点匹配算法,解决了轻点匹配算法原设计中有的较重节点被压缩的问题;阐述了初始划分阶段的有选择的图增长划分算法和有选择的贪心图增长划分算法,解决了原算法因初始点不同而影响边切割大小的敏感性问题。设计了运行参数循环优化调节的具体过程,给出循环变量的具体选择与调节方法。采用有选择的轻点匹配算法并对照轻点匹配算法和有选择的重边匹配算法进行网络模拟图划分对比实验,实验数据表明,有选择的轻点匹配算法在边切割和均衡度两方面都比对照算法更好,证明有选择的轻点匹配算法比对照算法更适于网络模拟图的划分。第三,为了解决CDN缓存服务器放置问题,提出一种用最大化边切割算法对CDN图进行划分的新方法。给出CDN图划分应满足的条件和CDN图划分的定义,确定CDN图划分的权重抽象规则。实现用单次边压缩算法和有选择的轻点压缩算法进行CDN图划分粗化压缩,用单次轻边压缩k路划分法进行初始划分,并改造KL/FM算法实现了CDN图划分的细化还原。CDN图划分实验数据证实有选择的轻点压缩算法和单次轻边压缩算法是解决CDN图划分问题的有效方法。第四,为了比较不同划分算法的划分性能和验证图划分的效果,提出一种网络拓扑图划分质量综合评价指标法。定义了多项网络拓扑图划分的基本评价参数,构建了网络拓扑图划分质量评价的基本方法,包括割衡积Q、网络模拟图划分质量相对评价指数J和无量纲评价指数C的概念。设计了网络模拟图划分质量的综合评价指标法和完成任务花费时间指标法。分别给出用J值法和C值法对网络模拟图划分质量进行综合评价的示例,实验数据分析表明,评价结果反映了用不同评价指标联合评价划分质量的综合效果,说明综合评价法具有理论意义和实际应用价值。制定了 CDN图划分质量的评价指标,包括割衡商R和CDN图划分相对评价指数L等概念。给出CDN图划分质量的L值法评价示例,对有选择的轻点压缩算法、单次轻边压缩算法和轻边匹配算法的实验数据进行对比分析,证明有选择的轻点压缩算法和单次轻边压缩算法具有优势,效果较好。