基于感染原理判断图的连通性算法

在大规模网络中，网络的连通性对各种图算法效率有重大影响，而采用传统遍历算法的方法来判断连通性和侦测子图具有迭代复杂、效率较低的缺点。本研究借鉴生物病毒的感染原理，采用低值传递的方法，提出了一种子图数侦测算法。该方法能大幅提高侦测效率，简化复杂网络计算。

传统的判断图的子图数方法，以 DFS（深度优先搜索）和 BFS（广度优先搜索）等遍历搜索算法为基础，在网络的节点上遍历调用搜索算法，检验有新节点被搜到的调用次数来判明子图数。这种方法运算次数为 T(N)=n*T(遍历算法) (n 为图的节点数)，不仅复杂度高，而且在一些层次较深的网络中，因为调用的深度太大可能导致堆栈溢出。

自然界生物病毒感染具有区域性，两个绝对隔离的区域是不可能感染同种病毒的。这种特性可以用来对复杂网络进行连通性测试，网络中的节点视为生物体，而关系则视为病毒绝对可感染的通道。假设所有的子图都被本区特有的病毒感染，最后只用统计图中的病毒数，即可计算出图的子图数。

病毒感染具有水平传播和垂直传播两种方式，水平传播是指病人和健康人个体之间通过呼吸道、消化道、节肢动物叮咬、直接或间接接触等的传播方式。垂直传播是指病原体通过胎盘由母体传给胎儿或于分娩时经产道由母体传给胎儿的传播方式。我们假设病毒具有互斥性，生命力更强的病毒可以吞噬、替代生命力较弱的病毒。在网络中，两个相邻的节点可以实现水平传播，而两个相邻的网络一旦连接到一块，则可以实现垂直传播，即某区的病毒传染给另一区所有的节点。

基于此，设计感染理论模拟算法。假设网络在初始状态下顺序标定各点值，通过遍历，将各点与其相邻的点采用低值传递方式，各点均感染较小值代表的病毒。在迭代循环中，反复感染，直到所有的节点都感染完毕。步骤是:①给每个节点一个标志变量,并以节点编号作为初始值(每个节点开始时均被认为不连通);②每个节点对相邻节点进行“低值传递”,传递后的标志数以相邻节点的较小标志数代替;③重复执行上述过程 N 次直至系统稳定,当不再有节点标志数发生改变时终止。重复次数 N 为图的任意两个连通节点的邻接阶数(最小步数)中的最大值。

                                       图 1 低值传递过程

在此算法上，实现的运算次数为 N*Arc.length。大大低于重复调用遍历算法的时间复杂度。

总结

本实验数据是基于坐标点的纽约地图，在经纬度一度的空间内大约有 266000 个节点，在如此庞大的节点数上求最短路径、最小生成树都是十分复杂的，而其中是否为连通图对最短路和生成树有决定性意义。借鉴病毒感染原理，提出一种基于感染病原理的算法，可以大幅度缩减算法复杂度。     

参考文献

1． GIS 网络分析的图简化方法研究 王杰臣 测绘学报 2001.8 30（3）263