Write map-reduce functions for computing the degree distribution of a massive social network such as Facebook.
No actual code is needed; pseudocode is sufficient. To see an example of what pseudocode looks like, see slide 12 of the map-reduce lecture slides on Canvas.
The input given to you describes a dataset of nodes connected to each other via edges. An example of such a network could be the Facebook network, in which the users denote nodes and two nodes are connected by an edge if the corresponding users are friends with each other.
The degree of a node in a network is the number of connections it has to other nodes.
The degree distribution is the distribution of these degrees over the whole network.
As an example, you can assume that the input you are given is an edgelist in the form of a table as shown below. This table shows pairs of edges connected to each other and thus capture the graph shown on the right:
NODE 1 NODE 2
A B
A C
A D
B C
C A
C B
D A
The degree distribution for the above graph is given as:
Degree Count
1 2
2 1
3 1
As you can see, we have two nodes with degree 1 (which are B and D), one node with degree 2 (which is), and one node with degree 3 (which is A). Thus, the degree distribution captures, for each value of degree, the number of nodes that have that degree. Note that the sum of the counts (i.e., 4) equals the number of nodes in the network/graph.