Research On Algorithm For Mining Community Based On The Importance Of Node In Complex Networks

Complex networks are ubiquitous in the real world. Community structure is one of the important topological characteristcs of the network. Mining community structure has become a hot research direction in the complex network discipline. It is important for analyzing network functions and properties,discovering the hidden rules and predicting the behavior of the network. Community structure mining has important theoretical significance and application value. In recent years, more and more community structure mining algorithms have been proposed. Based on the expansion of the network size, it is particularly prominent that community mining results are often affected by the initial node location, community size specified in advance and high time complexity. On the basis of the found important node, related research on mining community structure of complex networks has just started.The research of this thesis is based on node importance evaluation of complex network to explore the mining algorithms in association with important nodes, and try to solve or partially solve the common problems in the current classical algorithms.And the proposed algorithms are applied to real networks. The main contributions of this thesis are as follows:(1)In the aspect of node importance evaluation, the current mainstream of the four types of evaluation indicators and a calculation method of comprehensive evaluation index based on Principal Component Analysis are studied. The important nodes distributions for benchmark networks based on different indicators are also given.(2)We proposed a seed node non-overlapping community mining algorithm.Seed nodes are determined according to the central evaluation index, and depth first search strategy is used to divide the global community. For the overlapping nodes between communities, overlapping nodes and the number of edges between two communities are used to solve the attribution problem. Compared with the classical clustering algorithms, the seed node mining algorithm has achieved good communityclassification results on benchmark networks. And the computational complexity of the algorithm is low.(3)Local community mining algorithm based on core node are proposed in this thesis.The important node of network is viewed as core node of initial community. By calculating the similarity between the core node and its neighbor nodes, the local communities are divided. And then the similar local communities are combined to get the final community structure. Compared with the classical community clustering algorithms and the proposed seed node mining algorithm, local community mining algorithm has obvious advantage in terms of performance on benchmark network.(4)The proposed local community mining algorithm is applied to detection the function module of protein-protein interaction network, and the biological significance of the module is analyzed by combining with the gene ontology database.Compared with CPM algorithm and MCODE algorithm, experimental results show that the proportion of the number of protein modules whose match rate are more than50% is higher at the lower node loss rate by using the proposed local community mining algorithm.