CFP last date
20 June 2024
Reseach Article

Implementation and Behavioural Analysis of Graph Clustering using Restricted Neighborhood Search Algorithm

by Mohit Kumar, K. K. Agrawal, Dr. Deepak Arora, Reena Mishra
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 22 - Number 6
Year of Publication: 2011
Authors: Mohit Kumar, K. K. Agrawal, Dr. Deepak Arora, Reena Mishra
10.5120/2589-3581

Mohit Kumar, K. K. Agrawal, Dr. Deepak Arora, Reena Mishra . Implementation and Behavioural Analysis of Graph Clustering using Restricted Neighborhood Search Algorithm. International Journal of Computer Applications. 22, 6 ( May 2011), 15-20. DOI=10.5120/2589-3581

@article{ 10.5120/2589-3581,
author = { Mohit Kumar, K. K. Agrawal, Dr. Deepak Arora, Reena Mishra },
title = { Implementation and Behavioural Analysis of Graph Clustering using Restricted Neighborhood Search Algorithm },
journal = { International Journal of Computer Applications },
issue_date = { May 2011 },
volume = { 22 },
number = { 6 },
month = { May },
year = { 2011 },
issn = { 0975-8887 },
pages = { 15-20 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume22/number6/2589-3581/ },
doi = { 10.5120/2589-3581 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:08:40.794648+05:30
%A Mohit Kumar
%A K. K. Agrawal
%A Dr. Deepak Arora
%A Reena Mishra
%T Implementation and Behavioural Analysis of Graph Clustering using Restricted Neighborhood Search Algorithm
%J International Journal of Computer Applications
%@ 0975-8887
%V 22
%N 6
%P 15-20
%D 2011
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Restricted Neighborhood Search Algorithm or RNSC is a cost-based clustering technique for clustering the graph into separate clusters, where each cluster has some similar properties. The properties considered in this case are low inter-connectivity and high intra-connectivity in clusters. This is implemented only for un-weighted and undirected graphs. This algorithm applies a heuristic approach in which we only consider the moves in the restricted neighborhood of previous move, i.e., after a move has been made the next move will only be allowed in the neighbor clusters of that move. After a fixed number of moves we apply diversification moves to avoid the solution reaching local-minima in-spite of global solution. A tabu list is also maintained to avoid same moves which it has made in the recent past. This technique reduces the run-time of clustering algorithm many-folds, as it skips those redundant cases which occur multiple times and don’t improve the cost of the function. The plus point of this algorithm is improvement in run-time due to the data-structure it is maintaining to update the clustering. The updating of the clustering is very fast and thus makes the algorithm fast. The paper proposes an effective behaviour analysis of some parameters of this algorithm which may help in the future modification of this algorithm. For better analysis of RNSC algorithm we have used Random Scaled-Free graphs having more than 10,000 nodes. Thus in our approach RNSC algorithm is successfully implemented in C++ for a graph of more than 10,000 nodes.

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. Scaled-Free graph generator code. [Online].Available: http://www-rp.lip6.fr/~latapy/FV/
  9. King, A. D., Przulj, N., and Jurisica, I. (2004) Bioinformatics 20, 3013-20.
  10. King, A. D. (2005), McGill University, Montreal.
  11. C. Avanthay, A. Hertz and N. Zuerey. A variable neighbourhood search for graph coloring. European Journal of Operational Research, 151:379 388, 2003.
  12. J. U. Brandes, M. Gaertler and D. Wagner. Experiments on graph clustering algorithms. In Proc. 11th Europ. Symp. Algorithms (ESA'03), Lecture Notes in Computer Science, volume2832, pages568-579. Springer-Verlag, 2003.
  13. F. Glover. Tabu search, part I. ORSA Journal on Computing, 1(3):190-206, summer 1989. “ORSA" is called Informs today.
  14. F. Glover. Tabu search, part II. ORSA Journal on Computing, 2(1): 4-32, Winter 1990. “ORSA" is called Informs today.
  15. A. Hertz and D. de Werra. Using tabu search techniques for graph colouring. Computing, 39(4), 1987.
  16. Unix Make utility, online documentation: http://www.gnu.org/software/make/manual/.
Index Terms

Computer Science
Information Sciences

Keywords

Graph clustering Tabu search Destructive diversification Shuffling diversification naïve move Scaled move Move cost Neighborhood search RNSC