Maintenance of structural hole spanners in dynamic networks

Diksha Goel, Hong Shen, Hui Tian, Mingyu Guo

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Citation (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationProceedings of the IEEE 46th Conference on Local Computer Networks, LCN 2021
EditorsLyes Khoukhi, Sharief Oteafy, Eyuphan Bulut
PublisherIEEE Computer Society
Pages339-342
Number of pages4
ISBN (Electronic)9780738124766
DOIs
Publication statusPublished - 4 Oct 2021
Externally publishedYes
Event46th IEEE Conference on Local Computer Networks, LCN 2021 - Edmonton, Canada
Duration: 4 Oct 20217 Oct 2021

Publication series

NameProceedings - Conference on Local Computer Networks, LCN
Volume2021-October

Conference

Conference46th IEEE Conference on Local Computer Networks, LCN 2021
Country/TerritoryCanada
CityEdmonton
Period4/10/217/10/21

Keywords

  • Connected components
  • Dynamic networks
  • Pair-wise connectivity
  • Structural hole spanners

Fingerprint

Dive into the research topics of 'Maintenance of structural hole spanners in dynamic networks'. Together they form a unique fingerprint.

Cite this