Comparative Performance Analysis Of Rnsc And Mcl Algorithms On Power-Law Distribution

Cluster analysis of graph related problems is an important issue now-a-day. Different types of graphclustering techniques are appeared in the field but most of them are vulnerable in terms of effectivenessand fragmentation of output in case of real-world applications in diverse systems. In this paper, we willprovide a comparative behavioural analysis of RNSC (Restricted Neighbourhood Search Clustering) andMCL (Markov Clustering) algorithms on Power-Law Distribution graphs. RNSC is a graph clusteringtechnique using stochastic local search. RNSC algorithm tries to achieve optimal cost clustering byassigning 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 graphs. Another popular graph clusteringalgorithm MCL is based on stochastic flow simulation model for weighted graphs. There are plentifulapplications 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. Complex network topologies like World Wide Web, the web ofhuman sexual contacts, or the chemical network of a cell etc., are basically following power-lawdistribution to represent different real-life systems. This paper uses real large-scale power-lawdistribution graphs to conduct the performance analysis of RNSC behaviour compared with Markovclustering (MCL) algorithm. Extensive experimental results on several synthetic and real power-lawdistribution datasets reveal the effectiveness of our approach to comparative performance measure ofthese algorithms on the basis of cost of clustering, cluster size, modularity index of clustering results andnormalized mutual information (NMI).