Call for Paper - December 2021 Edition
IJCA solicits original research papers for the December 2021 Edition. Last date of manuscript submission is November 20, 2021. Read More

Finding Frequent Subgraphs in a Single Graph based on Symmetry

Print
PDF
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Year of Publication: 2016
Authors:
D. Kavitha, V. Kamakshi Prasad, J. V. R. Murthy
10.5120/ijca2016910895

D Kavitha, Kamakshi V Prasad and J V R Murthy. Finding Frequent Subgraphs in a Single Graph based on Symmetry. International Journal of Computer Applications 146(11):5-8, July 2016. BibTeX

@article{10.5120/ijca2016910895,
	author = {D. Kavitha and V. Kamakshi Prasad and J. V. R. Murthy},
	title = {Finding Frequent Subgraphs in a Single Graph based on Symmetry},
	journal = {International Journal of Computer Applications},
	issue_date = {July 2016},
	volume = {146},
	number = {11},
	month = {Jul},
	year = {2016},
	issn = {0975-8887},
	pages = {5-8},
	numpages = {4},
	url = {http://www.ijcaonline.org/archives/volume146/number11/25440-2016910895},
	doi = {10.5120/ijca2016910895},
	publisher = {Foundation of Computer Science (FCS), NY, USA},
	address = {New York, 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.

Keywords

Frequent subgraph, single graph, graph isomorphism, symmetry