Research On Community Detection Algorithms Based On Indirect Nodes Relationship

Network is an abstract expression of subjects and the relationships among them in the real world system,such as the Internet formed by computers,the social network of human beings and so on.The network inherits the complexity of the real world system.Research on the network will help people understand the complex system.Among thearious network attributes,the community structure is an important medium property that reflects the characteristics of the network.Efficiently detecting the community structure in the network plays a key role in the analysis of complex networks and trend forecasting of the network.In addition,accurate community structure is vary important in improving the relevance of search engine results and the accuracy of recommender systems.At present,researchers have proposed a variety of community detection algorithms in the complex networks.However,there exist many problems in the community structure division such as the randomness,higher complexity and low accuracy.In this paper,I studied static network and dynamic network respectively and proposed several community detection algorithms by introducing indirect relationships of nodes into label propagation,matrix factorization and incremental computation.The proposed algorithms can solve the random and low accuracy problems.The work of the dissertation is supported by the National Natural Science Foundation of China under Grant 61271308 and 61172072,Beijing Natural Science Foundation under Grant 4112045 and the Fundamental Research Funds for the Central Universities 2016YJS029.The main contributions and innovations of the dissertation are as follows:1.This paper studies the label weight problem in traditional propagation algorithm and proposed a community detection algorithm for label propagation based on user similarity.In the traditional label propagation algorithm,the node only selects the label with the highest number of labels in the neighbor users.It considers the same label weight for different users and lacks personalized user label processing.Therefore,the traditional label propagation algorithm has low overallness and accuracy.This study is based on the idea of different similar value among users in real society and introduces the concept of information entropy to calculate the similarity.The similarity of different users is considered for the choice of label in the label propagating process.The label propagating process can reflect the real information interaction mode.It is found that the labelpropagation algorithm can effectively improve the accuracy of the network community structure detection with the information entropy as the measure similarity.2.A community discovery algorithm based on matrix factorization is proposed for binary networks which are sparse.The traditional matrix factorization model dose not consider the physical meaning of the decomposed matrices.The objective function has no features for different decomposed matrices,which will affect the accuracy of community discovery.In order to identify the network structure accurately,we propose different optimization strategies for the two decomposed matrices with different properties,which makes the base matrix close to the orthogonal state,and the membership matrix approximate to sparse matrix.This paper proposed the network preprocessing and optimization of matrix factorization results to obtain the best number of communities.Through experiments,it is found that the proposed algorithm can effectively divide the community structure,and identify network overlay communities and overlapping nodes.3.The dynamic is ofen ignored in the detection of community structure of static network.Thus,it is difficult to identify the dynamic network changes in the community structure.Based on the characteristics of dynamic networks,this paper analyzes the influence of variables in dynamic network on community structure,and proposes an incremental algorithm for community identification in dynamic networks.The algorithm considers the direct and indirect effects of changing nodes of their own community.We also consider the coherent neighborhood propinquity and improve the influence range of variable nodes.Experimental results show that the proposed algorithm has better performance and less running time compared with traditional algorithms.The proposed algorithm can divide better communities structure compared with traditional incremental algorithm.4.This paper established a big data community detection model based on user influence for the large-scale network.The paper proposed a parallel propagation method based on synchronous asynchronous update,which avoided the occurrence of high time consumption and label oscillation.It also improved the Jaccard algorithm to calculate the indirect user influence value.The proposed algorithm extended the range to which the label can spreadand enhance the globality of the label.The simulation results showed that the algorithm proposed in this paper has obvious advantages in average excution time,accuracy and adaptability.