We propose a balanced multi-label propagation algorithm (BMLPA) for overlapping community detection in networks. As well as its fast speed, another important advantage of our method is good stability, which other multi-label propagation algorithms, such as COPRA, lack. In BMLPA, we propose a new update strategy, which requires that community identifiers of one vertex should have balanced belonging coefficients. The advantage of this strategy is that it allows vertices to belong to any number of communities without a global limit on the largest number of community memberships, which is needed for COPRA. Also, we propose a fast method to generate “rough cores”, which can be used to initialize labels for multi-label propagation algorithms, and are able to improve the quality and stability of results. Experimental results on synthetic and real social networks show that BMLPA is very efficient and effective for uncovering overlapping communities.
In general, to run BMLPA:
windows: BMLPA.exe -i networkFile [options]
linux: ./BMLPA -i networkFile [options]
Option 1: -p p_value.
Threshold parameter must be in (0, 1]. The default value of p is 0.75.
Option 2: -on2cf n2c_file
Output n2c community file format : vertex and its communities in each line.
Option 3: -oc2nf filename
Output c2n community file format : vertices of a community in each line.
Input and outputs format
Input network file format: list of edges without edge weight and any additional information.
Download BMLPA program and user guide (pdf version)
The source code of BMLPA is released under GNU General Public License.
Seource code:BMLPA-src.tar
Windows binary: BMLPA_Windows_32 BMLPA_Windows_64
Linux binary: BMLPA_Linux_32.tar BMLPA_Linux_64.tar
BMLPA Guide:BMLPA-guide
Wu Zhihao
Aug 29, 2011