The week's pick
Reseach Article
An Effective Comparison of Graph Clustering Algorithms via Random Graphs
| 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
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
- Sauta Elisa Schaeffer, “Survey Graph clustering,” Elsevier Computer Science Review, vol. I, pp. 27-64, 2007.
- P. Erdos and A. Renyi. On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci., 5:17-61, 1960.
- A.-L. Barabasi and R. Albert. Emergence of scaling in random networks. Science 286(5439) (1999) 509-512.
- A.-L. Barabasi and Z. N. Oltvai. Network biology: Understanding the cell’s functional organization. Nature Reviews Genetics, 5:101-113, 2004.
- A.D. King, Graph clustering with restricted neighbourhood search. Master’s Thesis, University of Toronto, 2004.
- 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.
- 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.
- S. M. Van Dongen. Graph Clustering by Flow Simulation. PhD thesis, University of Utrecht, May 2002. [Online].Available: http://www.svdthesis.pdf
- Scaled-Free graph generator code. [Online].Available: http://www-rp.lip6.fr/~latapy/FV/
- King, A. D., Przulj, N., and Jurisica, I. (2004) Bioinformatics 20, 3013-20.
- King, A. D. (2005), McGill University, Montreal.
Index Terms
Keywords