Skip to content

Instantly share code, notes, and snippets.

@mhawksey
Created January 26, 2012 16:11
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save mhawksey/1683530 to your computer and use it in GitHub Desktop.
Google Apps Script (JavaScript) to calculate betweenness centraility
// compute betweenness of each node in a network
// using the Brandes algorithm
// modified from NetVis Module 2.0
// by Jonathon N. Cummings
function compute_betweenness(matrix,ncols){
var betweenness = [];
var bMax = 0;
Logger.log(new Date()+":make betweenness matrix ...");
for(var i=0; i<ncols; i++){
betweenness[i]=0;
}
for(var s=0; s<ncols; s++){
var stack=[],
P=[],
sigma=[],
dist=[];
for(i=0;i<ncols;i++){
P[i]=[];
if(i==s){
sigma[i]=1;
dist[i]=0;
}else{
sigma[i]=0;
dist[i]=-1;
}
}
var queue=[];
queue.push(s);
while(queue.length > 0){
Logger.log(new Date()+":queue length: "+queue.length);
var v=queue.shift();
stack.push(v);
for(var w=0; w<ncols; w++){
if(matrix[v][w]==1){
if(dist[w] < 0){
//queue[]=w;
queue.push(w);
dist[w]=dist[v] + 1;
}
if(dist[w]==dist[v] + 1){
sigma[w]=sigma[w] +sigma[v];
//P[w][]=v;
P[w][P[w].length] = v;
}
}
}
}
var delta=[];
for(var i=0; i<ncols; i++){
delta[i]=0;
}
while(stack.length>0){
Logger.log(new Date()+":stack length: "+stack.length);
w=stack.pop();
for(var i=0; i<P[w].length; i++){
v=P[w][i];
delta[v] +=(sigma[v] /sigma[w]) * (1 +delta[w]);
}
if(w != s){
betweenness[w] +=delta[w];
}
}
}
for (var i=0; i<ncols; i++){
betweenness[i]=[(betweenness[i]/(2))];
if (betweenness[i] > bMax) bMax = betweenness[i][0];
}
ScriptProperties.setProperty("Betweenness",bMax);
return betweenness;
}
function calcBetweenness(){
var doc = SpreadsheetApp.getActiveSpreadsheet();
var edgeSheetName = "Edges";
var verticesSheetName = "Vertices";
var sheetE = doc.getSheetByName(edgeSheetName);
var sheetV = doc.getSheetByName(verticesSheetName);
var test = sheetV.getLastRow();
var user_ids = sheetV.getRange(2,2,sheetV.getLastRow()-1,1).getValues();
var edge_ids = sheetE.getRange(2,1,sheetE.getLastRow()-1,2).getValues();
Logger.log(new Date()+":make matrix ...");
var matrix = new Array(user_ids.length);
for (i=0; i <user_ids.length; i++) matrix[i]=replicate(user_ids.length,0);
for (var i=0; i<user_ids.length; i++){
Logger.log(new Date()+":user ..."+(i+1));
for (var j=0; j<user_ids.length; j++){
for (var k=0; k<edge_ids.length; k++){
if (user_ids[i][0]==edge_ids[k][0] && user_ids[j][0]==edge_ids[k][1]){
matrix[i][j] = 1;
break;
} else {
matrix[i][j] = 0;
}
}
}
}
Logger.log(new Date()+":... matrix made");
Logger.log(new Date()+":compute_betweenness");
var betweenness = compute_betweenness(matrix,user_ids.length);
var user_ids = sheetV.getRange(2,6,betweenness.length,1).setValues(betweenness);
}
@biarm
Copy link

biarm commented Jun 29, 2015

Martin, it seems ScriptProperties API is deprecated, which makes the script unfunctionable. Do you think there is a way to fix it? I just wanted to run it with a small number of vertices.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment