High Density Subgraphs Detection Methods In Complex Networks

Study of complex networks has become one of the hottest research fields in data mining. Detecting all high-density subgraphs from given complex networks are fundamentally important for both theoretical researches and practical applications. It can be used to analyze the topological structures, recognize the hidden patterns, even predict the functions and the behaviors of complex networks including biological networks, social networks, World Wide Webs and so on.This thesis proposes two algorithms about detecting high-density subgraphs. The first algorithm MSK is the computing of k-edge connected sub-graphs of network. First, computing the sequence of vertices named L, according to the link densities between vertices. In this process, the strategy of merge vertices is applied to merge two k-edge connected vertices into a super-vertex; and the strategy of early split is applied to improve the efficiency of the algorithm, as soon as the value of one cut is less than k, remove all edges of this cut to split graph. Performing above steps iteratively until graph contains only by isolated vertices, then each super-vertex corresponds to a k-edge connected sub-graph. The thesis gives an approximate algorithm PMSK, to further improve efficiency, the algorithm ignoring the character of k-edge connectivity between vertices changed by applying the strategy of early split. The second algorithm is network clustering detection algorithm which based on a dynamic model of synchronization(SYN). First, sorting vertices in the network by the vertices similarity, each vertice is showed by one-dimensional values, so the network structure is transformed to vector structure. Then, the local synchronization subgraph is found based on the local neighborhood during the synchronization process. By expanding the radius of vertices synchronization, a lot of subgraphs are gotten, by cooperating with the networks module function, the best subgraphs are detected, the result fits in the character that densely inter-connected and sparsely connected to other parts of the network. The algorithm, without depending on any data distribution assumptions, can detect any size of the networks.Extensive experiments on synthetic and real-world data demonstrate that: the algorithm of computing k-edge connected sub-graphs of network MSK is efficient and accurate, PMSK is more efficient than other approximation algorithms; the result which computed by the network community algorithm SYN shows more accuracy than other algorithms, and can effectively select the most stable societies, it can be well applied to the actual network data analysis system.