Hypergraphs and bipartite graphs ?? Why must a link be defined as the connection between just two…
Hypergraphs and bipartite graphs ??
Why must a link be defined as the connection between just two nodes? Suppose eight papers are in the fields of physics or chemistry. Group membership, i.e., to which field a paper belongs, is presented as a hypergraph in Figure 8.22. Each dotted area is a group or a hyperedge, which is a generalization of an undirected edge to connect possibly more than two nodes. Papers 4 and 5 are “interdisciplinary” papers, so their nodes are contained in both hyperedges.
(a) We can transform the hypergraph in Figure 8.22 into an undirected bipartite graph by introducing two more nodes, each representing one of the hyperedges, and linking a “standard” node to a “hyperedge” node if the former is contained in the corresponding hyperedge. Draw this bipartite graph.
(b) Define an incidence matrix B of size 2 × 8 with
where group 1 is “Physics” and group 2 is “Chemistry.” Write down B for this
graph.
(c) Compute the matrix BT B. What is its interpretation?
(d) Compute the matrix BBT. What is its interpretation?
