Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

# Source code for networkx.linalg.laplacianmatrix

"""Laplacian matrix of graphs.
"""
#    Copyright (C) 2004-2019 by
#    Aric Hagberg <hagberg@lanl.gov>
#    Dan Schult <dschult@colgate.edu>
#    Pieter Swart <swart@lanl.gov>
import networkx as nx
from networkx.utils import not_implemented_for
__author__ = "\n".join(['Aric Hagberg <aric.hagberg@gmail.com>',
'Pieter Swart (swart@lanl.gov)',
'Dan Schult (dschult@colgate.edu)',
'Alejandro Weinstein <alejandro.weinstein@gmail.com>'])
__all__ = ['laplacian_matrix',
'normalized_laplacian_matrix',
'directed_laplacian_matrix',
'directed_combinatorial_laplacian_matrix']

[docs]@not_implemented_for('directed')
def laplacian_matrix(G, nodelist=None, weight='weight'):
"""Returns 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().

weight : string or None, optional (default='weight')
The edge data key used to compute each value in the matrix.
If None, then each edge has weight 1.

Returns
-------
L : SciPy sparse matrix
The Laplacian matrix of G.

Notes
-----
For MultiGraph/MultiDiGraph, the edges weights are summed.

--------
to_numpy_matrix
normalized_laplacian_matrix
"""
import scipy.sparse
if nodelist is None:
nodelist = list(G)
A = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, weight=weight,
format='csr')
n, m = A.shape
diags = A.sum(axis=1)
D = scipy.sparse.spdiags(diags.flatten(), [0], m, n, format='csr')
return D - A

[docs]@not_implemented_for('directed')
def normalized_laplacian_matrix(G, nodelist=None, weight='weight'):
r"""Returns the normalized Laplacian matrix of G.

The normalized graph Laplacian is the matrix

.. math::

N = D^{-1/2} L D^{-1/2}

where 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().

weight : string or None, optional (default='weight')
The edge data key used to compute each value in the matrix.
If None, then each edge has weight 1.

Returns
-------
N : NumPy matrix
The normalized Laplacian matrix of G.

Notes
-----
For MultiGraph/MultiDiGraph, the edges weights are summed.
See to_numpy_matrix for other options.

If the Graph contains selfloops, D is defined as diag(sum(A,1)), where A is
the adjacency matrix [2]_.

--------
laplacian_matrix

References
----------
.. [1] Fan Chung-Graham, Spectral Graph Theory,
CBMS Regional Conference Series in Mathematics, Number 92, 1997.
.. [2] Steve Butler, Interlacing For Weighted Graphs Using The Normalized
Laplacian, Electronic Journal of Linear Algebra, Volume 16, pp. 90-98,
March 2007.
"""
import scipy
import scipy.sparse
if nodelist is None:
nodelist = list(G)
A = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, weight=weight,
format='csr')
n, m = A.shape
diags = A.sum(axis=1).flatten()
D = scipy.sparse.spdiags(diags, [0], m, n, format='csr')
L = D - A
with scipy.errstate(divide='ignore'):
diags_sqrt = 1.0 / scipy.sqrt(diags)
diags_sqrt[scipy.isinf(diags_sqrt)] = 0
DH = scipy.sparse.spdiags(diags_sqrt, [0], m, n, format='csr')
return DH.dot(L.dot(DH))

###############################################################################
# Code based on
# https://bitbucket.org/bedwards/networkx-community/src/370bd69fc02f/networkx/algorithms/community/

[docs]@not_implemented_for('undirected')
@not_implemented_for('multigraph')
def directed_laplacian_matrix(G, nodelist=None, weight='weight',
walk_type=None, alpha=0.95):
r"""Returns the directed Laplacian matrix of G.

The graph directed Laplacian is the matrix

.. math::

L = I - (\Phi^{1/2} P \Phi^{-1/2} + \Phi^{-1/2} P^T \Phi^{1/2} ) / 2

where I is the identity matrix, P is the transition matrix of the
graph, and \Phi a matrix with the Perron vector of P in the diagonal and
zeros elsewhere.

Depending on the value of walk_type, P can be the transition matrix
induced by a random walk, a lazy random walk, or a random walk with
teleportation (PageRank).

Parameters
----------
G : DiGraph
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().

weight : string or None, optional (default='weight')
The edge data key used to compute each value in the matrix.
If None, then each edge has weight 1.

walk_type : string or None, optional (default=None)
If None, P is selected depending on the properties of the
graph. Otherwise is one of 'random', 'lazy', or 'pagerank'

alpha : real
(1 - alpha) is the teleportation probability used with pagerank

Returns
-------
L : NumPy array
Normalized Laplacian of G.

Notes
-----
Only implemented for DiGraphs

--------
laplacian_matrix

References
----------
.. [1] Fan Chung (2005).
Laplacians and the Cheeger inequality for directed graphs.
Annals of Combinatorics, 9(1), 2005
"""
import scipy as sp
from scipy.sparse import spdiags, linalg

P = _transition_matrix(G, nodelist=nodelist, weight=weight,
walk_type=walk_type, alpha=alpha)

n, m = P.shape

evals, evecs = linalg.eigs(P.T, k=1)
v = evecs.flatten().real
p = v / v.sum()
sqrtp = sp.sqrt(p)
Q = spdiags(sqrtp, [0], n, n) * P * spdiags(1.0 / sqrtp, [0], n, n)
I = sp.identity(len(G))

return I - (Q + Q.T) / 2.0

@not_implemented_for('undirected')
@not_implemented_for('multigraph')
def directed_combinatorial_laplacian_matrix(G, nodelist=None, weight='weight',
walk_type=None, alpha=0.95):
r"""Return the directed combinatorial Laplacian matrix of G.

The graph directed combinatorial Laplacian is the matrix

.. math::

L = \Phi - (\Phi P + P^T \Phi) / 2

where P is the transition matrix of the graph and and \Phi a matrix
with the Perron vector of P in the diagonal and zeros elsewhere.

Depending on the value of walk_type, P can be the transition matrix
induced by a random walk, a lazy random walk, or a random walk with
teleportation (PageRank).

Parameters
----------
G : DiGraph
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().

weight : string or None, optional (default='weight')
The edge data key used to compute each value in the matrix.
If None, then each edge has weight 1.

walk_type : string or None, optional (default=None)
If None, P is selected depending on the properties of the
graph. Otherwise is one of 'random', 'lazy', or 'pagerank'

alpha : real
(1 - alpha) is the teleportation probability used with pagerank

Returns
-------
L : NumPy array
Combinatorial Laplacian of G.

Notes
-----
Only implemented for DiGraphs

--------
laplacian_matrix

References
----------
.. [1] Fan Chung (2005).
Laplacians and the Cheeger inequality for directed graphs.
Annals of Combinatorics, 9(1), 2005
"""
from scipy.sparse import spdiags, linalg

P = _transition_matrix(G, nodelist=nodelist, weight=weight,
walk_type=walk_type, alpha=alpha)

n, m = P.shape

evals, evecs = linalg.eigs(P.T, k=1)
v = evecs.flatten().real
p = v / v.sum()
Phi = spdiags(p, [0], n, n)

Phi = Phi.todense()

return Phi - (Phi*P + P.T*Phi) / 2.0

def _transition_matrix(G, nodelist=None, weight='weight',
walk_type=None, alpha=0.95):
"""Returns the transition matrix of G.

This is a row stochastic giving the transition probabilities while
performing a random walk on the graph. Depending on the value of walk_type,
P can be the transition matrix induced by a random walk, a lazy random walk,
or a random walk with teleportation (PageRank).

Parameters
----------
G : DiGraph
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().

weight : string or None, optional (default='weight')
The edge data key used to compute each value in the matrix.
If None, then each edge has weight 1.

walk_type : string or None, optional (default=None)
If None, P is selected depending on the properties of the
graph. Otherwise is one of 'random', 'lazy', or 'pagerank'

alpha : real
(1 - alpha) is the teleportation probability used with pagerank

Returns
-------
P : NumPy array
transition matrix of G.

Raises
------
NetworkXError
If walk_type not specified or alpha not in valid range
"""

import scipy as sp
from scipy.sparse import identity, spdiags
if walk_type is None:
if nx.is_strongly_connected(G):
if nx.is_aperiodic(G):
walk_type = "random"
else:
walk_type = "lazy"
else:
walk_type = "pagerank"

M = nx.to_scipy_sparse_matrix(G, nodelist=nodelist, weight=weight,
dtype=float)
n, m = M.shape
if walk_type in ["random", "lazy"]:
DI = spdiags(1.0 / sp.array(M.sum(axis=1).flat), [0], n, n)
if walk_type == "random":
P = DI * M
else:
I = identity(n)
P = (I + DI * M) / 2.0

elif walk_type == "pagerank":
if not (0 < alpha < 1):
raise nx.NetworkXError('alpha must be between 0 and 1')
# this is using a dense representation
M = M.todense()
# add constant to dangling nodes' row
dangling = sp.where(M.sum(axis=1) == 0)
for d in dangling[0]:
M[d] = 1.0 / n
# normalize
M = M / M.sum(axis=1)
P = alpha * M + (1 - alpha) / n
else:
raise nx.NetworkXError("walk_type must be random, lazy, or pagerank")

return P

# fixture for nose tests

def setup_module(module):
from nose import SkipTest
try:
import numpy
except:
raise SkipTest("NumPy not available")