Network Science (Computer Science)

Network Science

NAME:

1. Briefly describe, in your own words, what Network Science is and list at least 3 applications.– 4 points

2. What is the “small world” property? Briefly describe. – 6 points

3. How did Euler solve the Bridges of Konigsberg problem? What was the outcome and how did he come to this conclusion? – 6 points

4. Give the definition of a graph. How are edges represented? – 6 points

5. Suppose a graph has 1000 vertices, and 100,000 edges. What is the sum of the vertex degrees? What is the average degree? – 6 points

6. What is a complete (clique) graph? How many edges are there in a complete graph with 40 vertices? – 6 points

7. Consider the following network. Specify the degree distribution for this network. Either draw a chart (make sure to label and specify the values) or just specify the p_i values. – 6 points

8. What is the diameter of the graph in problem 7? – 4 points

9. Draw the following undirected graph. V={0,1,2,3,4,5}, E={(0,1), (0,4), (1,2), (2,3), (2,5), (3,4), (3,5), (4,5)}. – 6 points

10. Draw the adjacency matrix for the undirected graph in problem 9. – 6 points

11. What is the density of the graph in problem 9? – 4 points

12. What is the average path length i.e. the average shortest path length for all pairs of vertices for the graph in problem 9? – 6 points

13. What is the local clustering coefficient of vertex 1 in problem 7? – 4 points

14. What is the global clustering coefficient of the graph in problem 9? – 6 points

15. In the Erdös-Rényi random network model, suppose N=101 and p=1/20, that is, there are 101 vertices, and every pair of vertices has a probability of 1/20 of being connected by an edge. What is the average degree <k> of a vertex in this network model? – 6 points

16. For the network model given in problem 15, what is the probability that a vertex in the network has degree equal to 2? No need to give the decimal value, the mathematical expression will suffice. – 6 points

17. For the network model given in problem 15, what is the probability that a network generated with those parameters has exactly 400 edges? No need to give the decimal value, the mathematical expression will suffice. – 6 points

18. What is a power law degree distribution (scale free) network? Briefly explain and give the mathematical expression for the degree distribution. – 6 points

19. Bonus – 5 points. Draw the adjacency matrix for a complete graph consisting of 5 vertices ().

8