Similarity Evalution between Graphs: A Formal Concept Analysis Approach
2
조회
0
다운로드
5
인용
0
참고문헌
키워드
초록
Many real-world applications information are organized and represented with graph structure which is oftenused for representing various ubiquitous networks, such as World Wide Web, social networks, and proteinproteininteractive networks. In particular, similarity evaluation between graphs is a challenging issue inmany fields such as graph searching, pattern discovery, neuroscience, chemical compounds exploration andso forth. There exist some algorithms which are based on vertices or edges properties, are proposed foraddressing 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 onformal concept analysis. The feature of this approach is able to characterize the relationships between nodesand further reveal the similarity between graphs. Therefore, the highlight of our approach is to take verticesand edges into account simultaneously. The proposed algorithm is evaluated using a case study for validatingthe effectiveness of the proposed approach on detecting and measuring the similarity between graphs.
Abstract
Many real-world applications information are organized and represented with graph structure which is oftenused for representing various ubiquitous networks, such as World Wide Web, social networks, and proteinproteininteractive networks. In particular, similarity evaluation between graphs is a challenging issue inmany fields such as graph searching, pattern discovery, neuroscience, chemical compounds exploration andso forth. There exist some algorithms which are based on vertices or edges properties, are proposed foraddressing 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 onformal concept analysis. The feature of this approach is able to characterize the relationships between nodesand further reveal the similarity between graphs. Therefore, the highlight of our approach is to take verticesand edges into account simultaneously. The proposed algorithm is evaluated using a case study for validatingthe effectiveness of the proposed approach on detecting and measuring the similarity between graphs.
참고문헌 (20)
- D. Bu, "Topological structure analysis of the protein–protein interaction network in budding yeast", Nucleic Acids Research, 31(9), pp.2443~2450 (2003)
- R. Kumar, "Link Mining:Models, Algorithms, and Applications", pp.337~357 (2010), Springer
- L. Tong, "Transportation network design for maximizing space–time accessibility", Transportation Research Part B: Methodological, 81(Part 2), pp.555~576 (2015)
- Z. Zeng, "Comparing stars: on approximating graph edit distance", Proceedings of the VLDB Endowment, 2(1), pp.25~36 (2009)
- W. Zheng, "Graph similarity search with edit distance constraint in large graph databases", Proceedings of the 22nd ACM International Conference on Information &Knowledge Management, pp.1595~1600 (2013)
- X. Yan, "Feature-based similarity search in graph structures", ACM Transactions on Database Systems(TODS), 31(4), pp.1418~1453 (2006)
- F. Hao, "k-Clique community detection in social networks based on formal concept analysis", IEEE Systems Journal, 11(1), pp.250~259 (2017)
- F. Hao, "k-Cliques mining in dynamic social networks based on triadic formal concept analysis", Neurocomputing, 209, pp.57~66 (2016)
- F. Hao, "Detecting k-balanced trusted cliques in signed social networks", IEEE Internet Computing, 18(2), pp.24~31 (2014)
- H. Bunke, "On a relation between graph edit distance and maximum common subgraph", Pattern Recognition Letters, 18(8), pp.689~694 (1997)
- X. Gao, "A survey of graph edit distance", Pattern Analysis and Applications, 13(1), pp.113~129 (2010)
- C. H. Elzinga, "Kernels for acyclic digraphs", Pattern Recognition Letters, 33(16), pp.2239~2244 (2012)
- B. Cao, "Measuring similarity between graphs based on the Levenshtein distance", Applied Mathematics and Information Sciences, 7(1), pp.169~175 (2013)
- D. Koutra, "DeltaCon: a principled massive-graph similarity function", Proceedings of the 2013 SIAM International Conference on Data Mining, pp.162~170 (2013)
- S. V. N. Vishwanathan, "Graph kernels", Journal of Machine Learning Research, 11, pp.1201~1242 (2010)
- K. M. Borgwardt, "Shortest-path kernels on graphs", Proceedings of the 5th IEEE International Conference on Data Mining, pp.74~81 (2005)
- Y. Tian, "Tale: a tool for approximate large graph matching", Proceedings of the 24th IEEE International Conference on Data Engineering, pp.963~972 (2008)
- F. Hao, "Measuring similarity between graphs based on formal concept analysis", Proceedings of the 11th International Conference on Ubiquitous Information Technologies and Applications (CUTE 2016), pp.730~735 (2016)
- F. Hao, "Tag recommendation based on user interest lattice matching", Proceedings of the 3rd IEEE International Conference on Computer Science and Information Technology, pp.276~280 (2010)
- X. Wang, "A novel method to measure graph similarity", Proceedings of the IEEE 12th International Conference on e-Business Engineering, pp.180~185 (2015)