What is the number of triangles in a complete graph

Assignment Help Computer Networking
Reference no: EM13342956

1. A triangle in a graph is defined as a triple of vertices (u, v, w) in which (u, v), (v, w) and (u, w) are edges in the graph. Answer the following questions and provide your best justification.

a. What is the number of triangles in a complete graph with vertices?

b. What is the expected number of triangles in an Erdos-Rényi graph , a graph on vertices where each edge appears with a probability independently?

2. The friendship paradox is the phenomenon that most people have fewer friends than their friends have, on average. This question asks for a mathematical explanation of the phenomenon. Given an undirected graph , where the set of vertices corresponds to the people in the social network, and the set of edges corresponds to the friendship relation between pairs of people. Denote by the degree of vertex .

We can compute the following quantities.

+ The average number of friends of a (random) person in the graph:

2455_What is the number of triangles.png

+ The average number of friends that a typical friend has can be computed as follows.

Choose, uniformly at random, an edge of the graph and an edge of the graph and an end point of that edge, and calculate the degree of the selected end point. That is

445_What is the number of triangles1.png

a) Prove that and provide your best justification.

3. Write a program in your preferred programming language to compute edge betweeness centrality of edges in an undirected graph. The program will read the graph from a file called "graph.txt" and output the edge degree centrality of edges to a file called "edge_betweeness.txt".

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

The output file "edge_betweeness.txt" contains exactly m lines in which the line is the edge betweeness of the th edge in the input file.

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

4. Visualize your own Facebook network following the Gephi tutorial in the class.

a. Report top 3 people in your networks according to their degree, betweeness centrality, and eigenvector centrality.

b. Export the final network to a PDF file lastname_firstname.pdf and upload the file to Blackboard.

Attachment:- degree.rar

Reference no: EM13342956

How long it take to send the file from source to destination

Suppose the network is a packet-switched datagram network, and a connectionless service is used. Now suppose each packet has 2h bits of header. How long does it take to send

What are the ssids of the two access points

What are the SSIDs of the two access points that are issuing most of the beacon frames in this trace - What are the intervals of time between the transmissions of the beacon f

What is a telecommunications network protocol

What is telecommunications network architecture? Select a network protocol and provide details on the steps that preceded the formal adoption of the protocol by the industry

Create a project plan for moving the data center

Describe the knowledge and processes areas of project management in accordance to the Project Management Institute Project Management Body of Knowledge (PMBOK®) Guide.

Explain the basic components and media of network systems

Write an five to seven (5-7) page proposal in which you: Recommend one (1) suitable network design. Suggest one (1) network architecture. Suggest LAN and Wireless LAN (WLAN) w

Network consultation proposal

Recommend software options and costs.Outline the labor costs, equipment costs, and service costs for your suggested design in table format.Identify the single point of failu

Create a detailed diagram or set of diagrams

Create a detailed diagram or set of diagrams to show how the letter A is transmitted in an electrical, light, and radio wave. Show the similarities and differences between h

What information in packet does switch use to find link

When one of these packets arrives to packet switch, what information in packet does switch use to determine link onto which packet is forwarded?


Write a Review

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