Algorithms for Graph Similarity and Subgraph Matching

Algorithms for Graph Similarityand Subgraph MatchingDanai KoutraComputer Science DepartmentCarnegie Mellon ParikhMachine Learning DepartmentCarnegie Mellon RamdasMachine Learning DepartmentCarnegie Mellon XiangMachine Learning DepartmentCarnegie Mellon 4, 2011 AbstractWe deal with two independent but related problems, those of Graph Similarity and subgraphmatching, which are both important practical problems useful in several fields of science, engineer-ing and data analysis. For the problem of Graph Similarity , we develop and test a new frameworkfor solving the problem using belief propagation and related ideas. For the Subgraph matchingproblem, we develop a new algorithm based on existing techniques in the bioinformatics and datamining literature, which uncover periodic or infrequent matchings.

3.1 Graph Similarity Graph similarity has numerous applications in diverse fields (such as social networks, image process-ing, biological networks, chemical compounds, and computer vision), and therefore there have been suggested many algorithms and similarity measures. The proposed techniques can be classified into

Loading..

Tags:

  Matching, Algorithm, Graph, Similarity, Algorithms for graph similarity and subgraph matching, Subgraph, Graph similarity graph similarity

Information