A distance measure for large graphs based on prime graphs

PATTERN RECOGNITION

卷:47

Article

Lagraa, Sofiane¹  Seba, Hamida¹  Khennoufa, Riadh²  M'Baya, Abir¹  Kheddouci, Hamamache¹ 

[1] Univ Lyon 1, CNRS, LIRIS, UMR5205, F-69622 Villeurbanne, France

[2] Univ Lyon 1, IUT Lyon1, Dept INFO Bourg, F-01000 Lyon, France

关键词: Graph similarity;    Graph decomposition;    Quotient graph;    Prime graph;    Edit distance;    Graph probing;   

DOI  :  10.1016/j.patcog.2014.03.014

来源: Elsevier

【 摘 要 】

Graphs are universal modeling tools. They are used to represent objects and their relationships in almost all domains: they are used to represent DNA, images, videos, social networks, XML documents, etc. When objects are represented by graphs, the problem of their comparison is a problem of comparing graphs. Comparing objects is a key task in our daily life. It is the core of a search engine, the backbone of a mining tool, etc. Nowadays, comparing objects faces the challenge of the large amount of data that this task must deal with. Moreover, when graphs are used to model these objects, it is known that graph comparison is very complex and computationally hard especially for large graphs. So, research on simplifying graph comparison gainedan interest and several solutions are proposed. In this paper, we explore and evaluate a new solution for the comparison of large graphs. Our approach relies on a compact encoding of graphs called prime graphs. Prime graphs are smaller and simpler than the original ones but they retain the structure and properties of the encoded graphs. We propose to approximate the similarity between two graphs by comparing the corresponding prime graphs. Simulations results show that this approach is effective for large graphs. (C) 2014 Elsevier Ltd. All rights reserved.

【 授权许可】

Free