Counting Random Graphs
In this example we are going to explore the density of randomly generated graphs (aka networks). This was a problem on the Stanford Midterm Fall 2022. As an example to get us started, here are three different networks each with 10 nodes and 12 random edges:
Count locations for edges: First, lets establish how many locations there are for edges in a random network. Consider a network with 10 nodes. Count the number of possible locations for undirected edges. Recall that an undirected edge from node A to node B is not distinct from an edge from node B to node A. You can assume that an edge does not connect a node to itself.
Count ways to place edges: Now lets add random edges to the network! Assume the same network (with 10 nodes) has 12 random edges. If each pair of nodes is equally likely to have an edge, how many unique ways could we chose the location of the 12 edges?
Probability of node degree: Now that we have a randomly generated graph, lets explore the degree of our nodes! In the same network with 10 nodes and 12 edges, select a node uniformly at random. What is the probability that our node has exactly degree $i$? Note that $0 \leq i \leq 9$. Recall that there are only 9 nodes to connect to from our chosen node, since there are 10 nodes in the graph.
- Select $i$ edges from the 9 possible edge locations connected to our node.
- Select the location for the $12 - i$ remaining edges. The edges can go to any of the $k$ locations for edges except for the $9$ incident to our node.