基于连通性指标的网络分解方法

Connectivity index-based network decomposition method

为减少由网络分解造成的网络分析精度损失,基于系统科学中节点删除的方法,提出一种度量节点间连通性影响的指标——相对连通系数.以该指标为依据,应用主成分分析方法提取与目标相关的节点来生成子网的方式建立了新的网络分解方法,在解空间损失较小的情况下降低了网络分析的计算复杂性.求解最短路径的试验表明:该方法可有效控制网络分解造成的精度损失;网络规模压缩至原有的20.12%,而最大误差为13.85%;计算时间由秒级降至百毫秒级.

A connectivity index called the relative connectivity coefficient was proposed to reduce the loss of analytic precision caused by network decompositions. The index based on the vetex removal method in systems science, can measure the impact between vertexes in a network. The principal component analyses were carried out based on these indices, and the most relevant elements to the destinations were extracted from the entire network to compose subnetworks, thus the computational complexity of these subnetworks can be reduced with less accuracy loss. Tests on solving problem of the shortest path distance show that the method can effectively control the accuracy loss caused by network decompositions, and subnetwork＇s size is compressed to 20.12% of the original network while the maximum accuracy loss is 13.85 %. The computing time is reduced from second magnitude to 100 microsecond magnitude at the same time.