This is a demo for the use of the local clustering code.



In [1]:

    
using Laplacians

First, a small example



In [2]:

    
a = chimera(100, 3);



In [3]:

    
s = prn(a, [1,2,3], 0.2, 5);
conds = compConductance(a, s)
println(conds, " ", length(s))









    



0.1951219512195122 29



In [4]:

    
minEpsSigma = getVolume(a, s) / getVolume(a, setdiff(collect(1:max(a.n, a.m)), s));
cut, flow = localImprove(a, s, epsSigma = minEpsSigma);
condcut = compConductance(a, cut)
println(concut, " ", length(cut))









    Out[4]:





0.01557632398753894

If maxSize isn't set, the new conductance is always better than the initial one. In some cases much better.

Now a larger example



In [5]:

    
a = chimera(1000000, 1);



In [6]:

    
s = prn(a, [1,2,3], 0.5, 5);
conds = compConductance(a, s)
println(conds, " ", length(s))









    



0.47058823529411764 12



In [7]:

    
minEpsSigma = getVolume(a, s) / getVolume(a, setdiff(collect(1:max(a.n, a.m)), s));
cut, flow = localImprove(a, s, epsSigma = minEpsSigma, maxSize = 10000);
condcut = compConductance(a, cut)
println(condcut, " ", length(cut))









    



0.1587607739135676 7012

There are however cases where we don't get any improvements, even if our maxSize value is set to something sensibly larger. This is mainly because of the structure of the graphs we are working with. The process can be hit & miss.



In [8]:

    
a = chimera(1000000, 2);



In [9]:

    
s = prn(a, [1,2,3], 0.5, 5);
conds = compConductance(a, s)
println(conds, " ", length(s))









    



0.4925373134328358 37



In [10]:

    
minEpsSigma = getVolume(a, s) / getVolume(a, setdiff(collect(1:max(a.n, a.m)), s));
cut, flow = localImprove(a, s, epsSigma = minEpsSigma, maxSize = 100000);
condcut = compConductance(a, cut)
println(condcut, " ", length(cut))









    



0.4925373134328358 37

We can however try a refinind heuristic to get a slight improvement on our result.



In [11]:

    
heur = refineCut(a, cut)
condref = compConductance(a, heur)
println(condref, " ", length(heur))









    



0.4426229508196721 21