edge_percolation

graph_tool.topology.edge_percolation(g, edges, second=False)

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

Parameters:

gGraph

Graph to be used.

edgesnumpy.ndarray or iterable of pairs of ints

List of edges in reversed order of removal. If the type is numpy.ndarray, it should have a shape (E, 2), where E is the number of edges, such that edges[i,0] and edges[i,1] are the both endpoints of edge i.

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 edge.

compVertexPropertyMap

Vertex property map with component labels.

Notes

The algorithm runs in \(O(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)
>>> edges = sorted([(e.source(), e.target()) for e in g.edges()],
...                key=lambda e: e[0].out_degree() * e[1].out_degree())
>>> sizes, comp = gt.edge_percolation(g, edges)
>>> numpy.random.shuffle(edges)
>>> sizes2, comp = gt.edge_percolation(g, edges)
>>> figure()
<...>
>>> plot(sizes, label="Targeted")
[...]
>>> plot(sizes2, label="Random")
[...]
>>> xlabel("Edges remaining")
Text(...)
>>> ylabel("Size of largest component")
Text(...)
>>> legend(loc="lower right")
<...>
>>> savefig("edge-percolation.svg")

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