Defined in File EdgeSwitching.hpp
public NetworKit::Algorithm
(Class Algorithm)
EdgeSwitching and EdgeSwitchingInPlace implement the same algorithm — while the former copies the input graph provided and is more versatile, the in-place implementation only keeps a reference to the input graph.
The Edge
Switching Markov Chain [“The markov chain simulation method for generating connected
power law random graphs”, Mihail and Zegura] perturbates simple directed or undirected graphs while preserving their degrees. In each step, two edges are selected uniformly at random, and their endpoints exchanged. Swaps that introduce multi-edges or self-loops are rejected WITHOUT replacement
—this is necessary to allow uniform sampling [see “Switching edges to randomize
networks: what goes wrong and how to fix it”, Carstens and Horadam]. The number of successful swaps can be queried using
getNumberOfAffectedEdges()/2.It’s recommended to implement the preprocessing step in the calling code or to use copying EdgeSwitching implementation.
Note
In general, simple edge switching does not yield a uniform distribution on simple DIRECTED graphs because the orientation of directed triangles cannot be changed. Using DegreePreservingShuffle as a preprocessing step overcomes this limitation. The preprocessing can also jump-start the perturbation process, yielding to potentially faster mixing.
Public Functions
Constructs an EdgeSwitch algorithm that will change the input graph IN-PLACE.
Warning
For directed graphs preprocessing with DegreePreservingShuffle is necessary. Either do it manually, or use another constructor.
Attempts to carry out numberOfSwitchesPerEdge * numberOfEdges() edge swaps (i.e., rejected swaps are counted as well, see Algorithm’s description why)
Note
This function can be called several times. The graph’s topology may not be changed externally between two invocations.
Returns twice the total number of non-rejected swaps carried out during calls to run(). It hence has the same semantics as Curveball::getNumberOfAffectedEdges().
Note
If run() is called multiple time, the sum over all invocations is returned.
Return (average) number of switches per edge that will be executed on next run.
Modify (average) number of switches per edge that will be executed on next run.