[MUSIC]. 
So what are some more sophisticated 
structural analytics tasks we can do with 
a graph? 
Well, one is to the find diameter of the 
graph. 
So this is the longest of all the 
shortest paths in the graph. 
So what's the shortest path? 
Well, given an x, well, given a vertex x 
and a vertex y, find all the different 
ways of reaching y from x and take the 
shortest one of those. 
That's the shortest path. 
Now, do that again, for all possible 
pairs of vertices in the graphs. 
The longest of all those shortest paths 
is the diameter, and so intuitively, what 
this is measuring is, you know, the width 
of the graph. 
What's the longest sort of, path you have 
to take to get from one place to another? 
Okay, and this gives us a measure of how 
much work we have to do, when we're 
transversing the graph. 
Okay, so if everything is very tightly 
connected, then the diameter will be very 
short, right? 
It only takes a few hops to get from 
anywhere to anywhere. 
and if the diameter is much longer, then 
it could potentially take longer then. 
So this gives you kind of the six degrees 
of separation, you know, six degrees of 
Kevin Bacon sort of, sort of measure, 
fine. 
So what is the diameter of this graph 
here. 
Well, we're looking for shortest paths, 
so, so let's look at some possible 
candidates. 
Well, things like a to f and a to b and d 
to c are all going to be shortest path 
one. 
So let's look a little closer at ones 
that appear to be far apart on the, you 
know, page here. 
So a to c, what's the shortest path 
there? 
Well, one path is a to b, b to e, e to g, 
and g to c. 
And that's a path, that's a path of 
length four, but there's a shorter one. 
There's a to b, b to d, and d to, and d 
to c, and so, a to c, the shortest path 
is three. 
So let's look at other ones. 
Well, f to anywhere, well you can't reach 
anywhere from f, because all the edges 
point inward and we're assuming a 
directed graph for this particular 
exercise. 
and g, similarly, you can't get anywhere. 
You can get to c, but c you can't get 
anywhere except back to g. 
So it looks like starting back from a, a 
to g, how many hops does it take to get 
there? 
1, 2, 3, so a to g is 3 And that should 
be the longest ones. 
So the diameter of this graph is 3. 
So we can also measure the connectivity 
coefficient of a graph as a structural 
analysis task. 
So this is the minimum number of vertices 
you need to remove that will disconnect 
the graph. 
And so this, you can think of this 
intuitively as a sense of the measure of 
the fragility of the graph, right? 
How, how much redundancy is built into 
it? 
So if you're designing a network and it 
turns out the connectivity coefficient of 
the graph is 1. 
That means that if one machine, 
potentially, if one machine goes down. 
You could partition the network where 
nobody could communicate. 
Okay, so, if you're an advertiser, you 
might be interested in the connectivity 
coefficient of a graph. 
If you're trying to reach as many people 
as possible, it could be that if a few 
people don't pay attention to the ads, 
then a whole bunch of people won't send 
the message, if you're sort of in viral 
advertising or social media advertising, 
okay? 
And so, remember in the cap theorem that 
we discussed in the no sequel lectures, p 
was partitioning, right, so this was the, 
if your, if your system becomes 
partitioned. 
If your network becomes partitioned, can 
the system still function? 
And so connectivity coefficient could be 
a measure to help you estimate how likely 
it is that your network is going to be 
partitioned. 
Okay, so what is the connectivity 
coefficient of this graph? 
Well, depends on exactly what we mean by 
connectivity first. 
So we can say that a, that two vertices x 
and y are strongly connected if x is 
reachable from y and y is reachable from 
x, okay. 
Okay, and we might say that they are just 
connected if x is reachable from y or y 
is reachable from x. 
And so, this is sort of equivalent to 
ignoring the directionality of the edges. 
So if we just assume that everything is 
undirected, then we'll be using the 
second definition. 
So, let's assume that for a second. 
Let's assume we just mean connected here. 
Well, look, if, if we don't care about 
direction of traversing. 
Then if we remove e, is the graph 
disconnected? 
No because you can still reach everything 
through this other edge up there. 
And so, the only node here that appears 
to not be redundant here is b, and so, if 
you remove b though, you'll have two 
partitions in the network, a and f, and 
all the other ones here. 
So, the connectivity coefficient of this 
graph is one, because we can a vertex 
that if we remove it It'll partitioned at 
work. 
Okay, and we already discussed why you 
might want to compute this. 
So the connectivity coefficient is a 
measure of the graph itself and doesn't 
really give us a way to understand the 
relative importance of a single vertex. 
And so for this purpose has been various 
notion of centrality to find. 
So one is the closeness of centrality of 
a vertex, which is the average length of 
all the shortest paths that pass through 
it. 
Right? 
So this, intuitively this is, you can 
maybe compare this with a diameter of the 
graph, right? 
If the diameter is long, and the average 
length of all the shortest paths that go 
through a particular vertex is short, 
then it's not part of the diameter of the 
paths that define the diameter of the 
graph. 
And so, in some sense, it's maybe less 
central or less important. 
Okay, so another that may be more common 
is the between the centrality of a 
vertex, and this is the fraction of all 
the shortest paths in the whole graph 
that pass through this vertex. 
All right, so if you need to, if you need 
to go, you know, all roads lead through 
Rome. 
Right? 
If you need to go from Seattle to Atlanta 
in the US, then perhaps all paths go 
through one of two different major 
highways, or one or two, maybe one or two 
major cities, the northern route and the 
southern route or something. 
And so, the betweenness centrality of 
these two intermediate hubs is high. 
And so, if you think about a s-, a, a 
public transportation system where all 
trains lead into some central hub and 
then go out again, that central hub will 
have a high betweeness centrality, 
because the shortest path to get from 
point A to point B always goes through 
this one central vertex, okay? 
So what is the betweenness centrality of 
vertex e in this case? 
Well, there's a shortest path a to b to d 
to c that we found. 
The shortest path from a to c goes 
through there and the shortest path from 
a to g, ab, eg is, is 3. 
So, if you sort of add all these up, 
you'll see that the e is only involved in 
a, b, e, g and then a bunch of ones that 
are rooted in e itself, e to c and e to 
g, so between the centrality of e is 3. 
Oh, I'm sorry, 3 divided by the total 
number of shortest paths in the graph. 
Okay? 
It's the fraction.