I’m trying to adapt TG betweenness centrality algorithm to run on a virtual network, that we call a backbone network.
More specifically, the backbone network, is a selection of nodes, as opposed to all the node in the networks.
Here is my attempt at it, please confirm if the adaptation is the way to go?
Original algorithm can be find here: https://github.com/tigergraph/gsql-graph-algorithms/blob/master/algorithms/examples/Centrality/betweenness_cent.gsql
MMy adaptation is mostly about flagging the network the node that are part of the virtual/backbone network and testing it, as opposed to {ANY} node.
CREATE QUERY bc_subquery (VERTEX<Protein> source, SET<VERTEX<Protein>> backboneNetwork, INT maxHops) FOR GRAPH PPI RETURNS(MapAccum<vertex, float>) {
/* The TigerGraph implementation is based on A Faster Algorithm for Betweenness Centrality by Ulrik Brandes, Journal of Mathematical Sociology 25(2):163-177, (2001). According to the algorithm, sigma is the number of shortest paths from source; delta is the pair dependency from source; and dist is the shortest distance from source. The subquery returns a map of (s.id->s.@delta)
*/
SumAccum<float> @sigma;
SumAccum<float> @delta;
MaxAccum<int> @dist;
SumAccum<int> @@currDist = 0;
MapAccum<vertex, float> @@MapDelta;
//To identify what it part of the backboneNetwork
OrAccum @backbone = false;
//The BackBoneNetwork, include the source vertex.
All = backboneNetwork;
All = Select s From All:s
Accum s.@backbone = true;
Start = {source};
Start = SELECT s FROM Start:s
ACCUM s.@sigma = 1, s.@dist = 0;
# traverse in the order of increasing distance and calculate @sigma and @dist
WHILE (Start.size()>0) LIMIT maxHops DO # explore up to (maxHops) hops FROM s
@@currDist += 1;
Start = SELECT t FROM Start:s-(Binding:e)->:t
WHERE t.@backbone == true and t.@dist < 0
ACCUM t.@sigma += s.@sigma,
t.@dist = @@currDist;
END;
@@currDist += -1;
Start = SELECT s FROM All:s
WHERE s.@dist == @@currDist;
# traverse in the order of non-increasing distance and calculate @delta
WHILE (@@currDist>0) DO
@@currDist += -1;
Start = SELECT s FROM Start:s -(Binding:e)->:t
WHERE t.@backbone == true and t.@dist == s.@dist-1
ACCUM t.@delta += t.@sigma/s.@sigma*(1+s.@delta);
Start = SELECT s FROM All:s
WHERE s.@dist == @@currDist;
END;
Start = SELECT s FROM All:s
ACCUM
CASE WHEN s!=source THEN
@@MapDelta += (s->s.@delta/2)
ELSE @@MapDelta += (s->0)
END;
return @@MapDelta;
CREATE QUERY ppi_betweenness_cent () FOR GRAPH PPI {
# Betweenness Centrality main query
MapAccum<VERTEX,SumAccum<float>> @@BC;
SumAccum<float> @localBC;
SetAccum<Vertex<Protein>> @@all;
SetAccum<String> @@proteins;
# measure distance for vertices up to 10 hops away
INT maxHops = 10;
/*@@proteins = ("ACE2","ADD1","ADIPOQ","ADRA2B","ADRB1","ADRB2",
"AGT","AGTR1","ALDH2","ATP1A1","ATP1B1","BDKRB2",
"CACNA1C","CACNA1D","CALCA","CHGA","CLCNKB","CYBA","CYP11B2",
"CYP19A1","CYP2J2","CYP4A11","CYP4F2","EMILIN1","FABP3","FBN1","FURIN","GDF15",
"GNB3","GRK4","GSTM3","GUCA2B","HMOX1","HSD3B1","HSPA4","IL10","IL6","KL","KLK1",
"KLKB1","KNG1","MTHFR","NEDD4L","NOS3","NPPB","NPR1","NR3C2","P2RY2","PNMT","PPARG","PSMA6","PTGER2",
"PTK2B","PTPN1","REN","RNLS","SCNN1A","SCNN1B","SELE","SLC6A9","SLC7A1","SLCO1B1","SOD3","TGFB1","TH","TNFRSF4","VEGFA","WNK1","WNK4");*/
@@proteins = ("APOA1", "APOA4", "APOC3", "C7", "FGFR4", "LGALS3BP", "LGALS4", "MFAP4", "P4HA1", "TAGLN", "TPM2", "TPM4");
@@all = createBackbone(@@proteins); //Orginal protein and their 1 hop neighbour optionally those within their shortest path.
backbone = @@all;
backbone = SELECT s FROM backbone:s
ACCUM @@BC += bc_subquery(s, @@all, maxHops);
backbone = SELECT s FROM backbone:s
ACCUM s.@localBC += @@BC.get(s)
ORDER BY s.@localBC DESC;
PRINT backbone[backbone.name as name, backbone.@localBC as bc_Score];
}