Fifty years of graph matching, network alignment and network comparison

DOI10.1016/J.INS.2016.01.074MaRDI QIDQ1991876zbMATH OpenOpenAlexFDO

Authors Frank Emmert-Streib, Matthias Dehmer, Yongtang Shi

Publication date 30 October 2018

Published in Information Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ins.2016.01.074

zbMATH Keywords

biological networkscomputational graph theorygraph matchingnetwork comparisonnetwork similarityquantitative graph theory

Mathematics Subject Classification ID

History of combinatorics (05-03) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Random graphs (graph-theoretic aspects) (05C80) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph algorithms (graph-theoretic aspects) (05C85) Applications of graph theory (05C90) History of computer science (68-03) Graph theory (including graph drawing) in computer science (68R10) Pattern recognition, speech recognition (68T10) History of biology (92-03) Systems biology, networks (92C42) Molecular structure (graph-theoretic methods, methods of differential topology, etc.) (92E10)

Recommendations

• Network Analysis
• The graph matching problem
• Toward quantifying vertex similarity in networks
• Network comparison and the within-ensemble graph distance
• A large database of graphs and its use for benchmarking graph isomorphism algorithms

Cites work

• A graph distance metric based on the maximal common subgraph
• A Measure of Similarity between Graph Vertices: Applications to Synonym Extraction and Web Searching
• A new method of measuring similarity for a special class of directed graphs
• A similarity measure for graphs with low computational complexity
• A survey of graph edit distance
• Algorithms on Strings, Trees and Sequences
• An Algorithm for Subgraph Isomorphism
• Authoritative sources in a hyperlinked environment
• Collective dynamics of `small-world' networks
• Distance-based analysis of variance: Approximate inference
• Edge rotations and distance between graphs
• Graph similarity scoring and matching
• scientific article; zbMATH DE number 4174951 (Why is no real title available?)
• scientific article; zbMATH DE number 4179407 (Why is no real title available?)
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3819112 (Why is no real title available?)
• scientific article; zbMATH DE number 3966099 (Why is no real title available?)
• scientific article; zbMATH DE number 3979120 (Why is no real title available?)
• scientific article; zbMATH DE number 4039703 (Why is no real title available?)
• scientific article; zbMATH DE number 3703996 (Why is no real title available?)
• scientific article; zbMATH DE number 3781232 (Why is no real title available?)
• scientific article; zbMATH DE number 3781233 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3639162 (Why is no real title available?)
• scientific article; zbMATH DE number 1865747 (Why is no real title available?)
• scientific article; zbMATH DE number 3240929 (Why is no real title available?)
• scientific article; zbMATH DE number 3251135 (Why is no real title available?)
• scientific article; zbMATH DE number 3284071 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• scientific article; zbMATH DE number 3413820 (Why is no real title available?)
• Inexact graph matching for structural pattern recognition
• Information processing in complex networks: Graph entropy and information functionals
• Matching graphs with unique node labels
• Multivariate generalizations of the Wald-Wolfowitz and Smirnov two-sample tests
• Multivariate image similarity in the compressed domain using statistical graph matching
• On a certain distance between isomorphism classes of graphs
• On graph kernels: hardness results and efficient alternatives.
• Rotation and jump distances between graphs
• Statistical mechanics of complex networks
• The structure and dynamics of networks
• The Tree-to-Tree Correction Problem
• The tree-to-tree editing problem
• Tools and Algorithms for the Construction and Analysis of Systems

Cited in

(40)

• New inequalities for network distance measures by using graph spectra
• Network alignment by discrete Ollivier-Ricci flow
• New highlights and a new centrality measure based on the adapted PageRank algorithm for urban networks
• A novel method for analyzing inverse problem of topological indices of graphs using competitive agglomeration
• Counterexamples to conjectures on graph distance measures based on topological indexes
• Stackelberg game based relay selection for physical layer security and energy efficiency enhancement in cognitive radio networks
• Network entropies based on independent sets and matchings
• Inferring the reputation enhances the cooperation in the public goods game on interdependent lattices
• Characterizing the optimal pivots for efficient similarity searches in vector space databases with Minkowski distances
• Compositional properties of alignments
• The effect of graph operations on the degree-based entropy
• A new coupled disease-awareness spreading model with mass media on multiplex networks
• Network similarity measure and Ediz eccentric connectivity index
• Comparing large-scale graphs based on quantum probability theory
• On efficient network similarity measures
• A comparative analysis of new graph distance measures and graph edit distance
• Highly unique network descriptors based on the roots of the permanental polynomial
• Properties of graph distance measures by means of discrete inequalities
• Strong behavioral similarities in timed-arc Petri nets
• Impact of self interaction on the evolution of cooperation in social spatial dilemmas
• Quantum walk inspired algorithm for graph similarity and isomorphism
• Network distances for weighted digraphs
• Spectrally robust graph isomorphism
• On network similarities and their applications
• Network comparison and the within-ensemble graph distance
• Network Analysis
• Spectral graph matching and regularized quadratic relaxations. I: Algorithm and Gaussian analysis
• Subgraph matching on temporal graphs
• Relationships between symmetry-based graph measures
• Magnitude and Topological Entropy of Digraphs
• Heat diffusion distance processes: a statistically founded method to analyze graph data sets
• Graph distance measures based on topological indices revisited
• Hoeffding-type decomposition for U-statistics on bipartite networks
• Graph matching via convex relaxation to the simplex
• Graph matching based on similarities in structure and attributes
• On Seeded Subgraph-to-Subgraph Matching: The ssSGM Algorithm and Matchability Information Theory
• Efficient graph similarity assessment method based on vectors of topological indices
• Forest Expression of Networks and their Applications
• A distribution-based framework for network similarity assessment
• Quantitative graph theory: a new branch of graph theory and network science

Describes a project that uses

Uses Software

• GSNCA
• chemometrics
• DNA
• GHOST
• SPINAL
• NETAL
• PINALOG
• HubAlign

This page was built for publication: Fifty years of graph matching, network alignment and network comparison

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