Take a node in a graph and consider it as a user in twitter. A link between two users is the minimum retweet time. The link represents the close connection between users. You may be interested to compute the distance among all users. Why ? To determine clusters, to find the closest nit of friends, to find relations between celebrity, or because WTF we can.
In the era of large graphs it may be interesting to compute distances among nodes. If a weighed edge represents the distance between two nodes, we could compute the all-pairs shortest path (APSP) so that to know, given any node, what is its distance from any other node in the graph. APSP and MM are computationally equivalent (“the design and analysis of computer algorithms” Aho, Hopcroft, and Ullman 1974. This is a great book to have anyway, I stole my advisor’s copy) and we have shown that incidentally they are the same. I will clarify in the post.
Read full article from » Matrix Multiply, All-Pairs Shortest Path, and Large Dense Graphs FastMMW: fast matrix multiply or fast matrix multiplication
No comments:
Post a Comment