?? communitystructure.as
字號:
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 <a href="http://arxiv.org/abs/cond-mat/0309508">Newman's
* fast algorithm for detecting community structure</a>. 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<N; ++i) Z.set(i,i,0); // clear diagonal
Z.scale(1 / Z.sum); // normalize matrix
// initialize column sums and edge list
var E:MergeEdge = new MergeEdge(-1,-1);
var e:MergeEdge = E, m:MergeEdge = _merges;
var eMax:MergeEdge = new MergeEdge(0,0);
var A:Array = new Array(N);
for (i=0; i<N; ++i) {
A[i] = 0;
for (j=0; j<N; ++j) {
if ((v=Z.get(i,j)) != 0) {
A[i] += v;
e = e.add(new MergeEdge(i,j));
}
}
}
// run the clustering algorithm
for (var ii:int=0; ii<N-1 && E.next; ++ii) {
dQmax = Number.NEGATIVE_INFINITY;
eMax.update(0,0);
// find the edge to merge
for (e=E.next; e!=null; e=e.next) {
i = e.i; j = e.j;
if (i==j) continue;
dQ = Z.get(i,j) + Z.get(j,i) - 2*A[i]*A[j];
if (dQ > dQmax) {
dQmax = dQ; eMax.update(i,j);
}
}
// perform merge on graph
i = eMax.i; j = eMax.j; if (j<i) { i=eMax.j; j=eMax.i; }
var na:Number = 0;
for (k=0; k<N; ++k) {
v = Z.get(i,k) + Z.get(j,k);
if (v != 0) {
na += v; Z.set(i,k,v); Z.set(j,k,0);
}
}
for (k=0; k<N; ++k) {
v = Z.get(k,i) + Z.get(k,j);
if (v != 0) {
Z.set(k,i,v); Z.set(k,j,0);
}
}
A[i] = na;
A[j] = 0;
for (e=E.next; e!=null; e=e.next) {
s = e.i; t = e.j;
if ((i==s && j==t) || (i==t && j==s)) {
e.remove();
} else if (s==j) {
e.i = i;
} else if (t==j) {
e.j = i;
}
}
Q += dQmax;
if (Q > Qmax) {
Qmax = Q;
imax = ii;
}
_qvals.push(Q);
m = m.add(new MergeEdge(i,j));
}
}
} // end of class CommunityStructure
}
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -