A Maximal Clique Partition Method for Network Based on Granularity

With regard to large-scale network, the classical methods are not suitable for resolving the problems of network analysis, which is due to large space demanding and time consuming. Most of large-scale networks have the feature of community structure in the area of complex network. Sub graphs of the original network have closer relations within them while estranged one between any two sub graphs. Therefore, we could divide a large-scale network into some smaller counterparts in terms of maximal clique in graph theory. Granular computing simulate human´s thought of solving complex problems and granularity decomposition method is good for resolving the complex problems under large-scale networks. Each of the sub graphs divided on the basis of maximal clique theory can be regarded as a coarse granularity. Meanwhile, by modularity for evaluation criteria and network properties of node for heuristic information, it makes sub graph scale similar and sub graph with community structure. The proposed method is effective for the classic graph theory algorithm of network analysis, such as the algorithm of finding the shortest path, because the graph scale is smaller and it is similar within the sub graph. Due to sub graph with community structure, there are less connection among sub graphs and it is suitable for granular computing method. The result of our experiments show that the proposed method is efficacious to divide a large-scale network with keeping the its community structure.