With the growing number of available social and biological networks, the problem of detecting the network community structure is becoming more and more important which acts as the first step to analyze these data. The community structure is generally regarded as that nodes in the same community tend to have more edges and less if they are in different communities. We propose a simple probabilistic algorithm for detecting community structure which employs expectation-maximization (SPAEM). We also give a criterion based on the minimum description length to identify the optimal number of communities. SPAEM can detect overlapping nodes and handle weighted networks. It turns out to be powerful and effective by testing simulation data and some widely known data sets.

• Received 18 October 2007

DOI:https://doi.org/10.1103/PhysRevE.79.036111