August 8, 2011 at 22:05

NetworkX for convenient work with network structures


    The NetworkX library is considered for creating, manipulating and studying the structure, dynamics and functioning of complex network structures.
    The basics of using the library as a learning tool, applied programming or research are considered.
    The basis for the description of the library are official materials from the site.
    The version of library 1.5 is considered.


    Library features


    The networkX library was created in Python and is designed to work with graphs and other network structures. This is free software distributed under the new BSD license .
    Key features of the library:
    • Classes for working with simple, oriented and weighted graphs;
    • A node can be almost anything: time-series, text, image, XML;
    • Saving / loading graphs to / from the most common graph storage file formats;
    • Built-in procedures for creating graphs of basic types;
    • Methods for detecting subgraphs, clicks, and K-partite graphs (K-core) (the maximum subgraph in which each vertex has at least level K).
    • Obtaining such characteristics of the graph as degrees of vertices, graph height, diameter, radius, path lengths, center, intermediateness, etc.
    • Visualize networks in the form of 2D and 3D graphs;
    • And much more…


    Performance


    It is stated that the library is free to operate with very large network structures, a graph level with 10 million nodes and 100 million arcs between them. In view of the fact that it is based on a low-level data structure of the Python language called “dictionary dictionaries” , memory is used up efficiently, graphs scale well, depend little on the features of the operating system in which the script is executed, and are excellent for the currently popular  analysis area data from social networks and graphs .

    Basic data structures


    The library is organized as a hierarchy of packages. The upper level in each package provides general methods for manipulating its structures, the lower ones gain more and more specialization.
    In all the following examples, networkX is connected with the following directive:
     >>> import networkx as nx


    Class graph


    The following major graph types are supported:
    • Graph is an implementation of a simple undirected graph. Additional vertices between two nodes are ignored; nodes connected to itself are possible.
    • DiGraph is a directed graph, functions and restrictions specific to this type of graph are added.
    • MultiGraph - implementation of multigraphs, in such graphs graphs, there may exist pairs of vertices that are connected by more than one edge (non-directional), or more than two arcs of opposite directions.
    • MultiDiGraph is a suitably oriented multigraph.

    Examples of creating empty graphs of various types:
    
>>> G=nx.Graph()
>>> G=nx.DiGraph()
>>> G=nx.MultiGraph()
>>> G=nx.MultiDiGraph()


    The internal representation of graphs is implemented in the form of adjacency lists. However, in order to avoid inconsistency, all operations with graphs should be performed not directly with this list, but using the library functions API.

    Knots and Arcs


    Components of any graph. Any node or arc has a unique identifier by which you can get all the information associated with it, and additionally there may be names more convenient for implementing the current algorithm than identifiers that also allow you to get this data.
    Additionally, each node or arc can have any number of attributes storing different types of data. Weighted graphs have a service attribute called “weight” and this name cannot be used to store other information in order to avoid breaking the internal logic of its presentation.

    Graph creation


    At the moment, a graph can be created using one of three methods:

    The created graph has both general and method-specific methods.
    
>>> import networkx as nx
>>> G=nx.Graph()
>>> G.add_edge(1,2)  # значение по умолчанию для дуги задаётся = 1
>>> G.add_edge(2,3,weight=0.9) # задаётся значение атрибута

    As the added values ​​can serve data of various types:
    
>>> import math
>>> G.add_edge('y','x',function=math.cos)
>>> G.add_node(math.cos) # любой объект типа hashable может быть узлом

    Arcs can also be added from arrays and data values:
    
>>> elist=[('a','b',5.0),('b','c',3.0),('a','c',1.0),('c','d',7.3)]
>>> G.add_weighted_edges_from(elist)


    Getting graph information


    In addition to creating a graph, you usually need to obtain information about its nodes, arcs, paths, etc. The main methods for this are to obtain arrays of nodes and arcs (edges () and nodes (), respectively), as well as obtaining an iterator over nodes and arcs (edges_iter () and nodes_iter () respectively).
    Additionally, there are a large number of functions for obtaining more specific information about the graph, for example, nx.triangles (G, n) will return the number of triangles in the graph G in which the vertex n is one of the nodes.
    All available functions are described in the documentation section at networkx.lanl.gov/reference/algorithms .

    Predefined algorithms


    The library implements a large number of algorithms typical for working on graphs. Algorithms such as finding the shortest path, search in height and width, clustering, finding isomorphism of graphs, and much more are implemented.
    For example, Dijkstra's algorithm for finding the minimum path on a weighted graph is implemented as follows:
    
>>> G=nx.Graph()
>>> e=[('a','b',0.3),('b','c',0.9),('a','c',0.5),('c','d',1.2)]
>>> G.add_weighted_edges_from(e)
>>> print(nx.dijkstra_path(G,'a','d'))
['a', 'c', 'd']


    Graph visualization


    The main purpose of the library is to work with graphs, and their visual display is secondary, but implemented, as it is an important analysis tool.
    Convenient methods are provided for displaying graphs using the Python Matplotlib library or the Graphviz plug-in for more complex cases. Full documentation on visualization capabilities is available at networkx.lanl.gov/reference/drawing.html .
    A simple graph visualization example:
    
>>> G=nx.cubical_graph()
>>> nx.draw(G)   # тип по умолчанию spring_layout
>>> nx.draw(G,pos=nx.spectral_layout(G), nodecolor='r',edge_color='b')


    Visualization using Matplotlib


    Visualization using Graphviz


    Data structures


    The entire internal representation of graphs uses a dictionary of dictionaries as the main data type. This approach has many advantages. For example, convenient access to nodes using notation of access to elements of a multidimensional array:
    
>>> G=nx.Graph()
>>> G.add_edge(1,2,color='red',weight=0.84,size=300)
>>> print(G[1][2]['size'])
300


    More detailed documentation is located at http://networkx.lanl.gov/reference/index. html
    I really enjoyed working with this library. I used a couple of small scripts and I hope to successfully implement it in one small study.
    Successful projects!
    Tags:

    Also popular now: