Algorithms For Dummies

  Understanding Graph Basics 

     165

because it lacks any edge information. (You can find this code in the 

A4D; 08; 

Graph Measurements.ipynb

 file.)

import networkx as nx

import matplotlib.pyplot as plt

%matplotlib inline

AGraph = nx.Graph()

Nodes = range(1,5)

Edges = [(1,2), (2,3), (3,4), (4,5), (1,3), (1,5)]

AGraph.add_nodes_from(Nodes)

AGraph.add_edges_from(Edges)

AGraph.add_node(6)

sorted(nx.connected_components(AGraph))

[{1, 2, 3, 4, 5}, {6}]

The output from this code shows that nodes 1 through 5 are connected and that 

node 6 lacks a connection. Of course, you can remedy this situation by adding 

another edge by using the following code and then checking again:

AGraph.add_edge(1,6)

sorted(nx.connected_components(AGraph))

[{1, 2, 3, 4, 5, 6}]

The output now shows that every one of the nodes connects to at least one other 

node. However, you don’t know which nodes have the most connections. The 

count of edges to a particular node is the degree. The higher the degree, the more 

complex the node becomes. By knowing the degree, you can develop an idea of 

which nodes are most important. The following code shows how to obtain the 

degree for the example graph.

nx.degree(AGraph).values()

dict_values([4, 2, 3, 2, 2, 1])

The degree values appear in node order, so node 1 has four connections and node 6 

has only one connection. Consequently, node 1 is the most important, followed by 

node 3, which has three connections.

---

166

 

   

  PART 3