0001 function leader = kernel4f (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. Find a Maximal Independent Set (MIS) in G. 
0008 % 2. All graph nodes vote for one of the neighbouring IS nodes as a leader. 
0009 % 3. Each node selects the most popular leader from its neighbours.
0010 %
0011 % Viral Shah (c) 2005-06. All rights reserved.
0012 % Last updated: May 22, 2006.
0013 
0014 G = G.graph;
0015 n = length (G);
0016 G = G | speye (n);
0017 
0018 % Find a Maximal Independent Set in G
0019 [IS, misrounds] = mis (G); 
0020 fprintf ('MIS rounds: %d. MIS nodes: %d\n', misrounds, length(IS));
0021 
0022 % Find neighbours of each node from the IS
0023 neighFromIS = G * sparse(IS, IS, 1, n, n); 
0024 
0025 % Pick one of the neighbouring IS nodes as a leader
0026 [ign leader] = max (neighFromIS, [], 2);
0027 
0028 [I J] = find (G);
0029 % Collect votes from neighbours
0030 S = sparse (I, leader(J), 1, n, n);
0031 
0032 % Pick the most popular leader among neighbours and join that cluster
0033 [ign leader] = max (S, [], 2);
0034