论文标题
链接预测的快速多路图图关联规则
Fast Multiplex Graph Association Rules for Link Prediction
论文作者
论文摘要
多重网络使我们能够研究各种复杂的系统，在这些系统中，节点以多种方式相互连接，例如社交网络中的朋友，家人和同事关系。链接预测是网络分析的分支，使我们能够预测网络的未来状态：将来最有可能出现哪些新连接？在多重链接预测中，我们还问：哪种类型？由于最后一个问题无法通过经典链接预测无法接近，因此我们在这里调查了图形关联规则来告知多重链接预测的使用。我们通过通过多重图挖掘确定网络中的所有频繁模式来得出此类规则，然后通过在原始网络中找到每个规则的出现来评分每个未观察到的链接的可能性。关联规则为多重链接预测添加了新的能力：预测新的节点到达，考虑具有四个或多个节点的高阶结构，并有效。我们通过创建一个在运行时也有效的框架来改善以前的工作，这可以提高预测性能。效率的提高使我们能够在签名的多重网络上改善案例研究，以表明图形关联规则如何提供有价值的见解来扩展社会平衡理论。
Multiplex networks allow us to study a variety of complex systems where nodes connect to each other in multiple ways, for example friend, family, and co-worker relations in social networks. Link prediction is the branch of network analysis allowing us to forecast the future status of a network: which new connections are the most likely to appear in the future? In multiplex link prediction we also ask: of which type? Because this last question is unanswerable with classical link prediction, here we investigate the use of graph association rules to inform multiplex link prediction. We derive such rules by identifying all frequent patterns in a network via multiplex graph mining, and then score each unobserved link's likelihood by finding the occurrences of each rule in the original network. Association rules add new abilities to multiplex link prediction: to predict new node arrivals, to consider higher order structures with four or more nodes, and to be memory efficient. We improve over previous work by creating a framework that is also efficient in terms of runtime, which enables an increase in prediction performance. This increase in efficiency allows us to improve a case study on a signed multiplex network, showing how graph association rules can provide valuable insights to extend social balance theory.
