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

Abstract:  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.

Key words: granular computing, network structure analysis, quotient space theory, shortest path