Subgraph Matching on Multiplex Networks
Subgraph Matching on Multiplex Networks
复制标题
DOI：
10.1109/tnse.2021.3056329
复制
发表时间：
2021-02
影响因子：
6.6
通讯作者：
Jacob D. Moorman;Thomas K. Tu;Qinyi Chen;Xie He;A. Bertozzi
中科院分区：
文献类型：
--
作者：
Jacob D. Moorman;Thomas K. Tu;Qinyi Chen;Xie He;A. Bertozzi
计算科学的一个活跃研究领域是设计算法来解决子图匹配问题，以在更大的世界图中找到给定模板图的副本。先前的工作主要使用各种方法来解决单通道网络。我们提出了一套针对多路网络子图同构的过滤方法（节点之间具有不同类型的边，并且每个通道类型内具有多个边）。我们的目标是了解整个解决方案空间，而不是专注于寻找一种同构。结果显示在几类数据集上：(a) 映射到子图同构问题的数独谜题，(b) Erdős-Rényi 多重图，(c) 来自 Twitter 和交通网络的真实世界数据集，(d) 为 DARPA MAA 计划创建的合成数据。
An active area of research in computational science is the design of algorithms for solving the subgraph matching problem to find copies of a given template graph in a larger world graph. Prior works have largely addressed single-channel networks using a variety of approaches. We present a suite of filtering methods for subgraph isomorphisms for multiplex networks (with different types of edges between nodes and more than one edge within each channel type). We aim to understand the entire solution space rather than focusing on finding one isomorphism. Results are shown on several classes of datasets: (a) Sudoku puzzles mapped to the subgraph isomorphism problem, (b) Erdős-Rényi multigraphs, (c) real-world datasets from Twitter and transportation networks, (d) synthetic data created for the DARPA MAA program.