Are hypergraph partitioning, and bipartite graph partitioning related, or equivalent, given that hypergraphs can be represented as bipartite graphs?

In the first case, we want to partition the set of vertices only based on edge information.

In the second case, we want to partition both the set of vertices (left nodes in the bipartite graph) and the set of edges (right nodes in the bipartite graph).

From this perspective, the problems seem different. But maybe existing bipartite partitioning methods allow to control the number of partitions on the right nodes (edges) to be 1, and hence reduce one problem to the other?

Is there an application, where clearly we need to use one versus the other, and cannot do the other way around? I know lots of people seem to use bipartite graph partitioning to co-cluster documents and topics. What would be the interpretation of using hypergraph clustering on documents, using documents as nods and topics as edges as topics, or the other way around?

Also, does any one know of easy-to-use software, and corresponding algorithms, that try to solve both problems?

  • $\begingroup$ PS: I am also interested in the question of comparing both problems when the hypergraph and bipartite graph are weighted. $\endgroup$ – Carlos Botas Jan 9 at 0:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.