Community Detecting Of Multiple Granularity Based On Centrality And Routing Features

A large number of complex systems in nature can be described by complex network. And, community structure is the most important feature of complex network found following the small-world and scale-free feature. Community is a group of closely interconnected nodes in a network, these nodes tend to have certain common characteristics or information indicating the network functional entities. Faced with a large number of target object in networks, we often need to classify these objects in a multi-granularity manner to conduct research or treatment, which requires effective multi-granularity community detecting algorithm. Research on multi-granularity community detecting algorithm in complex network is of great significance.Most traditional community detecting algorithms are based on the assumption that communities do not overlap, and few can find hierarchy community structure of Multiple Granularity. Studies have shown that communities in networks often overlap such that nodes simultaneously belong to several groups, meanwhile, many networks are known to possess hierarchical organization where communities are recursively grouped into a hierarchical structure. Therefore, the traditional community detecting algorithms are not good enough in reflecting real community features. Yong-Yeol Ahn et al. has proposed an community detecting algorithm which is based on link clustering and it can find overlapping community structure with multi-granularity.Based on link clustering method, we use four different centralities as factor to redefine the link similarity, i.e., transforming the link clustering process in the algorithm to develop a new algorithm. This allows us to detect overlapping community structure of multiple granularities better than the original algorithm on the Internet and other types of networks.There is relatively few study focus on community structure in internet network. What’s more, link frequency probed in a cycle for a link which connects two different communities is always large. Thus we propose a community detecting algorithm which redefines link similarity with routing features to transform the link clustering process. This gives us a better community structure in internet topology. Link betweenness is similar to link frequency probed in a cycle in nature, so implement the modified algorithm using link betweenness instead of link frequency probed in a cycle can also achieve better community structure in other networks of different type.We also presents a comprehensive evaluation method for community detecting algorithms synthesizing four kinds of evaluation index that commonly used in international academic research. We select eight real networks of different types and sizes as a test data set; evaluate the algorithm using the comprehensive evaluation method, and derived a conclusion:the community detecting algorithm of multi-granularity based on the centrality and routing features can find community structures better than the original algorithm.