<s> """<STR_LIT>""" <EOL> import networkx as nx <EOL> from networkx . exception import NetworkXError <EOL> __author__ = """<STR_LIT>""" <EOL> __all__ = [ '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' ] <EOL> def pagerank ( G , alpha = <NUM_LIT> , personalization = None , <EOL> max_iter = <NUM_LIT:100> , tol = <NUM_LIT> , nstart = None , weight = '<STR_LIT>' ) : <EOL> """<STR_LIT>""" <EOL> if type ( G ) == nx . MultiGraph or type ( G ) == nx . MultiDiGraph : <EOL> raise Exception ( "<STR_LIT>" ) <EOL> if len ( G ) == <NUM_LIT:0> : <EOL> return { } <EOL> if not G . is_directed ( ) : <EOL> D = G . to_directed ( ) <EOL> else : <EOL> D = G <EOL> W = nx . stochastic_graph ( D , weight = weight ) <EOL> scale = <NUM_LIT:1.0> / W . number_of_nodes ( ) <EOL> if nstart is None : <EOL> x = dict . fromkeys ( W , scale ) <EOL> else : <EOL> x = nstart <EOL> s = <NUM_LIT:1.0> / sum ( x . values ( ) ) <EOL> for k in x : x [ k ] *= s <EOL> if personalization is None : <EOL> p = dict . fromkeys ( W , scale ) <EOL> else : <EOL> p = personalization <EOL> s = <NUM_LIT:1.0> / sum ( p . values ( ) ) <EOL> for k in p : <EOL> p [ k ] *= s <EOL> if set ( p ) != set ( G ) : <EOL> raise NetworkXError ( '<STR_LIT>' <EOL> '<STR_LIT>' ) <EOL> out_degree = W . out_degree ( ) <EOL> dangle = [ n for n in W if out_degree [ n ] == <NUM_LIT:0.0> ] <EOL> i = <NUM_LIT:0> <EOL> while True : <EOL> xlast = x <EOL> x = dict . fromkeys ( xlast . keys ( ) , <NUM_LIT:0> ) <EOL> danglesum = alpha * scale * sum ( xlast [ n ] for n in dangle ) <EOL> for n in x : <EOL> for nbr in W [ n ] : <EOL> x [ nbr ] += alpha * xlast [ n ] * W [ n ] [ nbr ] [ weight ] <EOL> x [ n ] += danglesum + ( <NUM_LIT:1.0> - alpha ) * p [ n ] <EOL> s = <NUM_LIT:1.0> / sum ( x . values ( ) ) <EOL> for n in x : <EOL> x [ n ] *= s <EOL> err = sum ( [ abs ( x [ n ] - xlast [ n ] ) for n in x ] ) <EOL> if err < tol : <EOL> break <EOL> if i > max_iter : <EOL> raise NetworkXError ( '<STR_LIT>' <EOL> '<STR_LIT>' % ( i - <NUM_LIT:1> ) ) <EOL> i += <NUM_LIT:1> <EOL> return x <EOL> def google_matrix ( G , alpha = <NUM_LIT> , personalization = None , <EOL> nodelist = None , weight = '<STR_LIT>' ) : <EOL> """<STR_LIT>""" <EOL> try : <EOL> import numpy as np <EOL> except ImportError : <EOL> raise ImportError ( "<STR_LIT>" ) <EOL> if personalization is None : <EOL> nodelist = G . nodes ( ) <EOL> else : <EOL> nodelist = personalization . keys ( ) <EOL> if set ( nodelist ) != set ( G ) : <EOL> raise NetworkXError ( '<STR_LIT>' <EOL> '<STR_LIT>' ) <EOL> M = nx . to_numpy_matrix ( G , nodelist = nodelist , weight = weight ) <EOL> ( n , m ) = M . shape <EOL> if n == <NUM_LIT:0> : <EOL> return M <EOL> dangling = np . where ( M . sum ( axis = <NUM_LIT:1> ) == <NUM_LIT:0> ) <EOL> for d in dangling [ <NUM_LIT:0> ] : <EOL> M [ d ] = <NUM_LIT:1.0> / n <EOL> M = M / M . sum ( axis = <NUM_LIT:1> ) <EOL> e = np . ones ( ( n ) ) <EOL> if personalization is not None : <EOL> v = np . array ( list ( personalization . values ( ) ) , dtype = float ) <EOL> else : <EOL> v = e <EOL> v = v / v . sum ( ) <EOL> P = alpha * M + ( <NUM_LIT:1> - alpha ) * np . outer ( e , v ) <EOL> return P <EOL> def pagerank_numpy ( G , alpha = <NUM_LIT> , personalization = None , weight = '<STR_LIT>' ) : <EOL> """<STR_LIT>""" <EOL> try : <EOL> import numpy as np <EOL> except ImportError : <EOL> raise ImportError ( "<STR_LIT>" ) <EOL> if len ( G ) == <NUM_LIT:0> : <EOL> return { } <EOL> if personalization is None : <EOL> nodelist = G . nodes ( ) <EOL> else : <EOL> nodelist = personalization . keys ( ) <EOL> M = google_matrix ( G , alpha , personalization = personalization , <EOL> nodelist = nodelist , weight = weight ) <EOL> eigenvalues , eigenvectors = np . linalg . eig ( M . T ) <EOL> ind = eigenvalues . argsort ( ) <EOL> largest = np . array ( eigenvectors [ : , ind [ - <NUM_LIT:1> ] ] ) . flatten ( ) . real <EOL> norm = float ( largest . sum ( ) ) <EOL> centrality = dict ( zip ( nodelist , map ( float , largest / norm ) ) ) <EOL> return centrality <EOL> def pagerank_scipy ( G , alpha = <NUM_LIT> , personalization = None , <EOL> max_iter = <NUM_LIT:100> , tol = <NUM_LIT> , weight = '<STR_LIT>' ) : <EOL> """<STR_LIT>""" <EOL> try : <EOL> import scipy . sparse <EOL> except ImportError : <EOL> raise ImportError ( "<STR_LIT>" ) <EOL> if len ( G ) == <NUM_LIT:0> : <EOL> return { } <EOL> if personalization is None : <EOL> nodelist = G . nodes ( ) <EOL> else : <EOL> nodelist = personalization . keys ( ) <EOL> M = nx . to_scipy_sparse_matrix ( G , nodelist = nodelist , weight = weight , dtype = '<STR_LIT:f>' ) <EOL> ( n , m ) = M . shape <EOL> S = scipy . array ( M . sum ( axis = <NUM_LIT:1> ) ) . flatten ( ) <EOL> S [ S > <NUM_LIT:0> ] = <NUM_LIT:1.0> / S [ S > <NUM_LIT:0> ] <EOL> Q = scipy . sparse . spdiags ( S . T , <NUM_LIT:0> , * M . shape , format = '<STR_LIT>' ) <EOL> M = Q * M <EOL> x = scipy . ones ( ( n ) ) / n <EOL> dangle = scipy . array ( scipy . where ( M . sum ( axis = <NUM_LIT:1> ) == <NUM_LIT:0> , <NUM_LIT:1.0> / n , <NUM_LIT:0> ) ) . flatten ( ) <EOL> if personalization is not None : <EOL> v = scipy . array ( list ( personalization . values ( ) ) , dtype = float ) <EOL> v = v / v . sum ( ) <EOL> else : <EOL> v = x <EOL> i = <NUM_LIT:0> <EOL> while i <= max_iter : <EOL> xlast = x <EOL> x = alpha * ( x * M + scipy . dot ( dangle , xlast ) ) + ( <NUM_LIT:1> - alpha ) * v <EOL> x = x / x . sum ( ) <EOL> err = scipy . absolute ( x - xlast ) . sum ( ) <EOL> if err < n * tol : <EOL> return dict ( zip ( nodelist , map ( float , x ) ) ) <EOL> i += <NUM_LIT:1> <EOL> raise NetworkXError ( '<STR_LIT>' <EOL> '<STR_LIT>' % ( i + <NUM_LIT:1> ) ) <EOL> def setup_module ( module ) : <EOL> from nose import SkipTest <EOL> try : <EOL> import numpy <EOL> except : <EOL> raise SkipTest ( "<STR_LIT>" ) <EOL> try : <EOL> import scipy <EOL> except : <EOL> raise SkipTest ( "<STR_LIT>" ) </s>
