5 ms·
Not an expert, but analysis of very large graphs is already computationally expensive. Does generalizing to hypergraphs ease this in any way? The cost-benefit
by _gmax0 3y ago
Not an expert, but analysis of very large graphs is already computationally expensive.
Does generalizing to hypergraphs ease this in any way? The cost-benefit trade-off seems to be greater computational complexity for potentially unobserved insights.
- zmgsabst 3y agoHypergraphs 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
- dleeftink 3y agoFor 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 https://github.com/anvaka/ngraph.coarsen
- zmgsabst 3y agoI 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.
- woolion 3y agoNot 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.
- _gmax0 3y agoExisting graph-theoretic analysis would still apply to hypergraphs after essentially redefining the graph using coloring algorithms no?
- gilleain 3y agoI'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 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.