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

Clustering coefficient

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

Local 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')

Global clustering coefficient

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)

Distance Measures

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]

Connected graphs

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

Undirected graph

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:

1. Every node in the subset has a path to every other node.
2. 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')

Directed graph

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:

1. Every node in the subset has a direct path to every other node.
2. 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))

Connectivity and Robustness in Networks

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.

Simple path

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')

Ending

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