0
$\begingroup$

As a follow-up to What are the Applications of Hypergraphs, the linked article:

Learning with Hypergraphs: Clustering, Classification, and Embedding

Mentions this:

Let us consider a problem of grouping a collection of articles into different topics. Given an article, assume the only information that we have is who wrote this article. One may construct an undirected graph in which two vertices are joined together by an edge if there is at least one common author of their corresponding articles...

A natural way of remedying the information loss issue occurring in the above methodology is to represent the data as a hypergraph instead. A hypergraph is a graph in which an edge can connect more than two vertices [2]. In other words, an edge is a subset of vertices. In what follows, we shall unifiedly refer to the usual undirected or directed graphs as simple graphs. Moreover, without special mentioning, the referred simple graphs are undirected. It is obvious that a simple graph is a special kind of hypergraph with each edge containing two vertices only. In the problem of clustering articles stated before, it is quite straightforward to construct a hypergraph with the vertices representing the articles, and the edges the authors (Figure 1). Each edge contains all articles by its corresponding author.

What I'm wondering is, instead of using 1 edge with many vertices, why not use many edges. That way it's just like a normal graph, not a hypergraph.

I don't yet understand the value in making 1 edge become essentially like a new type of node, if you could do the same thing by creating many edges. In hypergraphs they even call these new things "tentacles" or "attachments", connecting the edge to many things. Then it's like an edge is just another node. Hoping for some clarification on why this is necessary or what advantage this provides that multiple edges can't accomplish.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ FYI: 'tentacle' and 'attachment' are horrible and highly unusual terms; the usual technical term is 'hyperedge', or even shorter, 'edge'. $\endgroup$
    – Peter Heinig
    Feb 25, 2018 at 20:01

1 Answer 1

Reset to default
3
$\begingroup$

The hypergraph gives strictly more information than the graph: it can distinguish between the case where Larry, Curly, and Moe wrote a joint paper from the case where Larry and Curly wrote a paper and Curly and Moe wrote a different paper.

Improve this answer
$\endgroup$
9
  • $\begingroup$ You could still do that with a basic graph, please explain how you can't do that with a basic graph. Not sure what I'm missing (coming from a programming perspective). $\endgroup$
    – Lance
    Feb 25, 2018 at 19:31
  • $\begingroup$ @lancejpollard In the graph you’d have the same 3 edges either way: Larry—Curly, Curly—Moe, and Larry—Moe. With the hypergraph you could have these edges, a Larry-Curly-Moe edge/tentacle, or any combination thereof. $\endgroup$
    – Charles
    Feb 25, 2018 at 19:56
  • 1
    $\begingroup$ @lancejpollard: no, one cannot possiblly do this with an ordinary graph. To do what Charles explained to you, one would have to use edgecolored graphs. The essence is this: you propose to encode the information 'Persons X,Y,Z simultaneously collaborated (in doing something)' by putting the three edges XY, YZ, ZX into the graph. So far so good. But the rule you propose would create the exact same graph in the following genuinely distinct scenario: 'Persons X and Y collaborated at time t_0', 'Persons Y and Z collaborated at time t_1>t_0', 'Persons Z and X collaborated at time t_2>t_1>t_0'. $\endgroup$
    – Peter Heinig
    Feb 25, 2018 at 19:57
  • $\begingroup$ @Charles I'm thinking about this from a programming perspective. You could have Larry-Paper1, Curly-Paper1, Moe-Paper1 as well as Larry-Paper2, Curly-Paper2, Curly-Paper3, Moe-Paper3... Then you would just combine the information from all the edges and figure out what you're saying, it seems like the same information. Not sure what I'm missing. $\endgroup$
    – Lance
    Feb 25, 2018 at 20:12
  • 2
    $\begingroup$ @lancejpollard: sorry, I believed that writing this would automatically open up a link to a chat. Actually, I have never used the chat and don't know how to do this. So I try to clarify this briefly here: what you say is very relevant: you say "if you use the time information...you would be able"; indeed, but an ordinary graph, i.e. 'symmetric irreflexive relation on a set' does *not offer any possibility to 'store' the time-information'. All information contained in a graph is who is connected with whom. Does that help? $\endgroup$
    – Peter Heinig
    Feb 25, 2018 at 20:21

Not the answer you're looking for? Browse other questions tagged or ask your own question.