.png){kind=icon}
.png){kind=icon}
Return
Efficient Algorithm Based on Non-Backtracking Matrix for Community Detection in Signed Networks
.png){kind=icon}
OA
AI
DOI：10.1109/TNSE.2022.3158030.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Community detection or clustering is a crucial task for understanding the structure of complex systems. In some networks, nodes are permitted to be linked by either positive or negative edges; such networks are called signed networks. Discovering communities in signed networks is more challenging than that in unsigned networks. In this study, we innovatively develop a non-backtracking matrix of signed networks, theoretically derive a detectability threshold for this matrix, and demonstrate the feasibility of using the matrix for community detection. We further improve the developed matrix by considering the balanced paths in the network (referred to as a balanced non-backtracking matrix). Simulation results demonstrate that the algorithm based on the balanced non-backtracking matrix significantly outperforms those based on the adjacency matrix, the signed non-backtracking matrix, and other benchmark algorithms. The proposed (improved) matrix shows great potential for detecting communities with or without overlap.
Keywords:
Image edge detection
Mathematical models
Backtracking
Social networking (online)
Stochastic processes
Proteins
Heuristic algorithms
Community detection
detectability threshold
non-backtracking matrix
signed networks
spectral analysis
Journal
I
IF:
7.9
Papers:
2.5K
Citations:
10.0K