Research Article
Finding Frequent Subgraphs in a Single Graph based on Symmetry
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 146 - Issue 11 |
| Published: Jul 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 },
year = { 2016 },
volume = { 146 },
number = { 11 },
pages = { 5-8 },
doi = { 10.5120/ijca2016910895 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2016
%A D. Kavitha
%A V. Kamakshi Prasad
%A J. V. R. Murthy
%T Finding Frequent Subgraphs in a Single Graph based on Symmetry%T
%J International Journal of Computer Applications
%V 146
%N 11
%P 5-8
%R 10.5120/ijca2016910895
%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
- D. Cook, L. Holder, Mining Graph Data, John Wiley & Sons Inc, 2007.
- R. Kumar, P Raghavan, S. Rajagopalan, D. Sivakumar, A. Tomkins, E. Upfal. The Web as a Graph. ACM PODS Conference, 2000.
- 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
- F. Eichinger, K. Bohm, M. Huber. Improved Software Fault Detection with Graph Mining. Workshop on Mining and Learning with Graphs, 2008
- M. S. Gupta, A. Pathak, S. Chakrabarti. Fast algorithms for top-k personalized pagerank queries. WWW Conference, 2008
- M. Koyuturk, A. Grama, W. Szpankowski. An Efficient Algorithm for Detecting Frequent subgraphs in Biological Networks. Bioinformatics, 20:I200–207, 2004.
- B. Zhou, J. Pei. Preserving Privacy in Social Networks Against Neighborhood Attacks. ICDE Conference, pp. 506-515, 2008
- Kuramochi, M. and Karypis, G., Finding frequent patterns in a large sparse graph. Data Min. Knowledge Discovery, 2005, 11(3),243–271
- L. Zou, L. Chen, and M. T. ¨Ozsu. Distance-join: pattern match query in a large graph database. PVLDB, 2(1):886–897, 2009.
- 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.
- 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
- 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.
- 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.
- 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.
- McKay, B., Practical Graph Isomorphism, Citeseer, 1981.
- J.R. Ullmann, An algorithm for subgraph isomorphism, J. ACM 23 (1976) 31–42.
- J. Gross, J. Yellen (Eds.), Handbook of Graph Theory, CRC Press, Florida, 2004
- SUBDUE databases: http://ailab.wsu.edu/subdue/
- 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
Keywords