Compute degree centrality of an undirected graph

Assignment Help Software Engineering
Reference no: EM13318245

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

1116_centrality of nodes in the graph.png

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:

771_centrality of nodes in the graph1.png

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

615_centrality of nodes in the graph2.png

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.

1294_centrality of nodes in the graph3.png

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

Reference no: EM13318245

Questions Cloud

Out of the motivational theories : Out of the motivational theories, which theory appeals to you the most and why? Also, share one motivational incident at your and try to relate that incident to the theory of your choice
Account a is facing tough competition in the marketplace : Account A is facing tough competition in the marketplace.
Draw ray inside the core by using matlab : Draw ray inside the core by using matlab, draw three circles or four circles with different angles, so every circle has different angle.
Compare with the allowable stresses on a simple span : A 4 X 12 (S4S) hem-fir timber beam carries a superimposed uniformly distributed load of 325 lb/ft on a simple span of 12ft. Determine the maximum bending stress and the maximum shear stress
Compute degree centrality of an undirected graph : Compute the degree centrality- closeness centrality of nodes in the graph - write a program in your preferred programming language to compute degree centrality of an undirected graph.
Calculate max bending stress and shear stress in the pole : A Timber power-line pole is 10 in. in diameter at its base where it is solidly embedded in concrete. The pole extends 20 ft vertically upward from its base and is subjected to a horizontal pull of 300 lb at its top.
What is the angular velocity in the time interval : A machinist turns the power on to a grinding wheel, at rest, at time t=0 s. What is the angular velocity in the time interval from t=0 to t=25s
Calculate the maximum shear force v of resisting : If the allowable shear stress is 100 MPa, calculate the maximum shear force V that a W460 X 60 structural steel wide flange is capable of resisting. Use the average web shear approach.
Explain what radioactive isotope emits a beta particle : What radioactive isotope emits a beta particle to give magnesium-24? a. sodium-24 b. silicon-28 c. aluminium-24 d. magnesium-25

Reviews

Write a Review

 

Software Engineering Questions & Answers

  Pushdown automaton

A useless state in a pushdown automaton is never entered on any input string. Think about the problem of testing whether a pushdown automaton has any useless states.

  Three possible social effects of feasibility study

In context of a feasibility study explain one cost, one benefit and three possible social effects which would be considered.

  Designing e-r diagram for each product at pvf

Suppose that at PVF, each product. Design E-R diagram for this situation and state minimum and maximum cardinalities on the diagram.

  Implementing reusable code

Many programming languages exist in various libraries and on the Internet and using some of these functions and process, this can permit you to use these technique rather than having to write out the code from scratch on your own.

  Draw entity-relationship diagram for heg

Instructors are capable of teaching many different courses. Draw an entity-relationship diagram for HEG (in 3NF).

  Find multicanonical monte carlo methods and rare growth

MATH7601: Project Descriptions. Multicanonical Monte Carlo Methods and Rare Growth Factors. One of the big unsolved research problem in Gaussian elimination is the question of backward stability. Even with partial pivoting examples are known.

  Analyze advantages and disadvantages of erp implementations

Analyze the advantages and disadvantages of ERP implementations as a method of reuse?

  Design and implementation of e-commerce website

Design and Implementation of E-commerce Website - the E-commerce management system needs to provide the following facilities to different classes of users

  Example of a business related report

Recognize an example of a business related report created with MS Excel. Attach a sample of the report in an Microsoft Excel file.

  Contribute to producing program code

Under what circumstances is this view sensible, and under what circumstances is it foolish and in the latter case, how would you persuade such a manager that the specification does need to be high quality

  Finding output of the code sequence

Construct the pseudocode for a program that finds the sums of the numbers input that are greater than or equal to 10 and the numbers input that are less than ten.

  Indirect port addressing capability

Determine how many ports can the Z8000 address in each I/O addressing mode?

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd