The Research Of Community Detection Based On Incremental Clustering Algorithm On Dynamic Social Network

With the development of Internet technology, the research outcome of network technology became one indispensable part of people’s lives. The appearance of Micro letter, QQ, microblogging, blog, forum, email and other achievements of modern network communication technology make the relation of people form many complex networks, and these networks often hide a lot of valuable information. Social network analysis approach uses mathematical methods, graph theory, physics and other methods mining the relation of social network. Community detection method can dig out the set of nodes which closely connection in network, can help people to mine valuable information in social network, and it has become an important part of the social network analysis methods. Previously, since the limitations of network size and understanding of network community structure, the attention of researchers focused on small-scale static social network community detection. With the dramatic increase of network size and the intensive study of the community detection, the dynamic characteristic of network emerges, and the research of static community detection has been unable to meet the demand of the instantaneity and continuity of network community.The main research work of this thesis is aimed at large scale social network and puts forward a fast community detection based on incremental clustering framework. The framework includes two algorithms one is CCDE algorithm, another is FICET algorithm. CCDE algorithm is used to detect community structure in large-scale static network. FICET algorithm is used to detect dynamic evolution trend and track club in dynamic network. There are several innovative results achieved in this thesis showing as follows:(1) This thesis proposes the static community detection(CCDE) algorithm which based on the core community extending. CCDE algorithm uses the modified PageRank algorithm to obtain core network nodes in order to forming the core of network. Then we designed this CCDE algorithm to get the core community of network adopting hierarchical clustering method. At last, this algorithm extends to give the overall structure of the network society. By introducing the concept of core network and core organizations, comparing the experiments with the classic static community detection algorithms in real data sets, it shows that the algorithm has good accuracy of test results and high efficiency. This also indicts that CCDE algorithm can suitable for large-scale network detecting.(2) This thesis also presents the dynamic community detection(FICET) algorithm which based on incremental clustering. Based on CCDE algorithms, FICET algorithm research dynamic community detection problem. FICET algorithm introduces the concept of community structure stability, processes the change of the nodes and edges in core network node of neighboring time incrementally, and quickly get to the core community structure in the current network time. After that the algorithm expands to gain the overall network community structure. The experiments on the simulation data sets and real network data sets, compared with classic dynamic community detection algorithm shows that the algorithm can emerge better accuracy and higher time efficiency. This also proves that the algorithm can be used into the network which is change slowly, the network which is highly evolving, and can cope with large-scale dynamic network as well.