Strong and weak random walks on signed networks

Journal article

Random walks are essential for analyzing complex networks. On signed networks, where edges can be positive or negative, designing random walks that capture signed community structure is challenging. Communities in signed networks typically have predominantly positive internal edges and negative external edges. While prior methods focus on strong balance (two communities), this scenario is rare in empirical networks. We introduce a random walk framework tailored to weak balance, accommodating networks with more than two communities. This approach generates a similarity matrix that enables effective community detection. Comparing strong and weak walks on synthetic and empirical networks, we demonstrate that weak walks outperform strong walks in scenarios involving more than two communities or asymmetric link densities. Our findings suggest that replacing strong walks with weak walks could enhance other signed network random-walk algorithms, broadening their applicability to more realistic network structures.

Authors: Babul, SA; Tian, Y; Lambiotte, R

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Springer Nature
• Journal: npj Complexity
• Volume: 2
• Issue: 1
• Article number: 4
• Publication date: 2025-02-03
• Acceptance date: 2024-12-30
• DOI: 10.1038/s44260-025-00027-1
• EISSN: 2731-8753
• Language: English