Real-world networks
1. Describe (in fair detail) at least 3 real-world networks. Make sure to specify what the nodes and edges correspond to in each network. – 9 points
2. Briefly describe at least 2 characteristics of network science. – 6 points
3. True/False: if a graph has at least 2 nodes of odd degree, then no Eulerian path exists. Note: an Eulerian path is one that visits every edge in the graph exactly once. – 4 points
4. Suppose a graph has 500,000 edges, and the average degree is 100. How many vertices does it have? – 6 points
5. What is a bipartite graph? Draw an example. How many edges are there in a complete bipartite graph between a set of 100 vertices and a set of 25 vertices? – 6 points
6. Consider the following network. What is the diameter of this network? – 6 points
9. What is the betweenness centrality of vertex 5 in problem 6? – 8 points
10. Draw the following undirected graph. V={0,1,2,3,4,5,6}, E={(0,1), (0,2), (0,3), (1,4), (2,4), (2,5), (2,6), (3,6), (4,5), (5,6)}. – 8 points
11. What is the density of the graph in problem 10? – 7 points
12. What is the global clustering coefficient of the graph in problem 10? – 8 points
13. In the Erdös-Rényi random network model, suppose N=51 and p=1/10. What is the average degree <k> of a vertex in this network model? – 6 points
14. For the network model given in problem 13, what is the probability that a vertex in the network has degree equal to 50? No need to give the decimal value, the mathematical expression will suffice. – 6 points
15. Draw the optimal group testing matrix (experiment design) for the case where there are 7 units, and it is known at most 1 unit is infected/defective/sensitive. Hint: It could be the case that no units are infected, your design must be able to determine this. – 6 points
16. Bonus 5 points If the Latin Square Group Testing Design is applied to a network containing N vertices, how many vertices does each group test network have? That is, for each group test, vertices are grouped into a single supervertex which results in a smaller compressed network on which the test is done. How many vertices do each of these smaller networks have?