CFP last date
20 May 2024
Call for Paper
June Edition
IJCA solicits high quality original research papers for the upcoming June edition of the journal. The last date of research paper submission is 20 May 2024

Submit your paper
Know more
The week's pick
Responsive image
Enhancing Privacy Preservation: Multi-Attribute Protection with P-Sensitive K-Anonymity

Twinkle Patel Kiran Amin
Random Articles
Reseach Article

An Efficient behavioural analysis of Graph Clustering Algorithms via Random Graphs

by Mohit Kumar, Nitin Yadav, Vaibhav Pratap, Avdhesh Kumar
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 47 - Number 3
Year of Publication: 2012
Authors: Mohit Kumar, Nitin Yadav, Vaibhav Pratap, Avdhesh Kumar
10.5120/7170-9785

Mohit Kumar, Nitin Yadav, Vaibhav Pratap, Avdhesh Kumar . An Efficient behavioural analysis of Graph Clustering Algorithms via Random Graphs. International Journal of Computer Applications. 47, 3 ( June 2012), 33-39. DOI=10.5120/7170-9785

@article{ 10.5120/7170-9785,
author = { Mohit Kumar, Nitin Yadav, Vaibhav Pratap, Avdhesh Kumar },
title = { An Efficient behavioural analysis of Graph Clustering Algorithms via Random Graphs },
journal = { International Journal of Computer Applications },
issue_date = { June 2012 },
volume = { 47 },
number = { 3 },
month = { June },
year = { 2012 },
issn = { 0975-8887 },
pages = { 33-39 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume47/number3/7170-9785/ },
doi = { 10.5120/7170-9785 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:40:57.327107+05:30
%A Mohit Kumar
%A Nitin Yadav
%A Vaibhav Pratap
%A Avdhesh Kumar
%T An Efficient behavioural analysis of Graph Clustering Algorithms via Random Graphs
%J International Journal of Computer Applications
%@ 0975-8887
%V 47
%N 3
%P 33-39
%D 2012
%I Foundation of Computer Science (FCS), NY, USA
Abstract

The proposed last research entitled "An Effective Data Comparison of Graph Clustering Algorithms via Random Graphs" compared two mostly used algorithms for graph clustering i. e. restricted neighborhood search and markov clustering algorithms via random graph generators i. e. Erdos-Renyi and power law graphs. This paper is an extension to our last research work. In this we have examined an efficient behavioral analysis of both algorithms via random graphs. This paper mainly shows the behavior of both the algorithms under certain parameters which we have used. Previously in case of Erdos-renyii we used graphs with 1000 nodes with variable edge densities, while in this paper we have modified the number of nodes from 1000 to 15000 with variable edge densities ranging from 0. 1 to 0. 5 while in case of Power-law we have variable number of nodes ranging from 1000 to 15000. This paper also depicts as to which algorithm works more efficient, whether in case of Erdos-Renyi or Power-Law graphs. Our last research showed that in case of Erdos-Renyi graph run time of RNSC algorithm is better as compared to MCL for graph having nodes less than 2000 but as nodes keep on increasing the run time of RNSC increases drastically while run time of MCL doesn't increase, so MCL is better in case of Erdos-Renyi graph having more than 2000 nodes and having high connectivity between the nodes [12] while in this paper it is clearly visible that both RNSC and MCL works better in case of Power-Law graph as compared to Erdos-Renyi graph which clearly states that both algorithm shows some similar characteristics in graphs where edge connectedness is not very high for all vertices. Furthermore we studied the behaviour of RNSC in case of Erdos-Renyi individually also.

References
  1. Sauta Elisa Schaeffer, "Survey Graph clustering," Elsevier Computer Science Review, vol. I, pp. 27-64, 2007.
  2. P. Erdos and A. Renyi. On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci. , 5:17-61, 1960.
  3. A. -L. Barabasi and R. Albert. Emergence of scaling in random networks. Science 286(5439) (1999) 509-512.
  4. A. -L. Barabasi and Z. N. Oltvai. Network biology: Understanding the cell's functional organization. Nature Reviews Genetics, 5:101-113, 2004.
  5. A. D. King, Graph clustering with restricted neighborhoods search. Master's Thesis, University of Toronto, 2004.
  6. X. Hu and J. Han. Discovering clusters from large scale-free network graph. In ACM SIG KDD Second Workshop on Fractals, Power Laws and Other Next Generation Data Mining Tools, August 2003.
  7. S. Enright, A. j. van Dongen, C. A. Ouzounis, An efficient algorithm for large-scale detection of protein families, Nucleic Acids Res. 30(7) (2002) 1575-1584.
  8. S. M. Van Dongen. Graph Clustering by Flow Simulation. PhD thesis, University of Utrecht, May 2002. [Online]. Available: http://www. svdthesis. pdf
  9. Scaled-Free graph generator code. [Online]. Available: http://www-rp. lip6. fr/~latapy/FV/
  10. King, A. D. , Przulj, N. , and Jurisica, I. (2004) Bioinformatics 20, 3013-20.
  11. King, A. D. (2005), McGill University, Montreal.
  12. Reena Mishra, Mohit Kumar, An Effective Data Comparison of Graph Clustering Algorithms via Random Graphs, International Journal of Computer Applications Volume 1 No. 1, May 2011.
  13. Mohit Kumar, Reena Mishra, Implementation and Behavioural Analysis of Graph Clustering using Restricted Neighborhood Search Algorithm, International Journal of Computer Applications Volume 1 No. 1, May 2011.
Index Terms

Computer Science
Information Sciences

Keywords

Rnsc Mcl Erdos-renyi Scaled-free Edge Density Singleton Cluster Run Time Number Of Nodes Cluster Size

Powered by PhDFocusTM