BasicNotions.hpp File Reference

Plans regarding notions of bicliques. More...

Go to the source code of this file.

Detailed Description

Plans regarding notions of bicliques.

The notion of a "biclique"
  • General discussion:
    1. The "full" mathematical notion of a biclique B in a (general/multi-) graph G is that of a sub-graph of G, which itself is a complete bipartite graph.
    2. Since the edges determine the sub-graph B, it is natural to represent B by a set B' of edges.
    3. However then we have the problem, that this notion is not stable under sub-set-formation, i.e., a subset of B' in general is not again a biclique.
    4. So for multigraphs and graphs G alternatively we can use sets of *vertices* B' such that we can find edges in B' making it a complete biclique.
    5. For graphs this is the subgraph induced by B'
    6. However, then it is needed to specify the bipartitioning, since in general there are many ways that a set of vertices could form a biclique.
  • For multigraphs a biclique partition is a "numerical condition", which seems perfectly appropriate since multigraphs are close to combinatorial matrices.
  • Only for general graphs, where the edges have an identity, we need to know precisely which edges are part of the biclique.
  • So we could speak of a "subgraph-biclique", "edge-set-biclique" and "vertex-set-biclique" (where the latter is a pair of vertex-sets).
  • For the ordered graph versions instead a vertex-sets we have vertex-lists, and their order must conform with the given total order; the abbreviation then is "ovbc".
  • DONE (since we need two subsets, it's not really a hypergraph) The vertex-bicliques then form a hereditary hypergraph (vertices the vertices of the given graph; "hereditary" means that for every hyperedge also every subset is a hyperedge, where here we must exclude subsets of size 0 or 1).
  • DONE (solved by using pairs) Likely for (general) digraphs for a given vertex-biclique there are several possibilities to interprete it as a edge-biclique, but otherwise there should be no ambiguities.
  • A subgraph-biclique as well as an edge-biclique can be refined by specifying an associated vertex-biclique (which fixes the bipartitioning).
  • "bc" for "biclique".
  • Bicliques exist as "sbc", "ebc" and "vbc" (subgraphs, edge-sets or vertex-sets).
  • A test would be named e.g. "sbc_ogdg_p".
Maximal biclique
  • We need tests for checking whether a biclique is maximal (cannot be extended).
  • We need maximal_bc_ogl.
  • We need a version of maximal_bc_ogl allowing randomisation.
    1. One control parameter is the given order of the vertices.
    2. And then we have 0 <= p <= 1, which controls the probability that the left or right side is considered first.
  • For an algorithm finding all maximal bicliques see ComputerAlgebra/Graphs/Lisp/Bicliques/plans/Consensus.hpp.
  • And regarding *maximum* bicliques see "Maximum bicliques" in ComputerAlgebra/Graphs/Lisp/Bicliques/plans/general.hpp.

Definition in file BasicNotions.hpp.