Stochastic Solutions for Dense Subgraph Discovery in Multilayer Networks
Stochastic Solutions for Dense Subgraph Discovery in Multilayer Networks
复制标题
DOI：
10.1145/3539597.3570444
复制
发表时间：
2022-11
期刊：
影响因子：
--
通讯作者：
Yasushi Kawase;Atsushi Miyauchi;Hanna Sumita
中科院分区：
文献类型：
--
作者：
Yasushi Kawase;Atsushi Miyauchi;Hanna Sumita
网络分析在知识发现和数据挖掘中发挥着重要作用。在近年来的许多实际应用中，我们对挖掘多层网络感兴趣，其中我们有许多称为层的边集，这些边集编码同一组顶点上的不同类型的连接和/或时间相关连接。在众多的网络分析技术中，稠密子图发现是一种重要的网络分析技术，其目的是发现网络中的稠密分支，在不同的领域有着广泛的应用。本文提出了一种新的多层网络中稠密子图发现的优化模型。我们的模型旨在找到随机解，即，在顶点子集族上的概率分布，而不是单个顶点子集，然而它也可以用于获得单个顶点子集。对于我们的模型，我们设计了一个基于LP的多项式时间精确算法。此外，为了处理大规模的网络，我们还设计了一个简单的，可扩展的预处理算法，这往往会显着减少输入网络的大小，并在一个显着的加速结果。计算实验证明了模型的正确性和算法的有效性。
Network analysis has played a key role in knowledge discovery and data mining. In many real-world applications in recent years, we are interested in mining multilayer networks, where we have a number of edge sets called layers, which encode different types of connections and/or time-dependent connections over the same set of vertices. Among many network analysis techniques, dense subgraph discovery, aiming to find a dense component in a network, is an essential primitive with a variety of applications in diverse domains. In this paper, we introduce a novel optimization model for dense subgraph discovery in multilayer networks. Our model aims to find a stochastic solution, i.e., a probability distribution over the family of vertex subsets, rather than a single vertex subset, whereas it can also be used for obtaining a single vertex subset. For our model, we design an LP-based polynomial-time exact algorithm. Moreover, to handle large-scale networks, we also devise a simple, scalable preprocessing algorithm, which often reduces the size of the input networks significantly and results in a substantial speed-up. Computational experiments demonstrate the validity of our model and the effectiveness of our algorithms.