3
$\begingroup$

Context:

When studying percolation in finite sized systems, there exist various definitions and criteria for determining when a given system is percolating, i.e. it contains a spanning connected cluster. Such systems can e.g. be bond/site percolation in 2D.

Two commonly used definitions are (i) the side-to-side spanning one, where a connected cluster connects two side/walls of the system together. This is generally used when the system has open boundaries (no periodic conditions). (ii) the wrapping criterion, where a connected cluster wraps the system (box, domain, etc). This definition is used when the system domain is endowed with periodic boundary conditions. Wrapping is usually described in terms of: all constituent bonds/sites in the wrapping cluster being connected by a contiguous path to their own periodic image.

More formally, snippets from literature (Newman and Ziff 2001, also relevant is Fig 7.):

Cluster spanning: In many calculations one would like to detect the onset of percolation in the system as sites or bonds are occupied. One way of doing this is to look for a cluster of occupied sites or bonds which spans the lattice from one side to the other...

Cluster wrapping: An alternative criterion for percolation is to use periodic boundary conditions and look for a cluster which wraps all the way around the lattice...

However, at least to me, the latter is still a very counter-intuitive image of what such cluster might look like, and how it differs from the more conventional spanning definition.

I was wondering, whether it would be possible to visualise what it means to have a wrapping cluster, and to compare with the spanning one. For instance, highlighting the path that connects a given bond/site to its periodic image. Or maybe it would be more helpful didactically to also draw a number of periodic images of the system in order to capture the wrapping more intuitively. Another idea might be to map system to a graph and show that wrapping leads to loops in graph representation.

Question:

  • Is there a way using Mathematica's built-in graphics functionalities to visualise what a wrapping cluster looks like, or possibly showing how it differs from a simple spanning one, such that the definition of wrapping the lattice or system becomes visually clear? Any ideas would be most appreciated. I have to add that in Mathematica, I do not have a detection routine for finding wrapping clusters, but below I copy a quick way of setting up a percolation problem in Mathematica.

(This is asked in the context of teaching, I figured it would be helpful to learn to visualise these different criteria for percolation, instead of just giving formal definitions.)

Dummy example:

g = GridGraph[{10, 10}];
SeedRandom[100];
g2 = Graph[VertexList[g], 
   RandomSample[EdgeList[g], Floor[EdgeCount[g] .49]], 
   VertexCoordinates -> GraphEmbedding[g], 
   EdgeStyle -> Thickness[.01], VertexStyle -> EdgeForm[], 
   VertexSize -> Medium];
HighlightGraph[g2, Subgraph[g2, #] & /@ ConnectedComponents[g2]]

Which results in:

enter image description here

but this is only with open boundaries (no periodicity, so no wrapping), and the big red cluster is a spanning one as it connect left-right side of the lattice.

Other related posts:

Improve this question
$\endgroup$
2
  • $\begingroup$ The connection between the two criteria is essentially that any wrapping graph is a spanning graph, but the converse is not true (e.g. if you have a graph spanning from the top left to the middle right, the graph is spanning, but not wrapping) $\endgroup$
    – Lukas Lang
    Sep 2, 2020 at 14:41
  • $\begingroup$ @LukasLang Very useful remark, thank you! Is there a way one could visualise your first sentence, namely, to see that wrapping clusters are spanning? (in a purely imaginative way, for me it's difficult to make the connection of why a cluster connected to itself via periodic boundaries, is similar to a cluster spanning the walls of a system). Incidentally, any recommended references where these things might be fleshed out more intuitively, would be most helpful. Thanks again $\endgroup$
    – CuriousBadger
    Sep 2, 2020 at 15:00

1 Answer 1

Reset to default
3
$\begingroup$

Here a potential way to illustrate the difference between wrapping and spanning clusters: (see the comments in the code for an explanation of what it does)

replicateGraph[n_, g_] :=
 VertexReplace[g, v_ :> v + #] &(* create copies of the graph with translated vertices *)/@
  (ReverseSortBy[Abs]@Tuples[{-1, 0, 1}, {2}] (n - 1))(* translate the graph by 0,+-1 in x/y *)
wrapGraph[n_, g_, sg_] :=
 GraphUnion @@ replicateGraph[n, g] //(* combine the 9 graph copies*)
   Graph[(* apply basic styling & reconstruct the vertex coordinates *)
     #,
     VertexCoordinates -> VertexList@#,
     VertexSize -> Medium,
     BaseStyle -> {EdgeForm[], [email protected], Thickness[.01]}
     ] & // HighlightGraph[(* highlight the spanning clusters *)
    #,
    sg // Map[
       replicateGraph[n, #] & /*(* replicate all graphs that need to be highlighted *)
        Map[Join[VertexList@#, EdgeList@#] &] /*(* get the edges & vertices of all subgraphs to apply stlying to them *)
        MapAt[Style[#, Darker@Red] &, {-1}] /*(* apply styling to the last graph (the center one) *)
        MapAt[Style[#, Lighter@Lighter@Red] &, {;; -2}](* apply styling to the outer graphs *)
       ] //
     Flatten(* flatten into one list *)
    ] &

n = 8;
g = GridGraph[{n, n}];
g = VertexReplace[(* create grid graph where vertex names are their coordinates *)
   g,
   Thread[VertexList@g -> Round@GraphEmbedding@g],
   VertexCoordinates -> GraphEmbedding@g
   ];
SeedRandom[109];
g2 = EdgeDelete[(* delete some edges *)
   g,
   RandomSample[EdgeList@g, Round[0.51 EdgeCount@g]]
   ];
spanning = ConnectedComponents[g2] //(* get clusters *) 
    Select[(* select spanning clusters by looking at the coordinates of the vertices *)
     MinMax@#[[All, 1]] == {1, n} ||
       MinMax@#[[All, 2]] == {1, n} &
     ] // Map[Subgraph[g2, #] &](* convert to subgraphs *);
Show[
 wrapGraph[n, g, spanning],(* create a 3x3 grid of graph replicas *)
 GridLines -> {{1, n}, {1, n}},(* add grid lines to plot *)
 Method -> {"GridLinesInFront" -> True}
 ]

enter image description here

As you can see, the cluster is spanning from left to right, but it doesn't connect to the copies of itself in the neighboring cells, so this cluster is spanning, but not wrapping. Changing the seed to 105 yields this image:

enter image description here

Here, the cluster is spanning and wrapping on both axes. Changing the seed to 106 results in a case where the cluster is spanning and wrapping only along the horizontal direction:

enter image description here

Improve this answer
$\endgroup$
5
  • $\begingroup$ What a beautiful demonstration Lukas, thank you! This makes the teaching much easier ;) Out of curiosity, I wonder if it's really impossible to have a wrapping cluster that is not in fact spanning! $\endgroup$
    – CuriousBadger
    Sep 3, 2020 at 11:36
  • $\begingroup$ I am pretty sure that "wrapping but not spanning" is impossible: For a wrapping cluster, each point $(x,y)$ is connected to $(x+n,y)$ (i.e. its copy in the next $n\times n$ cell to the left). If you choose a point $(0,y)$ on the left boundary (which exists, because there exist points on the left and right of the boundary are connected, and the path between them necessarily crosses the boundary), then you get that this point $(0,y)$ is connected to $(n,y)$ which shows that you have a spanning cluster $\endgroup$
    – Lukas Lang
    Sep 3, 2020 at 12:23
  • $\begingroup$ I see what you mean, but what if it is only connecting say the bottom side to the right side, then it's not spanning, but wrapping, I have found one example in this paper (see Fig. 8 and the right plot). $\endgroup$
    – CuriousBadger
    Sep 3, 2020 at 12:25
  • $\begingroup$ @CuriousBadger I see, I seem to have misinterpreted the definition for wrapping clusters - still, I think if one allows the cell to be moved around (essentially changing the origin, which is allowed due to the periodic boundary conditions), one should always find a position such that the wrapping cluster is in fact spanning. I am not entirely sure about this though $\endgroup$
    – Lukas Lang
    Sep 4, 2020 at 12:43
  • $\begingroup$ hmmm, good hunch! Maybe we can achieve that by simply translating the whole cluster by an amount such that it lies in the centre of the cell? Or a similar idea with translations. $\endgroup$
    – CuriousBadger
    Sep 5, 2020 at 12:10

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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.