Characteristics of restricted neighbourhood search algorithm and Markov clustering on modified power-law distribution

Abstract

Restricted neighbourhood search clustering (RNSC) is a graph clustering technique using stochastic local search. RNSC algorithm tries to achieve optimal cost clustering by assigning some cost functions to the set of clusterings of a graph. This algorithm was implemented by A. D. King only for undirected and unweighted random graph and its performance was evaluated on a limited set of graphs. Another popular graph clustering algorithm MCL is based on stochastic flow simulation model. This algorithm was implemented by Stijn van Dongen and tested on some weighted graphs. Complex network topology like World Wide Web, the web of human sexual contacts, or the chemical network of a cell etc., describe different real-life systems. There are plentiful applications of power-law or scale-free graphs in nature and society. Scale-free topology is stochastic i.e. nodes are connected in a random manner. This paper uses undirected real large scale-free graphs, to conduct analysis of RNSC behaviour compared with Markov clustering(MCL) algorithm as degree of nodes increases and also when degree exponent (γ) of the power-law distribution is changed. This paper reports for the first time, a comparative performance behaviour of these algorithms on twenty real-life, large-scale, undirected power-law graph data on the basis of run time, cluster coefficient, normalized mutual information (NMI) and cluster size. © 2012 IEEE.