# Running TG betweenness centrality on virtual network

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;

"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];

}
``````

This might be slow. unless the size of the backbone is very small. (However, the graph scale that can run BC is small too.)

If the size is very big, @@all = createBackbone(@@proteins); copies vertexes from sub query to a set @@all. And bc_subquery(s, @@all, maxHops) copies @@all every time you call the sub query. that means we copied @@all.size() * @@all.size() vertexes during the calculation.

One possible way to improve this is to have createBackbone query to update the attribute, then modify the bc_subquery query to make it only traverse the vertexes got the attribute update. However, this will require you to run two separate queries.

Hope this helps.

Ah but i can’t modify the attribute of the network. The idea is that many backbone network can be build and analyse at the same time, by different users.