Graph matching beyond perfectly-overlapping Erdős--Rényi random graphs

DOI10.48550/ARXIV.2006.03284zbMATH Open1482.62013OpenAlexW4211244437MaRDI QIDQ136800FDOQ136800

Authors: Yaofang Hu, Wanjie Wang, Yi Yu, Yaofang Hu, Wanjie Wang, Yi Yu 

Publication date: 5 June 2020

Published in: Statistics and Computing (Search for Journal in Brave)

Abstract: Graph matching is a fruitful area in terms of both algorithms and theories. In this paper, we exploit the degree information, which was previously used only in noiseless graphs and perfectly-overlapping ErdH{o}s--R'enyi 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 varations. We conduct a thorough analysis of our proposed methods' performances in a range of challenging scenarios, including a zebrafish neuron activity data set and a coauthorship data set. Our methods are proved to be numerically superior than the state-of-the-art methods.

Full work available at URL: https://arxiv.org/abs/2006.03284

Recommendations

• Efficient random graph matching via degree profiles
• Exact matching of random graphs with constant correlation
• Settling the Sharp Reconstruction Thresholds of Random Graph Matching
• Seeded graph matching for correlated Erdős-Rényi graphs
• Graph Matching Based on Stochastic Perturbation
• Random-link matching problems on random regular graphs
• A Fast Perfect-Matching Algorithm in Random Graphs
• Inexact graph matching by means of estimation of distribution algorithms
• Perfect matchings in random intersection graphs

zbMATH Keywords

stochastic block modelsdegree profilegraph matchingpartially-overlapping graphs correlated Bernoulli networks

Mathematics Subject Classification ID

Computational methods for problems pertaining to statistics (62-08) Small world graphs, complex networks (graph-theoretic aspects) (05C82)

Cites Work

• Title not available (Why is that?)
• Random Dot Product Graph Models for Social Networks
• Fast community detection by SCORE
• Efficient random graph matching via degree profiles
• An Algorithm for Subgraph Isomorphism
• A distance measure between attributed relational graphs for pattern recognition
• Title not available (Why is that?)
• Vertex nomination via seeded graph matching
• Coauthorship and citation networks for statisticians
• Seeded graph matching for correlated Erdős-Rényi graphs
• Power balance and apportionment algorithms for the United States Congress
• Improved random graph isomorphism

Cited In (9)

• GMPro
• Title not available (Why is that?)
• Seeded graph matching for correlated Erdős-Rényi graphs
• Inexact graph matching using a hierarchy of matching processes
• Efficient random graph matching via degree profiles
• Matchability of heterogeneous networks pairs
• Spectral graph matching and regularized quadratic relaxations. II: Erdős-Rényi graphs and universality
• Information Recovery in Shuffled Graphs via Graph Matching
• Exact matching of random graphs with constant correlation

Uses Software

• R
• igraph

This page was built for publication: Graph matching beyond perfectly-overlapping Erdős--Rényi random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q136800)