Fifty years of graph matching, network alignment and network comparison

DOI10.1016/j.ins.2016.01.074zbMath1398.68393OpenAlexW2289831356MaRDI QIDQ1991876

Matthias Dehmer, Yongtang Shi, Frank Emmert-Streib

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

graph matchingbiological networksquantitative graph theorynetwork similaritynetwork comparisoncomputational graph theory

Mathematics Subject Classification ID

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

Related Items

New inequalities for network distance measures by using graph spectra, Impact of self interaction on the evolution of cooperation in social spatial dilemmas, Spectral graph matching and regularized quadratic relaxations. I: Algorithm and Gaussian analysis, Subgraph matching on temporal graphs, Quantum walk inspired algorithm for graph similarity and isomorphism, Relationships between symmetry-based graph measures, Magnitude and Topological Entropy of Digraphs, A new coupled disease-awareness spreading model with mass media on multiplex networks, Network alignment by discrete Ollivier-Ricci flow, Network similarity measure and Ediz eccentric connectivity index, 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, Spectrally Robust Graph Isomorphism, Network entropies based on independent sets and matchings, Inferring the reputation enhances the cooperation in the public goods game on interdependent lattices, Graph distance measures based on topological indices revisited, Network comparison and the within-ensemble graph distance, Characterizing the optimal pivots for efficient similarity searches in vector space databases with Minkowski distances, 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, Network Distances for Weighted Digraphs, Compositional properties of alignments, Quantitative graph theory: a new branch of graph theory and network science, Strong behavioral similarities in timed-arc Petri nets, The effect of graph operations on the degree-based entropy, On Network Similarities and Their Applications

Uses Software

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A survey of graph edit distance
• Matching graphs with unique node labels
• A similarity measure for graphs with low computational complexity
• Information processing in complex networks: Graph entropy and information functionals
• Multivariate generalizations of the Wald-Wolfowitz and Smirnov two-sample tests
• The tree-to-tree editing problem
• Graph similarity scoring and matching
• Multivariate image similarity in the compressed domain using statistical graph matching
• Statistical mechanics of complex networks
• Authoritative sources in a hyperlinked environment
• Edge rotations and distance between graphs
• On a certain distance between isomorphism classes of graphs
• An Algorithm for Subgraph Isomorphism
• The Tree-to-Tree Correction Problem
• Rotation and jump distances between graphs
• A graph distance metric based on the maximal common subgraph
• Algorithms on Strings, Trees and Sequences
• A Measure of Similarity between Graph Vertices: Applications to Synonym Extraction and Web Searching
• Inexact graph matching for structural pattern recognition
• Distance-based analysis of variance: Approximate inference
• Learning Theory and Kernel Machines
• Collective dynamics of ‘small-world’ networks
• Tools and Algorithms for the Construction and Analysis of Systems