0001 function label = kernel4g (G)
0002 % KERNEL4F : SSCA#2 Kernel 4 -- Graph Clustering
0003 %
0004 % USAGE:  label = kernel4f (G);
0005 %
0006 % A peer-pressure algorithm for kernel 4. The algorithm is as follows:
0007 % 1. Each node votes for highest numbered neighbouring node as a leader. 
0008 % 2. Each node selects the most popular leader from its neighbours.
0009 %
0010 % This is based on an observation of Eric S. that for SSCA#2, using
0011 % 1:n as the leader set gives very good clustering.
0012 %
0013 % Viral Shah (c) 2005-06. All rights reserved.
0014 % Last updated: May 22, 2006.
0015 
0016 G = G.graph;
0017 n = length (G);
0018 G = G | speye (n);
0019 
0020 % Pick one of the neighbouring nodes as a leader
0021 % The size of the leader set is quite small, since the cliques are large.
0022 [ign leader] = max (G, [], 2);
0023 
0024 % Collect votes from neighbours
0025 S = G * sparse(1:n, leader, 1, n, n);
0026 
0027 % Pick the most popular leader among neighbours and join that cluster
0028 [ign label] = max (S, [], 2);
0029 
0030 
0031