ABCD: Algorithm for Balanced Component Discovery in Signed Networks
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916566414655488 |
|---|---|
| author | Shebaro, Muhieddine Tešić, Jelena |
| author_facet | Shebaro, Muhieddine Tešić, Jelena |
| contents | The largest balanced element in signed graphs plays a vital role in helping researchers understand the fundamental structure of the graph, as it reveals valuable information about the complex relationships between vertices in the network. The challenge is an NP-hard problem; there is no current baseline to evaluate state-of-the-art signed graphs derived from real networks. In this paper, we propose a scalable state-of-the-art approach for the maximum balanced sub-graph detection in the network of any size. The proposed approach finds the largest balanced sub-graph by considering only the top $K$ balanced states with the lowest frustration index. We show that the ABCD method selects a subset from an extensive signed network with millions of vertices and edges, and the size of the discovered subset is double that of the state-of-the-art in a similar time frame. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_00848 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | ABCD: Algorithm for Balanced Component Discovery in Signed Networks Shebaro, Muhieddine Tešić, Jelena Social and Information Networks Combinatorics The largest balanced element in signed graphs plays a vital role in helping researchers understand the fundamental structure of the graph, as it reveals valuable information about the complex relationships between vertices in the network. The challenge is an NP-hard problem; there is no current baseline to evaluate state-of-the-art signed graphs derived from real networks. In this paper, we propose a scalable state-of-the-art approach for the maximum balanced sub-graph detection in the network of any size. The proposed approach finds the largest balanced sub-graph by considering only the top $K$ balanced states with the lowest frustration index. We show that the ABCD method selects a subset from an extensive signed network with millions of vertices and edges, and the size of the discovered subset is double that of the state-of-the-art in a similar time frame. |
| title | ABCD: Algorithm for Balanced Component Discovery in Signed Networks |
| topic | Social and Information Networks Combinatorics |
| url | https://arxiv.org/abs/2311.00848 |