5
$\begingroup$

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[123]
n = 15;
m = 20;

weights = ConstantArray[1., m];
G = RandomGraph[{n, m}, VertexLabels -> "Name"];
Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ 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? $\endgroup$
    – Szabolcs
    Mar 7, 2019 at 17:05
  • $\begingroup$ 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. $\endgroup$
    – Szabolcs
    Mar 7, 2019 at 17:16
  • $\begingroup$ 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, ... $\endgroup$
    – Szabolcs
    Mar 7, 2019 at 17:53
  • $\begingroup$ ... however if we chose $i=3,j=6$ then it would be this? $\endgroup$
    – Szabolcs
    Mar 7, 2019 at 17:53
  • $\begingroup$ 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". $\endgroup$
    – Szabolcs
    Mar 7, 2019 at 18:02

3 Answers 3

Reset to default
8
$\begingroup$

Maybe this is what you are looking for?

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

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


grad = With[{edges = UpperTriangularize[AdjacencyMatrix[G]]["NonzeroPositions"]},
   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]}]]}}
    ]
   ];
L = grad\[Transpose].DiagonalMatrix[SparseArray[conductances]].grad;

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 *)
Iedges = conductances grad.Unodes;

ϵ = 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]]
    )
 ]

enter image description here

This paper was extremely helpful for me in order to set this up:

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

Improve this answer
$\endgroup$
14
  • $\begingroup$ "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. $\endgroup$
    – Henrik Schumacher
    Mar 13, 2019 at 18:38
  • $\begingroup$ "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. $\endgroup$
    – Henrik Schumacher
    Mar 13, 2019 at 18:41
  • $\begingroup$ 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). $\endgroup$
    – Henrik Schumacher
    Mar 14, 2019 at 13:18
  • $\begingroup$ You're welcome. "but it's a grind work that hopefully pays off" - I am pretty sure that it will =D $\endgroup$
    – Henrik Schumacher
    Mar 14, 2019 at 15:24
  • $\begingroup$ 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. $\endgroup$
    – Henrik Schumacher
    Apr 3, 2019 at 11:13
1
$\begingroup$

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,#]&
Improve this answer
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – user52181
    Apr 11, 2019 at 14:12
  • 1
    $\begingroup$ @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. $\endgroup$
    – Fortsaint
    Apr 11, 2019 at 19:47
  • 1
    $\begingroup$ 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. $\endgroup$
    – Fortsaint
    Apr 11, 2019 at 22:26
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.