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.

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