1. Describe (in fair detail) real-world networks.
2. Briefly describe at least 2 characteristics of network science.
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. Suppose a graph has 500,000 edges, and the average degree is 100. How many vertices does it have?
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. Consider the following network. What is the diameter of this network?
7. What is the local clustering coefficient of vertex 4 in problem 6?
8. What is the closeness centrality of vertex 4 in problem 6?
9. What is the betweenness centrality of vertex 5 in problem 6?
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)}.
11. What is the density of the graph in problem 10?
12. What is the global clustering coefficient of the graph in problem 10?
13. In the Erdös-Rényi random network model, suppose N=51 and p=1/10. What is the average degree
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.
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.
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?
Recent Comments