Research On Community Identification And Dynamic Evolution In Complex Networks

Community identification and dynamic evolution in complex networks, which exist in many different fields of study, have been playing a more and more important role in people's everyday life. This dissertation presents three algorithms to detect community structure in complex networks, the first algorithm improves traditional spectral decomposition method, and the two algorithms take full advantage of line graph to find community.Traditional spectral decomposition algorithm performs a bisection of the networks. Partitions into more than two clusters are usually attained by iterative bisectioning. we present a node-based spectral decomposition algorithm (NSDA) to find multi-community. There are three steps in NSDA:Firstly, some special nodes and local gathered structures are pre-processed. Secondly, we establish Laplace matrix and utilize three eigenvectors that are corresponding to the three special eigenvalues to obtain the graph of node distribution in a 3-dimensional coordinate system. Thirdly, we determine threshold of community structure in a 3-dimensional coordinate system, to find the members of the community. This dissertation presents an improved NSDA, which refer to Edge-based Spectral Decomposition Algorithm (ESDA). It takes advantage of line graph to find overlapping community. ESDA of community follows the three steps: firstly, the ESDA transform from origin graph to line graph. Secondly, ESDA apply NSDA to obtain community division of line graph.Thirdly, we transform from community division of line graph to community division of original networks to achieve overlapping community and determine members of the community.Line graph again is applied to dynamic evolution of community; we put forward a heuristic hierarchy and aggregation algorithm of line graph.The method has four steps: firstly, these nodes with low semantic similarity want to be pretreated in an original complex networks. Secondly, historical value and temporal value of networks are calculated with factorαto obtain integrated graph of weighted networks, then it is converted into line graph of weighted networks. Thirdly, a certain proportion of nodes with high semantic similarity are polymerized with its closest friend nodes, and then all nodes are stratified, to achieve the members of community. Fourthly, more importantly, the method gradually merges some communities into higher-level ones as compared to the corresponding weighted modularity, to find a potentially better exploitation of the structural community of complex networks.