Research On Overlapping Community Discovery Algorithm Based On Average Mutual Information

In recent years,the convergence and development of Internet and the Internet of Things has attracted many scholars to study complex networks.Studying complex networks has important values in many fields,such as it can discover the protein complexes in biology,recommend the commodity to customers and prevent the criminal activities.Based on the ideas of maximizing average mutual information and maximal clique expansion,the thesis proposes a new community discovery algorithm MCGE and parallelization algorithm P-MCGE.The main research of the thesis is as follows:(1)For the lower accuracy of the existing local expansion algorithms,average mutual information is introduced to measure the node information of complex networks,and it improves the accuracy finally;(2)For the existing local expansion algorithms only can be applied to discover the overlapping community structures,the overlapping nodes were divided into single community to gain the nonoverlapping community structures;(3)For the situation that complex network may exist lots of isolated nodes after the discovery of existing local expansion algorithms,we maximize the division of these isolated nodes in complex networks;(4)For the time-consuming problem of MCGE algorithm to handle large networks,P-MCGE is proposed by introducing Open MP to parallelize the original algorithm,and the experiment shows that the efficiency of P-MCGE to handle large networks is promoted significantly.The thesis conducts the experiments on some typical datasets of real world and synthetic network,in the experiments of non-overlapping community discovery,the evaluation criterion NMI is adopted,the experimental results indicate that the algorithm of the thesis is superior to FN,GN,IE,LPA,etc.In the experiments of overlapping community discovery,two evaluation criterions,NMI and the improving overlapping modularity,are used.The experimental results show that the algorithm of the thesis gains the best performance in whole,comparing with LFM,CFinder,HMLPAi,GCE,OCDDP,SLPA,COPRA,Speak Easy,Multiscale,CMNN,etc.