NetworkX
Python library for graphs and networks From Wikipedia, the free encyclopedia
NetworkX is a Python library for studying graphs and networks. NetworkX is free software released under the BSD-new license.
A graph created with NetworkX | |
| Original author(s) | Aric Hagberg Pieter Swart Dan Schult |
|---|---|
| Developer(s) | Many others |
| Initial release | 11 April 2005[1][2] |
| Stable release | |
| Repository | |
| Written in | Python |
| Operating system | Cross-platform |
| Type | Software library |
| License | BSD-new license |
| Website | networkx |
History
Summarize
Perspective
NetworkX began development in 2002 by Aric A. Hagberg, Daniel A. Schult, and Pieter J. Swart.[4] It is supported by the National Nuclear Security Administration of the U.S. Department of Energy at Los Alamos National Laboratory.
The package was crafted with the aim of creating tools to analyze data and intervention strategies for controlling the epidemic spread of disease, while also exploring the structure and dynamics of more general social, biological, and infrastructural systems.[4]
Inspired by Guido van Rossum's 1998 essay on Python graph representation,[5] NetworkX made its public debut at the 2004 SciPy annual conference. In April of 2005, NetworkX was made available as open source software.[1]
Several Python packages focusing on graph theory, including igraph, graph-tool, and numerous others, are available. As of April 2024, NetworkX had over 50 million downloads,[6] surpassing the download count of the second most popular package, igraph, by more than 50-fold.[7] This substantial adoption rate could potentially be attributed to NetworkX's early release and its continued evolution within the SciPy ecosystem.
In 2008, SageMath, an open source mathematics system, incorporated NetworkX into its package and added support for more graphing algorithms and functions.[4]
| Version | Release Date | Major Changes |
|---|---|---|
| 0.22 | 17 June 2005 |
Topological sorting for testing directed acyclic graphs (DAGs).
Integration of Dijkstra's algorithm for finding shortest paths in weighted graphs. [8] |
| 0.99 | 18 November 2008 |
Default graph type transitioned to a weighted graph.
MultiGraph, MultiDiGraph, LabeledGraph, and LabeledDiGraph introduced.[8] |
| 1.0 | 8 January 2010 |
Addition of difference and intersection operators.
Implementation of the A* algorithm for optimized pathfinding. Incorporation of PageRank, HITS, and [eigenvector] centrality algorithms for network analysis. Integration of Kruskal’s algorithm for constructing minimum spanning trees. [8] |
| 2.0 | 20 September 2017 |
Significant revisions to the methods within the MultiGraph and DiGraph classes.
Overhaul of documentation system. Various user quality of life changes.[8] |
| 3.0 | 7 January 2023 |
Improved integrations to SciPy ecosystem packages.
Added new plugin feature to allow users to use different backends (GraphBLAS, CuGraph) for computation. [9] |
Features
Supported Graph Types
Summarize
Perspective
Overview
Graphs, in this context, represent collections of vertices (nodes) and edges (connections) between them. NetworkX provides support for several types of graphs, each suited for different applications and scenarios.
Directed Graphs (DiGraph)
Directed graphs, or DiGraphs, consist of nodes connected by directed edges. In a directed graph, edges have a direction indicating the flow or relationship between nodes. [10]
Undirected Graphs (Graph)
Undirected graphs, simply referred to as graphs in NetworkX, are graphs where edges have no inherent direction. The connections between nodes are symmetrical, meaning if node A is connected to node B, then node B is also connected to node A. [11]
MultiGraphs
MultiGraphs allow multiple edges between the same pair of nodes. In other words, MultiGraphs permit parallel edges, where more than one edge can exist between two nodes. [12]
MultiDiGraphs
MultiDiGraphs are directed graphs that allow multiple directed edges between the same pair of nodes. Similar to MultiGraphs, MultiDiGraphs enable the modeling of scenarios where multiple directed relationships exist between nodes. [13]
Challenges in Visualization
While NetworkX provides powerful tools for graph creation and analysis, producing visualizations of complex graphs can be challenging. Visualizing large or densely connected graphs may require specialized techniques and external libraries beyond the capabilities of NetworkX alone.
Graph Layouts
Summarize
Perspective
NetworkX provides various layout algorithms for visualizing graphs in two-dimensional space. These layout algorithms determine the positions of nodes and edges in a graph visualization, aiming to reveal its structure and relationships effectively.
Spring Layout
The Spring Layout in NetworkX is a popular way to visualize graphs using a force-directed algorithm. It’s based on the Fruchterman-Reingold model, which works like a virtual physics simulation. Each node in your graph is a charged particle that repels other nodes, while the edges act like springs that pull connected nodes closer together. This balance creates a layout where the graph naturally spreads out into an informative shape.
As the algorithm runs, it tries to reduce the overall "energy" of the system by adjusting the positions of the nodes step by step. The result often highlights patterns in the graph—like clusters or groups of nodes that are tightly connected. It works best for small to medium-sized graphs, where clarity and appearance are important.
You can create this layout in NetworkX using the spring_layout() function, found in networkx.drawing.layout. The function gives you a few options to customize the layout, you can control the distance between nodes with the k parameter or decide how many iterations the simulation should run. It lets you lay out the graph in more than two dimensions by setting the dim parameter.
G = nx.path_graph(4)
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True)
This layout method is used for interactive and exploratory visualizations. The spring layout often reveals the structure of the graph in a intuitive and readable way[14]
Spectral Layout
The Spectral layout is based on the spectral properties of the graph's adjacency matrix. It uses the eigenvalues and eigenvectors of the adjacency matrix to position nodes in a low-dimensional space. Spectral layout tends to emphasize the global structure of the graph, making it useful for identifying clusters and communities.[15]
Circular Layout
The Circular layout arranges nodes evenly around a circle, with edges drawn as straight lines connecting them. This layout is particularly suitable for visualizing cyclic or symmetric graphs, where the arrangement of nodes along the circle reflects the underlying topology of the graph.[16]
Shell Layout
The Shell layout organizes nodes into concentric circles or shells based on their distance from a specified center. Nodes within the same shell have the same distance from the center, while edges are drawn radially between nodes in adjacent shells. Shell layout is often used for visualizing hierarchical or tree structures.[17]
Sample code
# simple shell‐layout example
G = nx.balanced_tree(2, 2)
shells = [[0], [1, 2], [3, 4, 5, 6]]
pos = nx.shell_layout(G, nlist=shells)
nx.draw(G, pos, with_labels=True)
Kamada-Kawai Layout
The Kamada-Kawai layout algorithm positions nodes based on their pairwise distances, aiming to minimize the total energy of the system. It takes into account both the graph's topology and edge lengths, resulting in a layout that emphasizes geometric accuracy and readability.[18]
Usage
NetworkX provides functions for applying different layout algorithms to graphs and visualizing the results using Matplotlib or other plotting libraries. Users can specify the desired layout algorithm when calling the drawing functions, allowing for flexible and customizable graph visualizations.
Suitability
NetworkX is suitable for operation on large real-world graphs: e.g., graphs in excess of 10 million nodes and 100 million edges.[clarification needed][19] Due to its dependence on a pure-Python "dictionary of dictionary" data structure, NetworkX is a reasonably efficient, very scalable, highly portable framework for network and social network analysis.[4]
Applications
Summarize
Perspective
NetworkX was designed to be easy to use and learn, as well as a powerful and sophisticated tool for network analysis. It is used widely on many levels, ranging from computer science and data analysis education to large-scale scientific studies.[4]
NetworkX has applications in any field that studies data as graphs or networks, such as mathematics, physics, biology, computer science and social science.[20] The nodes in a NetworkX graph can be specialized to hold any data, and the data stored in edges is arbitrary, further making it widely applicable to different fields. It is able to read in networks from data and randomly generate networks with specified qualities. This allows it to be used to explore changes across wide amounts of networks.[4] The figure below demonstrates a simple example of the software's ability to create and modify variations across large amounts of networks.
NetworkX has many network and graph analysis algorithms, aiding in a wide array of data analysis purposes. One important example of this is its various options for shortest path algorithms. The following algorithms are included in NetworkX, with time complexities given the number of vertices (V) and edges (E) in the graph:[21]
- Dijkstra: O((V+E) log V)
- Bellman-Ford: O(V * E)
- Goldberg-Radzik: O(V * E)
- Johnson: O(V^2 log(V) + VE)
- Floyd Warshall: O(V^3)
- A*: O((V+E) log V)
An example of the use of NetworkX graph algorithms can be seen in a 2018 study, in which it was used to analyze the resilience of livestock production networks to the spread of epidemics. The study used a computer model to predict and study trends in epidemics throughout American hog production networks, taking into account all livestock industry roles. In the study, NetworkX was used to find information on degree, shortest paths, clustering, and k-cores as the model introduced infections and simulated their spread. This was then used to determine which networks are most susceptible to epidemics.[22]
In addition to network creation and analysis, NetworkX also has many visualization capabilities. It provides hooks into Matplotlib and GraphViz for 2D visuals, and VTK and UbiGraph for 3D visuals.[4] This makes the package useful in easily demonstrating and reporting network analysis and data, and allows for the simplification of networks for visual processing.
Comparison with Matlab
Summarize
Perspective
Matlab allows users to graph networks. Matlab is widely used to graph networks and it is widely applicable in mathematical, physical, biological, and information systems. [23]
Dealing with large data
The main issue with NetworkX is memory usage with large graphs. Since NetworkX stores graph data in Python objects, it cannot handle tens of millions of objects without consuming memory. This leads to out-of-memory errors when working with that large graphs.[24] On the other hand, MATLAB can help you process big data efficiently by integrating it with your existing infrastructure. You can scale up and run your MATLAB code interactively using parallel processing as well as in deployed production mode. You can deploy analytics in streaming, and batch applications royalty-free. Also, you can run your MATLAB code and models with big data on different cloud data platforms like Databricks, Domino Data Lab, and Google® BigQuery.[25]
Cost
Python is an open-source programming language, which means it is completely free to use: you can download Python and its frameworks and libraries at no charge.[26] While, MATLAB has 6 pricing edition(s), from $49 to $2,150. [27]
Applications to pure mathematics
Networks are useful tools to visualize, which helps with analyzing or making good predictions. It gives the clear picture when dealing with a finite set. It can be used in different fields of mathematics like Set theory, Abstract algebra, and Number Theory.
Graph a subgroups lattice of a group
Lattice of subgroups can be graphed for finite groups with a reasonable order.
Graph ordered relations
Ordered relations on finite sets with reasonable size can be graphed.
Graph equivalence relations
An Equivalence relation on a finite set with reasonable size could be graphed with Networkx. This is an efficient way to visualize it as it separates the equivalence classes.
Integration
See also
References
External links
Wikiwand - on
Seamless Wikipedia browsing. On steroids.