Research And Implementation Of Dynamic Overlapping Community Discovery Algorithm

With the development of e-communication and social media and other technologies,there are massive data relationships which highly complex and map the actual.Such relational data are represented as a Graph,and in practice such graphs are generally called Network(Social Network).In the study of complex networks,statistical features such as scale-free properties,small-world effects,and clustering properties are found on the networks.Community discovery(community detection)is often used to reveal the clustering behavior of nodes and is one of the important methods of Social Network Analysis(SNA).In real complex networks,nodes may belong to different communities and the community affiliation of nodes will keep changing with the change of relationships,i.e.,communities have overlapping and dynamic characteristics.In this thesis,we focus on the overlapping and dynamic characteristics of communities on real complex networks,enabling the application of community discovery-based network analysis methods to all levels of the network,from global to local.The main research results are as follows.1.A similarity network construction method based on percolation theory is proposed.For data types without definite relationships,the data are converted into feature vectors of nodes by assigning relationships,and the node similarity matrix is generated by using the cosine similarity function,and then the similarity threshold is set by using network percolation theory analysis to convert the node similarity matrix into a network adjacency matrix,so as to generate an unweighted undirected graph.2.A community discovery algorithm based on hierarchical-merging is proposed.By using the "hierarchical strategy",all the maximal cliques on the network are divided into different layers according to their sizes,and then the largest layer is used to fuse the cliques of all layers step by step through the "merging strategy",so that all the communities on the network are divided into hierarchical communities with "core-edge" structure.The hierarchical-merging community discovery algorithm takes into account the overlap and dynamics of the communities,while effectively detecting overlapping nodes and maintaining the stability of the algorithm results,so that it can be applied to the comparison of dynamic network community structures.Meanwhile,the hierarchical-merging community discovery algorithm can also represent the importance of nodes through different layers,allowing the network to be microscopically analyzed down to the node level.3.A community similarity calculation method based on "core members" is proposed,which improves the evolutionary analysis framework based on independent communities and makes it applicable to the evolutionary analysis of hierarchical communities.And the feasibility of macro-analysis of network evolution and micro-analysis of network evolution through community evolution sequence is verified through experiments.