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

CPSMA 4373 Network Science

Fall 2021 Post-Midterm Exam – 100 points + 5 bonus

All answers MUST be written in YOUR OWN words, do not just copy-paste from the slides or other sources. Write your answers immediately after the question and before the next question. You can attach photos/scans of handwritten work also. You may use your notes but no other resources.

Plagiarism will result in a score of 0 and a possible F in the class.

NAME: Sangam Shrestha

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

Network science is field that investigate the topology of complex networks, to understand more about the function, properties and behavior of the underlying systems.

The applications are listed below:

-Neuroscience: Human is one of the advanced creatures of this world. They contain billions and billions of neurons connected. This is the least understood network because we are lacking the map telling which neuron is connected and linked. If we understood this, we can treat many diseases.

-Epidemics: There are always some shot of advanced virus which create problems in the world. Their course of time and evolution can be predicted. Example: H1N1 time of evolution was predicted months before it reaches its peak.

-Security: Criminal activities where the large amount of financial activities are done can be disrupted.

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

Small world refers to the group of networks in which the shortest path or distance between nodes increases sufficiently slow as a function of the number of nodes in the network. Small world will have sub-networks that are characterized by the presence of connection between almost any two nodes within them. Most pair of nodes will be connected by at least one short path.

For example, websites with menus, electric power grids, networks of brain neurons, culture networks and many more shows the small world property.

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

A graph is a diagram (such as line, line segments, curve, areas) that represents the variation of a variable in comparison with that of one or more other variables or it is a collection of vertices and edges that join pairs of vertices.

Every graph is a set of point which are referred as vertices or nodes, and these are connected using a line called edges. It expresses the relationship between entities. Edges are represented as unordered or ordered pairs depending on the graph (graph might be directed or undirected).

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

Number of vertices = 1000

Sum of the all-vertex degrees = 2*100000 (each edge has a degree of 2)

=200000

Average degree= Total vertex degree/ number of vertices

=200000/1000

=200

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

A complete (clique) graph is a graph in which each pair of vertices (of graph) is connected by an edge.

-n vertices the degree of each vertex = n-1

Sun of degree of all vertices = n(n-1)

According to Handshaking Theorem,

2 * (number of edges) = Sum of degree of all vertices

=n(n-1)

Total number of edges = n(n-1)/2

Given, Vertices= 40

Total number of vertices = (40*(40-1))/2

=780

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

For this undirected network, the degrees are,

K (0) 2, K (5)3

K (1)2, K (6)2

K (2)3, K (7)1

K (3)3, K (8)2

K (4)3, K (9)1

Its degree distribution is

Pdeg (1) = 2/10 = 1/5 = 0.2

Pdeg (2) = 4/10 = 2/5 = 0.4

Pdeg (3) = 4/10 = 2/5 = 0.4

Fraction of nodes

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

The diameter of the graph is the maximum distances between the pair of vertices.

-Diameter of the graph in problem 7 will be 8.

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

The density of the graph(undirected) is

D = 2*|E|*|V|*(|V|-1) -> (|V| number of nodes, |E|number of edges)

Given,

|E|=8

|V|=6

D=2*8*6*5

=480

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

we can calculate the average path length by the formula:

-d (vi, vj) represents the length of shortest path exists between two vertices.

From graph,

From the graph, d (0,1) =1, d (0,2) =2, d (0,3) =2 d (0,4) = 1, d (0,5) =2

d (1,0) =1, d (1,2) =1, d (1,3) =2 d (1,4) = 2, d (1,5) =2

d (2,0) =2, d (2,1) =1, d (2,3) =1 d (2,4) = 2, d (2,5) =1

d (3,0) =2 , d (3,1) =2, d (3,2) =1 d (3,4) = 1, d (3,5) =1

d (4,0) =1, d (4,1) =2, d (4,2) =2 d (4,3) = 1, d (4,5) =1

d (5,0) =2, d (5,1) =2, d (5,2) =1 d (5,3) = 1, d (5,4) =1

n = 6

now according to formula,

= ((1 *((1+2+2+1+2)+(1+1+2+2+2)+(2+1+1+2+1)+(2+2+1+1+1)+(1+2+2+1+1)+(2+2+1+1+1))/(6*5)

=44/30

=1.467

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

0->1->2->3->4->5->6->7->8->9

The local clustering coefficient of vertex 1 in problem 7= 0(because there is no edge between neighboring vertices of vertex 1).

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

The global clustering coefficient (C)= 3 * Number of triangle/ number of triplets

Triplet of 0: 401

Triplet of 1: 012

Triplet of 2: 123, 125

Triplet of 3: 234, 435, 532

Triplet of 4: 043, 045, 345

Triplet of 5: 452, 453, 352

Number of triangles = 2

C = (3*2) / (1+1+2+3+3+3)

= 6/13

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

Average degree = N * p

=101 *(1/20)

= 5.05

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

Average degree = N * p

=101 *(1/20)

= 5.05

=5 (removing decimal value)

Probability that the network generated with those parameters has 400 edges = 5 *(400/100)

= 20 (removed decimal)

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

It is network that is characterized by the presence of large hub. It follows the power law.In a non-targeted network, degree distribution is written as, I-Pdeg (k) ∝k − γ, where γ is a specific exponent. Pdeg(k) decays slightly when degree of k increases. Networks have a power distribution law called scale free because power law have the same functionality on all scales. Many real-world networks are thought to be scale free, but it is still inconclusive due to the ongoing awareness of robust data analysis technique. An example of non-scale networks are protein-protein interaction network, semantic networks, flight networks.

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

Degrees 1 2 3 0.2 0.4 0.4

8