In analysis of graphs representing social media, it is popular to get informatio

Question

In analysis of graphs representing social media, it is popular to get information on the triangles in the graph. In this problem, we explore some of those issues. Let G be an undirected graph with n nodes. A triangle in G is a set of three nodes {u, v, w} such that all three edges (u, v),(v, w) and (u, w) are in G. Let N(x) be the number of triangles in G that contain node x. We want to compute N(x) for every node x. Trivially, this can be done in (n 3 ) time by simply enumerating every set of three nodes, and for each such triple, seeing if all the three edges are in G. Then when a triangle (u, v, w) if found, we increment each of the variables N(u), N(v), N(w) by one. But we want to compute all of the values N(x) in time faster than (n 3 ) time. 1 Let A be a full, symmetric n by n adjacency matrix representing graph G. That is, A will have a row for each node in G and a column for each node in G; and for each edge (u, v) in G, A(u, v) = A(v, u) = 1. The diagonal will have all zeros. Let Z be the matrix obtained by multiplying A by A, i.e. Z = A × A. a) Explain why Z(u, v) is the number of paths of exactly length two (i.e., containing two edges) between node u and node v in G. Be sure to explain why Z(u, v) does not count any path of length one (i.e. a single edge) between u and v. After computing Z we set a variable M(v) = 0 for each node v, and then do the following: For each entry (u, v) in Z, where Z(u, v) > 0, we check if (u, v) is an edge in G. If it is, then we add Z(u, v) to M(u) and to M(v). b) For each node v, will the resulting value of M(v) computed by the algorithm be equal to N(v), i.e., the number of triangles that contain node v? If not, how can this be corrected, so that we learn N(v) for each node v? c) How much time is needed for this algorithm?

Explanation / Answer

a) Z(u,v) = sum(A(u,a)*A(a,v)) for all possible values of a.

case 1: u!=v

The values of A(u,a)=1or0, A(a,v)=1or0, so A(u,a)*A(a,v)=1 only if A(u,a)=1 and A(a,v)=1. That means there is an edge from (u to a) and also from (a,v). So there exists a path from (u to v) via a. The value Z(u,v) gives the count of all such a's in the graph. So the path from u to v now has one point in between i.e, two edges.

case 2:u=v

so Z(u,v) = sum(A(u,a)*A(a,v)) = A(u,a)^2 as A(u,a)=A(a,u). So this counts the number of points which can be reached from point u.

b) No. Two reasons: It is true that if A(u,a)*A(a,v)=1 (u!=v) means that a,u,v form a triangle. That means Z(u,v) gives the number of triangles with u,v as one of the edges.

1) M(V) = Z(u,v) + Z(v,u) both values will be same and count redundant triangles. So we should only add one of them.

2) lets say there is a triangle formed by u,v,w. This is also counted in Z(u,v),Z(v,w),Z(u,w). In M(v) it counted twice once in Z(u,v) and Z(v,w).

So the way to correct it is the number of triangle = M(v)/4;

c) The time taken is matrix multiplicaiton time + O(n^2) (for calculating M values). Normal method for matrix multiplication takes O(n^3) time. Multiplying matrices with coppersmith-winograd takes O(n^2.375) time.So the fastest way to do this is O(n^2.375).

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.