Efficient random graph matching via degree profiles

DOI10.1007/s00440-020-00997-4zbMath1460.05171arXiv1811.07821OpenAlexW3088419579MaRDI QIDQ2660385

Zongming Ma, Yihong Wu, Jiaming Xu, Jian Ding

Publication date: 30 March 2021

Published in: Probability Theory and Related Fields (Search for Journal in Brave)

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

zbMATH Keywords

quadratic assignment problemgraph matchingErdős-Rényi graphdegree profilesrandom graph isomorphism

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (10)

Iterative algorithm for discrete structure recovery ⋮ Correlated randomly growing graphs ⋮ Maximum Likelihood Estimation and Graph Matching in Errorfully Observed Networks ⋮ Spectral alignment of correlated Gaussian matrices ⋮ Aligning random graphs with a sub-tree similarity message-passing algorithm ⋮ Exact matching of random graphs with constant correlation ⋮ Testing correlation of unlabeled random graphs ⋮ Matching recovery threshold for correlated random graphs ⋮ Unnamed Item ⋮ Graph matching beyond perfectly-overlapping Erdős--Rényi random graphs

Uses Software

• IsoRank

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers
• Some inequalities relating to the partial sum of binomial probabilities
• Improved random graph isomorphism
• Semidefinite programming relaxations for the quadratic assignment problem
• Central limit theorems for the Wasserstein distance between the empirical and the true distributions
• A sharp estimate of the binomial mean absolute deviation with applications
• The graph matching problem
• Graphs on unlabelled nodes with a given number of edges
• A Complete Proof of Universal Inequalities for the Distribution Function of the Binomial Law
• On convex relaxation of graph isomorphism
• Generalized Sphere-Packing Bounds on the Size of Codes for Combinatorial Channels
• Maximal Flow Through a Network
• Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-Based Approximation Algorithm
• Mean, Median and Mode in Binomial Distributions
• Random Graph Isomorphism
• Distinguishing Vertices of Random Graphs
• Order Statistics
• On spectral properties for graph matching and graph isomorphism problems
• Seeded graph matching via large neighborhood statistics
• Seeded graph matching for correlated Erd\H{o}s-R\'enyi graphs
• Probability and Computing
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

This page was built for publication: Efficient random graph matching via degree profiles