网络结构分析的粒计算

Granular Computing Based on Network Structure Analysis

网络结构分析是人工智能领域基本问题。应用粒计算方法讨论了网络结构信息计算,从粒计算基本问题角度,采用商空间理论研究了网络结构粒化和粒化后不同粒度空间中的问题,特别是基于粒化如何计算不同粒层的粒间距离问题。应用方面,讨论了大规模网络结构最短路径搜索问题。作为大规模网络路径分析的预处理方法,选择社团作为基本粒,将大规模网络粒化到不同的粒度空间,形成不同粒度商空间的分层递阶粒度链。提出了基于分层递阶粒度链的大规模网络的启发式路径搜索方法。与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.