Hacker News Reader

Comment by zmgsabst | Hacker News Reader

Hypergraphs do two things:

- they provide a type for conclusions that span several nodes, eg a ring’s interior is a node that represents the existence of a ring (and so cache your analysis conclusions)

- they allow for generalization by placing nodes within a cell, eg “people who make $50k-$150k/yr” can be a collection of people within a cell (and we can talk about aggregated edges from that cell’s interior to other objects)

A third (but useful in a different context):

- logic can be represented as hypergraphs and deduction rules on them

View on HN

For the first two, these relationships can be modelled from the derived community graph of a binary network, so I am interested to see the performance gains over the binary approach.

See for instance, the ngraph coarsen procedure that reduces communities and their interrelations to single nodes connected to other community nodes [0].

[0]: https://github.com/anvaka/ngraph.coarsen

I too would be curious to see the comparison of different approaches.

But my intuition is that caching derived graphs and caching computed cells will be similar — and might even be two conceptual frameworks on equivalent data.

Not only that but there are lots of good results and algorithms on 'bipartite graphs', which are the kind that encode hypergraphs, so in practice it should work very well.

Existing graph-theoretic analysis would still apply to hypergraphs after essentially redefining the graph using coloring algorithms no?

I'm not sure if there is a neat relation between labelled (coloured) simple graphs and hypergraphs, however there is (from https://en.wikipedia.org/wiki/Hypergraph) :

> Hypergraphs can be viewed as incidence structures. In particular, there is a bipartite "incidence graph" or "Levi graph" corresponding to every hypergraph

Where the relation is one-to-one, so there is a Levi graph for every hypergraph and the reverse is also true.

Reply on news.ycombinator.com