Detecting Communities Algorithm In Directed Complex Networks Based On Priori Knowledge

In recent years, the study of complex networks ,which has become a research hotspot today,has been widespread concerned by researchers in physics and other disciplines. Numerous studies have shown that a variety of complex networks have many common structural features in the real world,for example,small-world nature and scale-free nature and community structure,and so on. As the gradual deepening of research which the physical meaning and mathematical characteristics of the nature of complex networks ,it has been found that many networks that exist in the real world have a common nature - Community Structure. In other words, the network is composed of several groups or clusters. It has close connection between nodes In each community,but the connection between the groups and group is relatively sparse.How to efficiently tap these structures on the understanding and analysis of network structure is a very important issue. Such structural characteristics of the network have important influence on the network dynamics, and in a real network, these communities are usually corresponds to a certain functional unit such as the real social groups in social networks,relevant web on the WWW,Papers which cited a specific topic in network. Address the issue of community structure detection in network,In recent years, many researchers were exploring a variety of methods or principles to design the detection algorithm. According to the needs of the study,in chapter 3, the paper systematically has analyzed Some more classic community detection algorithm.In the real world,the real networks often in the form of directed networks,for example, social networks, information networks, technology networks and biological networks, etc. Researches have been observing its structural characteristics and other aspects of property,and carrying out research work in mathematics on the network. It was found that social networks often show small-world characteristics and community structure. An important set of experiments is the famous Milgram "small world" experiment. in chapter 4,the paper has analyzed several typical structure of the directed complex networks in the real world.Previously,by the study of community structure of undirected complex network and detection method,it has found that There is a big flaw in these algorithms when detect directed network community structure. But,there are a large number of the directed network in the real world,such as the Introduced,in chapter 4,information networks, technology networks, biological networks, social networks etc. The strategy of these algorithms is ignoring the direction of the edge in directed network in solving this problem. these algorithms regard directed network as undirected network. This approach, in some cases,has compared good results,however, in most cases, results were not so satisfactory,because the direction of the edge in network contains very important information to network results analysis. It is of great significance to design a targeted community detection algorithm which is able to make us recognize and understand structure and function of real directed complex network.The algorithm emphasized the priori knowledge of the network structure, especially the effect of the node degrees for finding community structure. Specifically, this algorithm first get a initial community network structure based -network node degree , using HITS algorithm based on the center of the point of evaluation methods, that is, the value of a larger hub nodes as the center complete the initial clustering of directed network, then using similar algorithms with the FN of community structure as a sub-network to detect the combined clustering process get the most Q' . The greatest difference from FN algorithm is the algorithm of clustering is not from a single node in the beginning, but from the sub-networks (the initial community) , thus it could reducing the number of iterations the algorithm, the algorithm's time complexity greatly reduce .Accessing to the initial network of community structures requires a certain amount of computation, but it smaller than the amount of the FN iterative calculation. More importantly, this algorithm takes into account the social networks, information networks, and the e-mail network. Network and web links the structural features of the network and its node degree of a priori knowledge introduced in the initial probe into online communities cited by this paper, thereby it expands the scope of application of the algorithm.In the process of exploring the structure of the network society, the descriptive definition can not be directly applied. Therefore, Girvan and Newman define a modular function, Q, quantitative description of the undirected network to measure the community structure of the network division is also often used to measure the similarity between communities. Newman again re-define the module to the network in his article. function is mainly applied to the directed non-right network, through the redefinition of some parameters, it can also be applied to the weighting network.Finally, the algorithm is used in computer-generated with a known community structure as well as some real network.If we deal with the network before, that is, ignoring the information of the direction of the edges. If we take into account the direction of the edge, the proposed algorithm will be applied to this well to the network, and the detect results are very good, only one node is assigned to the wrong communities. Compared our algorithm with the FN method, The results showed that both in the computer-generated networks and the real network, our algorithm are better than that in the performance. In addition, we have tested some real networks by using our algorithms, such as the network quoted the paper, the network to web link.In the past studies, many algorithms have been proposed to analyze the network whose size is not large. when we analyze the large-scale network, the time consumed and the results of the division is often not satisfactory. This problem also exists to the directed networks. Thus, for many researchers, the studies of the algorithms to the network for ultra large-scale societies have considerable significance and challenges.