网络结构分析的粒计算  

Granular Computing Based on Network Structure Analysis

作　　者：何富贵[1] 刘仁金[1] 张燕平[2] 

机构地区：[1]皖西学院信息工程学院,安徽六安237012 [2]安徽大学计算机科学与技术学院,合肥230039

出　　处：《计算机科学与探索》2012年第11期1049-1056,共8页Journal of Frontiers of Computer Science and Technology

基　　金：国家自然科学基金(61073117,61175046);国家重点基础研究发展规划(973)(2007CB311003);安徽省自然科学基金(11040606M145);安徽高校省级自然科学研究项目(KJ2012B212)~~

摘　　要：网络结构分析是人工智能领域基本问题。应用粒计算方法讨论了网络结构信息计算,从粒计算基本问题角度,采用商空间理论研究了网络结构粒化和粒化后不同粒度空间中的问题,特别是基于粒化如何计算不同粒层的粒间距离问题。应用方面,讨论了大规模网络结构最短路径搜索问题。作为大规模网络路径分析的预处理方法,选择社团作为基本粒,将大规模网络粒化到不同的粒度空间,形成不同粒度商空间的分层递阶粒度链。提出了基于分层递阶粒度链的大规模网络的启发式路径搜索方法。与A*和ALT方法进行了比较,验证了粒计算方法的有效性。Network structure analysis is one of the fundamental problems in artificial intelligence. This paper discusses a granular analysis method of network based on granular computing. From basic problems of granular computing, using mathematical description of quotient space theory, the paper proposes some methods how to select grain of network and deal with problems among different granular spaces, especially, how to compute the distance between two grains in the same granular space. In application, the paper puts forward a path-finding method of massive networks based on granular computing. As preprocessing work of massive network path analysis, selecting community as basic granule, a massive network is decomposed to different granular spaces. Different granular quotient spaces constitute a hierarchical granular chain. The paper also proposes a heuristic searching path method based on the hierarchical granular chain in a massive network. Compared with other heuristic searching path methods （A star search （A＊） and A＊ using landmarks and triangle inequality to compute feasible lower bounds （ALT））, the experimental results show that the proposed method is effective.

关 键 词：粒计算 网络结构分析 商空间理论 最短路径 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]