Simplifying Calculation of Graph Similarity Through Matrices
A method to simplify the calculation in the process of measuring graph similarity is proposed, where lots of redundant operations are avoided in order to quickly obtain the initial tickets matrix. In this proposal, the element value of the initial tickets
- PDF / 1,184,283 Bytes
- 12 Pages / 439.37 x 666.142 pts Page_size
- 7 Downloads / 216 Views
2
College of Computer Science and Technology, Jilin University, Changchun 130012, China [email protected], [email protected] Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012, China 3 College of Information Technology, Jilin Agricultural University, Changchun 130118, China [email protected]
Abstract. A method to simplify the calculation in the process of measuring graph similarity is proposed, where lots of redundant operations are avoided in order to quickly obtain the initial tickets matrix. In this proposal, the element value of the initial tickets matrix is assigned to 1 when it is positive in corresponding position of the paths matrix at the first time. The proposed method calculates the initial tickets matrix value based on the positive value in the paths matrix in a forward and backward way. An example is provided to illustrate that the method is feasible and effective. Keywords: Graph similarity measure Paths and tickets Adjacency matrix Forward and backward Simplifying calculation
1 Introduction The complex objects with structural properties can be naturally established as graphs in chemistry, bioinformatics, data mining, social network, image processing and other fields [1–6]. For example, the science citation can be represented as a graph with the literatures as vertices and the indexes as edges. As the large amount of graph data is increasing, how to characterize the difference of the graph data becomes an important problem [7]. The graph similarity method that efficiently solves the problem can be applied to classify the graphical data. In order to measure the graph similarity, we usually calculate the number of the common paths of the graph, such as random walk graph kernel (abbreviated as RWGK) [8,9], the shortest path graph kernel (abbreviated as SPGK) [10], and the function of the common paths or tickets [4], etc. The function of the common paths or tickets, in the spirit of the neighborhood counting and all common subsequences in measuring the sequence similarity [11–13], measures graph similarity by calculating all common paths or tickets matrices between two graphs [14–16]. Compared with RWGK and
© IFIP International Federation for Information Processing 2016 Published by Springer International Publishing AG 2016. All Rights Reserved D. Li and Z. Li (Eds.): CCTA 2015, Part II, IFIP AICT 479, pp. 417–428, 2016. DOI: 10.1007/978-3-319-48354-2_41
418
X. Wang et al.
SPGK, this method considers more information of vertices and edges in graph. This method is remarkable in accuracy and running time, in addition, it is not restrictive and can be applied in larger graph dataset. Also, it avoids the tottering phenomenon [17]. In the process of calculating the tickets matrices, the initial tickets matrix is raised from all paths matrix, which is calculated by Floyd-Warshall Algorithm [18–20]. When the element value in the paths matrix is positive, by using the method in [4], the value in the initial tickets matri
Data Loading...
