|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'501'711
Articles rated: 2609
20 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Seeded graph matching for large stochastic block model graphs | | Vince Lyzinski
; Daniel L. Sussman
; Donniell E. Fishkind
; Henry Pao
; Carey E. Priebe
; | | Date: |
4 Oct 2013 | | Abstract: | Graph matching is an increasingly important problem in inferential graph
statistics. There are no known efficient exact graph matching algorithms,
though current approximate algorithms achieve excellent performance on numerous
benchmarks, with complexity O(n^3) (n the number of vertices to be matched).
Herein, we present a novel approximate seeded graph matching algorithm
specifically designed to match very large graphs. Our algorithm, the LSGM
algorithm, combines spectral graph embedding with existing state-of-the-art
seeded graph matching procedures. We prove that modestly correlated, large
stochastic block model random graphs are correctly matched through the joint
procedure of spectral embedding and graph matching utilizing very few seeds. We
show that under very mild conditions, our algorithm has complexity O(dn^2),
with potential for significantly faster speed in the sparse regime, ($d$ the
embedding dimension), and demonstrate the effectiveness of LSGM in recovering
the unknown alignment in simulated and real data examples. | | Source: | arXiv, 1310.1297 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER