一种基于特征环的复杂网络结构化简方法  

Reduction Method for Complex Net Structure Based on Characteristic Circle

作　　者：胡飞虎[1] 荆娟娟[1] 刘露露[1] 马贝龙[1] 

机构地区：[1]西安交通大学电气工程学院工业自动化系西安710049

出　　处：《计算机科学》2013年第6期52-56,共5页Computer Science

基　　金：国家自然科学基金项目(61174154);国家“863”高技术研究发展计划基金项目(2009AA04Z121);中央高校基本科研业务费专项资金资助

摘　　要：具有复杂连接关系的网难以进行结构分析和运行控制。基于特征环的网络化简方法,保持了原有网络的特性并有效降低了网络连接的复杂程度。网的研究基于单重有向图,在连接和路径概念的基础上,定义了环路径和复合环路径,进而引入了特征点和普通点的概念,并给出了单纯特征环和复合特征环的定义。给出了基于特征环的网结构化简原则和化简算法,结合实例对网络结构的化简进行了探讨。结果证明该方法可以有效化简复杂网络,但特征环的选择顺序不同时,网络化简的结果也可能不同。Nets with complex structure are difficult to analyze and control. Reduction method based on characteristic cir- cle may assist in its analysis as its reduced version may be significantly smaller while still retaining the original net~ s es- sential properties. Study of the net is based on single directed graph. On the basis of the conception of connection and path, the circle path and composite circle path were defined. The pure characteristic circle and composite characteristic circle were defined based on conception Of characteristic node and common node. The reduction rule and algorithm based on characteristic circle were discussed with samples. The result shows this method can effectively reduce complex net into small parts. However, different sequence of characteristic circle selection may have different reduction result.

关 键 词：复杂网络 网络化简 图化简 复合环 特征环 工作流 

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