# 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.

The radius is the minimum eccentricity of the graph.

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

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)$$ ##### Maya Gans
###### Data Visualization Engineer

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.