Few important characteristics of a Graph –
- Eccentricity: For a node n in graph G, the eccentricity of n is the largest possible shortest path distance between n and all other nodes.
- Diameter : The maximum shortest distance between a pair of nodes in a graph G is its Diameter. It is the largest possible eccentricity value of a node.
- Radius : It is the minimum eccentricity value of a node.
- Periphery : It is the set of nodes that have their eccentricity equal to their Diameter.
- Center : Center of a Graph is the set of nodes whose eccentricity is equal to the radius of the Graph.
Networkx offers built-in function for computing all these properties.
Python3
import networkx as nx import matplotlib.pyplot as pltG = nx.Graph()G.add_edges_from([('A', 'B'), ('A', 'K'), ('B', 'K'), ('A', 'C'), ('B', 'C'), ('C', 'F'), ('F', 'G'), ('C', 'E'), ('E', 'F'), ('E', 'D'), ('E', 'H'), ('H', 'I'), ('I', 'J')])plt.figure(figsize =(9, 9))nx.draw_networkx(G, with_labels = True, node_color ='green')print("Eccentricity: ", nx.eccentricity(G))print("Diameter: ", nx.diameter(G))print("Radius: ", nx.radius(G))print("Preiphery: ", list(nx.periphery(G)))print("Center: ", list(nx.center(G))) |
Output:
Eccentricity: {‘A’: 5, ‘K’: 6, ‘B’: 5, ‘H’: 4, ‘J’: 6, ‘E’: 3, ‘C’: 4, ‘I’: 5, ‘F’: 4, ‘D’: 4, ‘G’: 5}
Diameter: 6
Radius: 3
Periphery: [‘K’, ‘J’]
Center: [‘E’]
Reference: https://networkx.github.io/documentation.
Python | Clustering, Connectivity and other Graph properties using Networkx
Triadic Closure for a Graph is the tendency for nodes who has a common neighbour to have an edge between them. In case more edges are added in the Graph, these are the edges that tend to get formed. For example in the following Graph :
The edges that are most likely to be formed next are (B, F), (C, D), (F, H), and (D, H) because these pairs share a common neighbour.
Local Clustering Coefficient of a node in a Graph is the fraction of pairs of the node’s neighbours that are adjacent to each other. For example the node C of the above graph has four adjacent nodes, A, B, E and F.
Number of possible pairs that can be formed using these 4 nodes are 4*(4-1)/2 = 6.
Number of actual pairs that are adjacent to each other = 2. These are (A, B) and (E, F).
Thus Local Clustering Coefficient for node C in the given Graph = 2/6 = 0.667
Networkx helps us get the clustering values easily.
Python3
import networkx as nx G = nx.Graph()G.add_edges_from([('A', 'B'), ('A', 'K'), ('B', 'K'), ('A', 'C'), ('B', 'C'), ('C', 'F'), ('F', 'G'), ('C', 'E'), ('E', 'F'), ('E', 'D'), ('E', 'H'), ('I', 'J')])# returns a Dictionary with clustering value of each nodeprint(nx.clustering(G))# This returns clustering value of specified nodeprint(nx.clustering(G, 'C')) |
Output:
{'A': 0.6666666666666666,
'B': 0.6666666666666666,
'C': 0.3333333333333333,
'D': 0,
'E': 0.16666666666666666,
'F': 0.3333333333333333,
'G': 0,
'H': 0,
'I': 0,
'J': 0,
'K': 1.0}
0.3333333333333333