网络综合预警的可视化技术(编辑修改稿)

网络综合预警的可视化技术(编辑修改稿)内容摘要：

条内部通路相连通。 定义 5： ( , ) ije dg e c ut e u v u G v G i j      。 算法目标 基于分治法分解的思想， 无向图分割算法 Multilevel kway Graph Partitioning with Connectivity Restriction(MLkP/CR)的目的是把大规模的网络拓扑图分割成 k(k=|G0|/N,N 是子图平均大小 )个 大小相近、规模小的网络拓扑子图，并使子图间的边尽可能少。 算法描述 MLkP/CR 算法包含三个阶段 [4,5]，首先是图的逐 步规约阶段，这一阶段 通 过原图),( 000 EVG  构造一系列规模逐渐减小的子图 ),( iii EVG  ，其中 1 ii VV。 在大多数的规约策略中，把 iG 的一个顶点集合联合起来作为 1iG 的一个点。 然后对最终的规约图),( mmm EVG  计算一个 k 划分 Pm，使划分后的每一部分大致包含 kV/0 个 原图的点。 第三阶段把 规约图 mG 的划分向量 mP 通过 121 , GGG mm  反向映射回原图。 1iG 中的每一点都是 iG 中一个点的子集 viV ，只需将把 viV 中的点设为 1iP 就可获得 iG 的划分向量 iP ，viii VuuPuP   ].[][ 1 ， 从而求出了原图的 0G 划分向量，形成了对原图的 k 划分。 注意即使mG 的划分是局部最优的，映射后 1mG 的划分也不是局部最优的。 所以 每映射到一层图上10{ , }mmG G G 都要对映射后的划分结果优化。 因此，第三阶段 包括了一 系列的迭代过程，每一次迭代都检查所有的点，看它们 能否移动，来使子图 间边的总数 edgecut 减少，或 能改进平衡。 优化的策略如下： edgecut 考虑一个图 Gi = ( iV , iE ) ,它的划分向量为 iP ，定义参数如下： 定义 1： ()iNv = {P( jv ) | iv 与 jv 相邻 ,且 P(iv ) 不等于 P( jv )} 定义 2： []bEDv =  Edge(u,v) 其中， P[u] = b，且 b∈ N(v). 定义 3： ID(v) = Edge(u,v) 其中， P[u] = P[v]. 定义 4： []bgv = []bEDv – ID(v) []bgv 是移动一个点带来的优化效果度量参数。 如果 []bgv 0,那么把 v划分到 b中， edgecut将减少 []bgv 条边。 引入该参数的目的是找到能够减少子图间边的个数的点。 2. 保证子图的平衡 由于移动一个点必然导致各个部分大小的改变，为了使各个部分大小接近，保持平衡 [14]。 必须加入平衡条件限制。 只有当移动的点满足平衡条件，才可以移动点。 平衡条件定义如下： 式中 []iWa— 划分后 iG 第 a部分的权重； w(v)— v的权重； maxW — 每部分大小的上限； minW — 每部分大小的下限       m i nm a x )( WvwaWandWvwbW ii  3. 保证子图的自连通 移动一个点，可能导致该点所在部分自身不连通。 为了保证自连通，我们必须加入连通限制哈尔滨工业大学 2020 届本科优秀毕业设计（论文）选集 425 来保证连通。 如果要移动的点不是在它所在子图 iG ( iV , iE )的割点，那么可以移动它，否则，它把 iG 分成 m个分支， {1， 2,……,m} ,令 jKv=  e(v,u),其中 v为割点， u∈分支 j。 若存在一分支j满足：  jKv []bEDv  W[j] W[b] 则把割点 v和除第 j个分支以外的其他分支一起移入到划分 b中。 这样，移动后 j分支单独作为一个子图，它是自连通的 ,从而保证了连通性。 由第一个条件知，移动后， edgecut减少 ED[v]b–K[v]j条边。 第二个条件是保证移动后的平衡 ,使剩余分支不会太小而失去整个划分的平衡， 这两个条件称为移动割点的两个条件。 子 图的平面可视化算法 [6] 算法目标 对子图的平面可视化就是解决大规模网络平面可视化 问题分解后 的子问题。 子图平面可视化算法主要实现以下几个目标：  点的互斥性：对于任意两点，为其分配的坐标不同。 否则，将导致若干点在平面上被覆盖。  点的邻接性：若两个点相邻，则它们尽量分布在一起，这样能更好的体现点的相邻关系。  边的准平面性：一条边不经过除顶点外的其他任何顶点，这样能够更 好的体现点的连接关系，避免误解。 算法描述 1． 点的分布算法： 首先找到子图内度数最大的点，以它为起始点按广度优先遍历子图，生成树状结构。 然后，从树根开始分配坐标，子结点按顺时针的方向依次排列在以父结点为圆心的圆周或半圆上。 如果父节点的子介点较多，排满一周后，则加大半径排另一圈，原则是尽量使度数小的子节点接近圆心，度数大的子节点远离圆心，这样使度数大的子节点有更多的空间分配它的子节点。 2． 边的布局算法： 拓扑图绘线时容易出现两点连线经过其他点，即点线重叠的情况，影响视觉效果，同时容易引起误解， 为 实现边的准平面性，在确定图中每个顶点的坐标后，绘制 每条边之前，先判断两点的直接连线是否有其他点，如果没有，则直接连线；如果有，则在两点间做。