Research On Overlapping Community Detection Algorithms Based On Probabilistic Model

Many complex systems in the real world such as social networks and biological networks can be represented as the form of networks. Entities in such systems can be denoted by nodes and the relationships between them can be denoted by links. With the development of the research in this area, many interesting properties have been revealed such as the small world and power-law properties. Recently, researchers found that networks are are commonly of community structure nature, which indicates that the nodes in the same community tend to be connected more closely than the ones cross different commnities. Discovering this community structure is one of the most important problems in the field of complex networks.Traditional approaches for identifying communities mainly include graph partition and hierarchical clustering, and the second one could be divided into the agglomerative methods and the divisive methods. There are some algorithms based on maximizing the modularity proposed by Newman and Girvan. However, most of these algorithms can only detect non-overlapping communities. Subsequent algorithms were designed to deal with overlapping communities. Recently, researchers proposed methods based on statistical inference to detect overlapping communities. A simple probabilistic algorithm which employs expectation-maximization (SPAEM) can detect overlapping community structure very well.In this paper, we have studied the idea of SPAEM. We found that the algorithms is very slow while dealing with large-scale networks. Firstly, we analyze the time complexity of SPAEM algorithm. Then, we reduce the time complexity by improving the algorithm. In addition, in order to avoid falling into local optimal solutions, we propose a method to initialize the SPAEM algorithm to make it return better results within shorter time.The experimental results on both real networks and synthetic networks show that the improvement is effective. It can get better results than other algorithms in many real network. And for synthetic networks, especially when they are sparse, the improved algorithm performs very well.