COMP 3121 Homework 2
Question 1
Affiliation network is an example of bipartite graphs. An affiliation network has two categories,
people and foci, where each edge connects a person to a focus that he or she participates in.
Consider the following graph. On the left hand side, there are 7 nodes representing people
whereas on the right hand side, there are 5 nodes representing companies (foci). If a person is on
the director board of a company, there will have an edge connecting the person node and the
company node.
Given a bipartite affiliation graph, showing the membership of people in different social foci,
researchers sometimes create a projected graph on just the people, in which we join two people
when they have a focus in common. An edge will be formed between two persons to represent
they participated in the same social activity. Please select which of the following graph represents
such “projection” of the graph above.
1.
2.
3.
4.
Question 2
Projected graph satisfies: an edge will be formed if and only if two individuals participate the
same social activities (foci).
If the following graph is a projection of an affiliation network, what is the minimum number of
social activities (foci) in that affiliation network?
