Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2502.11396 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913692688318464 |
|---|---|
| author | Goel, Diksha Shen, Hong Tian, Hui Guo, Mingyu |
| author_facet | Goel, Diksha Shen, Hong Tian, Hui Guo, Mingyu |
| contents | Structural Hole (SH) spanners are the set of users who bridge different groups of users and are vital in numerous applications. Despite their importance, existing work for identifying SH spanners focuses only on static networks. However, real-world networks are highly dynamic where the underlying structure of the network evolves continuously. Consequently, we study SH spanner problem for dynamic networks. We propose an efficient solution for updating SH spanners in dynamic networks. Our solution reuses the information obtained during the initial runs of the static algorithm and avoids the recomputations for the nodes unaffected by the updates. Experimental results show that the proposed solution achieves a minimum speedup of 3.24 over recomputation. To the best of our knowledge, this is the first attempt to address the problem of maintaining SH spanners in dynamic networks. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_11396 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Maintenance of Structural Hole Spanners in Dynamic Networks Goel, Diksha Shen, Hong Tian, Hui Guo, Mingyu Social and Information Networks 68R10 (Graph Theory) Structural Hole (SH) spanners are the set of users who bridge different groups of users and are vital in numerous applications. Despite their importance, existing work for identifying SH spanners focuses only on static networks. However, real-world networks are highly dynamic where the underlying structure of the network evolves continuously. Consequently, we study SH spanner problem for dynamic networks. We propose an efficient solution for updating SH spanners in dynamic networks. Our solution reuses the information obtained during the initial runs of the static algorithm and avoids the recomputations for the nodes unaffected by the updates. Experimental results show that the proposed solution achieves a minimum speedup of 3.24 over recomputation. To the best of our knowledge, this is the first attempt to address the problem of maintaining SH spanners in dynamic networks. |
| title | Maintenance of Structural Hole Spanners in Dynamic Networks |
| topic | Social and Information Networks 68R10 (Graph Theory) |
| url | https://arxiv.org/abs/2502.11396 |