Sampling.hpp File Reference

Plans regarding sampling of biclique partitions in (general) graphs. More...

Go to the source code of this file.

Detailed Description

Plans regarding sampling of biclique partitions in (general) graphs.

Sampling maximal vertex-bicliques
  • First task, given an ordered graph, find a maximal ordered biclique.
    1. Parameter 0 <= p <= 1.
    2. Run through the vertices in the given order, try to add it to one of the sides of the biclique, and if both are possible, then use p for a random choice.
    3. One possibility for the check is that the new vertex is always checked against all vertices already in the biclique.
    4. The other possibility is that for both parts of the biclique we maintain the set of vertices addable to it, and then for a new vertex we only need to check membership.
Sampling maximal edge-bicliques
  • The algorithms from [Crama/Hammer et al, Consensus algorithms ..., DAM 2004] yield poly-delay algorithms for enumerating all maximal bicliques; see ComputerAlgebra/Graphs/Lisp/Bicliques/plans/Consensus.hpp.
  • Another algorithm is [Sanderson et al, Molecular Biology and Evolution, 20(7)].
  • A central question for us now is whether, just running them once, randomised, we also obtain (reasonable) sampling of all maximal bicliques.
  • More precisely, randomising the starting conditions appropriately, can every maximal biclique be created (and this with reasonable fair distribution)?
  • This then could be used in the natural greedy biclique partitioning algorithm (grabbing some maximal bicliue, remove the edges, repeat ...).

Definition in file Sampling.hpp.