1
$\begingroup$

For "regular" graphs (lattices, if you will), it's easy to define the percolation threshold $p_c$ as the critical probability beyond which the infinite graph will contain an infinitely large cluster with probability 1. (And below that, with probability 0).

In practice, you can measure that by doing a finite-size analysis and extrapolating.

But what if I'm interested in just the percolation properties of a single instance of a given finite graph?

In that case, I can personally think of a few ways to define a percolation threshold, but it wouldn't be unique. For example, you could say: "For a graph $G$ let $p_c$ be the probability such that the largest cluster will have size $n|G|$ with probability $p > 0.99$ or something like that.

But I wonder if there's one common definition that everyone in the research community uses?

I find it hard to nail down my literature search, probably because I'm using the wrong terms. All papers I could dig up so far talk about finite-size-scaling analysis but with the goal at arriving at $p_c$ for the infinite graph. Pointers in the right direction would be appreciated.

$\endgroup$
  • $\begingroup$ there is some work on the emergence of a giant component that seems related math.cmu.edu/~af1p/Texfiles/quasigiant.pdf $\endgroup$ – Sasho Nikolov Oct 17 '16 at 20:01
  • $\begingroup$ A nice find, but they still focus on the limit $n \rightarrow \infty$ from what I could skim $\endgroup$ – Lagerbaer Oct 17 '16 at 20:19
  • $\begingroup$ I think you will be hard pressed to find literature for the truly finitary case, (no limits and no asymptotics) exactly because there is no way to make a canonical choice among various possible definitions. $\endgroup$ – Sasho Nikolov Oct 17 '16 at 21:05
  • $\begingroup$ Okay. Well, I guess that's cool too. Just wanted to make sure that when I use my definition I'm not wasting time by not following the "official" definition :) $\endgroup$ – Lagerbaer Oct 17 '16 at 23:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.