#NEWLINE# @ require ( 'numpy' ) #NEWLINE# @ not_implemented_for ( 'undirected' ) #NEWLINE# @ not_implemented_for ( 'multigraph' ) #NEWLINE# def directed_laplacian_matrix( G , nodelist = None , weight = 'weight' , walk_type = None , alpha = 0.95 ) : #NEWLINE# #INDENT# "Return the directed Laplacian matrix of G.\n\n    The graph directed Laplacian is the matrix\n\n    .. math::\n\n        L = I - (\\Phi^{1/2} P \\Phi^{-1/2} + \\Phi^{-1/2} P^T \\Phi^{1/2} ) / 2\n\n    where `I` is the identity matrix, `P` is the transition matrix of the\n    graph, and `\\Phi` a matrix with the Perron vector of `P` in the diagonal and\n    zeros elsewhere.\n\n    Depending on the value of walk_type, `P` can be the transition matrix\n    induced by a random walk, a lazy random walk, or a random walk with\n    teleportation (PageRank).\n\n    Parameters\n    ----------\n    G : DiGraph\n       A NetworkX graph\n\n    nodelist : list, optional\n       The rows and columns are ordered according to the nodes in nodelist.\n       If nodelist is None, then the ordering is produced by G.nodes().\n\n    weight : string or None, optional (default='weight')\n       The edge data key used to compute each value in the matrix.\n       If None, then each edge has weight 1.\n\n    walk_type : string or None, optional (default=None)\n       If None, `P` is selected depending on the properties of the\n       graph. Otherwise is one of 'random', 'lazy', or 'pagerank'\n\n    alpha : real\n       (1 - alpha) is the teleportation probability used with pagerank\n\n    Returns\n    -------\n    L : NumPy array\n      Normalized Laplacian of G.\n\n    Raises\n    ------\n    NetworkXError\n        If NumPy cannot be imported\n\n    NetworkXNotImplemnted\n        If G is not a DiGraph\n\n    Notes\n    -----\n    Only implemented for DiGraphs\n\n    See Also\n    --------\n    laplacian_matrix\n\n    References\n    ----------\n    .. [1] Fan Chung (2005).\n       Laplacians and the Cheeger inequality for directed graphs.\n       Annals of Combinatorics, 9(1), 2005\n    " #NEWLINE# import numpy as np #NEWLINE# if ( walk_type is None ) : #NEWLINE# #INDENT# if nx . is_strongly_connected ( G ) : #NEWLINE# #INDENT# if nx . is_aperiodic ( G ) : #NEWLINE# #INDENT# walk_type = 'random' #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# walk_type = 'lazy' #NEWLINE# #UNINDENT# #UNINDENT# else : #NEWLINE# #INDENT# walk_type = 'pagerank' #NEWLINE# #UNINDENT# #UNINDENT# M = nx . to_numpy_matrix ( G , nodelist = nodelist , weight = weight ) #NEWLINE# ( n , m ) = M . shape #NEWLINE# if ( walk_type in [ 'random' , 'lazy' ] ) : #NEWLINE# #INDENT# DI = np . diagflat ( ( 1.0 / np . sum ( M , axis = 1 ) ) ) #NEWLINE# if ( walk_type == 'random' ) : #NEWLINE# #INDENT# P = ( DI * M ) #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# I = np . identity ( n ) #NEWLINE# P = ( ( I + ( DI * M ) ) / 2.0 ) #NEWLINE# #UNINDENT# #UNINDENT# else : #NEWLINE# #INDENT# if ( walk_type == 'pagerank' ) : #NEWLINE# #INDENT# if ( not ( 0 < alpha < 1 ) ) : #NEWLINE# #INDENT# raise nx . NetworkXError ( 'alpha must be between 0 and 1' ) #NEWLINE# #UNINDENT# dangling = np . where ( ( M . sum ( axis = 1 ) == 0 ) ) #NEWLINE# for d in dangling [ 0 ] : #NEWLINE# #INDENT# M [ d ] = ( 1.0 / n ) #NEWLINE# #UNINDENT# M = ( M / M . sum ( axis = 1 ) ) #NEWLINE# P = ( ( alpha * M ) + ( ( 1 - alpha ) / n ) ) #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# raise nx . NetworkXError ( 'walk_type must be random, lazy, or pagerank' ) #NEWLINE# #UNINDENT# #UNINDENT# ( evals , evecs ) = np . linalg . eig ( P . T ) #NEWLINE# index = evals . argsort ( ) [ ( - 1 ) ] #NEWLINE# v = np . array ( evecs [ : , index ] ) . flatten ( ) . real #NEWLINE# p = ( v / v . sum ( ) ) #NEWLINE# sp = np . sqrt ( p ) #NEWLINE# Q = ( ( np . diag ( sp ) * P ) * np . diag ( ( 1.0 / sp ) ) ) #NEWLINE# I = np . identity ( len ( G ) ) #NEWLINE# return ( I - ( ( Q + Q . T ) / 2.0 ) )