We apologize for a recent technical issue with our email system, which temporarily affected account activations. Accounts have now been activated. Authors may proceed with paper submissions. PhDFocusTM
CFP last date
20 December 2024
Reseach Article

An Effective Comparison of Graph Clustering Algorithms via Random Graphs

by Reena Mishra, Shashwat Shukla, Dr. Deepak Arora, Mohit Kumar
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 22 - Number 1
Year of Publication: 2011
Authors: Reena Mishra, Shashwat Shukla, Dr. Deepak Arora, Mohit Kumar
10.5120/2547-3490

Reena Mishra, Shashwat Shukla, Dr. Deepak Arora, Mohit Kumar . An Effective Comparison of Graph Clustering Algorithms via Random Graphs. International Journal of Computer Applications. 22, 1 ( May 2011), 22-27. DOI=10.5120/2547-3490

@article{ 10.5120/2547-3490,
author = { Reena Mishra, Shashwat Shukla, Dr. Deepak Arora, Mohit Kumar },
title = { An Effective Comparison of Graph Clustering Algorithms via Random Graphs },
journal = { International Journal of Computer Applications },
issue_date = { May 2011 },
volume = { 22 },
number = { 1 },
month = { May },
year = { 2011 },
issn = { 0975-8887 },
pages = { 22-27 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume22/number1/2547-3490/ },
doi = { 10.5120/2547-3490 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:08:17.714447+05:30
%A Reena Mishra
%A Shashwat Shukla
%A Dr. Deepak Arora
%A Mohit Kumar
%T An Effective Comparison of Graph Clustering Algorithms via Random Graphs
%J International Journal of Computer Applications
%@ 0975-8887
%V 22
%N 1
%P 22-27
%D 2011
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Many graph clustering algorithms have been proposed in recent past researches, each algorithm having its own advantages and drawbacks. All these algorithms rely on a very different approach so it’s really hard to say that which one is the most efficient and optimal if we talk in the sense of performance. It is really hard to decide that which algorithm is beneficial in case of highly complex networks like PPI networks which consist of thousands of nodes. The paper proposes an effective data comparison of RNSC (Restricted Neighbourhood Search Clustering) and MCL (Markov Clustering) algorithms based on Erdos-Renyi and Power-Law Distribution graphs. The basic parameters used for comparison are Edge Density, Run Time, Number of Nodes, Cluster Size and Singleton Cluster. Our approach is an effective one because firstly we have used two types of graph generators, Erdos-Renyi and Scaled-Free for generation of input graphs which are very much closer to the real input graphs and secondly we have generated input graphs having more than 1000 nodes, so in our approach we have used both the algorithms for clustering highly complex input graphs just like PPI networks. For comparison and analysis purpose we have collected data sets and generated some graphs based on these parameters. The proposed approach depicts which algorithm is best to be used for clustering such complex graphs and also some fields for extension if possible in both them. All graphs used in this thesis are unweighted and undirected.

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 neighbourhood 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.
Index Terms

Computer Science
Information Sciences

Keywords

RNSC MCL Erdos-Renyi Scaled-Free Edge Density Singleton Cluster Run Time Number of Nodes Cluster Size