论文标题
使用确定性步行构建的仅拓扑图索引检测大型精确子图的同构。
Detection of large exact subgraph isomorphisms with a topology-only graphlet index built using deterministic walks
论文作者
论文摘要
我们介绍了第一种仅执行仅拓扑的本地图匹配的算法（又称本地网络对准或子图同构）：浮躁，用于网络拓扑的基本本地对齐。 Blant首先创建了一个有限的高特异性索引，其中包含k = 6-15的连接的k节点诱导子图，称为k-graphlets。该索引的构建方式是确定性的，因此，如果两个网络之间存在重要的共同网络拓扑，则它们的索引可能会重叠。这是关键的见解，它使Blant可以仅使用拓扑信息发现对齐。为了使两个网络保持一致，Blant询问其各自的索引以形成大型高质量的本地对准。 Blant能够发现高达150个节点对的高度相似的比对（S3> = 0.95），最多50％的节点对与其“分配的”全局对应物不同。这些结果与基线相比，基线是一种最新的本地对齐算法，该算法适用于仅拓扑。与基线发现的相似拓扑相似性（S3> = 0.95）相比，此类比对大3倍，与全局比对的比对更大3倍，并且比全局比对多30％（添加剂）。我们希望这样的高地相似性和较低全球相似性的地区可以为全球一致性算法提供互补的见解。
We introduce the first algorithm to perform topology-only local graph matching (a.k.a. local network alignment or subgraph isomorphism): BLANT, for Basic Local Alignment of Network Topology. BLANT first creates a limited, high-specificity index of a single graph containing connected k-node induced subgraphs called k-graphlets, for k=6-15. The index is constructed in a deterministic way such that, if significant common network topology exists between two networks, their indexes are likely to overlap. This is the key insight which allows BLANT to discover alignments using only topological information. To align two networks, BLANT queries their respective indexes to form large, high quality local alignments. BLANT is able to discover highly topologically similar alignments (S3 >= 0.95) of up to 150 node-pairs for which up to 50% of node pairs differ from their "assigned" global counterpart. These results compare favorably against the baseline, a state-of-the-art local alignment algorithm which was adapted to be topology-only. Such alignments are 3x larger and differ 30% more (additive) more from the global alignment than alignments of similar topological similarity (S3 >= 0.95) discovered by the baseline. We hope that such regions of high local similarity and low global similarity may provide complementary insights to global alignment algorithms.
