Posted: January 30th, 2019

Compute degree centrality of an undirected graph – Software Engineering

Compute degree centrality of an undirected graph – Software Engineering

1. Compute the degree centrality, betweeness centrality, closeness centrality of nodes in the following graph.

2. A k-regular undirected network is a network in which every vertex has degree ??. Show that the vector ?? = (1, 1, 1, . . . , 1) is an eigenvector of the adjacency matrix with eigenvalue ??.

3. Consider an undirected tree of n vertices. A particular edge in the tree joins vertices 1 and 2 and divides the tree into two disjoint regions of n1 and n2 vertices as sketched here:

Show that the closeness centralities ??1 and ??2 of the two vertices are related by

4. Calculate the betweenness centrality of the ??^th vertex from the end of a “line graph” of n vertices. Here a line graph on n vertices 1, 2, 3,…, n has exactly n – 1 edges that connect vertices ?? and ?? + 1, for ?? = 1,…, n – 1.

5. Write a program in your preferred programming language to compute degree centrality of an undirected graph. The program will read the graph from a file called “graph.txt” and output the degree centrality of nodes to a file called “degree.txt”.

The file “graph.txt” includes multiples lines in which the first line contains two integers n and m that correspond to the number of nodes and edges in the graph. Each of the following m lines contain two integers u and v, separated by one space, to denote an edge from u to v. Nodes are numbered from 1 to n.

The output file “degree.txt” contains exactly n lines in which the ????h line is the (unnormalized) degree centrality of node ??.

Your submission must include
– The source file(s)
– The sample input/output
– A README file that describes the compile and running instruction

6. Write a program in your preferred programming language to compute (normalized) closeness centrality of an undirected graph. The program will read the graph from a file called “graph.txt” and output the degree centrality of nodes to a file called “closeness.txt”.

The file “graph.txt” includes multiples lines in which the first line contains two integers n and m that correspond to the number of nodes and edges in the graph. Each of the following m lines contain two integers u and v, separated by one space, to denote an edge from u to v. Nodes are numbered from 1 to n.

The output file “closeness.txt” contains exactly n lines in which the ????h line is the (normalized) closeness centrality of node ??.

Your submission must include

– The source file(s)
– The sample input/output
– A README file that describes the compile and running instruction