Community Detection Algorithm Based On Probabilistic Graphical Models

Community detection in networks is to group nodes with similar connectivity patterns.A good community detection scheme should have several properties.First,it should be effective in detecting communities,and effectiveness is usually evaluated by several similarity metrics between detected communities and ground truth communities.Second,it should be applicable in a variety of situations,such as detecting density-based communities as well as pattern-based communities.Third,it should be efficient as the size of the network grows.Since large networks in real world usually exhibit great sparsity,an algorithm which scales linearly with the number of nodes in network or the number of edges in network is preferable.In this paper,we work on probabilistic graphical model-based community detection algorithms.The first step to detecting communities is to model the generative process of the network using graphical models.Traditional graphical models in graph modeling usually suffer from problems,for example some of them are only designed for density-based communities,and some of them are not efficient in large networks.In this paper,the main work on model development and algorithm improvement is as follows:1.We propose a graphical model for graph modeling based on Poisson and Gamma distribution.In our model,the number of connections between nodes is Poisson distributed,and the membership of nodes in each community is Gamma distributed.Compared with traditional graphical models in graph modeling,our model is more reasonable in the explanation of edge generation,and is applicable in pattern-based community detection.2.We use Gibbs sampling to inference the posterior distribution of variables in our model,and we demonstrate theoretically that time complexity of our algorithm scales linearly with the number of edges in network,so our model can be efficient in large sparse networks.3.We further optimize our algorithm in space and running time.We also adjust our algorithm to make it applicable in both directed and undirected networks.At last,we propose a method on dealing with missing data in networks.Experiments demonstrate the accuracy of our model.We also compare our model with traditional models in some datasets.Results show that our model has better performance than traditional graphical models.