Research On Network Path Analysis Based On Quotient Space Theory

Quotient Space theory which was proposed by Ling Zhang and Bo Zhang is one of granular computing theories. It is a problem solving theory in artificial intelligence. It can imitate the activity and cognitive thinking process of human intelligence. Quotient Space Theory as a mathematical model, combines the different granularities with the concept of mathematical quotient set and represents a problem by a triplet(X,f,T), where X is the set of our discussing object, namely the universe;f(.) is the attribute function of universe X; T is the structure of universe X namely the interrelations of elements. It's unique contributions that the structure of universe makes topological relationships clear description in universe, complex problem is decomposed to different granular spaces and is solved in different granular spaces, and the original problem's solution is obtained by synthetizing solutions of different granular spaces. These contributions can reduce problem complexity. Quotient space theory, as a granular computing theory, mainly discusses some issues incluing:Issue one:Projection—How to select a suitable grain?Issue two:Deduction—How to problem solving in different granular spaces?Issue three:Synthesis—How to deal with original problem's solution according to solutions of different granular spaces?Two representative principles, false-preserving principle and true-preserving principle, are introduced in Quotient Space Theory. It makes theory and technique indemnity for sloving Issue two and Issue three. However, Issue one can made a deal contacting with particular problems in practical application. Computing paths in a given nework is one of the fundamental problems in graph theory and artificial intelligence and still an important field of research. The scale of network decides complexity of the problem, which is path finding algorithm's "bottleneck". In current research, many scholars have proposed different ways of decomposition method to reduce computational complexity in path finding of massive networks. This dissertation studies network path analysis based on Quotient Space Theory. Applying granular decomposition method, network routing problem is projected different granular quotient spaces which constitute a hierarchical quotient space chain. The solution of network routing problem is synthesized by solutions of different granular quotient spaces. For network path analysis, selecting suitable grains in different type networks are discussed, some path finding algorithms is introdued. At end, a Quotient Space Theory problem solving model of network path analysis is established.The dissertation includes:1. Selecting suitable grains of different type of neworks in Quotient Space Theory is analyzed.In Quotient Space Theory, selecting grain methods include universe-based method, attribute-based method, and structure-based method. Different from other granular computing theories, Quotient Space Theory introduces structure to describe topology information of universe. In different basic types of network (including unweighted network, weighted network, directed network), this dissertation studies selecting grain method based on structure-based method.2. The optimal path finding algorithm based on Quotient Space Theory is put forward.In weight network, according to different edge weights, an equivalence relationship is defined. By this equivalence class as basic granue, weight network is decomposed to different granular spaces which is a quotient space having the same edge weight. Different granular quotient spaces constitute a hierarchical quotient space chain. An optmail path finding algorithm is put forward based on the hierarchical quotient space chain. The optimal path which is a local optimal method achieve global optimal. In simulation datas, experiment results verify the optimal path approximate to the shortest path. In Chengdu city traffic road network, the experiment compares the optimal path's driving routes with the shortest path's driving routes. The experiment result reflects that the optimal path has its own characteristics. 3. The shortest path finding algorithm based on Quotient Space Theory is put forward.In unweight network, according to maximal complete-subgraph, a consistent relationship is defined. By maximal complete-subgraph (covering) as basic granue, unweight network is decomposed to different granular spaces. Different granular quotient spaces constitute a hierarchical quotient space chain. A shortest path finding algorithm is put forward based on the hierarchical quotient space chain in unweight network. Solving maximal complete-subgraph having high computational complexity, the proposed algorithm isn't suit for large and medium-scale network. In a general network, an improved algorithm based on Dijkstra algorithm and Floyd algorithm is put forward. According to the shortest path steps among vertice, all shortest paths between two vertice are searched.4. The shortest path finding algorithm based on community is put forward in massive networks.In massive network analysis, the scale of network is path finding algorithm's "bottleneck". A multi-granular network partitioning method is put forward. As proprecessing works of massive network path analysis, by community as basic granue, a massive network is decomposed to different granular spaces. Different granular quotient spaces constitute a hierarchical quotient space chain. Estimate function of heuristic searching path method is computed based on the hierarchical quotient space chain in a massive network. It resolves the point-to-point shortest path finding in a massive network.In multi-granular network partitioning method, resolving massive network partitioning, a community partition heuristic method of network was proposed. By modularity for the evaluation criteria and network properties of vertice for heuristic information, it makes sub-graph scale similar and sub-graph with community structure. Due to sub-graph scale similar and medium, the proposed method is beneficial effect on the classic graph theory algorithms (such as minimum spanning tree method) of network analysis.In U.S. city transportation road networks of different scales, the result of experiments shows that the proposed methods are effective. Comparing with A*, ALT, the proposed methods have some advantages in point-to-point shortest path finding of massive networks.