"""
Laplacian, adjacency matrix, and spectrum of graphs.
"""
__author__ = "\n".join(['Aric Hagberg (hagberg@lanl.gov)',
'Pieter Swart (swart@lanl.gov)',
'Dan Schult(dschult@colgate.edu)'])
# Copyright (C) 2004-2010 by
# Aric Hagberg <hagberg@lanl.gov>
# Dan Schult <dschult@colgate.edu>
# Pieter Swart <swart@lanl.gov>
# All rights reserved.
# BSD license.
import networkx as nx
__all__ = ['adj_matrix', 'laplacian', 'generalized_laplacian',
'laplacian_spectrum', 'adjacency_spectrum','normalized_laplacian']
def adj_matrix(G,nodelist=None):
"""Return adjacency matrix of G.
Parameters
----------
G : graph
A NetworkX graph
nodelist : list, optional
The rows and columns are ordered according to the nodes in nodelist.
If nodelist is None, then the ordering is produced by G.nodes().
Returns
-------
A : numpy matrix
Adjacency matrix representation of G.
Notes
-----
If you want a pure Python adjacency matrix representation try
networkx.convert.to_dict_of_dicts which will return a
dictionary-of-dictionaries format that can be addressed as a
sparse matrix.
See Also
--------
to_numpy_matrix
to_dict_of_dicts
"""
return nx.to_numpy_matrix(G,nodelist=nodelist)
def laplacian(G,nodelist=None):
"""Return the Laplacian matrix of G.
The graph Laplacian is the matrix L = D - A, where
A is the adjacency matrix and D is the diagonal matrix of node degrees.
Parameters
----------
G : graph
A NetworkX graph
nodelist : list, optional
The rows and columns are ordered according to the nodes in nodelist.
If nodelist is None, then the ordering is produced by G.nodes().
Returns
-------
L : NumPy matrix
Laplacian of G.
See Also
--------
normalized_laplacian
"""
try:
import numpy as np
except ImportError:
raise ImportError, \
"laplacian() requires numpy: http://scipy.org/ "
# this isn't the most efficient way to do this...
n=G.order()
I=np.identity(n)
A=np.asarray(nx.to_numpy_matrix(G,nodelist=nodelist))
D=I*np.sum(A,axis=1)
L=D-A
return L
def normalized_laplacian(G,nodelist=None):
"""Return the normalized Laplacian matrix of G.
The normalized graph Laplacian is the matrix NL=D^(-1/2) L D^(-1/2)
L is the graph Laplacian and D is the diagonal matrix of node degrees.
Parameters
----------
G : graph
A NetworkX graph
nodelist : list, optional
The rows and columns are ordered according to the nodes in nodelist.
If nodelist is None, then the ordering is produced by G.nodes().
Returns
-------
L : NumPy matrix
Normalized Laplacian of G.
See Also
--------
laplacian
References
----------
.. [1] Fan Chung-Graham, Spectral Graph Theory,
CBMS Regional Conference Series in Mathematics, Number 92, 1997.
"""
# FIXME: this isn't the most efficient way to do this...
try:
import numpy as np
except ImportError:
raise ImportError, \
"normalized_laplacian() requires numpy: http://scipy.org/ "
A=np.asarray(nx.to_numpy_matrix(G,nodelist=nodelist))
d=np.sum(A,axis=1)
I=np.identity(len(d))
L=I*d-A
osd=np.zeros(len(d))
for i in range(len(d)):
if d[i]>0: osd[i]=np.sqrt(1.0/d[i])
T=I*osd
L=np.dot(T,np.dot(L,T))
return L
def laplacian_spectrum(G):
"""Return eigenvalues of the Laplacian of G
Parameters
----------
G : graph
A NetworkX graph
Returns
-------
evals : NumPy array
Eigenvalues
See Also
--------
laplacian
"""
try:
import numpy as np
except ImportError:
raise ImportError, \
"laplacian_spectrum() requires NumPy: http://scipy.org/ "
return np.linalg.eigvals(laplacian(G))
def adjacency_spectrum(G):
"""Return eigenvalues of the adjacency matrix of G.
Parameters
----------
G : graph
A NetworkX graph
Returns
-------
evals : NumPy array
Eigenvalues
See Also
--------
adj_matrix
"""
try:
import numpy as np
except ImportError:
raise ImportError, \
"adjacency_spectrum() requires NumPy: http://scipy.org/ "
return np.linalg.eigvals(adj_matrix(G))
combinatorial_laplacian=laplacian
generalized_laplacian=normalized_laplacian
|