Question 1:
CSC303: Practice Questions
We’ll be covering solutions in-tutorial on February 10th
(a) Run the Sintos & Tsaparas algorithm on the following graph G to find the solution to the MINSTC problem. Recall, in MINSTC our goal is to producing a labeling of strong & weak edges such that STC is preserved and the number of weak edges in minimized.
Make sure to draw the complementary graph GT . Find the optimal vertex covering of GT manually.
(b) Compute the clustering coefficient of each node. Also compute the clustering coefficients of B and C
if we added the edge (B, C).
(c) Run the Rozenshtein algorithm on this graph, given the communities {A, B, E} and {F, C}. If there is a tie for which edge to consider next, then use the edge with the earliest endpoint in alphabetical order (if this leads to another tie, then tie-break by the other endpoint, again by earliest alphabetical order).
Question 2: Cluster the following graph using the Girvan-Newman algorithm
Question 3: A classmate of yours is studying homophily with respect to yodeling in a network. In this network, there exists data on 1-way friendships. In the network, the directed edge ⟨A,B⟩ signifies that A views B as a friend, but the feeling is not mutual. Your classmate finds that given that B is a yodeler, there is no change in the probability that A yodels based on direction of friendship (i.e. the probability that A yodels is the same when either ⟨A,B⟩ or ⟨B,A⟩ is in the network). Is this evidence for or against social influence causing homophily with respect to yodeling? Briefly justify.
Code Help, Add WeChat: cstutorcs
Question 4: Are all labellings of all undirected trees completable to a strongly balanced network? Either provide a proof or a counterexample.
CS Help, Email: tutorcs@163.com
Question 5: Describe a graph which is not a social network (i.e., the nodes cannot be people or similarly intelligent entities such as companies or an artificial general intelligence), but where Triadic closure could be argued to be applicable.
Question 6: [This is a much longer question!] Let G = (V, E) be a simple, undirected, unweighted, graph with n nodes, v1,…vn.
For an unordered pair of nodes, (vk, vl) ∈ E, let us define the n × n matrix L ̃(G, (vk, vl)) as:
1 i = j = k
L ̃(G,(vk,vl))ij = From these smaller matrices, let us define L(G) as:
L(G) = L ̃(G, e) e∈E
(a) [5 points] What is the meaning of values on the diagonal of L(G)? Explain your answer.
(b) [10 points] Show that if G is a connected graph, then the nullspace of L(G) is of dimension one. Provide a corresponding eigenvector with zero eigenvalue. (HINT: there are many ways to solve this problem, but it may be helpful to consider xT L(G)x).
(c) [10 points] Show that for an arbitrary G, then the nullspace of L(G) is of dimension equal to the number of connected components in G. You can assume the results from (b). (HINT: You can assume, without loss of generality, any particular ordering of the nodes of G. It may also be helpful to partition L(G)).
−1 i=k,j=l −1 i=l,j=k 0 else
Programming Help
Question 7: This is a brief review of probability.
(a) Briefly explain the difference the terms mutually exclusive, and independent. In general, are mutually
exclusive events independent?
(b) For an unbiased coin, what is the probability of getting 5 heads in a row?
(c) For an unbiased coin, what is the probability of getting at least 1 tail out of 5 coin tosses?