Strong and weak random walks on signed networks
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 exte...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Springer Nature
2025
|
| _version_ | 1824459111467581440 |
|---|---|
| author | Babul, SA Tian, Y Lambiotte, R |
| author_facet | Babul, SA Tian, Y Lambiotte, R |
| author_sort | Babul, SA |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2025-02-19T04:36:35Z |
| format | Journal article |
| id | oxford-uuid:9724078f-5b00-4322-b717-4dcaaad6557c |
| institution | University of Oxford |
| language | English |
| last_indexed | 2025-02-19T04:36:35Z |
| publishDate | 2025 |
| publisher | Springer Nature |
| record_format | dspace |
| spelling | oxford-uuid:9724078f-5b00-4322-b717-4dcaaad6557c2025-02-03T09:17:08ZStrong and weak random walks on signed networksJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:9724078f-5b00-4322-b717-4dcaaad6557cEnglishSymplectic ElementsSpringer Nature2025Babul, SATian, YLambiotte, RRandom 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. |
| spellingShingle | Babul, SA Tian, Y Lambiotte, R Strong and weak random walks on signed networks |
| title | Strong and weak random walks on signed networks |
| title_full | Strong and weak random walks on signed networks |
| title_fullStr | Strong and weak random walks on signed networks |
| title_full_unstemmed | Strong and weak random walks on signed networks |
| title_short | Strong and weak random walks on signed networks |
| title_sort | strong and weak random walks on signed networks |
| work_keys_str_mv | AT babulsa strongandweakrandomwalksonsignednetworks AT tiany strongandweakrandomwalksonsignednetworks AT lambiotter strongandweakrandomwalksonsignednetworks |