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

graph matchingbiological networksquantitative graph theorynetwork similaritynetwork comparisoncomputational graph theory

Mathematics Subject Classification ID

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

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

• 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?)
• A Measure of Similarity between Graph Vertices: Applications to Synonym Extraction and Web Searching
• A graph distance metric based on the maximal common subgraph
• 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
• 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 Tree-to-Tree Correction Problem
• The structure and dynamics of networks
• The tree-to-tree editing problem
• Tools and Algorithms for the Construction and Analysis of Systems

Cited in

(33)

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

Describes a project that uses

Uses Software

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

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)