Installation and Basic Usage Constructing Graphs Analyzing Graphs Plotting (Matplotlib)
NetworkX Tutorial
Jacob Bank (adapted from slides by Evan Rosen)
September 28, 2012
Jacob Bank (adapted from slides by Evan Rosen)
NetworkX Tutorial
Installation and Basic Usage Constructing Graphs Analyzing Graphs Plotting (Matplotlib)
1 Installation and Basic Usage
2 Constructing Graphs
3 Analyzing Graphs
4 Plotting (Matplotlib)
Jacob Bank (adapted from slides by Evan Rosen)
NetworkX Tutorial
Installation and Basic Usage Constructing Graphs Analyzing Graphs Plotting (Matplotlib)
Local Installation
install manually from
http://pypi.python.org/pypi/networkx
or use built-in python package manager, easy install
$ easy install networkx
or use macports
$ sudo port install py27-networkx
use pip (replacement for easy install)
$ sudo pip install networkx
or use debian package manager
$ sudo apt-get install python-networkx
Jacob Bank (adapted from slides by Evan Rosen)
NetworkX Tutorial
Installation and Basic Usage Constructing Graphs Analyzing Graphs Plotting (Matplotlib)
Using Corn
networkx is already installed on the corn cluster
Only works for python version 2.6, 2.7
However default mapping of command ’python’ is to version
2.4
Just type ‘python2.6’ instead or make an alias in your shell
configuration
Jacob Bank (adapted from slides by Evan Rosen)
NetworkX Tutorial
Installation and Basic Usage Constructing Graphs Analyzing Graphs Plotting (Matplotlib)
Basic Usage
>>> import networkx as nx
>>> g = nx . Graph ()
>>> g . add_node ( " spam " )
>>> g . add_edge (1 ,2)
>>> print ( g . nodes () )
[1 , 2 , ’ spam ’]
>>> print ( g . edges () )
[(1 , 2) ]
Jacob Bank (adapted from slides by Evan Rosen)
NetworkX Tutorial
Installation and Basic Usage Constructing Graphs Analyzing Graphs Plotting (Matplotlib)
Graph Types
Graph : Undirected simple (allows self loops)
DiGraph : Directed simple (allows self loops)
MultiGraph : Undirected with parallel edges
MultiDiGraph : Directed with parallel edges
can convert to undirected: g.to undirected()
can convert to directed: g.to directed()
To construct, use standard python syntax:
>>> g = nx . Graph ()
>>> d = nx . DiGraph ()
>>> m = nx . MultiGraph ()
>>> h = nx . MultiDiGraph ()
Jacob Bank (adapted from slides by Evan Rosen)
NetworkX Tutorial
Installation and Basic Usage Constructing Graphs Analyzing Graphs Plotting (Matplotlib)
Adding Nodes
add nodes from() takes any iterable collection and any
object
>>> g = nx . Graph ()
>>> g . add_node ( ’a ’)
>>> g . add_nodes_from ( [ ‘ b ’ ,‘c ’ ,‘d ’ ])
>>> g . add_nodes_from ( ’ xyz ’)
>>> h = nx . path_graph (5)
>>> g . add_nodes_from ( h )
>>> g . nodes ()
[0 ,1 , ‘ c ’ ,‘b ’ ,4 , ‘ d ’ ,2 ,3 ,5 , ‘ x ’ ,‘y ’ ,‘z ’]
Jacob Bank (adapted from slides by Evan Rosen)
NetworkX Tutorial
Installation and Basic Usage Constructing Graphs Analyzing Graphs Plotting (Matplotlib)
Adding Edges
Adding an edge between nodes that don’t exist will
automatically add those nodes
add nodes from() takes any iterable collection and any type
(anything that has a iter () method)
>>> g = nx . Graph ( [( ‘ a ’ ,‘b ’) ,( ‘ b ’ ,‘c ’) ,( ‘ c ’
,‘a ’) ] )
>>> g . add_edge ( ’a ’ , ’d ’)
>>> g . add_edges_from ([( ‘ d ’ , ‘c ’) , ( ‘ d ’ , ‘b ’)
])
Jacob Bank (adapted from slides by Evan Rosen)
NetworkX Tutorial
Installation and Basic Usage Constructing Graphs Analyzing Graphs Plotting (Matplotlib)
Node Attributes
Can add node attributes as optional arguments along with
most add methods
>>> g = nx . Graph ()
>>> g . add_node (1 , name = ‘ Obrian ’)
>>> g . add_nodes_from ([2] , name = ‘ Quintana ’ ])
>>> g [1][ ‘ name ’]
‘ Obrian ’
Jacob Bank (adapted from slides by Evan Rosen)
NetworkX Tutorial
Installation and Basic Usage Constructing Graphs Analyzing Graphs Plotting (Matplotlib)
Edge Attributes
Can add edge attributes as optional arguments along with
most add methods
>>> g . add_edge (1 , 2 , w =4.7 )
>>> g . add_edges_from ([(3 ,4) ,(4 ,5) ] , w =3.0)
>>> g . add_edges_from ([(1 ,2 ,{ ‘ val ’ :2.0}) ])
# adds third value in tuple as ‘ weight ’ attr
>>> g . ad d _w ei g h t e d _ e d g e s _ f r o m ([(6 ,7 ,3.0) ])
>>> g . get_edge_data (3 ,4)
{ ‘ w ’ : 3.0}
>>> g . add_edge (5 ,6)
>>> g [5][6]
{}
Jacob Bank (adapted from slides by Evan Rosen)
NetworkX Tutorial
Installation and Basic Usage Constructing Graphs Analyzing Graphs Plotting (Matplotlib)
HW0 - Loading the Wikipedia Graph
We want to load in the Wikipedia graph as a directed graph.
>>> file = ‘ wiki . txt ’
>>> wiki = nx . read_adjlist ( file , delimiter
= ‘\ t ’ , create_using = nx . DiGraph () )
Jacob Bank (adapted from slides by Evan Rosen)
NetworkX Tutorial
Installation and Basic Usage Constructing Graphs Analyzing Graphs Plotting (Matplotlib)
Importing Other Graph Formats
GML
Pickle
GraphML
YAML
Pajek
GEXF
LEDA
SparseGraph6
GIS Shapefile
Jacob Bank (adapted from slides by Evan Rosen)
NetworkX Tutorial
Installation and Basic Usage Constructing Graphs Analyzing Graphs Plotting (Matplotlib)
Simple Graph Generators
located in networkx.generators.classic module
Complete Graph
nx . complete_graph (5)
Chain
nx . path_graph (5)
Bipartite
nx . c om p l e te _ b i p a r t i t e _ g r a p h ( n1 , n2 )
Arbitrary Dimensional Lattice (nodes are tuples of ints)
nx . grid_graph ([10 ,10 ,10 ,10]) # 4D , 100^4
nodes
Jacob Bank (adapted from slides by Evan Rosen)
NetworkX Tutorial
Installation and Basic Usage Constructing Graphs Analyzing Graphs Plotting (Matplotlib)
Random Graph Generators
located in module networkx.generators.random graphs
Preferential Attachment
nx . ba raba si_ a l b e r t _ g r a p h (n , m )
Gn,p
nx . gnp_random_graph (n , p )
nx . gnm_random_graph (n , m )
nx . watts_str o g a t z _ g r a p h (n , k , p }
Jacob Bank (adapted from slides by Evan Rosen)
NetworkX Tutorial
Installation and Basic Usage Constructing Graphs Analyzing Graphs Plotting (Matplotlib)
HW0 - Simple Properties
Number of nodes :
>>> len ( wiki )
Number of Self-loops
>>> wiki . num b er _ o f_ s e lf l o o ps ()
Number of Directed Edges
>>> wiki . size ()
Number of Undirected Edges
>>> wiki . to_undirected () . size ()
Jacob Bank (adapted from slides by Evan Rosen)
NetworkX Tutorial
Installation and Basic Usage Constructing Graphs Analyzing Graphs Plotting (Matplotlib)
Degrees
>>> g . degree (0)
1
>>> g . degree ([0 ,1])
{0: 1 , 1: 2}
>>> g . degree ()
{1: 1 , 2: 2 , 3: 2 , 4: 1}
>>> g . degree () . values () # useful for degree
dist
[1 , 2 , 2 , 1]
Jacob Bank (adapted from slides by Evan Rosen)
NetworkX Tutorial
Installation and Basic Usage Constructing Graphs Analyzing Graphs Plotting (Matplotlib)
HW0 - Simple Properties Continued
Number of Reciprocated Edges :
>>> wiki . to_undirected ( True ) . size ()
Number of Nodes with OutDegree 0
>>> reduce ( lambda c , n : c + 1 if wiki .
out_degree ( n ) < 1 else c , wiki . nodes ()
, 0)
Number of Nodes with InDegree < 10
>>> reduce ( lambda c , n : c + 1 if wiki .
in_degree ( n ) < 10 else c , wiki . nodes ()
, 0)
Jacob Bank (adapted from slides by Evan Rosen)
NetworkX Tutorial
Installation and Basic Usage Constructing Graphs Analyzing Graphs Plotting (Matplotlib)
Neighbors
Quickly find all of the neighbors of a node.
>>> g = nx . Graph ()
>>> g . add_edge (1 ,2)
>>> g . add_edge (2 ,3)
>>> g . neighbors (2)
[1 , 3]
Jacob Bank (adapted from slides by Evan Rosen)
NetworkX Tutorial
Installation and Basic Usage Constructing Graphs Analyzing Graphs Plotting (Matplotlib)
Algorithms Package (networkx.algorithms)
bipartite flow (package)
block isolates
boundary isomorphism (package)
centrality (package) link analysis (package)
clique matching
cluster mixing
components (package) mst
core operators
cycles shortest paths (package)
dag smetric
distance measures
Jacob Bank (adapted from slides by Evan Rosen)
NetworkX Tutorial
Installation and Basic Usage Constructing Graphs Analyzing Graphs Plotting (Matplotlib)
Use the Python Help Viewer
>>> import networkx as nx
>>> help ( nx . algorithms )
pops up an instance of ‘less’ (the pager utility)
Jacob Bank (adapted from slides by Evan Rosen)
NetworkX Tutorial
Installation and Basic Usage Constructing Graphs Analyzing Graphs Plotting (Matplotlib)
A Few Useful Functions
As subgraphs
nx . c o n n e c t e d _ c o m p o n e n t _ s u b g r a p h s ( G )
Operations on Graph
nx . union (G , H ) , intersection (G , H ) ,
complement ( G )
k-cores
nx . find_cores ( G )
Jacob Bank (adapted from slides by Evan Rosen)
NetworkX Tutorial
Installation and Basic Usage Constructing Graphs Analyzing Graphs Plotting (Matplotlib)
A Few More
shortest path
nx . shortest_path (G ,s , t )
clustering
nx . average_c lu st er in g ( G )
diameter
nx . diameter ( G )
Jacob Bank (adapted from slides by Evan Rosen)
NetworkX Tutorial
Installation and Basic Usage Constructing Graphs Analyzing Graphs Plotting (Matplotlib)
Matplotlib
A python package which emulates matlab functionality
Well documented at
http://matplotlib.sourceforge.net/contents.html
Interfaces nicely with NetworkX
Depends on Numpy which provides multidimensional array
support:
http://numpy.scipy.org/
We only really need it for plotting
Jacob Bank (adapted from slides by Evan Rosen)
NetworkX Tutorial
Installation and Basic Usage Constructing Graphs Analyzing Graphs Plotting (Matplotlib)
Setting up Matplotlib
Need to specify a backend, which is the program which is
responsible for either displaying or writing the plots to file
For more info, see: http://matplotlib.sourceforge.net/
faq/installing_faq.html#what-is-a-backend
On corn, you simply add the following magic incantation to
the top of your python scripts:
import matplotlib
matplotlib . use ( ‘ Agg ’)
import matplotlib . pyplot as plt
Jacob Bank (adapted from slides by Evan Rosen)
NetworkX Tutorial
Installation and Basic Usage Constructing Graphs Analyzing Graphs Plotting (Matplotlib)
Basic Graph Drawing
def draw_graph () :
G = nx . Graph ()
G . add_edges_from ([(1 ,2) , (2 ,3) , (1 ,3) ,
(1 ,4) ])
nx . draw ( G )
plt . savefig ( " simple_graph . png " )
consult package nx.drawing for more options
Jacob Bank (adapted from slides by Evan Rosen)
NetworkX Tutorial
Installation and Basic Usage Constructing Graphs Analyzing Graphs Plotting (Matplotlib)
Data Plotting - Degree Distribution
First, we find the degree distribution as follows.
def p l ot _ d e gr e e _ d i s t r i b u t i o n () :
degs = {}
for n in wiki . nodes () :
deg = wiki . degree ( n )
if deg not in degs :
degs [ deg ] = 0
degs [ deg ] += 1
items = sorted ( degs . items () )
Jacob Bank (adapted from slides by Evan Rosen)
NetworkX Tutorial
Installation and Basic Usage Constructing Graphs Analyzing Graphs Plotting (Matplotlib)
Data Plotting - Degree Distribution continued
Then we plot it.
items = sorted ( degs . items () )
fig = plt . figure ()
ax = fig . add_subplot (111)
ax . plot ([ k for (k , v ) in items ] , [ v for (k ,
v ) in items ])
ax . set_xscale ( ’ log ’)
ax . set_yscale ( ’ log ’)
plt . title ( " Wikipedia Degree Distribution " )
fig . savefig ( " d e gr e e _d i s tr i b ut i o n . png " )
Jacob Bank (adapted from slides by Evan Rosen)
NetworkX Tutorial
Installation and Basic Usage Constructing Graphs Analyzing Graphs Plotting (Matplotlib)
Data Plotting - Degree Distribution continued
And voila!
Jacob Bank (adapted from slides by Evan Rosen)
NetworkX Tutorial
Installation and Basic Usage Constructing Graphs Analyzing Graphs Plotting (Matplotlib)
Resources
NetworkX Docs
http://networkx.lanl.gov/tutorial/index.html
NetworkX Tutorial
http://networkx.lanl.gov/contents.html
Matplotlib Docs
http://matplotlib.sourceforge.net/contents.html
Matplotlib Tutorial
http://matplotlib.sourceforge.net/users/pyplot_
tutorial.html
Numpy Docs
http://numpy.scipy.org/
MacPorts
http://macports.org
Jacob Bank (adapted from slides by Evan Rosen)
NetworkX Tutorial
