MEMO-ESU

使用备忘录并行ESU算法进行子图枚举。

背景

子图枚举是计算特定子图在一个较大图中出现多少次的进程。

这需要遍历图，避免对节点集进行重复计数，并计算每个子图的同构性以增加其丰度。

ESU算法由Wernicke在2005年¹描述，该算法描述了一种类似于DFS的图遍历方法，但只遵循具有较大节点标签的子节点。

这是一个非常快的子图识别方法，但在每个子图识别结束时都会调用NAUTY²来计算子图的规范标签，这是算法的瓶颈。

该程序是ESU算法的rust实现，但增加了一个备忘录步骤，通过散列表示子图邻接矩阵的位向量来避免对NAUTY进行多次调用。它还允许用户在多个线程上并行运行ESU算法以加快枚举速度。

安装

使用Cargo

可以使用cargo（Rust包管理器）进行安装

cargo install memoesu

安装Cargo

您可以使用以下命令安装Rust包管理器cargo

curl https://sh.rustup.rs -sSf | sh

用法

枚举

此工具的基本用法是运行enumerate子命令，该命令至少接受一个纯文本图的路径和要枚举的子图大小。

在以下命令中，我们枚举ecoli图中的所有大小为4的子图。

memoesu enumerate -i example/ecoli.txt -s 4

默认情况下，假设图是有向的，但您也可以强制将图设置为无向并计算所有无向子图。

memoesu enumerate -i example/ecoli.txt -s 4 -u

您还可以指定多个线程，在这种情况下为8。

memoesu enumerate -i example/ecoli.txt -s 4 -t 8

格式

memoesu仅接受具有整数标签的网络。

但是，您可以使用format子命令将带有标签的字符串图重新格式化为整数图

memoesu format -i example/unformatted.txt -o formatted

这将生成两个具有formatted前缀的新文件

formatted.network.tsv 和 formatted.dictionary.tsv

这提供了整数标签的网络和将每个标签与其相应整数关联的字典。

开关

为了计算网络基序，我们首先需要创建一组与原始网络可比的随机图。

我们采用的方法是随机切换方法，最初用于 mfinder 工具，由 Milo³ 描述，该方法描述了一种生成与原始图具有等效度序列的随机图的算法。

要执行切换算法以生成随机图，我们可以使用 switch 子命令

memoesu switch -i example/example.txt

这会创建一个具有与原始图相同度序列的新随机图。

组

NAUTY 正则图的计算也为子图中的每个节点计算轨道信息。为了收集原始图中的每个节点的子图成员资格，以及子图节点标签和轨道，我们可以使用 groups 子命令。

目前，此命令仅作为单线程命令支持。

memoesu groups -i example/example.txt -s 3 -o groups.txt

这将输出一个表格，其列包括

1. 节点索引
2. 子图 graph6 字符串
3. 节点标签（即子图中的位置）
4. 轨道

参考文献

1. S. Wernicke，“高效检测网络基序，”IEEE/ACM Trans. Comput. Biol. and Bioinf.，第 3 卷，第 4 期，第 347–359 页，2006 年 10 月，doi: 10.1109/TCBB.2006.51。
2. B. D. McKay 和 A. Piperno，“实际图同构，II，”Journal of Symbolic Computation，第 60 卷，第 94–112 页，2014 年 1 月，doi: 10.1016/j.jsc.2013.09.003。
3. R. Milo，N. Kashtan，S. Itzkovitz，M. E. J. Newman 和 U. Alon，“关于具有指定度序列的随机图的均匀生成。”arXiv，2004 年 5 月 30 日。访问时间：2023 年 6 月 26 日。[在线]。可在：http://arxiv.org/abs/cond-mat/0312028