论文标题
通过图神经网络在动态网络中发现结构孔跨度
Discovering Structural Hole Spanners in Dynamic Networks via Graph Neural Networks
论文作者
论文摘要
结构孔（SH）理论指出，在其他断开社区之间充当连接链接的节点在网络中具有位置优势。这些节点称为结构孔跨度（SHS）。 SHS有许多应用程序，包括病毒营销，信息传播，社区发现等。提出了许多解决方案来发现SHSS；但是，大多数解决方案仅适用于静态网络。由于现实世界网络是动态网络；因此，在这项研究中，我们旨在在动态网络中发现SHS。发现SHSS是一个NP牢固的问题，因此，我们采用一种贪婪的方法来发现Top-K SHSS。从图形神经网络（GNN）在各种图挖掘问题上的成功中，我们设计了一个基于图神经网络的模型GNN-SHS，以发现动态网络中的SHSS，旨在降低计算成本，同时实现高精度。我们通过详尽的实验分析了所提出的模型的效率，我们的结果表明，所提出的GNN-SHS模型的速度至少比比较方法快31.8倍，并具有相当大的效率优势。
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 NP-hard 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.
