Research Of Local Community Structure Mining In Complex Networks

The rapid development of computer and information technology has brought humans into the Internet age. In human’s daily life, there are electricity networks and metabolic networks that we can’t live without it. To say nothing of the Internet, WWW and scientist cooperation network that we use to get information. Today, human lives in a world full of all kinds of complex networks. These huge networks in the real society attracted the attention of researchers, so they realized the importance of the research of complex networks and pay attention to the research of network topology and the dynamic behavior of networks. In recent years, the BA scale-free network model and WS small-world network model have instead of the random graph, and provide a more accurate description for the real complex systems.Community structure is one of the important features of complex networks. Research on the community structure is useful to deeply understand of the structure of network. Until now, a lot of researchers Plunge into the research of community structure mining and provide varieties of algorithms to detect community structure of societies quickly and accurately. But most algorithms require the network-wide information of network. It is difficult to be used in huge networks. In addition, the contradiction of time complexity of the algorithm and accuracy is also a major course of research. Therefore, research on the community structure need to be further deepened.A measure of local community structure was defined, and an mining algorithm of local community structure was presented for resolving the time complexity problems of finding local community structure in complex networks. The algorithm ran in time O(kd) for general graphs, where d is the mean degree and k is the number of community to be explored. In order to determine its performance and calculation precision, the algorithm was compared with the classical local community identification approach, CNM algorithm. Experimental results show t hat mining results of t he algorithm are as effective as those of CNM algorithm on the whole, and the algorithm is much faster than CNM algorithm.