vertex_percolation

graph_tool.topology.vertex_percolation(g, vertices, second=False)

Compute the size of the largest or second-largest component as vertices are (virtually) removed from the graph.

Parameters:

gGraph

Graph to be used.

verticesnumpy.ndarray or iterable of ints

List of vertices in reversed order of removal.

secondbool (optional, default: False)

If True, the size of the second-largest component will be computed.

Returns:

sizenumpy.ndarray

Size of the largest (or second-largest) component prior to removal of each vertex.

compVertexPropertyMap

Vertex property map with component labels.

Notes

The algorithm runs in \(O(V + E)\) time.

References

[newman-ziff]

M. E. J. Newman, R. M. Ziff, “A fast Monte Carlo algorithm for site or bond percolation”, Phys. Rev. E 64, 016706 (2001) DOI: 10.1103/PhysRevE.64.016706 [sci-hub, @tor], arXiv: cond-mat/0101295

Examples

>>> g = gt.random_graph(10000, lambda: geometric(1./4) + 1, directed=False)
>>> vertices = sorted([v for v in g.vertices()], key=lambda v: v.out_degree())
>>> sizes, comp = gt.vertex_percolation(g, vertices)
>>> numpy.random.shuffle(vertices)
>>> sizes2, comp = gt.vertex_percolation(g, vertices)
>>> figure()
<...>
>>> plot(sizes, label="Targeted")
[...]
>>> plot(sizes2, label="Random")
[...]
>>> xlabel("Vertices remaining")
Text(...)
>>> ylabel("Size of largest component")
Text(...)
>>> legend(loc="upper left")
<...>
>>> savefig("vertex-percolation.svg")

Targeted and random vertex percolation of a random graph with an exponential degree distribution.