See discussions, stats, and author profiles for this publication at: [Link]

net/publication/236407765

Exploring Network Structure, Dynamics, and Function Using NetworkX

Conference Paper · June 2008

DOI: 10.25080/TCWV9851

CITATIONS READS

8,085 15,440

3 authors, including:

Pieter Swart
Los Alamos National Laboratory
31 PUBLICATIONS 10,280 CITATIONS

SEE PROFILE

All content following this page was uploaded by Pieter Swart on 03 February 2017.

The user has requested enhancement of the downloaded file.

Proceedings of the 7th Python in Science Conference (SciPy 2008)

Exploring Network Structure, Dynamics, and Function using NetworkX

Aric A. Hagberg (hagberg@[Link]) – Los Alamos National Laboratory, Los Alamos, New Mexico USA
Daniel A. Schult (dschult@[Link]) – Colgate University, Hamilton, NY USA
Pieter J. Swart (swart@[Link]) – Los Alamos National Laboratory, Los Alamos, New Mexico USA

NetworkX is a Python language package for explo- and algorithms, to rapidly test new hypotheses and
ration and analysis of networks and network algo- models, and to teach the theory of networks.
rithms. The core package provides data structures The structure of a network, or graph, is encoded in the
for representing many types of networks, or graphs, edges (connections, links, ties, arcs, bonds) between
including simple graphs, directed graphs, and graphs nodes (vertices, sites, actors). NetworkX provides ba-
with parallel edges and self-loops. The nodes in Net- sic network data structures for the representation of
workX graphs can be any (hashable) Python object simple graphs, directed graphs, and graphs with self-
and edges can contain arbitrary data; this flexibil- loops and parallel edges. It allows (almost) arbitrary
ity makes NetworkX ideal for representing networks objects as nodes and can associate arbitrary objects to
found in many different scientific fields. edges. This is a powerful advantage; the network struc-
In addition to the basic data structures many graph ture can be integrated with custom objects and data
algorithms are implemented for calculating network structures, complementing any pre-existing code and
properties and structure measures: shortest paths, allowing network analysis in any application setting
betweenness centrality, clustering, and degree dis- without significant software development. Once a net-
tribution and many more. NetworkX can read and work is represented as a NetworkX object, the network
write various graph formats for easy exchange with structure can be analyzed using standard algorithms
existing data, and provides generators for many for finding degree distributions (number of edges inci-
classic graphs and popular graph models, such as dent to each node), clustering coefficients (number of
the Erdos-Renyi, Small World, and Barabasi-Albert triangles each node is part of), shortest paths, spectral
models. measures, and communities.
The ease-of-use and flexibility of the Python pro- We began developing NetworkX in 2002 to analyze
gramming language together with connection to the data and intervention strategies for the epidemic
SciPy tools make NetworkX a powerful tool for sci- spread of disease [EGK02] and to study the structure
entific computations. We discuss some of our recent and dynamics of social, biological, and infrastructure
work studying synchronization of coupled oscillators networks. The initial development was driven by our
to demonstrate how NetworkX enables research in need for rapid development in a collaborative, mul-
the field of computational networks. tidisciplinary environment. Our initial goals were to
build an open-source tool base that could easily grow
in a multidisciplinary environment with users and de-
Introduction velopers that were not necessarily experts in program-
ming or software engineering. We wanted to interface
Recent major advances in the theory of networks com- easily with existing code written in C, C++, and FOR-
bined with the ability to collect large-scale network TRAN, and to painlessly slurp in large nonstandard
data has increased interest in exploring and analyz- data sets (one of our early tests involve studying dy-
ing large networks [New03] [BNFT04]. Applications of namics on a 1.6 million node graph with roughly 10
network analysis techniques are found in many scien- million edges that were changing with time). Python
tific and technological research areas such as gene ex- satisfied all of our requirements but there was no ex-
pression and protein interaction networks, Web Graph isting API or graph implementation that was suitable
structure, Internet traffic analysis, social and collab- for our project. Inspired by a 1998 essay by Python
orative networks including contact networks for the creator Guido van Rossum on a Python graph repre-
spread of diseases. The rapid growth in network theory sentation [vR98] we developed NetworkX as a tool for
has been fueled by its multidisciplinary impact; it pro- the field of computational networks. NetworkX had
vides an important tool in a systems approach to the a public premier at the 2004 SciPy annual conference
understanding of many complex systems, especially in and was released as open source software in April 2005.
the biological sciences. In this paper we describe NetworkX and demonstrate
In these research areas and others, specialized software how it has enabled our recent work studying synchro-
tools are available that solve domain-specific problems nization of coupled oscillators. In the following we give
but there are few open-source general-purpose compu- a brief introduction to NetworkX with basic examples
tational network tools [CN] [OFS08]. NetworkX was that demonstrate some of the classes, data structures,
developed in response to the need for a well-tested and and algorithms. After that we describe in detail a re-
well-documented, open source network analysis tool search project in which NetworkX plays a central role.
that can easily span research application domains. It We conclude with examples of how others have used
has effectively served as a platform to design theory NetworkX in research and education.

11 A. Hagberg, D. Schult, P. Swart: Proc. SciPy 2008, G. Varoquaux, T. Vaught, J. Millman (Eds), pp. 11–16
 Exploring Network Structure, Dynamics, and Function using NetworkX

>>> G = networkx.path_graph(6)
Using NetworkX >>> print [Link]()
[1, 2, 2, 2, 2, 1]
To get started with NetworkX you will need the >>> print [Link](G)
Python language system and the NetworkX package. 0.333333333333
Both are included in several standard operating system >>> print [Link](G)
5
packages [pac]. NetworkX is easy to install and we sug- >>> print networkx.degree_histogram(G)
gest you visit the project website to make sure you have [0, 2, 4]
the latest software version and documentation [HSS]. >>> print networkx.betweenness_centrality(G)
{0: 0.0, 1: 0.4, 2: 0.6, 3: 0.6, 4: 0.4, 5: 0.0}
In some of the following examples we also show how
NetworkX interacts with other optional Python pack-
NetworkX leverages existing Python libraries to ex-
ages such as NumPy, SciPy, and Matplotlib, and we
tend the available functionality with interfaces to well-
suggest you also consider installing those; NetworkX
tested numerical and statistical libraries written in C,
will automatically use them if they are available.
C++ and FORTRAN. NetworkX graphs can easily be
The basic Graph class is used to hold the network in-
converted to NumPy matrices and SciPy sparse matri-
formation. Nodes can be added as follows:
>>> import networkx
ces to leverage the linear algebra, statistics, and other
>>> G = [Link]() tools from those packages. For example, to study the
>>> G.add_node(1) # integer eigenvalue spectrum of the graph Laplacian the Net-
>>> G.add_node(’a’) # string workX laplacian() function returns a NumPy matrix
>>> print [Link]()
[’a’, 1]
representation. The eigenvalues can be then easily
computed using the [Link] sub-package
Nodes can be any hashable object such as strings, num-
>>> L = [Link](G)
bers, files, or functions, >>> print L # a NumPy matrix
>>> import math [[ 1. -1. 0. 0. 0. 0.]
>>> G.add_node([Link]) # cosine function [-1. 2. -1. 0. 0. 0.]
>>> fh = open(’[Link]’,’w’) [ 0. -1. 2. -1. 0. 0.]
>>> G.add_node(fh) # file handle [ 0. 0. -1. 2. -1. 0.]
>>> print [Link]() [ 0. 0. 0. -1. 2. -1.]
[<built-in function cos>, [ 0. 0. 0. 0. -1. 1.]]
<open file ’[Link]’, mode ’w’ at 0x30dc38>] >>> import [Link]
>>> print [Link](L)
Edges, or links, between nodes are represented as tu- [ 3.7321e+00 3.0000e+00 2.0000e+00
ples of nodes. They can be added simply 1.0000e+00 -4.0235e-17 2.6795e-01]
>>> G.add_edge(1,’a’)
>>> G.add_edge(’b’,[Link]) For visualizing networks, NetworkX includes an inter-
>>> print [Link]() face to Python’s Matplotlib plotting package along
[(’b’, <built-in function cos>), (’a’, 1)]
with simple node positioning algorithms based on
When adding an edge, if the nodes do not already exist force-directed, spectral, and geometric methods.
they are automatically added to the graph. >>> G = networkx.circular_ladder_graph(12)
Edge data d can be associated with the edge by adding >>> [Link](G)
an edge as a 3-tuple (u, v, d). The default value for
d is the integer 1 but any valid Python object is al-
lowed. Using numbers as edge data allows a natural
way to express weighted networks. In the following ex- 8
7
19
ample we use Dijkstra’s algorithm to find the shortest 20
6 18
weighted path through a simple network of four edges 9
21
with weights. 5 17
>>> G = [Link]()
10
>>> e = [(’a’,’b’,0.3),(’b’,’c’,0.9), 22
(’a’,’c’,0.5),(’c’,’d’,1.2)] 4
16
>>> G.add_edges_from(e)
>>> print networkx.dijsktra_path(G,’a’,’d’) 11 23
[’a’, ’c’, ’d’] 3
15

NetworkX includes functions for computing network 0 12 2

1 14
statistics and metrics such as diameter, degree distri- 13
bution, number of connected components, clustering
coefficient, and betweenness centrality. In addition,
Figure 1: Matplotlib plot of a 24 node circular ladder
generators for many classic graphs and random graph
graph
models are provided. These graphs are useful for mod-
eling and analysis of network data and also for testing Connections to other graph drawing packages are
new algorithms or network metrics. The following ex- available either directly, for example using PyGraphviz
ample shows how to generate and compute some statis- with the Graphviz drawing system, or by writing the
tics for a network consisting of a path with 6 nodes: data to one of the standard file interchange formats.

[Link] 12
Proceedings of the 7th Python in Science Conference (SciPy 2008)

Inside NetworkX The “dictionary of dictionaries” data structure can

also be used to store graphs with parallel edges (multi-
NetworkX provides classes to represent directed and graphs) where the data for G[u][v] consists of a list of
undirected graphs, with optional weights and self edge objects with one element for each edge connecting
loops, and a special representation for multigraphs nodes u and v. NetworkX provides the M ultiGraph
which allows multiple edges between pairs of nodes. and M ultiDiGraph classes to implement a graph
Basic graph manipulations such as adding or removing structure with parallel edges.
nodes or edges are provided as class methods. Some There are no custom node objects or edge objects by
standard graph reporting such as listing nodes or edges default in NetworkX. Edges are represented as a two-
or computing node degree are also provided as class tuple or three-tuple of nodes (u, v), or (u, v, d) with d
methods, but more complex statistics and algorithms as edge data. The edge data d is the value of a dictio-
such as clustering, shortest paths, and visualization are nary and can thus be any Python object. Nodes are
provided as package functions. keys in a dictionary and therefore have the same re-
The standard data structures for representating graphs strictions as Python dictionaries: nodes must be hash-
are edge lists, adjacency matrices, and adjacency lists. able objects. Users can define custom node objects as
The choice of data structure affects both the storage long as they meet that single requirement. Users can
and computational time for graph algorithms [Sed02]. define arbitrary custom edge objects.
For large sparse networks, in which only a small frac-
tion of the possible edges are present, adjacency lists
are preferred since the storage requirement is the NetworkX in action: synchronization
smallest (proportional to m + n for n nodes and m
edges). Many real-world graphs and network models We are using NetworkX in our scientific research for
are sparse so NetworkX uses adjacency lists. the spectral analysis of network dynamics and to
Python built-in dictionaries provide a natural data study synchronization in networks of coupled oscilla-
structure to search and update adjacency lists [vR98]; tors [HS08]. Synchronization of oscillators is a fun-
NetworkX uses a “dictionary of dictionaries” (“hash of damental problem of dynamical systems with applica-
hashes”) as the basic graph data structure. Each node tions to heart and muscle tissue, ecosystem dynam-
n is a key in the [Link] dictionary with value consist- ics, secure communication with chaos, neural coordi-
ing of a dictionary with neighbors as keys to edge data nation, memory and epilepsy. The specific question
values with default 1. For example, the representation we are investigating is how to best rewire a network
of an undirected graph with edges A − B and B − C is in order to enhance or decrease the network’s ability
>>> G = [Link]() to synchronize. We are particularly interested in the
>>> G.add_edge(’A’,’B’) setting where the number of edges in a network stays
>>> G.add_edge(’B’,’C’) the same while modifying the network by moving edges
>>> print [Link]
{’A’: {’B’: 1}, (defined as removing an edge between one pair of nodes
’B’: {’A’: 1, ’C’: 1}, and adding an edge between another). What are the
’C’: {’B’: 1}} network properties that seriously diminish or enhance
The outer node dictionary allows the natural expres- synchronization and how hard is it to calculate the
sions n in G to test if the graph G contains node n required rewirings?
and for n in G to loop over all nodes [Epp08]. The Our model follows the framework presented by [FJC00]
“dictionary of dictionary” data structure allows find- where identical oscillators are coupled in a fairly gen-
ing and removing edges with two dictionary look-ups eral manner and said to be synchronized if their states
instead of a dictionary look-up and a search when using are identical at all times. Small perturbations from
a “dictionary of lists”. The same fast look-up could be synchronization are examined to determine if they
achieved using sets of neighbors, but neighbor dictio- grow or decay. If the perturbations decay the system
naries allow arbitrary data to be attached to an edge; is said to be synchronizable. In solving for the growth
the phrase G[u][v] returns the edge object associated rate of perturbations, it becomes apparent that the dy-
with the edge between nodes u and v. A common use is namical characteristics of the oscillator and coupling
to represent a weighted graph by storing a real number separate from the structural properties of the network
value on the edge. over which they are coupled. This surprising and pow-
For undirected graphs both representations (e.g A − B erful separation implies that coupled oscillators syn-
and B − A) are stored. Storing both representations chronize more effectively on certain networks indepen-
allows a single dictionary look-up to test if edge u − v dent of the type of oscillator or form of coupling.
or v −u exists. For directed graphs only one of the rep- The effect of the network structure on synchroniza-
resentations for the edge u → v needs to be stored but tion is determined via the eigenvalues of the network
we keep track of both the forward edge and the back- Laplacian matrix L = D − A where A is the adjacency
ward edge in distinct “successor” and “predecessor” matrix representation of the network and D is a diag-
dictionary of dictionaries. This extra storage simpli- onal matrix of node degrees. For a network with N
fies some algorithms, such as finding shortest paths, oscillators, there are N eigenvalues which are all real
when traversing backwards through a graph is useful. and non-negative. The lowest λ0 = 0 is always zero

13 [Link]
 Exploring Network Structure, Dynamics, and Function using NetworkX

and we index the others λi in increasing order. For found that while algorithms which use degree infor-
a connected network it is true that λi > 0 for i > 0. mation are much better than random edge choice, it is
The growth rate of perturbations is determined by a most effective to use information from the eigenvectors
Master Stability Function (MSF) which takes eigen- of the network rather than degree.
values as inputs and returns the growth rate for that Of course, the specific edge to choose for rewiring de-
eigenmode. The observed growth rate of the system is pends on the network you start with. NetworkX is
the maximum of the MSF evaluations for all eigenval- helpful for exploring edge choices over many different
ues. The separation comes about because the MSF is networks since a variety of networks can be easily cre-
determined by the oscillator and coupling but not by ated. Real data sets that provide network configura-
the network structure which only impacts the inputs to tions can be read into Python using simple edge lists as
the MSF. So long as all eigenvalues lie in an interval well as many other formats. In addition, a large collec-
where the MSF is negative, the network is synchro- tion of network model generators are included so that,
nizable. Since most oscillator/couplings lead to MSFs for example, random networks with a given degree dis-
where a single interval yields negative growth rates, tribution can be easily constructed. These generator
networks for which the eigenvalues lie in a wide band algorithms are taken from the literature on random
are resistant to synchronization. An effective measure network models. The Numpy package makes it easy
of the resistance to synchronization is the ratio of the to collect statistics over many networks and plot the
largest to smallest positive eigenvalue of the network, results via Matplotlib as shown in Fig. 2.
r = λN −1 /λ1 . The goal of enhancing synchronization
In addition to computation, visualization of the net-
is then to move edges that optimally decrease r.
works is helpful. NetworkX provide hooks into Mat-
plotlib or Graphviz (2D) and VTK or UbiGraph (3D)
Barabási − Albert high-to-low and thereby allow network visualization with node and
250 degree edge traits that correlate well with r as shown in Fig.
eigenvector
r 150 3.

50

900 Power-law configuration model

0
700 4
r
500
2
300
10.6 Watts − Strogatz
10.4 1
r 8
10.2 6 5
10.0

G(n, p) 3
2.6

r 2.4
2.2 9 7

0 5 10 15 20
number of edges moved
Figure 3: A sample graph showing eigenvector ele-
Figure 2: The change in resistance to synchrony r ments associated with each node as their size. The
as edges are moved in four example random net- dashed edge shows the largest difference between two
work models. An algorithm using Laplacian eigen- nodes. Moving the edge between nodes 3 and 8 is
vectors compares favorably to those using node de- more effective at enhancing synchronization than the
gree. Eigenvectors are found via NetworkX calls to edge between the highest degree nodes 3 and 6.
SciPy and NumPy matrix eigenvalue solvers.
Python makes it easy to implement such algorithms
quickly and test how well they work. Functions that NetworkX in the world
take [Link]() objects as input and return
an edge constitute an algorithm for edge addition or The core of NetworkX is written completely in Python;
removal. Combining these gives algorithms for mov- this makes the code easy to read, write, and document.
ing edges. We implemented several algorithms using Using Python lowers the barrier for students and non-
either the degree of each node or the eigenvectors of experts to learn, use, and develop network algorithms.
the network Laplacian and compared their effective- The low barrier has encouraged contributions from the
ness to each other and to random edge choice. We open-source community and in university educational

[Link] 14
Proceedings of the 7th Python in Science Conference (SciPy 2008)

settings [MS07]. The SAGE open source mathemat- [CN] Gábor Csárdi and Tamás Nepusz. The igraph
ics system [Ste08] has incorporated NetworkX and ex- library. [Link]
tended it with even more graph-theoretical algorithms igraph/.
and functions. [EGK02] Stephen Eubank, Hasan Guclu, V. S. Anil Ku-
NetworkX takes advantage of many existing applica- mar, Madhav V. Marathe, Aravind Srinivasan,
Zoltan Toroczkai, and Nan Wang. Modelling
tions in Python and other languages and brings then
disease outbreaks in realistic urban social net-
together to build a powerful analysis platform. For the works. Nature, page 180, 2002.
computational analysis of networks using techniques [EGK04] J. Ellson, E.R. Gansner, E. Koutsofios, S.C.
from algebraic graph theory, NetworkX uses adja- North, and G. Woodhull. Graphviz and dy-
cency matrix representations of networks with NumPy nagraph – static and dynamic graph draw-
dense matrices and SciPy sparse matrices [Oli06]. The ing tools. In M. Junger and P. Mutzel, edi-
NumPy and SciPy packages also provide linear sys- tors, Graph Drawing Software, pages 127–148.
tem and eigenvalue solvers, statistical tools, and many Springer-Verlag, 2004.
other useful functions. For visualizing and drawing, [Epp08] David Eppstein. PADS, a library of Python
NetworkX contains interfaces to the Graphviz network Algorithms and Data Structures, 2008. http:
layout tools [EGK04], Matplotlib (2d) [Hun07] and //[Link]/eppstein/PADS/.
[FJC00] Kenneth S. Fink, Gregg Johnson, Tom Car-
UbiGraph (3d) [Vel07]. A variety of standard net-
roll, Doug Mar, and Lou Pecora. Three cou-
work Models are included for realization and creation pled oscillators as a universal probe of synchro-
of network models and NetworkX can import graph nization stability in coupled oscillator arrays.
data from many external formats. Phys. Rev. E, 61(5):5080 – 90, MAY 2000.
[HS08] Aric Hagberg and Daniel A. Schult. Rewiring
Conclusion networks for synchronization. To appear in
Chaos, 2008.
Python provides many tools to ease exploration of sci- [HSS] Aric A. Hagberg, Daniel A. Schult, and Pieter
entific problems. One of its strengths is the ability to J. Swart. NetworkX. [Link]
[Link].
connect existing code and libraries in a natural way
[Hun07] John D. Hunter. Matplotlib: A 2d graphics
that eases integration of many tools. Here we have environment. Computing in Science and Engi-
shown how NetworkX, in conjunction with the Python neering, 9(3):90–95, May/June 2007.
packages SciPy, NumPy, Matplotlib and connection to [MS07] Christopher R. Myers and James P. Sethna.
other tools written in FORTRAN and C, provides a Python for education: Computational meth-
powerful tool for computational network analysis. We ods for nonlinear systems. Computing in Sci-
hope to have enticed you to take a look at NetworkX ence and Engineering, 9(3):75–79, 2007.
the next time you need a way to keep track of connec- [New03] M. E. J. Newman. The structure and function
tions between objects. of complex networks. SIAM Review, 45(2):167
– 256, June 2003.
[OFS08] Joshua O’Madadhain, Danyel Fisher, Padhraic
Acknowledgements Smyth, Scott White, and Yan-Biao Boey.
Analysis and visualization of network data
As an open source project this work has significantly using JUNG. [Link]
benefited from its own international social network of doc/JUNG_journal.pdf, 2008.
users. We thank the user community for feedback, [Oli06] Travis E. Oliphant. Guide to NumPy. Provo,
bug reports, software contributions and encourage- UT, March 2006.
ment. This work was carried out under the auspices of [pac] Available in Debian Linux and Fink (OSX)
the National Nuclear Security Administration of the package systems.
U.S. Department of Energy at Los Alamos National [Sed02] Robert Sedgewick. Algorithms in C: Part 5:
Graph algorithms. Addison- Wesley, Reading,
Laboratory under Contract No. DE-AC52-06NA25396
MA, USA, third edition, 2002.
and partially supported by the Laboratory Directed
[Ste08] William Stein. Sage: Open Source Mathe-
Research and Development Program. matical Software (Version 2.10.2). The Sage
Group, 2008. [Link]
References [Vel07] Todd L. Veldhuizen. Dynamic multilevel graph
visualization. Eprint arXiv:[Link]/07121549,
[BNFT04] Eli Ben-Naim, Hans Frauenfelder, and Zoltan Dec 2007.
Torozckai, editors. Complex Networks, vol- [vR98] Guido van Rossum. Python Patterns - Imple-
ume 650 of Lecture Notes in Physics. Springer, menting Graphs, 1998. [Link]
2004. org/doc/essays/graphs/

View publicati
15 [Link]