The Library
Graph matching beyond perfectly-overlapping Erdős–Rényi random graphs
Tools
Tools
Tools
Hu, Yaofang, Wang, Wanjie and Yu, Yi (2022) Graph matching beyond perfectly-overlapping Erdős–Rényi random graphs. Statistics and Computing, 32 (1). 19. doi:10.1007/s11222-022-10079-1 ISSN 0960-3174.
|
PDF
WRAP-Graph-matching-beyond-perfectly-overlapping-Erdos-Renyi-random-graphs-Yu-2022.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (1145Kb) | Preview |
Official URL: http://dx.doi.org/10.1007/s11222-022-10079-1
Abstract
Graph matching is a fruitful area in terms of both algorithms and theories. Given two graphs G1=(V1,E1) and G2=(V2,E2), where V1 and V2 are the same or largely overlapped upon an unknown permutation π∗, graph matching is to seek the correct mapping π∗. In this paper, we exploit the degree information, which was previously used only in noiseless graphs and perfectly-overlapping Erdős–Rényi random graphs matching. We are concerned with graph matching of partially-overlapping graphs and stochastic block models, which are more useful in tackling real-life problems. We propose the edge exploited degree profile graph matching method and two refined variations. We conduct a thorough analysis of our proposed methods’ performances in a range of challenging scenarios, including coauthorship data set and a zebrafish neuron activity data set. Our methods are proved to be numerically superior than the state-of-the-art methods. The algorithms are implemented in the R (A language and environment for statistical computing, R Foundation for Statistical Computing, Vienna, 2020) package GMPro (GMPro: graph matching with degree profiles, 2020).
| Item Type: | Journal Article | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | |||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Statistics | |||||||||
| Library of Congress Subject Headings (LCSH): | Matching theory, Graph theory, Stochastic models, Random graphs | |||||||||
| Journal or Publication Title: | Statistics and Computing | |||||||||
| Publisher: | Springer | |||||||||
| ISSN: | 0960-3174 | |||||||||
| Official Date: | 11 February 2022 | |||||||||
| Dates: |
|
|||||||||
| Volume: | 32 | |||||||||
| Number: | 1 | |||||||||
| Number of Pages: | 16 | |||||||||
| Article Number: | 19 | |||||||||
| DOI: | 10.1007/s11222-022-10079-1 | |||||||||
| Status: | Peer Reviewed | |||||||||
| Publication Status: | Published | |||||||||
| Access rights to Published version: | Open Access (Creative Commons) | |||||||||
| Date of first compliant deposit: | 15 March 2022 | |||||||||
| Date of first compliant Open Access: | 18 March 2022 | |||||||||
| RIOXX Funder/Project Grant: |
|
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
