Introduction to Networks

This is a graph

Node B is a pivotal node.

It provides the shortest path to get from A to C and A to D.

Pivotal is Relative.

Node B is NOT pivotal for D and F because because there is another shortest path they can take.

Some Nodes are Never Pivotal.

Also note D is not pivatol for any pairs.

Here's Another Graph.

Gatekeeper

Node A is a gatekeeper because it lies on every path from E to B.

Gatekeeper is Relative to Scale.

Node B is a local gatekeeper because it connects nodes C and D

But B is not a global gatekeeper because C and D can also be connected through A.

One More Graph

Graph Length

The number of edges within the entire graph

Graph Distance

The distance between two vertices in a graph is the number of edges in their shortest path. The matrix shows the minimum distance between every node

A B C F G E D
A 0 1 1 1 2 1 2
B 1 0 1 2 3 2 3
C 1 1 0 1 3 2 3
F 1 2 1 0 2 1 2
G 2 3 3 2 0 1 2
E 1 2 2 1 1 0 1
D 2 3 3 2 2 1 0

Eccentricity

Let's look at Node A, the first row in our matrix.

The path from A to B, C, F, & E is 1, and to G or D is 2.

The highest shortest path length of A [its eccentricitiy] is 2.

Diameter

While eccentricity is a metric we can apply to every node, the graph's diameter is the maximum overall distance of every pair of nodes in the graph.

Radius: Periheral

The radius is the minimum eccentricity of the graph.

Any vertex whose eccentricity is equal to the graph's diameter is peripheral.

Radius: Central

If the eccentricity of a node is equal to the graphs radius then it is a central vertex

As we can see here, the radius of a graph is always less than the diameter which always less than 2 times the diameter of the graph.

$$\text{rad}(G) \leq \text{diam}(G) \leq 2 \text{ rad}(G) $$

The first inequality, that the minimum eccentricities (2) is smaller than the maximum eccentricities (3) is logical.

We can prove the second inequality by looking at 2 peripheral nodes, G and B, and one central node, A.

We know the diameter is the distance from G to B.

We also know that distance is bounded by the distance from G to A (at most A's accentricity = 2) and A to B (at most A's accentricity = 2).

We also know A's accentricity is the radius because it is a central node. Therefore:

$$d(u,v) \leq 2*rad(G)$$

Avatar
Maya Gans
Data Scientist

Maya’s work as a Master’s student was focused in quantitative biology. She loves coding and is extremely passionate about data science and data visualization.

Related