Use networkx, a library that handles graphs in python (Part 2: Tutorial)

Eric Ma's Network Analysis-related course at Datacamp (Introduction to Network Analysis in Python -network-analysis-in-python)) was very good, so I will summarize what I learned about networkx based on the content of the course.

What went

1. Summary around the tutorial along networkx official website.

environment

Docker environment built last time has been modified as follows.

host

$ cat /etc/lsb-release 
DISTRIB_ID=Ubuntu
DISTRIB_RELEASE=16.04
DISTRIB_CODENAME=xenial
DISTRIB_DESCRIPTION="Ubuntu 16.04.6 LTS"

Dockerfile

FROM nvcr.io/nvidia/tensorflow:19.12-tf1-py3  

ARG DEBIAN_FRONTEND=noninteractive
             
RUN apt-get update && \
    apt-get install -y python3-tk && \
    pip install --upgrade pip && \
    pip install networkx && \
    pip install nxviz && \
    pip install pytest && \
    pip install nose

Graph element

A graph is defined by a collection of nodes (nodes, or vertices) and a pair of nodes called edges (edges, or links, etc.). Here, nodes consist of hashable objects (text, images, XML-defined objects, other graphs, etc.). Regarding the concept of hashable, Explanation of this article was easy to understand.

python_shell

>>> import networkx as nx
>>> G = nx.Graph()
>>> G2 = nx.Graph([(0, 1), (1, 2), (2, 0)])  #Specify nodes and edges

Add nodes and edges

python

>>> G.add_node(1)      　　　　#Add one node
>>> G.add_node('one')　　　　　
>>> G.add_nodes_from([2, 3])　#Add multiple nodes
>>> G.add_nodes_from(['two', 'three'])　

>>> G.add_edge(1, 2)          #Add edge
>>> G.add_edges_from([('one',1), (2, 3), (2, 4), (2, 'two'),  (2, 'three'), ('two', 'three')])

Delete nodes and edges

python

>>> G.remove_node(1)                         #The connecting edges are also deleted
>>> G.remove_nodes_from(['one', 'Two'])      #Delete multiple nodes

>>> G.remove_edge('one', 1)　　　　　　　　　　 #Delete one edge
>>> G.remove_edges_from([(2, 3), (2, 4)])　　 #Remove multiple edges
>>> G.clear()                                #Remove all elements

Graph display

python

>>> import matplotlib.pyplot as plt
>>> nx.draw(G, with_labels=True)             #Label
>>> plt.show()

Automatic graph creation

networkx has the ability to automatically create several types of graphs. Official site There is a detailed explanation, but the main graph is this blog //piroshhh.hatenablog.com/entry/2016/04/06/221852) was helpful. After all, it is easier to understand by looking at the structure of the graph, so I created the code graph_generator_classic.py to create the classic graph on the above official website. (Graph_generator_small.py for small graphs and graph_generator_random.py for random graphs will also be created.) (Note: If you create an environment with the above Dokerfile, the version of networkx will be 2.3. Networkx 2.4 is You need $ pip install --upgrade networkx if needed. )

python

>>> H = nx.path_graph(7)
>>> J = nx.turan_graph(5, 2)
>>> K = nx.star_graph(5)

Here in networkx, you can extract nodes and edges from other graphs and add them to another node, or you can make the other graph itself a node.

python

>>> G.add_nodes_from(H)　　　　　　  #Add only the nodes of graph H
>>> G.add_edges_from(H.edges)　　　 #Add only the edges of graph H

>>> G.add_node(H)    　　　　　　    #Add graph H as one node of graph G
>>> G.add_nodes_from([J, K])

Information extraction of graph elements

There are four basic properties that describe a graph element. Taking the following wheel graph with 7 nodes as an example, it will be as follows.

python

>>> G = nx.wheel_graph(7)
>>> nx.draw(G, with_labels=True)
>>> plt.show()

>>> G.nodes
NodeView((0, 1, 2, 3, 4, 5, 6))
>>> G.edges
EdgeView([(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (1, 2), (1, 6), (2, 3), (3, 4), (4, 5), (5, 6)])
>>> G.adj　　　　　　　　#Neighboring node information
AdjacencyView({0: {1: {}, 2: {}, 3: {}, 4: {}, 5: {}, 6: {}}, 1: {0: {}, 2: {}, 6: {}}, 2: {0: {}, 1: {}, 3: {}}, 3: {0: {}, 2: {}, 4: {}}, 4: {0: {}, 3: {}, 5: {}}, 5: {0: {}, 4: {}, 6: {}}, 6: {0: {}, 5: {}, 1: {}}})
>>> G.degree　　　　　　#Number of adjacent nodes
DegreeView({0: 6, 1: 3, 2: 3, 3: 3, 4: 3, 5: 3, 6: 3})

Since the return value is the same as the dictionary type, you can loop with .items () or search within the attribute with .data ('word'). In addition, it can be converted to lists, sets, dictionaries, and tuples by assignment.

Access to graph element attributes

The attributes of the nodes and edges of the graph can be accessed by subscription.

python

>>> G.nodes[0]           #Access to node 0 attributes
{}
>>> G.edges[0,1]　　　　　#Edge(0, 1)Access to attributes of
{}
>>> G.adj[0]　　　　　　　 #Access to the edge adjacent to node 0
AtlasView({1: {}, 2: {}, 3: {}, 4: {}, 5: {}, 6: {}})
>>> G.degree[0]　　　　　　#Number of adjacent nodes for node 0
6

The attributes of the graph element can be added with the following description.

python

>>> G.nodes[0]['color'] = 'blue'
>>> G.edges[0,1]['weight']=0.1

>>> G.nodes[0]
{'color': 'blue'}
>>> G.edges[0,1]
{'weight': 0.1}
>>> G.adj[0]
AtlasView({1: {'weight': 0.1}, 2: {}, 3: {}, 4: {}, 5: {}, 6: {}})

The attributes shown in G.adj [0] are edge attributes, not node attributes. Commonly used attributes, such as weights, can also be written as follows.

python

>>> G.add_weighted_edges_from([(0, 1, 0.1), (0, 2, 0.2), (0, 3, 0.3), (0, 4, 0.4), (0, 5, 0.5), (0, 6, 0.6)])
>>> G.adj[0]
AtlasView({1: {'weight': 0.1}, 2: {'weight': 0.2}, 3: {'weight': 0.3}, 4: {'weight': 0.4}, 5: {'weight': 0.5}, 6: {'weight': 0.6}})

If you want to delete the attribute, write as follows.

python

>>> del G.node[1]['color']
>>> del G.edges[0,1]['weight']

The graph drawn by specifying other attributes looks like this. The code can be found at draw_graph.py. (This official document and This article ) Was used as a reference.)

Graph type

In addition to the undirected graphs we have dealt with so far, there are also directed graphs with edges pointing and multigraphs that can define multiple edges between the same node pair. Regarding the types of graphs, the explanation in this article was easy to understand.

python

>>> GG = nx.Graph()          #Undirected graph
>>> DG = nx.DiGraph()        #Directed graph
>>> MG = nx.MultiGraph()     #Multiple undirected graph
>>> MG = nx.MultiDiGraph()   #Multiple directed graph

For directed graphs, you can use nx.out_degree () and nx.in_degree () to count adjacent nodes separately according to the edge orientation. In nx.degree (), the sum of the two is given.

Graph operation

Processing between graphs for graphs is also defined. Regarding the processing result, I also referred to this article. I also wrote the code graph_operation.py to draw these graphs.

Subgraph

A graph defined by only some nodes of the graph is called a subgraph. For example, from the complete graph with 5 nodes on the left, the subgraph consisting of the node set [1,2,3,4] is on the right. Of the edges contained in the original graph, only the edges between the selected node sets are included in the subgraph.

python

>>> Ga = nx.complete_graph(5)
>>> nbunch = [1,2,3,4]
>>> H = nx.subgraph(Ga, nbunch)

Union or Disjoint-Union of Graph A process called union / disjoint-union, which is the union of graphs, is defined. Generally speaking, union is a union of nodes and edges, but networkx assumes that graphs G1 and G2 do not include the same node (disjoint). If you want to find the union of two graphs containing nodes with the same name, use disjoint_union or use the rename attribute in union to rename the nodes contained in each graph. For the concept of disjoint-union of graphs, this wikipedia article was helpful.

python

>>> Ga = nx.complete_graph(5)
>>> Gb = nx.ladder_graph(5)
>>> H = nx.union(Ga, Gb, rename=('a-','b-'))   #When using union
>>> H = nx.disjoint_union(Ga, Gb)　　　　　　　　#disjoint_When using union

Cartesian product graph

The Cartesian product graph consisting of the above Ga and Gb is as follows.

python

>>> H = nx.cartesian_product(Ga, Gb)

compose The comose graph consisting of the above Ga and Gb is as follows. Comoise is a graph in which nodes with the same name are shared and composed.

python

>>> nx.compose(Ga, Gb)

Complement graph

A graph consisting of edges that are not defined between the nodes of the original graph is called a complement graph. For example, from the ladder graph on the left, the complementary graph that is composed is on the right.

python

>>> nx.complement(Gb)

Conversion between directed and undirected graphs

There is also the process of converting directed and undirected graphs. Now, if you convert an undirected graph to a directed graph, the edges will have both directions.

python

>>> H = nx.to_directed(Ga)
>>> H = nx.to_undirected(Ga)

Save graph

You can save the created graph to a file or load it from a file.

python

>>> nx.write_gml(red, "test.gml")
>>> G = nx.read_gml("test.gml")

Related article

-Use networkx, a library that handles graphs in python (Part 1: Environment construction) -Use networkx, a library that handles graphs in python (Part 2: Tutorial)