# Finding the dangling free part of a cluster connecting two nodes

I am trying to learn how to use Mathematica for analyzing graphs, more specifically in the context of connectivity and percolation.

For the sample graph that I have included in this post, we have a random graph to work with (see below).

• I am wondering, given how fast Mathematica is with its built-in randomgraph functionalities (e.g. FindPath, SpatialGraphDistribution, RandomGraph generation etc.), does there exist an efficient way of extracting or highlighting the backbone of the (percolating) cluster that connects two chosen nodes of the graph? The backbone is the conducting part of the cluster, that is, comprised of current carrying edges only, so e.g., the backbone is free of dangling ends of the percolating cluster.

Working graph example:

SeedRandom
n = 15;
m = 20;

weights = ConstantArray[1., m];
G = RandomGraph[{n, m}, VertexLabels -> "Name"];

• I don't quite understand what you want to highlight. Are you looking for a spanning tree? Can you define the backbone in precise and direct terms? Mar 7 '19 at 17:05
• Maybe you're looking for what is obtained using HighlightGraph[g, VertexDelete[g, IGTreelikeComponents[g]]] with the IGraph/M package. But that's not cycle-free (if that's what you mean by loop-free). It's exactly the opposite. Mar 7 '19 at 17:16
• I am still a bit confused. Taking the definition that it's the current carrying bonds: 1. Is it the case that this depends on the choice of $i$ and $j$ then? In this view, it should also depend on the resistances associated with graph edges. I assume we take all of them to have the same resistance. Take this example. What would be the backbone? Am I understanding correctly that if $i=1,j=5$ and all resistances are the same then it's this, ... Mar 7 '19 at 17:53
• ... however if we chose $i=3,j=6$ then it would be this? Mar 7 '19 at 17:53
• One point of confusion for me is that both of these have cycles. You said no loops (I assume by loops you meant cycles). However, they are consistent with the definition of "keep the current-carrying edges only". Mar 7 '19 at 18:02

Maybe this is what you are looking for?

SeedRandom
n = 15;
m = 20;
(*conductances=1/RandomReal[{0,1},m];*)

conductances = ConstantArray[1., m];
G = RandomGraph[{n, m}, VertexLabels -> "Name"];

With[{m = Length[edges]},
SparseArray @@ {Automatic, {m, n}, 0, {1, {
Range[0, 2 m, 2],
Partition[Flatten[edges], 1]
},
Flatten[Transpose[{ConstantArray[1., m], ConstantArray[-1., m]}]]}}
]
];


Now with source s and target t:

s = 1;
t = 2;
(* currents inserted at the nodes *)
Inodes = SparseArray[{{s}, {t}} -> {1., -1.}, {VertexCount[G]}, 0.];
a = SparseArray[ConstantArray[1., {1, n}]];
A = ArrayFlatten[{{L, a\[Transpose]}, {a, 0.}}];
S = LinearSolve[A];

(* potentials at the nodes *)
Unodes = S[Join[Inodes, {0.}]][[;; -2]];

(* currents through edges *)

ϵ = 1. 10^-8;
stylefun = x \[Function] Directive[Thickness[0.0001 + x 0.02], Opacity[1.], ColorData["DarkRainbow"][x]];

Graph[G, EdgeStyle -> (
Thread[EdgeList[G] ->stylefun /@ Normalize[Threshold[Abs[Iedges], ϵ], Max]]
)
] This paper was extremely helpful for me in order to set this up:

https://arxiv.org/pdf/1712.10263.pdf

• "In this example, so the thickness of the edges correspond to the current running through them? And I guess similarly for the coloring?" - Yes! "the path 1-11-6-7-14-2 in your example graph would also qualify as part of the backbone, right?" Yes. Actually, all edges apart from {3,9}, {12,15}, and {11,13} have nonzero current. Mar 13 '19 at 18:38
• "I wonder, how's the computational complexity of your calculation here compared to the one on resistance distances?" - Well, we employ the same saddle point matrix; the cost per pair of vertices is now one linear solve with S. So this is more expensive than what I did here to compute resistances between vertices. Mar 13 '19 at 18:41
• Nope, grad may remain as it is (it is actually not the gradient but rather the differential). The conductances really only appear where I put conductances (although it was constant in the experiment). Mar 14 '19 at 13:18
• You're welcome. "but it's a grind work that hopefully pays off" - I am pretty sure that it will =D Mar 14 '19 at 15:24
• At ii) grad is not equal to the incidence matrix because it contains signs. Indeed, each edge gets a more or less random orientation and grad is the signed incidence matrix of the directect graph. What are the signs for? Well, u.L.u should sum up the weighted squares of differences of u along the edges . Because of the squares, it does not matter if we sum conductances[[k]] (u[edges[[k,1]]] - u[edges[[k,2]]])^2 or conductances[[k]] (u[edges[[k, 2]]] - u[edges[[k, 1]]])^2 for the k-th edge. So does the chosen orientation of the edges not matter. Apr 3 '19 at 11:13

Aren't you asking for the union of all paths between the source and the target?

FindPath[G, 1, 2, Infinity, All] //
PathGraph /@ #& //
GraphUnion @@ #& //
HighlightGraph[G,#]&

• Oh this is so short and neat! So it seems it captures ultimately the same edges as does Henrik's approach, right? Except, we don't include the edge weights into the picture anymore. Can your approach be described as: taking the union of all possible self-avoiding walks between source-sink?
– user52181
Apr 11 '19 at 14:12
• @user929304 Yes. In graph theory, a path between two vertexes is self-avoiding by definition. That's why the solution is simply the union of all paths. Apr 11 '19 at 19:47
• Be careful that Henrik's approach catches the edges that have a "conductance" above a subjective and arbitrary value. So, if you set the epsilon too small, you might end up including dangling edges, if too high you exclude actual members of the backbone. Apr 11 '19 at 22:26

Here is a Code that @kglr developed as an answer to my Linear Programming problem. The flow between any source s and any target t can be found for directed graphs with vertices having two types of capacities: Absorption and Distribution capacities. One can find out all the existing pathways between a source s and a target t, as well as the associated maximum flow from s to t. The problem is a linear programming problem. See

Formulating a tailor-made Maximum Flow problem in a directed graph

See my answer to my own question at the very bottom of the above link.