CFP last date
20 December 2024
Reseach Article

Finding Frequent Subgraphs in a Single Graph based on Symmetry

by D. Kavitha, V. Kamakshi Prasad, J. V. R. Murthy
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 146 - Number 11
Year of Publication: 2016
Authors: D. Kavitha, V. Kamakshi Prasad, J. V. R. Murthy
10.5120/ijca2016910895

D. Kavitha, V. Kamakshi Prasad, J. V. R. Murthy . Finding Frequent Subgraphs in a Single Graph based on Symmetry. International Journal of Computer Applications. 146, 11 ( Jul 2016), 5-8. DOI=10.5120/ijca2016910895

@article{ 10.5120/ijca2016910895,
author = { D. Kavitha, V. Kamakshi Prasad, J. V. R. Murthy },
title = { Finding Frequent Subgraphs in a Single Graph based on Symmetry },
journal = { International Journal of Computer Applications },
issue_date = { Jul 2016 },
volume = { 146 },
number = { 11 },
month = { Jul },
year = { 2016 },
issn = { 0975-8887 },
pages = { 5-8 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume146/number11/25440-2016910895/ },
doi = { 10.5120/ijca2016910895 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T23:50:08.511135+05:30
%A D. Kavitha
%A V. Kamakshi Prasad
%A J. V. R. Murthy
%T Finding Frequent Subgraphs in a Single Graph based on Symmetry
%J International Journal of Computer Applications
%@ 0975-8887
%V 146
%N 11
%P 5-8
%D 2016
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Mining frequent subgraphs is a basic activity that plays an important role in mining graph data. In this paper an algorithm is proposed to find frequent subgraphs in a single large graph that has applications such as protein interactions, social networks, web interactions. One of the key operations required by any frequent subgraph discovery algorithm is to perform graph isomorphism. The proposed algorithm offers mining frequent subgraphs by avoiding the subgraph isomorphism problem through exploiting the symmetry properties present in the given graph.

References
  1. D. Cook, L. Holder, Mining Graph Data, John Wiley & Sons Inc, 2007.
  2. R. Kumar, P Raghavan, S. Rajagopalan, D. Sivakumar, A. Tomkins, E. Upfal. The Web as a Graph. ACM PODS Conference, 2000.
  3. D. Maio and D. Maltoni. A structural approach to fingerprint classification. In Proceedings of 13th International Conference on Pattern Recognition, Vienna, Austria, pp. 578–585, 1996
  4. F. Eichinger, K. Bohm, M. Huber. Improved Software Fault Detection with Graph Mining. Workshop on Mining and Learning with Graphs, 2008
  5. M. S. Gupta, A. Pathak, S. Chakrabarti. Fast algorithms for top-k personalized pagerank queries. WWW Conference, 2008
  6. M. Koyuturk, A. Grama, W. Szpankowski. An Efficient Algorithm for Detecting Frequent subgraphs in Biological Networks. Bioinformatics, 20:I200–207, 2004.
  7. B. Zhou, J. Pei. Preserving Privacy in Social Networks Against Neighborhood Attacks. ICDE Conference, pp. 506-515, 2008
  8. Kuramochi, M. and Karypis, G., Finding frequent patterns in a large sparse graph. Data Min. Knowledge Discovery, 2005, 11(3),243–271
  9. L. Zou, L. Chen, and M. T. ¨Ozsu. Distance-join: pattern match query in a large graph database. PVLDB, 2(1):886–897, 2009.
  10. Z. Sun, H. Wang, H. Wang, B. Shao, and J. Li. Efficient subgraph matching on billion node graphs. PVLDB, 5(9):788–799, May 2012.
  11. J. Lee, W.-S. Han, R. Kasperovics, and J.-H. Lee. An in-depth comparison of subgraph isomorphism algorithms in graph databases. PVLDB, 6(2):133–144, Dec. 2012
  12. Elseidy M., Abdelhamid E., Skiadopoulos S. and Kalnis P.  (2014) GraMi: Frequent subgraph and pattern mining in a single large graph. PVLDB, 7,517–528.
  13. Fiedler M. and Borgelt C.  (2007) Support Computation for Mining Frequent Subgraphs in a Single Graph. Proc. MLG 07, Firence, Italy, August 1–3. ACM, New York, NY, USA.
  14. Bringmann B. and  Nijssen S. (2008) What is Frequent in a Single Graph?. Proc. PAKDD 08, Osaka, Japan, May 20–23, pp. 858–863. Springer, Berlin.
  15. McKay, B., Practical Graph Isomorphism, Citeseer, 1981.
  16. J.R. Ullmann, An algorithm for subgraph isomorphism, J. ACM 23 (1976) 31–42.
  17. J. Gross, J. Yellen (Eds.), Handbook of Graph Theory, CRC Press, Florida, 2004
  18. SUBDUE databases: http://ailab.wsu.edu/subdue/
  19. L. Salwinski, C.S. Miller, A.J. Smith, F.K. Pettit, J.U. Bowie and D. Eisenberg, The database of interacting proteins: 2004 update. Nucleic Acids Research. 2004, 32: D449-D451.
Index Terms

Computer Science
Information Sciences

Keywords

Frequent subgraph single graph graph isomorphism symmetry