A distance measure for large graphs based on prime graphs

作者：

Highlights：

• A new similarity measure is proposed for large graphs.

• Simplifying graph comparison known to be NP-hard especially for largest graphs.

• Approximating the similarity between two graphs by comparing their prime graphs.

• Primes graphs are smaller and simpler than the original ones.

• Primes graphs are obtained by modular decomposition of graphs.

摘要

Highlights•A new similarity measure is proposed for large graphs.•Simplifying graph comparison known to be NP-hard especially for largest graphs.•Approximating the similarity between two graphs by comparing their prime graphs.•Primes graphs are smaller and simpler than the original ones.•Primes graphs are obtained by modular decomposition of graphs.

论文关键词：Graph similarity,Graph decomposition,Quotient graph,Prime graph,Edit distance,Graph probing

论文评审过程：Received 24 November 2012, Revised 22 January 2014, Accepted 19 March 2014, Available online 28 March 2014.

论文官网地址：https://doi.org/10.1016/j.patcog.2014.03.014