Wishlist: Giant component and percolation

[szhorvat]

What is the feature or improvement you would like to see?

Port IGPercolationCurve[] from IGraph/M to the C core, with potential generalizations.

See http://szhorvat.net/mathematica/IGDocumentation/#igpercolationcurve

This can be implemented using a union-find data structure.

Can be extended to support both bond percolation (edge removal) and site percolation (vertex removal). These should be two different functions.

Use cases for the feature

Percolation is among the most studies processes on networks. This functionality is useful both for teaching and research.

References

–

[ayushjariyal]

Hi @szhorvat , I want to try this issue. Is this still unresolved?

[szhorvat]

@Zepeacedust was intending to take this one. @Zepeacedust, let me know if you are still interested.

[Zepeacedust]

Yep, I have started to work on it.
I just don't know how to/if I should assign myself to it.

[szhorvat]

Please follow the quick start guide: https://github.com/igraph/igraph/wiki/Quickstart-for-new-contributors This should be targeted on master instead of develop.

Let's do bond percolation first.

[szhorvat]

@Zepeacedust As a first step, do you have a proposal for an interface: what is the input and output? My initial thoughts are along these lines:

Input:

• A graph.
• An order in which either edges or vertices are removed. This can be given as a vector of edge/vertex IDs.

Output:

• The fraction of nodes in the largest component after removals executed so far.
• Perhaps the mean degree after the removals so far. We need to think about what properties are the most useful to return here. This can be an optional output.

Variations on the function:

• There could be an additional function that takes not a graph, but an edge list as input. This would do the bulk of the work. The edge list can be given in the same format that igraph_add_edges() and igraph_get_edgelist() use. Note that IGPercolationCurve also takes this as input. To decide: Are edges give in the order of removal or the order in which they are added?

[Zepeacedust]

I think that giving an order to the removal would be nice, at least as an option.

My thoughts on the interface would then be along the lines of:
Input:

• A graph
• List of edges or vertices to remove

Output:

• Fraction of nodes in the largest component

With perhaps some exposed functions to make similar functionality.