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:
+ 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
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.