Efficient Community Detection For Network Data Based On Active Learning

Many complex systems in the real-world can be abstracted as a complex network, suchas computer email network, biological protein network, gene express network, etc. There aresome statistic features in those complex networks, such as small world effect, scale-freeproperty, community structure, etc. Community detection is important for theunderstanding of the topology structure of the network, the analysis of the function of thecomplex system, detecting the latent pattern of the network and the prediction about thefuture behavior of network both in theory and in application.In the past decade, researchers from math, physic, statistic physic have developedmany community detection algorithms. Some of those algorithms are based on graphpartition; some are based on optimization of modularity function, dynamic algorithm andother algorithms based on statistic inference, etc. Among all those algorithms, block modelhas become the research s focus as it offers more principle approach to community detectionand its ability to detecting any type of network structure in principle.In this works, we study the community detection problem and based on active learning,block model and Gibbs sample, we modify an existent algorithm. We also come out with ournew method. Our main contribution is as follows:(1) Modified an existent community detection algorithm which is based on activelearning and block model and then proposed a modified version. We adjust the originalGibbs sample to greedy Gibbs sample, and try to fit the true distribution according thelikehood of local extremum. In this way we largely decrease the cost time, and the efficiencywould be significant improved while still guaranteeing the accuracy.(2) We also make modification in the active learning strategy used by algorithm in work(1). The original algorithm try to detect community structure based on active learning on thelabel of nodes. However, we have noticed that in many real world networks, that informationis hard to acquire while information about the relationship of two nodes is ready to collect.We propose an algorithm and use active learning strategy to acquire this kind of information.By this way, our algorithm is more applicable. (3) We verity our algorithm on both real-world network and artificial synthetic networkand make comparison with the original algorithm on accuracy and efficiency. The resultshows that our modified algorithm in work (1) can largely improve the efficiency andsignificantly reduced the runtime while still guarantee a satisfied accuracy. The modifiedalgorithm we proposed in work (2) is a generalization of the original algorithm, thus is moreapplicable in real network.