Social Media Mining: An Introduction

(Axel Boer) #1

P1: WQS Trim: 6.125in×9.25in Top: 0.5in Gutter: 0.75in
CUUS2079-02 CUUS2079-Zafarani 978 1 107 01885 3 January 13, 2014 16:38


2.9 Exercises 49


  1. Given the following adjacency matrix, compute the adjacency list and
    the edge list.


A=



⎢⎢


⎢⎢


⎢⎢


⎢⎢


⎢⎢


⎢⎢




011000000


101000000


110110000


001011100


001101100


000110110


000111010


000001101


000000010



⎥⎥


⎥⎥


⎥⎥


⎥⎥


⎥⎥


⎥⎥




(2.29)


Special Graphs


  1. Prove that|E|=|V|−1 in trees.


Graph/Network Algorithms


  1. Consider the tree shown in Figure2.28. Traverse the graph using both
    BFS and DFS and list the order in which nodes are visited in each
    algorithm.


v 1

v 2 v^3

v 4 v 5 v 6 v 7

v 8 v 9 v 10 v 11 v 12
Figure 2.28. A Sample (Binary) Tree.


  1. For a tree and a nodev, under what condition isvvisited sooner by
    BFS than DFS? Provide details.

  2. For a real-world social network, is BFS or DFS more desirable? Provide
    details.

  3. Compute the shortest path between any pair of nodes using Dijkstra’s
    algorithm for the graph in Figure2.29.

  4. Detail why edges with negative weights are not desirable for computing
    shortest paths using Dijkstra’s algorithm.

Free download pdf