Research On Community Detection Algorithm Based On Hierarchical Granulation

Social relationships widely exist in real life and they can be abstracted into a variety of networks. In recent years, the researchers discover that community structure in social network is the basis of analysis and mining in the large-scale network. It has important research significance in the analysis of organizational principle, dynamic characteristics and predicting the behavior of the entity of social system. It has broad application prospect in sociology, biology, and business activities. The research of community detection methods has become an important subject with social and applicable value.How to detect community structure better and faster or how to detect true community structure is the key problem in the study of the social network. This dissertation studies how to achieve the balance between time complexity and accuracy of community detection, and gives a novel idea to detect the true community structure accurately. This dissertation studies the above problem and introduces hierarchical granulation method to achieve the division of community, and proposes two community detection algorithms. One is adjacency granulation based community detection algorithm (AGCDA) and the other is tolerance granulation based community detection algorithm (TGCDA).The main work is summarized as follows:1) The research status of community detection algorithms are carried on the detailed investigation, and the advantages and disadvantages of some classic algorithms are analyzed. At the same time, this dissertation introduces hierarchical granulation method to find community structure better and faster or find true community structure.2) In order to obtain the balance between time complexity and accuracy of community detection, hierarchical granulation method is applied to detecting community and a new community detection algorithm based on adjacency granulation (AGCDA) is proposed. The algorithm initially grains network according to the adjacency relation among the nodes, and then conducts hierarchical granulation constantly until the granulation conditions cannot meet, finally detects the overlapping community structure under the granularity. It can effectively solve the problem that the time complexity and precision is difficult to trade off. The algorithm is compared with several classic algorithms on benchmark and application datasets. The experimental results on benchmark datasets show that the algorithm can obtain modularity 7.6% higher than LPA and time 96% less than NFA. Therefore, AGCDA can achieve the balance between time complexity and accuracy of community detection, and the whole performance is better.3) In order to more accurately detect the true community structure in social network, this dissertation proposes tolerance granulation based community detection algorithm (TGCDA). The algorithm initially grains network according to tolerance relation between nodes, then constantly conducts hierarchical granulation until all nodes are included in one granule, finally detects the overlapping community structure under the granularity which has the biggest tolerance granulation standard. The community with a high density includes at least one maximal tolerance granule that is formed in TGCDA, so it can more accurately detect the true community structure. The effectiveness of TGCDA is tested on artificial and benchmark datasets. The experimental results on benchmark datasets show that the algorithm can obtain NMI accuracy17.5% higher than NFA and on synthetic random networks, the NMI accuracy is also improved. For some networks which have a clear community structure, TGCDA is more effective and can detect more accurate community structure.