The paper proposes an algorithm, COPRA (Community Overlap PRopagation Algorithm), for detecting overlapping communities in large networks. Based on the label propagation technique of Raghavan, Albert, and Kumara, COPRA extends the original algorithm to handle communities that overlap. Each vertex can belong to up to \( v \) communities, where \( v \) is a parameter of the algorithm. The main contributions include extending the label and propagation step to include information about multiple communities and handling weighted and bipartite networks.
The algorithm initializes each vertex with a unique label and then repeatedly updates the labels based on the labels of neighboring vertices. The propagation phase ensures that vertices with the same label are grouped into communities. The algorithm terminates when the number of community identifiers in use reaches a minimum, ensuring convergence.
Experiments on synthetic and real networks show that COPRA is highly effective in recovering overlapping communities. It is also very fast, capable of processing large and dense networks in a short time. The performance of COPRA is compared with other community detection algorithms, and it is found to outperform them in terms of modularity and execution time, especially for larger networks and smaller communities.
COPRA can handle weighted and bipartite networks by modifying the propagation step to allow community identifiers to propagate between modes. The algorithm is guaranteed to terminate and usually produces good solutions. The paper discusses the limitations of the algorithm, such as its nondeterminism, and suggests ways to improve it, including using belonging coefficients for fuzzy community assignments.The paper proposes an algorithm, COPRA (Community Overlap PRopagation Algorithm), for detecting overlapping communities in large networks. Based on the label propagation technique of Raghavan, Albert, and Kumara, COPRA extends the original algorithm to handle communities that overlap. Each vertex can belong to up to \( v \) communities, where \( v \) is a parameter of the algorithm. The main contributions include extending the label and propagation step to include information about multiple communities and handling weighted and bipartite networks.
The algorithm initializes each vertex with a unique label and then repeatedly updates the labels based on the labels of neighboring vertices. The propagation phase ensures that vertices with the same label are grouped into communities. The algorithm terminates when the number of community identifiers in use reaches a minimum, ensuring convergence.
Experiments on synthetic and real networks show that COPRA is highly effective in recovering overlapping communities. It is also very fast, capable of processing large and dense networks in a short time. The performance of COPRA is compared with other community detection algorithms, and it is found to outperform them in terms of modularity and execution time, especially for larger networks and smaller communities.
COPRA can handle weighted and bipartite networks by modifying the propagation step to allow community identifiers to propagate between modes. The algorithm is guaranteed to terminate and usually produces good solutions. The paper discusses the limitations of the algorithm, such as its nondeterminism, and suggests ways to improve it, including using belonging coefficients for fuzzy community assignments.