easygraph.functions.hypergraph.hypergraph_operation module#

easygraph.functions.hypergraph.hypergraph_operation.hypergraph_density(hg, ignore_singletons=False)[source]#

Hypergraph density.

The density of a hypergraph is the number of existing edges divided by the number of possible edges.

Let H have \(n\) nodes and \(m\) hyperedges. Then,

density(H) = \(\frac{m}{2^n - 1}\),
density(H, ignore_singletons=True) = \(\frac{m}{2^n - 1 - n}\).

Here, \(2^n\) is the total possible number of hyperedges on H, from which we subtract \(1\) because the empty hyperedge is not considered. We subtract an additional \(n\) when singletons are not considered.

Now assume H has \(a\) edges with order \(1\) and \(b\) edges with order \(2\). Then,

density(H, order=1) = \(\frac{a}{{n \choose 2}}\),
density(H, order=2) = \(\frac{b}{{n \choose 3}}\),
density(H, max_order=1) = \(\frac{a}{{n \choose 1} + {n \choose 2}}\),
density(H, max_order=1, ignore_singletons=True) = \(\frac{a}{{n \choose 2}}\),
density(H, max_order=2) = \(\frac{m}{{n \choose 1} + {n \choose 2} + {n \choose 3}}\),
density(H, max_order=2, ignore_singletons=True) = \(\frac{m}{{n \choose 2} + {n \choose 3}}\),

Parameters:

order (int, optional) – If not None, only count edges of the specified order. By default, None.
max_order (int, optional) – If not None, only count edges of order up to this value, inclusive. By default, None.
ignore_singletons (bool, optional) – Whether to consider singleton edges. Ignored if order is not None and different from \(0\). By default, False.