An Overlapping Community Detection Algorithm Based on Triangle Reduction Weighted for Large-Scale Complex Network

In this digital age, dramatically developed internet makes the data of complex networks appear an explosive growth, which aggrandizes the importance of multilevel community detection used in large-scale complex networks. Nowadays, there are so many community detection algorithms that could perform well on accuracy. However, none of them has an expected function to handle the time increasing problem which is caused by the inflated network scale. Hence, we propose An Overlapping Community Detection Algorithm based on Triangle Reduction Weighted for Large-scale Complex Network (TRWLPA). It consists of two main steps: 1) Transforming the original network to a small-scale triangle reduction network. This network could not only dramatically reduce the running time of community detection, but recover the original network structure by the inverse transformation. Moreover, the scale of the triangle reduction network could be controlled by setting the iteration times. 2) Doing the multi-label propagation on the reduced networks where the weight of each node is the number of initial nodes it contains. The experiments illustrate that the TRWLPA algorithm significantly reduces the running time of community detection on Youtube, DBLP, and LiveJournal datasets. Particularly, comparing with the MOSES algorithm, it achieves 98.1% running time reduction on the Youtube dataset. Furthermore, our algorithm performs well on both modularity and Normalized Mutual Information measure (NMI).