Graph types#
NetworkX provides data structures and methods for storing graphs.
All NetworkX graph classes allow (hashable) Python objects as nodes and any Python object can be assigned as an edge attribute.
The choice of graph class depends on the structure of the graph you want to represent.
Which graph class should I use?#
Basic graph types#
NetworkX uses dicts to store the nodes and neighbors in a graph. So the reporting of nodes and edges for the base graph classes may not necessarily be consistent across versions and platforms; however, the reporting for CPython is consistent across platforms and versions after 3.6.
Graph Views#
View of Graphs as SubGraph, Reverse, Directed, Undirected.
In some algorithms it is convenient to temporarily morph a graph to exclude some nodes or edges. It should be better to do that via a view than to remove and then re-add. In other algorithms it is convenient to temporarily morph a graph to reverse directed edges, or treat a directed graph as undirected, etc. This module provides those graph views.
The resulting views are essentially read-only graphs that report data from the original graph object. We provide an attribute G._graph which points to the underlying graph object.
Note: Since graphviews look like graphs, one can end up with view-of-view-of-view chains. Be careful with chains because they become very slow with about 15 nested views. For the common simple case of node induced subgraphs created from the graph class, we short-cut the chain by returning a subgraph of the original graph directly rather than a subgraph of a subgraph. We are careful not to disrupt any edge filter in the middle subgraph. In general, determining how to short-cut the chain is tricky and much harder with restricted_views than with induced subgraphs. Often it is easiest to use .copy() to avoid chains.
subgraph_view (G[, filter_node, filter_edge])
View of G applying a filter on nodes and edges.
View of G with edge directions reversed
Core Views#
Views of core data structures such as nested Mappings (e.g. dict-of-dicts). These Views often restrict element access, with either the entire view or layers of nested mappings being read-only.
An AtlasView is a Read-only Mapping of Mappings.
An AdjacencyView is a Read-only Map of Maps of Maps.
An MultiAdjacencyView is a Read-only Map of Maps of Maps of Maps.
A read-only union of two atlases (dict-of-dict).
A read-only union of dict Adjacencies as a Map of Maps of Maps.
A read-only union of two inner dicts of MultiAdjacencies.
A read-only union of two dict MultiAdjacencies.
Functions#
Functional interface to graph methods and assorted utilities.
Graph#
Returns a degree view of single node or of nbunch of nodes.
Returns a list of the frequency of each degree value.
Returns the density of a graph.
Returns a copy of the graph G with all of the edges removed.
Return True if graph is directed.
Returns a directed view of the graph graph .
Returns an undirected view of the graph graph .
Returns True if G has no edges.
add_star (G_to_add_to, nodes_for_star, **attr)
Add a star to Graph G_to_add_to.
add_path (G_to_add_to, nodes_for_path, **attr)
Add a path to the Graph G_to_add_to.
add_cycle (G_to_add_to, nodes_for_cycle, **attr)
Add a cycle to the Graph G_to_add_to.
Returns the subgraph induced on nodes in nbunch.
subgraph_view (G[, filter_node, filter_edge])
View of G applying a filter on nodes and edges.
Returns a SubGraph view of G showing only nodes in nbunch.
Returns a view of G with hidden nodes and edges.
View of G with edge directions reversed
Returns a view of the subgraph induced by the specified edges.
Nodes#
Returns an iterator over the graph nodes.
Returns the number of nodes in the graph.
Returns a list of nodes connected to node n.
Returns all of the neighbors of a node in the graph.
Returns the non-neighbors of the node in the graph.
Returns the common neighbors of two nodes in a graph.
Edges#
Returns an edge view of edges incident to nodes in nbunch.
Returns the number of edges in the graph.
Returns the density of a graph.
Returns the non-existent edges in the graph.
Self loops#
Returns an iterator over selfloop edges.
Returns the number of selfloop edges.
Returns an iterator over nodes with self loops.
Attributes#
Returns True if G has weighted edges.
Returns True if G has negatively weighted edges.
Sets node attributes from a given value or dictionary of values.
Get node attributes from graph
Sets edge attributes from a given value or dictionary of values.
Get edge attributes from graph
Paths#
Returns whether or not the specified path exists.
Returns total cost associated with specified path and weight
Freezing graph structure#
Modify graph to prevent further change by adding or removing nodes or edges.
Returns True if graph is frozen.
Software for Complex Networks#
NetworkX is a Python package for the creation, manipulation, and study of the structure, dynamics, and functions of complex networks. It provides:
- tools for the study of the structure and dynamics of social, biological, and infrastructure networks;
- a standard programming interface and graph implementation that is suitable for many applications;
- a rapid development environment for collaborative, multidisciplinary projects;
- an interface to existing numerical algorithms and code written in C, C++, and FORTRAN; and
- the ability to painlessly work with large nonstandard data sets.
With NetworkX you can load and store networks in standard and nonstandard data formats, generate many types of random and classic networks, analyze network structure, build network models, design new network algorithms, draw networks, and much more.
Citing#
To cite NetworkX please use the following publication:
Aric A. Hagberg, Daniel A. Schult and Pieter J. Swart, “Exploring network structure, dynamics, and function using NetworkX”, in Proceedings of the 7th Python in Science Conference (SciPy2008), Gäel Varoquaux, Travis Vaught, and Jarrod Millman (Eds), (Pasadena, CA USA), pp. 11–15, Aug 2008
Audience#
The audience for NetworkX includes mathematicians, physicists, biologists, computer scientists, and social scientists. Good reviews of the science of complex networks are presented in Albert and Barabási [BA02] , Newman [Newman03] , and Dorogovtsev and Mendes [DM03] . See also the classic texts [Bollobas01] , [Diestel97] and [West01] for graph theoretic results and terminology. For basic graph algorithms, we recommend the texts of Sedgewick (e.g., [Sedgewick01] and [Sedgewick02] ) and the survey of Brandes and Erlebach [BE05] .
Python#
Python is a powerful programming language that allows simple and flexible representations of networks as well as clear and concise expressions of network algorithms. Python has a vibrant and growing ecosystem of packages that NetworkX uses to provide more features such as numerical linear algebra and drawing. In order to make the most out of NetworkX you will want to know how to write basic programs in Python. Among the many guides to Python, we recommend the Python documentation and the text by Alex Martelli [Martelli03] .
License#
NetworkX is distributed with the 3-clause BSD license.
Copyright (C) 2004-2023, NetworkX Developers Aric Hagberg hagberg@lanl.gov> Dan Schult dschult@colgate.edu> Pieter Swart swart@lanl.gov> All rights reserved. Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: * Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. * Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution. * Neither the name of the NetworkX Developers nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
Bibliography#
R. Albert and A.-L. Barabási, “Statistical mechanics of complex networks”, Reviews of Modern Physics, 74, pp. 47-97, 2002. https://arxiv.org/abs/cond-mat/0106096
B. Bollobás, “Random Graphs”, Second Edition, Cambridge University Press, 2001.
U. Brandes and T. Erlebach, “Network Analysis: Methodological Foundations”, Lecture Notes in Computer Science, Volume 3418, Springer-Verlag, 2005.
S.N. Dorogovtsev and J.F.F. Mendes, “Evolution of Networks”, Oxford University Press, 2003.
A. Martelli, “Python in a Nutshell”, O’Reilly Media Inc, 2003.
M.E.J. Newman, “The Structure and Function of Complex Networks”, SIAM Review, 45, pp. 167-256, 2003. http://epubs.siam.org/doi/abs/10.1137/S003614450342480
R. Sedgewick, “Algorithms in C: Parts 1-4: Fundamentals, Data Structure, Sorting, Searching”, Addison Wesley Professional, 3rd ed., 2002.
R. Sedgewick, “Algorithms in C, Part 5: Graph Algorithms”, Addison Wesley Professional, 3rd ed., 2001.
D. B. West, “Introduction to Graph Theory”, Prentice Hall, 2nd ed., 2001.