Research On Some Issues Of Community Detection In Complex Networks

Many systems in the real world can be represented as networks,such as biological systems,social systems and transportation systems,etc.However,these networks are often too complex for people to understand directly.Complex network analysis has important research significance since it is helpful for people to understand the intrinsic mechanism of networks.Community detection is an important content of complex network analysis since it is helpful for people to understand the intrinsic organization structure and connection pattern of the network,thus guiding practice,such as infectious disease prevention and control,public opinion monitoring,traffic planning,optimal allocation of distribution network resources,etc.Therefore,the study on community detection has important theoretical significance and practical value.Community detection has attracted wide attention of scholars.However,how to further improve the accuracy and efficiency of community detection remains a challenge.In this paper,community detection is studied and the corresponding algorithms are proposed.The main research contents include: community detection in signed networks based on the Signed Stochastic Block Model and the exact Integrated Complete data Likelihood(ICLex),community detection in dynamic networks based on statistical inference,batch mode active learning based on statistical model on network node classification,and community detection based on moth-flame optimization.The specific work and contributions of this paper are as follows:Firstly,for community detection in signed networks,a method SSBMI(Signed Stochastic Block Model and ICLex)based on statistical inference and ICLex is proposed in this paper.To the best of our knowledge,this is the first time that ICLex is used to solve the problem of community detection in signed networks.At first,the ICLex for the Signed Stochastic Block Model SSBM is derived.Then,a greedy search is employed to optimize the value of the derived ICLex for signed networks to find communities.In contrast to the signed network community detection method SSL based on statistical inference published on AAAI 2015,SSBMI does not need to estimate the models one by one from the model space and select the best among the estimated results for model selection,which saves a large amount of calculation.SSBMI does not require prior knowledge of network structure,which reduces using threshold,and makes fitting mainly data-driven.The experimental results on synthetic networks and real network data show that SSBMI can find communities in signed networks more accurately than several competing methods such as SSL and moreefficiently than SSL.Secondly,for community detection in dynamic networks,a community detection method DSBMC(Dynamic Stochastic Block Model with Constraints)for dynamic networks based on statistical inference is proposed in this paper.A new dynamic Stochastic Block Model is proposed at first.The model uses transition probabilities to model the dynamic changes of node community assignments.And in this model,all the nodes share the same community transition probability,all nodes within communities share the same link probability,and all nodes between the communities share the same link probability.Then,based on Bayesian inference and Gibbs sampling,a learning method of the model is given.Experiments on synthetic and real data show that our method can achieve higher accuracy in community detection than several current competing algorithms.Thirdly,in order to improve the efficiency of active learning working in single node mode for network node classification,a batch mode active learning method based on statistical model BALN(Batch Active Learning for Networks)on node classification in assortative and disassortative networks is proposed.BALN uses mutual information and random walk to select a batch of nodes at a time to label.BALN can be used for node classification in assortative and disassortative networks.BALN only uses network topology as input data,does not need to know the number of blocks in the network structure in advance,and makes no initial assumptions about how the blocks connect.On two different types of networks: assortative structure and diassortative structure,BALN is compared with Moore method working in single node mode and several batch mode active learning methods using mutual information and simple heuristics.The experimental results show that the query times of BALN are significantly fewer than that of the Moore method under the same number of query nodes and almost the same accuracy,and at the same query cost,the accuracy of BALN is higher than those of these batch mode active learning methods using mutual information and simple heuristics.Finally,for community detection in unsigned networks,a method based on the moth-flame optimization MFOCD(Moth-Flame Optimization based Community Detection)is proposed in this paper.This method uses string coding to redesign the individual representation of the moth-flame optimization,and combines single point crossover,mutation and mountain climbing algorithm to redesign search of the moth-flame optimization,which makes moth-flame optimization suitable for community detection.Comparing with several current competing algorithms on synthetic and real data shows that the proposed method can achieves higher accuracy in community detection than these methods.