TY - GEN
T1 - Discovering Structural Hole Spanners in Dynamic Networks via Graph Neural Networks
AU - Goel, Diksha
AU - Shen, Hong
AU - Tian, Hui
AU - Guo, Mingyu
N1 - Publisher Copyright:
© 2022 IEEE.
PY - 2022
Y1 - 2022
N2 - 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). SHSs have many applications, including viral marketing, information dissemination, community detection, etc. 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 NPhard problem, due to which, instead of discovering exact k SHSs, we adopt a greedy approach to discover top-k SHSs. Motivated from the success of Graph Neural Networks (GNNs) on various graph mining problems, we 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 analyze the efficiency of the proposed model through exhaustive experiments, and our results show that the proposed GNN-SHS model is at least 31.8 times faster and, on an average 671.6 times faster than the comparative method, providing a considerable efficiency advantage.
AB - 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). SHSs have many applications, including viral marketing, information dissemination, community detection, etc. 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 NPhard problem, due to which, instead of discovering exact k SHSs, we adopt a greedy approach to discover top-k SHSs. Motivated from the success of Graph Neural Networks (GNNs) on various graph mining problems, we 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 analyze the efficiency of the proposed model through exhaustive experiments, and our results show that the proposed GNN-SHS model is at least 31.8 times faster and, on an average 671.6 times faster than the comparative method, providing a considerable efficiency advantage.
KW - Structural hole spanners
KW - dynamic networks
KW - graph neural network
KW - pairwise connectivity
UR - http://www.scopus.com/inward/record.url?scp=85158817771&partnerID=8YFLogxK
U2 - 10.1109/WI-IAT55865.2022.00019
DO - 10.1109/WI-IAT55865.2022.00019
M3 - Conference contribution
AN - SCOPUS:85158817771
T3 - Proceedings - 2022 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology, WI-IAT 2022
SP - 64
EP - 71
BT - Proceedings - 2022 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology, WI-IAT 2022
A2 - Zhao, Jiashu
A2 - Fan, Yixing
A2 - Bagheri, Ebrahim
A2 - Fuhr, Norbert
A2 - Takasu, Atsuhiro
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2022 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology, WI-IAT 2022
Y2 - 17 November 2022 through 20 November 2022
ER -