4
$\begingroup$

Is there a name for the problem of turning a bipartite graph into two graphs in the following way? We form one graph from the vertices on the left, such that two vertices are made adjacent if they share a common neighbour on the right; we form the other graph similarly from the vertices on the right.

This pops up, for example, when finding collaboration relationships in a bipartite graph from scientists to papers or actors to movies.

This being a common problem, I wonder if it has a common name, and maybe specific literature on it.

Improve this question
$\endgroup$
3
  • $\begingroup$ OK, thanks for the clarification of what you're trying to achieve. Now I don't understand what the problem is. It seems entirely straightforward to construct those two graphs. It's a straightforward programming exercise (just loop over vertices, etc.). What are you unsure about? What's wrong with the obvious way of constructing those two graphs? Why do you want a name/literature? What are you going to do with a name/literature? $\endgroup$ – D.W.♦ Aug 18 '16 at 20:30
  • $\begingroup$ @D.W. Seems to be a straight-forward reference request to me? $\endgroup$ – Raphael♦ Aug 18 '16 at 21:57
  • $\begingroup$ Which @saltthehash did provide $\endgroup$ – Rodrigo Stv Aug 18 '16 at 21:59
5
$\begingroup$

You're (basically) computing the square of the graph, in which two vertices are adjacent if there is a path of length 2 (or at most 2, depending on the definition) connecting them. The square will contain at least two connected components, corresponding to the two bipartitions.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Extremely useful. $\endgroup$ – Rodrigo Stv Aug 19 '16 at 0:40
0
$\begingroup$

It would just be an example of a graph partitioning problem. Here is a link to a paper on partitioning bipartite graphs: https://arxiv.org/pdf/cs/0108018.pdf

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks for the answer. However, given the clarifications to the question, it appears this answer is no longer correct/relevant. Does that sound right to you? If it does, I'd suggest deleting it, to avoid clutter. I realize it's a bit annoying to answer an unclear question and have your time turn out to have been wasted -- my sympathies on that. $\endgroup$ – D.W.♦ Aug 18 '16 at 20:31
  • $\begingroup$ The link saltthehash posted is relevant. I don't think this should be deleted. $\endgroup$ – Rodrigo Stv Aug 18 '16 at 21:35
  • $\begingroup$ @RodrigoStv, I don't understand. That paper does not construct a graph following the way that you requested in your updated question. Your question specifies a particular way of constructing the two graphs, which isn't the same as the way the paper describes. Perhaps the question needs to be revised to clarify what you are looking for? I'm terribly confused about what's going on here. $\endgroup$ – D.W.♦ Aug 18 '16 at 22:51
  • $\begingroup$ I was Just looking for an initial reference on anything related to the problem i described. Maybe i should review the question. But id say that terribly confused is a stretch. $\endgroup$ – Rodrigo Stv Aug 18 '16 at 22:53

Your Answer

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

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