Similaridade de grafos via hashing

Abstract

A graph is a universal data structure, useful to represent several objects and concepts.In the recent decades, the interest in graphs has been driven by a large amount of dataavailable. Examples include XML repositories, social networks, biological networks,and chemical graphs. Therefore, it is necessary to manage, query and analyze suchlarge graph data efficiently.The central problem of this thesis is the computation of the similarity betweengraphs in an efficient and effective manner. The proposed approach may be dividedinto two parts: (1) a transformation function, and (2) a signature function. A transformationfunction decomposes the input graph into approximate paths, which aresubstructures presented by this work. Approximate paths differ from simple paths byallowing gaps between nodes. Such flexible substructures are able to describe directand indirect relationships in graphs. The similarity between two graphs is computedthrough a kernel function based on the number of substructures shared by them. Sincethe number of substructures that represent a graph may be large, a signature functionapplies a hashing technique in order to provide a short descriptor for a set of substructures.The signatures are short enough to fit into the main memory and may estimatethe similarity between the sets efficiently, with theoretically guaranteed effectiveness.We have evaluated the proposed method using several real and synthetic datasets,from different application scenarios, such as information retrieval and classification.The results show that approximate paths may be used efficiently and achieve gainsw.r.t. the techniques from the literature.