  Structural Hole (SH) theory states that the node which acts as a connecting
link among otherwise disconnected communities gets positional advantages in the
network. These nodes are called Structural Hole Spanners (SHS). Numerous
solutions are proposed to discover SHSs; however, most of the solutions are
only applicable to static networks. Since real-world networks are dynamic
networks; consequently, in this study, we aim to discover SHSs in dynamic
networks. Discovering SHSs is an NP-hard problem, due to which, instead of
discovering exact k SHSs, we adopt a greedy approach to discover Top-k SHSs. We
first propose an efficient Tracking-SHS algorithm for updating SHSs in dynamic
networks. Our algorithm reuses the information obtained during the initial runs
of the static algorithm and avoids the recomputations for the nodes unaffected
by the updates. Besides, motivated from the success of Graph Neural Networks
(GNNs) on various graph mining problems, we also design a Graph Neural
Network-based model, GNN-SHS, to discover SHSs in dynamic networks, aiming to
reduce the computational cost while achieving high accuracy. We provide a
theoretical analysis of the Tracking-SHS algorithm, and our theoretical results
prove that for a particular type of graphs, such as Preferential Attachment
graphs [1], Tracking-SHS algorithm achieves 1.6 times of speedup compared with
the static algorithm. We perform extensive experiments, and our results
demonstrate that the Tracking-SHS algorithm attains a minimum of 3.24 times
speedup over the static algorithm. Also, the proposed second model GNN-SHS is
on an average 671.6 times faster than the Tracking-SHS algorithm.
