Bolin Wu
#
Network Connectivity

# Clustering coefficient

## Local clustering coefficient

## Global clustering coefficient

# Distance Measures

# Connected graphs

### Undirected graph

## Directed graph

# Connectivity and Robustness in Networks

### Simple path

# Ending

In this post I will briefly share the connectivity related concepts and functions of clustering coefficient, distance measures, and connection robustness.

**Tradic Closure** is the tendency for people who share lots of connections. People who share lots of friends have an increased likelihood of becoming connected themselves. One measure of the degree to which nodes in a network tend to "cluster" or form tranglies is **clustering coefficient**

The local clustering coefficient of Node C can be calculated as follows:

$\frac{\text{number of pairs of C's friends who are friends}}{\text{number of pairs of C's friends}}$

We assume that the local clustering coefficient of a node of degree less than 2 to be 0.

In NetworkX:

```
G = nx.Graph()
nx.clustering(G, 'Node Name')
```

We may also want to measure the clustering on the whole network.

- Approach 1: Average local clustering coefficient over all nodes in the graph.
- Approach 2: Measureing clustering on the whole network. Transitivity = $\frac{\text{3*Number of closed trads}}{\text{Number of open triads}}$. It weights nodes with large degree higher.

In Python you can find the average local clustering coefficient and transitivity as follows.

```
nx.transitivity(G)
nx.average_clustering(G)
```

Sometimes we would like to know how far nodes are away from each other. Distance between two nodes is the length of the shortest path between them. In Python we can find it as follows:

```
nx.shortest_path(G,'A', 'B')
nx.shortest_path_length(G, 'A','B')
```

**Average distance** characterize the average distance between all pairs of nodes in a graph.

```
nx.average_shortest_path_length(G)
```

**Diameter** is the maximum distance between any pair of nodes.

```
nx.diameter(G)
```

**Eccentricity** is the largest distance between node n and all other nodes.

```
nx.eccentricity(G)
```

The **radius** of a graph is the minimum eccentricity.

```
nx.radius(G)
```

The **periphery** of a graph is the set of nodes that have eccentricity equal to the diameter.

```
nx.periphery(G)
```

The **center** of a graph is the set of nodes that have eccentricity equal to the radius.

```
nx.center(G)
```

We can practice with an example. The graph data is from networkx library.

```
import networkx as nx
G = nx.karate_club_graph()
```

```
G = nx.convert_node_labels_to_integers(G, first_label= 1)
```

```
nx.draw_networkx(G)
```

```
# find average shortest path
nx.average_shortest_path_length(G)
```

```
2.408199643493761
```

```
# find radius
nx.radius(G)
```

```
3
```

```
# diameter
nx.diameter(G)
```

```
5
```

```
# center
nx.center(G)
```

```
[1, 2, 3, 4, 9, 14, 20, 32]
```

For directed and undirected graphs, we have different concepts for connected graphs.

An undiredted graph is **connected** if, for every pair nodes, there is a path between them.

```
# check if a graph is connected
nx.is_connected(G)
```

Connected component is a set of nodes satisfying the following two conditions:

- Every node in the subset has a path to every other node.
- No other node has a path to any node in the subset.

```
# the number of connected component subset
nx.number_connected_components(G)
# the specific connected component
sorted(nx.connected_components(G))
# the connected components of a node
nx.node_connected_component(G, 'M')
```

A directed graph is **strongly connected** if, for every pair nodes u and v, there is a directed path from u to v and a directed path from v to u.

```
# check if a graph is strongly connected
nx.is_strongly_connected(G)
```

A directed graph is **weakly connected** if replacing all directed edges with undirected edges produces a connected undirected graph.

```
# check if weakly connected
nx.is_weakly_connected(G)
```

Strongly connected component is a subset of nodes such as:

- Every node in the subset has a direct path to every other node.
- No other node has a directed path to and from every node in the subset.

```
# find strongly connected components
sorted(nx.strongly_connected_components(G))
```

Network robustness is the ability of a network to maintain its general structural properties when it faces failures or attacks. The typical attack is the removal of nodes or edges. The structural properties refer to connectivity.

Some examples are airport closures and internet router interruption.

We can measure the robustness by **node connectivity**, which is the smallest number of nodes to be removed from this graph in order to disconnect it.

```
# the smallest number
nx.node_connectivity(G_un)
# the specific node name
nx.minimum_node_cut(G_un)
```

Another question we can ask is what is the samllest number of edges that can be removed from this graph in order to disconnect it, a.k.a **edge connectivity**?

```
# minumum number of edges
nx.edge_connectivity(G_un)
# specific edges
nx.minimum_edge_cut(G_un)
```

Robus networks have large minimum node and edge cuts.

If we have a directed graph G and we want to know all the options to send a messages from node G to nodel L.

```
# all options
sorted(nx.all_simple_paths(G,'G', 'L'))
```

If we want to block all the options, how many nodes do we need to remove?

```
# the number of nodes need to remove in order to eliminate the connection
nx.node_connectivity(G, 'G', 'L')
# the specific node name
nx.minimum_node_cut(G, 'G', 'L')
```

What about removing edges instead of nodes?

```
# check the minimum number of edges need to be removed
nx.edge_connectivity(G, 'G', 'L')
# specific edges
nx.minimum_edge_cut(G. 'G', 'L')
```

Here I briefly shared the essential concepts and functions about Network connectivity. Hope this can be useful to you:)