Fei Hao, Dae-Soo Sim, Doo-Soon Park, Hyung-Seok Seo, Journal of Information Processing Systems Vol. 13, No. 5, pp. 1158-1167, Oct. 2017  

https://doi.org/10.3745/JIPS.04.0048
Keywords: formal concept analysis, Graph, Social Networks, Similarity Evaluation
Fulltext: PDF

Abstract

Many real-world applications information are organized and represented with graph structure which is often used for representing various ubiquitous networks, such as World Wide Web, social networks, and protein- protein interactive networks. In particular, similarity evaluation between graphs is a challenging issue in many fields such as graph searching, pattern discovery, neuroscience, chemical compounds exploration and so forth. There exist some algorithms which are based on vertices or edges properties, are proposed for addressing this issue. However, these algorithms do not take both vertices and edges similarities into account. Towards this end, this paper pioneers a novel approach for similarity evaluation between graphs based on formal concept analysis. The feature of this approach is able to characterize the relationships between nodes and further reveal the similarity between graphs. Therefore, the highlight of our approach is to take vertices and edges into account simultaneously. The proposed algorithm is evaluated using a case study for validating the effectiveness of the proposed approach on detecting and measuring the similarity between graphs.

Statistics
Cite this article