| Graph theory can be traced back to Euler’s study on Konigsberg seven bridges in the17th century. In1960s, two famous mathematicians. Erdos and Renyi introduced random graph theory, which is the base theory of modern complex networks’research. In1998and1999, two papers, which reviewed that most real networks’common attributes:scale-free and small world, were published in Science and Nature, and these two papers builded models to explain the generation mechanism of these characteristics respectively. These two papers’publication also opened up a new era of research on complex net-works. In the new century, cross-cutting between different subjects makes different kinds of networks’data easy to collect, and with the rapid develop-ment of computer science, it is possible for researchers to process large complex network data. Now, researchers focus on the following aspects:research on complex network’s statistical characteristics and its measurement methods and generation mechanism; predicting and controlling the network by analyzing it-s topology:network structure’s stability and dynamic mechanism of network evolution and so on.Community structure is a common character that most real network-s possess. Research on community structure of complex networks plays an important role on analysis of complex networks’topology, understanding the function of the networks and the prediction and control of complex network-s. Communities, or clusterings, are the sets of more tightly interconnected nodes in the network. Till now, scholars have published quite a lot of algo- rithms on community detection, such as Newman’s agglomeration algorithm and divisive algorithm which both are based on modularity, clique percolation method which is designed to detect overlapping communities, and link commu-nity method which is also used for overlapping communities, etc. This paper is a further study on community detection methods of complex networks.k-shell is a new concept in graph, and it has been shown that the nodes in the k-shell with larger k are playing a more important role on graph topology and information spreading in networks than traditionally studied nodes which are of high degrees, and also nodes in the k-shell with the highest k are more likely to be the center of the network. So researches on graph’s k-shell and its attributes are gradually rising. We have the following two definitions:Def1k-core is a minimal subgraph of G, in this subgraph each node’s degree is at least k.Def2Removing k-core’s node set from (k-1)-core’s node set. we get a new node set A, we call the subgraph, which is generated by set A,k-shell. And we denote the k-shell with the largest k as kmax-shell.According to k-shell’s important role on networks’ topology, we use it in community detection methods. Firstly, we combine k-shell and Newman agglomerative algorithm to get a new community detection algorithm. We consider the nodes in kmax-shell as the center of the graph, and then we merge nodes in each k-shell according to k values in descending order to make modu-larity increase the most. After that, we get a community structure with nodes of kmax-shell as the center, then we use Newman agglomerative algorithm in this community structure until all nodes are merged into one community. We choose the one which makes the maximal modularity. Secondly, we combine k-shell and link community algorithm to get a new overlapping community structure algorithm. Because of the important role of k-shell, nodes in kmax-shell are crucial nodes in graph, so are the links adjacent to these nodes. So we give priority to partitioning the community structure of the links which are adjacent to the nodes in kmax-shell. We gradually choose the pair of adjacent edges around the nodes in kmax-shell, which have the highest link similarity and haven’t been considered yet, then merge these two edges’communities into one till all the link communities around the nodes in kmax-shell have more than one edge. After that we gradually reduce the value of k and use the same method to merge all the link communities around the nodes in k-shell. Then we get a link community structure of the network, and we use the original link community algorithm to merge the existing link communities until all links are in one community. At last we choose the link community structure which has the maximal partition density as the result. We use the link community label to mark the link’s two endpoints’community, then we will get the network’s nodes overlapping community structure.After testing these two algorithms using real networks, our algorithms can get better results than the original algorithm without increasing algorithm complexity, and the resulting communities are more meaningful. At last, we extend the concepts of k-shell, modularity, link similarity and partition density to the weighted graph, then we’ll get weighted graph’s community detection based on k-shell. |
