CS423: Networks Assignment 1 Answer all 5 questions, each is worth 1 point. Deadline for submission: Wednesday, February 22 at 5pm. 1. Recall that a shortest path between two nodes is a path of minimal possible length. A node X is called pivotal for a pair of nodes Y and Z, if X lies on every shortest path between Y and Z (and X is different from Y and Z). For example, in the graph on the right, node B is pivotal for the pair A, C and for the pair A, D. But B is not pivotal for the pair D, E, as one shortest path from D to E does not pass through B. The node D is not pivotal for any pair of nodes. A B C D E F (a) Give an example of a graph in which every node is pivotal for at least one pair of nodes. Explain your answer. (b) Give an example of a graph in which every node is pivotal for at least two different pairs of nodes. Explain your answer. 2. The social graph of a node A in a (social) network is the induced subgraph on the set of friends of A. On MathSciNet (http://www.ams.org/ mathscinet), pick a (local) mathematician with at least 10 friends (i.e., co-authors). Then sketch their social graph and determine the clustering coefficient. 3. Consider the following two networks. 1 2 3 4 5 1 2 3 4 1 2 3 4 5 One is a directed network. The other is undirected but bipartite. Write down: 12 (a) the adjacency matrix of the directed network; (b) the cocitation matrix of the directed network; (c) the incidence matrix of the bipartite network; (d) the projection matrix for the projection of the bipartite network onto its square vertices. 4. Let A be the adjacency matrix of an undirected network and 1 be the column vector whose elements are all 1. In terms of these quantities write expressions for: (a) the vector k whose elements are the degrees ki of the vertices; (b) the number m of edges in the network; (c) the matrix N whose element Nij is equal to the number of common neighbors of vertices i and j; (d) the total number of triangles in the network, where a triangle means three vertices, each connected by edges to both of the others. 5. In the graph on the right, use Breadth First Search as one of the tools to determine how the flow from node B spreads out over the edges of the graph. Do the same for another two or three nodes . . . . Can you compute the betweenness values of all of the edges from these data? Which edge of the graph would the GirvanNewman method for graph partitioning remove first? B A C D E F G H I J K (Challenge: Write a computer program that performs the Girvan-Newman method on any given graph.)