Measuring Similarity Between Graphs Based on Formal Concept Analysis
Graph, an important information organizational structure, is commonly used for representing the social networks, web, and other internet applications. This paper tackles a fundamental problem on measuring similarity between graphs that is the essential st
- PDF / 781,610 Bytes
- 6 Pages / 439.37 x 666.142 pts Page_size
- 4 Downloads / 202 Views
Abstract. Graph, an important information organizational structure, is commonly used for representing the social networks, web, and other internet applications. This paper tackles a fundamental problem on measuring similarity between graphs that is the essential step for graph searching, matching, pattern discovery. To efficiently measure the similarity between graphs, this paper pioneers a novel approach for measurement of similarity between graphs by using formal concept analysis that can clearly describe the relationships between nodes. A case study is provided for demonstrating the feasibility of the proposed approach. Keywords: Graph
Similarity Formal concept analysis Social networks
1 Introduction Recent advancement of large-scale graph theory techniques and ubiquitous computing paradigm enrich the mining and analysis of graph data and other complex networks system, such as Protein interaction networks [1], social networks [2] and transportation networks [3]. Therefore, understanding the internal topological structure of networks is benefit to obtain the deep insights and knowledge from the graph. Similar subgraph matching refers to finding the subgraph structures with similar topological structure on the basis of isomorphism. In many practical applications, a given application issue is normally transformed into a graph, and then measure the similarity degree between graphs. This paper focuses on the similarity degree evaluation between graphs. There have been many existing research works on graph similarity measurement. One widely used approach, named GED is to sum the cost of elementary operations: node substitution, node insertion. However, this method is an NP-hard in general and its main shortcoming is the exponential computational complexity in terms of the number of graph edit vertices [8]. Yan et al. [9] proposed a feature-based approach for similarity search in graph structures. They used indexed features in graph database to filter graphs without performing pairwise similarity computation. This paper is the first work on similarity measurement between graphs by using formal concept analysis. Therefore, it is a pioneering research which can bridge the gap between graph mining and soft computing. The highlights of this paper lie in presenting an efficient measurement approach for similarity between graphs. (1) First, we © Springer Nature Singapore Pte Ltd. 2017 J.J. (Jong Hyuk) Park et al. (eds.), Advances in Computer Science and Ubiquitous Computing, Lecture Notes in Electrical Engineering 421, DOI 10.1007/978-981-10-3023-9_112
Measuring Similarity Between Graphs Based on Formal Concept
731
construct the formal context for given graphs according to Modified Adjacency Matrix; (2) Then, the corresponding formal concept lattices are generated. (3) Obtain the similarity between graphs since the similarity between the generated formal concept lattices is equivalent to the similarity between graphs. The rest of this paper is organized as follows. Section 2 describes the addressed problem and provides
Data Loading...
