Questions tagged [percolation]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
0answers
167 views

What is the *generally accepted* definition for the percolation threshold on finite-sized graphs?

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 ...
0
votes
1answer
184 views

Clique-Percolation Algorithm's “corner cases”

I'm programming an implementation of the Clique-Percolation algorithm, but I have many doubts about some corner cases. Imagine we want to find the communities of a graph using $k=4$. We are lucky and ...
7
votes
7answers
1k views

What is an accessible introduction to Percolation Theory?

What is the best place to start for someone in Computer Science with a graduate level background in linear algebra, probability theory, and graph theory?
8
votes
1answer
392 views

Complexity of percolation

In the context of bond percolation on $\mathbb{Z}^d$ where $d$ is a positive integer, consider the problem of computing a $2^{-k}$-approximation of the critical percolation $p_c$ given a lattice ...