RNSC is a cost-based local search algorithm that works to minimize a cost function in the solution space. The basic principle underlying local search is to start from an initial candidate solution and then, iteratively, to make moves from one candidate solution to another of the candidate solutions from its direct neighbourhood. The moves are based on local information, and continue until a termination condition is met. Starting from an initial random or user input clustering, RNSC searches a better clustering using a simple integer-valued cost function, the naive cost function. This naive cost function calculates the sum for each vertex i :
This sum is divided by 2. For an optimal clustering, these values have to be low for all vertices. When a user-defined number of moves has been done without decreasing the naive cost function, the program shifts to the real-value scaled cost function which also takes into account the size of the cluster during the calculations.
At each iteration, one node is moved from one cluster to another. If this move decreased the naive or the scaled cost function, this move (considered as an intensification move) is conserved.
In order to avoid local minima, a user-defined number of nodes are moved to random clusters according to a user-defined frequency.
In order to avoid cycling back to the previously explored partitioning, a list of vertices that may not move is maintained. The size of this list and the number of time a vertex must be in the list before being considered as non movable are user-defined.
The RNSC program was developed by Andrew King.
(King, 2004, M.Sc. thesis;
King et al, 2004) and is available upon request.
The input / output parsers, the webservices and the web interface were developped by Sylvain Brohée.