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

Connectivity index-based network decomposition method

作　　者：郭武斌[1] 胡祥培[1] 佟士祺[1] 刘伟国[1] 

机构地区：[1]大连理工大学管理学院,辽宁大连116024

出　　处：《大连海事大学学报》2008年第2期105-109,共5页Journal of Dalian Maritime University

基　　金：国家自然科学基金资助项目(70171040;70571009);教育部科技研究重点项目(03052);辽宁省自然科学基金资助项目(2001101074)

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

关 键 词：网络分析 网络分解 连通性 相对连通系数 

分 类 号：TP319[自动化与计算机技术—计算机软件与理论]