Research Of Community Detecting Algorithms Based On SCAN

Community detecting is one of the most important research fields in complex network analysis. Detecting communities in complex networks can be used in many research fields. A network consists of several communities. Vertices in community are densely connected to each other while vertices in different communities are connected sparsely. Community structure is one of the earliest found characters of networks by researchers. It is useful to understand the structure of networks. SCAN is an excellent community detecting algorithm proposed in recent years. It is based on structural clustering which is the origin of the name SCAN (Structural Clustering Algorithm for Networks). It is excellent because its linear time complexity, accurate classification results and more information besides the community structure (hub vertices and isolate vertices).Although SCAN has many advantages, its drawback is also obvious. SCAN is one of the traditional community detecting algorithms which based on the assumption that one vertice can and only belong to one community. So SCAN cannot detect overlapping communities (overlapping vertices) while overlapping is a common phenomenon in almost every network. As the online social networks develop very fast this days, detecting communities from dynamic networks is a main trend in community detecting while SCAN lacks the ability. In addition, SCAN needs two manual setting parameters and the result of SCAN is very sensitive to the parameters. Combining with the above content, we propose two algorithms based on SCAN, the specific research results are as follows. (1) The improvements of SCANSCAN needs the two manual setting parameters ε and μ. We optimize the algorithm by parameters. Firstly, we only keep the parameter ε to define core network. Secondly, we design a process named loop edges delete to reduce the sensitivity of the algorithm for the parameter. With a in very large range, our algorithm can obtain acceptable results. (2) The extensions of SCANThis paper extends the overlapping vertices recognition function to SCAN and proposed a new algorithm LED. Loop edges delete process makes community split, we analysis the vertices of edges which are deleted in loop edges delete process using the average degree of community to decide a vertice is an overlapping vertice or not.This paper also extends dynamic network analysis function on the basis of LED. Our algorithm consists of two parts:online and offline. We run static algorithm on the original network and then analyze the maximum affect region. Our algorithm update the middle data by network changes flow. Finally extract the community structure from the middle data and identify overlapping vertices.