On seeded subgraph-to-subgraph matching: The ssSGM Algorithm and matchability information theory
| Autor: | Meng, Lingyao, Lou, Mengqi, Lin, Jianyu, Lyzinski, Vince, Fishkind, Donniell E. |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | The subgraph-subgraph matching problem is, given a pair of graphs and a positive integer $K$, to find $K$ vertices in the first graph, $K$ vertices in the second graph, and a bijection between them, so as to minimize the number of adjacency disagreements across the bijection; it is ``seeded" if some of this bijection is fixed. The problem is intractable, and we present the ssSGM algorithm, which uses Frank-Wolfe methodology to efficiently find an approximate solution. Then, in the context of a generalized correlated random Bernoulli graph model, in which the pair of graphs naturally have a core of $K$ matched pairs of vertices, we provide and prove mild conditions for the subgraph-subgraph matching problem solution to almost always be the correct $K$ matched pairs of vertices. Comment: 27 pages, 16 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|