复杂网络社区发现方法以及在网络扰动中的影响-计算机应用技术专业论文.docx

ABSTRACT One of the fundamental scientific problems of understanding and controlling complex systems is the identification of community structures in complex networks. This problem has attracted more and more researchers from various disciplines. In recent years, the literatures published in Nature and some other top journals show that the hot research topics in community identification still focus on community detection algorithms in scenarios of specific community structure with specific assumptions. This thesis proposes several community structure detection methods for non-overlapping communities and overlapping communities. Furthermore, this thesis analyzes the impact of network perturbation on community detection methods. The innovative achievements of this thesis are as follows: A novel class of semi-suprvised methods for discovering non-overlapping community is proposed, which achieves higher accuracy compared with other non-overlapping community detection methods, especially in the situation where the community structure is obscure. The methods proposed here include semi-supervised method based on label propagation and semi-supervised method based on discrete potential theory. The former via label propagation simulates the dynamic processes of complex networks, and makes the vertices of the same community have the same label. While the latter through potential simulates the delivery processes of circuit networks so that the vertices of the same community have similar potentials. The above two algorithms are both tested on artificial benchmark networks and real networks, the experimental results demonstrate that they are more efficient both on accuracy and time complexity. We propose a novel algorithm for overlapping community detection based on local random walk, which owns higher accuracy and lower time complexity compared with other traditional overlapping community detection methods. The basic idea of this algorithm is converting the community detection