package flare.analytics.cluster {
import flare.animate.Transitioner;
import flare.util.math.IMatrix;
import flare.vis.data.DataList;
/**
* Hierarchically clusters a network based on inferred community structure.
* The result is a cluster tree in which each merge is chosen so as to
* maximize within-cluster linkage while minimizing between-cluster linkage.
* This class uses Newman's
* fast algorithm for detecting community structure. Optionally allows
* clients to provide an edge weight function indicating the strength of
* ties within the network.
*/
public class CommunityStructure extends HierarchicalCluster
{
/** A function defining edge weights in the graph. */
public var edgeWeights:Function = null;
// --------------------------------------------------------------------
/**
* Creates a new community structure instance
*/
public function CommunityStructure()
{
}
/** @inheritDoc */
public override function operate(t:Transitioner=null):void
{
calculate(visualization.data.group(group), edgeWeights);
}
/**
* Calculates the community structure clustering. As a result of this
* method, a cluster tree will be computed and graph nodes will be
* annotated with both community and sequence indices.
* @param list the data list to cluster
* @param w an edge weighting function. If null, each edge will be
* given weight one.
*/
public function calculate(list:DataList, w:Function=null):void
{
compute(list.adjacencyMatrix(w));
_tree = buildTree(list);
labelNodes();
}
/** Computes the clustering */
private function compute(G:IMatrix):void
{
_merges = new MergeEdge(-1, -1); _qvals = [];
_size = G.rows;
var i:int, j:int, k:int, s:int, t:int, v:Number;
var Q:Number=0, Qmax:Number=0, dQ:Number, dQmax:Number=0, imax:int;
// initialize normalized matrix
var N:int = G.rows, Z:IMatrix = G.clone();
for (i=0; i dQmax) {
dQmax = dQ; eMax.update(i,j);
}
}
// perform merge on graph
i = eMax.i; j = eMax.j; if (j Qmax) {
Qmax = Q;
imax = ii;
}
_qvals.push(Q);
m = m.add(new MergeEdge(i,j));
}
}
} // end of class CommunityStructure
}