1. Connectivity
Connectivity is a measure of how densely connected the vertices of a graph are. It's measured in two forms: vertex and edge connectivity. Each measure tells you how many vertices or edges need to be removed to disconnect the graph creating two distinct graphs.
2. Measuring connectivity
Here we have a small graph with 10 vertices. Let's measure the edge and vertex connectivity.
3. Measuring connectivity
Each measure is returning how many vertices or edges we need to remove. In this case, both are two. However this doesn't tell us what the split would be and what the specific cuts are being made.
4. Minimum number of cuts
Using the min_cuts() function we can learn a lot about the connectivity. First we get the value for edge connectivity, and then we can see the two cuts that are made. In this case between vertices 10 and 7 and 10 and 1. Lastly we see the two partitions. In this case it's a single vertex partitioned from the rest of the graph.
5. Connectivity randomizations
Now that we have a better understanding of connectivity, let's see how the graph connectivity of of a random graph compares to our bike sharing graph. To do this we'll use a similar process to what we've used in the intro lesson where we build a random graph with the same properties as the graph of interest and compare a metric to the distribution of metrics from a random graph.
6. Connectivity randomizations
The connectivity of our bike sharing graph is much less than we'd expect by chance. We can hypothesize this is likely because the connection between vertices is constrained by geography. It is unlikely that two stations that are 15 kilometers apart will be connected, but in a random graph, there is no geographic constraint - so those far apart vertices can be connected. This leads to much greater connectivity than a random graph.
7. Let's practice!
Now let's use some of the insights that connectivity can provide to a graph on the bike sharing data set.