NetworkX Graphs =============== The NetworkX library -------------------- NetworkX is a Python library for creating, manipulating, and displaying mathematical objects called *graphs*, or *networks*. We begin by importing the library: .. code:: python import networkx as nx Graphs ------ A graph is a mathematical object that consists of points called *nodes* together with lines connecting them called *edges*. Nodes are typically labeled with positive integers, and an edge between two nodes is given by an ordered pair. .. code:: python G = nx.Graph() G.add_nodes_from([1,2,3,4,5,6]) G.add_edge(1,4) nx.draw(G) In the above code, the function :code:`Graph()` creates an empty graph object in Python that we can then fill with nodes and edges. Nodes and edges can either be added individually or from a list using different methods. Below is the graph G generated by the code above. .. figure:: graph1.png :width: 450px :align: center Notice that the layout of the nodes is not ideal, and we do not know which node is which. To make the graph come out looking better, we can add some additional arguments to the :code:`draw` function. .. code:: python nx.draw(G, pos=nx.circular_layout(G), with_labels=True) .. figure:: graph1_circular.png :width: 450px :align: center In the above code, the argument :code:`pos=nx.circular_layout(G)` arranges the nodes in a circle going counterclockwise with the first node on the right. The argument :code:`with_labels=True` turns on the node labels so we can tell which node is which. To modify the graph, we do not need to start over from scratch, we can simply add additional nodes and edges using the methods :code:`add_node`, :code:`add_nodes_from`, :code:`add_edge`, and :code:`add_edges_from`. .. code:: python G.add_node(7) G.add_edges_from([(1,2),(1,3),(1,4),(3,5),(3,6),(5,7)]) nx.draw(G, pos=nx.circular_layout(G), with_labels=True) .. figure:: graph2.png :width: 450px :align: center We can also remove nodes and edges in a similar fashion using the methods :code:`remove_node`, :code:`remove_nodes_from`, :code:`remove_edge`, and :code:`remove_edges_from`. When removing nodes, any edges containing the removed node will also be removed. You can take at look at the nodes and edges in your graph at anytime using the :code:`nodes` and :code:`edges` methods. .. code:: python G.nodes() .. container:: output NodeView((1, 2, 3, 4, 5, 6, 7)) .. code:: python G.edges() .. container:: output EdgeView([(1, 2), (1, 3), (1, 4), (2, 4), (3, 5), (3, 6), (5, 7)]) The data structure of graph objects is composed of dictionaries with the nodes as keys. If you input the node :math:`x`, you will get a dictionary containing the nodes connected to :math:`x` by an edge. Such nodes are called *adjacent* or *neighbors*. .. code:: python G[1] .. container:: output AtlasView({2: {}, 3: {}, 4: {}}) The *neighborhood* of a node is the collection of all its neighbors. For example, the our graph :math:`G`, the neighborhood of node 1 is the collection of nodes 2, 3, and 4. The number of nodes in the neighborhood of :math:`x` is called the degree of the node :math:`x`. In our example, the degree of node 1 is 3 since node 1 has 3 neighbors. You can use the :code:`degree` method to obtain the degree of a node. .. code:: python G.degree(1) .. container:: output 3 Weighted Edges -------------- NetworkX also makes it possible to assign different attributes to each edge, the most common of which are edge weights. An *edge weight* is a real number associated to an edge, typically representing the importance of the connection between the two corresponding nodes. A weighted edge between nodes :math:`x` and :math:`y` with weight :math:`w` is represented by the triple :math:`(x,y,w)`. .. code:: python W = nx.Graph() W.add_weighted_edges_from([(1,2,1.3),(2,3,1.9),(2,4,0.8),(3,4,2.3)]) nx.draw(W, pos=nx.circular_layout(W), with_labels=True) .. figure:: weighted_graph1.png :width: 450px :align: center Notice that :code:`nx.draw` does not draw the edge weights. For that we will need some additional commands. .. code:: python weights = nx.get_edge_attributes(W,'weight') nx.draw(W, pos=nx.circular_layout(W), with_labels=True) nx.draw_networkx_edge_labels(W, pos=nx.circular_layout(W), edge_labels=weights) plt.show() .. figure:: weighted_graph2.png :width: 450px :align: center Digraphs -------- A *directed graph* or *digraph* is a graph where the edges have direction. The edge, often called an *arrow*, :math:`(x,y)` starts at node :math:`x` and goes to node :math:`y`. .. code:: python D = DiGraph() D.add_edges_from([(1,2),(3,2),(4,3),(4,1),(1,4),(3,1)]) nx.draw(D, pos=nx.circular_layout(D), with_labels=True) .. figure:: digraph1.png :width: 450px :align: center A node :math:`x` in a digraph :math:`D` has two neighborhoods, the out-neighborhood and the in-neighborhood. The *out-neighborhood* contains all the nodes :math:`y` such that :math:`D` contains the arrow :math:`(x,y)`. The *in-neighborhood* of :math:`x` contains all the nodes :math:`w` such that :math:`D` contains the arrow :math:`(w,x)`. Thus every node will also have an out-degree and an in-degree. It is easy to get the out-neighborhood of a node in a NetworkX digraph. .. code:: python D[1] .. container:: output AtlasView({2: {}, 4: {}}) The out-degree and in-degree can be obtained using the methods :code:`out_degree` and :code:`in_degree` respectively. .. code:: python D.out_degree(3),D.in_degree(3) .. container:: output (2,1) Multigraphs ----------- A *multigraph* is a graph that can have multiples edges connecting the same two nodes. .. code:: python M = nx.MultiGraph() M.add_edges_from([(1,2),(2,3),(3,1),(3,1),(3,1),(2,4),(2,4)]) Multigraphs also allow for edges to start and stop at the same node. .. code:: python M.add_edge(1,1) The neighborhood and degree are defined the same way as for graphs. .. code:: python M[1] .. container:: output AdjacencyView({2: {0: {}}, 3: {0: {}, 1: {}, 2: {}}, 1: {0: {}}}) .. code:: python M.degree(1) .. container:: output 6 Further reading --------------- `NetworkX website `__ can be used to access the official documentation for the NetworkX library.