Hipergrafos
Definições básicas
Um hipergrafo (rede de ordem superior) é definido pelo par \(\mathcal{H} = (\mathcal{V},\mathcal{E})\), em que \(\mathcal{V}\) é o conjunto de nós e \(\mathcal{E}\), de arestas (hiperarestas).
Formalmente, partimos de um conjunto de incidências, definido como conjunto enumerável de pares ordenados: \(\mathcal{F} \subset \mathbb{N} \times \mathbb{N}\). Cada elemento \(f \in \mathcal{F}\) é chamado de uma incidência, escrito como \(f = (f_1, f_2)\). Assim, dado dois elementos \(f,g\in\mathcal{F}\), podemos definir as relações:
- \(\sim_\nu\): \(f \sim_\nu g \iff f_1 = g_1\);
- \(\sim_\eta\): \(f \sim_\eta g \iff f_2 = g_2\);
que são, de fato, relações de equivalência (a demonstração é imediata, uma vez que a igualdade \(=\) garante reflexividade, simetria e transitividade).
Assim, o conjunto de vértices é definido como o conjunto quociente de \(\mathcal{F}\) pela relação \(\sim_\nu\): \[\mathcal{V} := \mathcal{F} / \sim_\nu \ = \Big\{ [f]_\nu \ \Big|\ f \in \mathcal{F} \Big\}\,;\] intuitivamente, isto significa que um nó é definido tomando a lista de todas as interações de que ele participa. Analogamente, o conjunto de hiperarestas é definido como o conjunto quociente de \(\mathcal{F}\) pela relação \(\sim_\eta\): \[\mathcal{E} := \mathcal{F} / \sim_\eta \ = \Big\{ [f]_\eta \ \Big|\ f \in \mathcal{F} \Big\}\,;\] intuitivamente, isto significa que uma hiperaresta é definida tomando a lista de todos os nós presentes na interação.
Esta definição formal tem algumas vantagens naturais:
- Ela parte do modelo configuracional de rede bipartida: cada incidência \(f\in\mathcal{F}\) representa uma “ligação” entre um nó e uma hiperaresta;
- Dado um conjunto de incidências \(\mathcal{F}\), podemos definir o hipergrafo dual \(\mathcal{H}^\star\) simplesmente invertendo as regras: \(\sim_\nu\) passa a definir as hiperarestas, e \(\sim_\eta\), os nós;
- Podemos facilmente generalizar para outros hipergrafos (com peso, direcionados, simplicial complex, \(\dots\)) apenas alterando a definição das classes de equivalência.