TEXT COMPARISON WITH GRAPH SIMILARITY

Year 2020, Volume: 5 Issue: 2, 114 - 125, 01.12.2020

Harun Darbaş , Ali Karci

Abstract

Graf similarity is a problem that is NP-difficult and requires a similar approach to solving the text similarity problem. Today, graf similarity is used in many different areas. Since this issue is tried to be solved with approach methods, the graph similarity measurements also differ from each other. By introducing a new graph similarity measurement, it is intended to be used in measuring the text similarity unlike the previously used fields. In this study, it is aimed to measure the graph similarity, which was previously measured by knot similarity calculation and by comparing nodes, by comparing the structural properties of graphs. This similarity was used for text similarity and the results of the study were evaluated in this article.

Keywords

GRAPH SIMILARITY, TEXT MINING, TEXT SIMILARITY

GRAF BENZERLİĞİ İLE METİN KIYASLAMA

Abstract

Graf benzerliği NP-zor olan bir problemdir ve metin benzerliği problemini çözmekte aynı şekilde yaklaşım gerektiren bir problemdir. Günümüzde çok farklı alanlarda graf benzerliği kullanılmaktadır. Bu konu yaklaşım yöntemlerle çözülmeye çalışıldığından graf benzerliği ölçümleri de birbirinden farklılık göstermektedir. Yeni bir graf benzerliği ölçümü ortaya konularak daha önce kullanılan alanlardan farklı olarak metin benzerliğinin ölçülmesinde kullanımı amaçlanmaktadır.
Bu çalışmada, daha önce düğüm bezerliği hesabıyla ve düğümlerin kıyaslanmasıyla ölçülen graf benzerliğinin, grafların yapısal özelliklerinin kıyaslanmasıyla ölçülmesi amaçlanmaktadır. Bu benzerlik durumu metin benzerliği için kullanılmıştır ve çalışmanın sonuçları bu makalede değerlendirilmiştir.

Keywords

Graf Benzerliği, Metin Madenciliği, Metin Benzerliği.

References

• Robin JW (1996) Introduction to Graph Theory Fourth edition, Addison Wesley Longman Limited, England.
• John AB (1982) Graph Theory With Applications, Elsevier Science Publishing, USA.
• Spizzirri, L. (2011). Justification and application of eigenvector centrality. Algebra in Geography: Eigenvectors of Network.
• Peter D, Wayne G, Christine SS (2004). The Average Eccentricity of a Graph and its Subgraphs. Utilitas Mathematica. 65.
• Douglas BW (2000) Introduction to Graph Theory (2nd Edition), Pearson, London
• Amir A, Fabrizio G, Virginia VW (2015). Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the twenty-sixth annual ACM- SIAM symposium on Discrete algorithms (SODA '15). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1681-1697.
• Erkan G, Dragomir R. (2011). LexRank: Graph-based Lexical Centrality As Salience in Text Summarization. Journal of Artificial Intelligence Research - JAIR. 22. 10.1613/jair.1523.
• Zhang H, Fiszman M, Shin D, Miller CM, Rosemblat G, Rindflesch TC. (2011). Degree centrality for semantic abstraction summarization of therapeutic studies. Journal of biomedical informatics, 44(5), 830–838.
• Jennifer G, (2013). Chapter 3 Network Structure and Measures, Analyzing the Social Web, Elsevier, Pages 25-44
• Derek LH, Ben S, Marc AS, Itai H, (Available online 17 May 2019), Chapter 3 - Social network analysis: Measuring, mapping, and modeling collections of connections,
• Analyzing Social Media Networks with NodeXL (Second Edition), ,Elsevier, Pages 31-51
• Sunil K, Balakrishnan K, Madambi J, Betweenness Centrality in Some Classes of Graphs, International Journal of Combinatorics, vol. 2014, Article ID 241723, 12 pages, 2014.
• Meghanathan N, (2015). Use of eigenvector centrality to detect graph isomorphism, Computer Science & Information Technology ( CS & IT ), Academy & Industry Research Collaboration Center (AIRCC)
• Lohmann G, Margulies DS, Horstmann A, Pleger B, Lepsien J, et al. (2010) Eigenvector Centrality Mapping for Analyzing Connectivity Patterns in fMRI Data of the Human Brain. PLOS ONE 5(4): e10232.
• Michael WB. (2004). Survey of Text Mining: Clustering, Classification, and Retrieval, Springer, USA
• Vrotsou K, Johansson J, Cooper M, (2009). Activitree: Interactive visual exploration of sequences in event-based data using graph similarity. IEEE Transactions on Visualization and Computer Graphics, 15(6), 945-952.
• Koutra, D., Parikh, A., Ramdas, A., & Xiang, J. (2011, December). Algorithms for graph similarity and subgraph matching. In Proc. Ecol. Inference Conf (Vol. 17).
• Koutra, D., Vogelstein, J. T., & Faloutsos, C. (2013, May). Deltacon: A principled massive-graph similarity function. In Proceedings of the 2013 SIAM International Conference on Data Mining (pp. 162-170). Society for Industrial and Applied Mathematics.
• Zhao, X., Xiao, C., Lin, X., & Wang, W. (2012, April). Efficient graph similarity joins with edit distance constraints. In 2012 IEEE 28th International Conference on Data Engineering (pp. 834-845). IEEE.
• Fischer, A., Riesen, K., & Bunke, H. (2010, November). Graph similarity features for HMM-based handwriting recognition in historical documents. In 2010 12th International Conference on Frontiers in Handwriting Recognition (pp. 253-258). IEEE.
• Naudé, K. A., Greyling, J. H., & Vogts, D. (2010). Marking student programs using graph similarity. Computers & Education, 54(2), 545-561.
• Skvortsova, M. I., Baskin, I. I., Stankevich, I. V., Palyulin, V. A., & Zefirov, N. S. (1998). Molecular similarity. 1. Analytical description of the set of graph similarity measures. Journal of chemical information and computer sciences, 38(5), 785-790.
• Runwal, N., Low, R. M., & Stamp, M. (2012). Opcode graph similarity and metamorphic detection. Journal in Computer Virology, 8(1-2), 37-52.
• Sorlin, S., & Solnon, C. (2005, April). Reactive tabu search for measuring graph similarity. In International Workshop on Graph-Based Representations in Pattern Recognition (pp. 172-182). Springer, Berlin, Heidelberg.
• Online Text Word Count, 2015-2019 COUNTWORDSFREE - Text Tools, https://countwordsfree.com
• MATLAB, The MathWorks, Inc., 1994-2019, 1 Apple Hill Drive Natick, MA 01760-2098, www.mathworks.com