Linear algebra
Tools of linear algebra.
Polynomials
- class sknetwork.linalg.Polynome(*args, **kwargs)[source]
Polynome of an adjacency matrix as a linear operator
\(P(A) = \alpha_k A^k + ... + \alpha_1 A + \alpha_0\).
- Parameters
adjacency – Adjacency matrix of the graph
coeffs (np.ndarray) – Coefficients of the polynome by increasing order of power.
Examples
>>> from scipy import sparse >>> from sknetwork.linalg import Polynome >>> adjacency = sparse.eye(2, format='csr') >>> polynome = Polynome(adjacency, np.arange(3)) >>> x = np.ones(2) >>> polynome.dot(x) array([3., 3.]) >>> polynome.T.dot(x) array([3., 3.])
Notes
The polynome is evaluated using the Ruffini-Horner method.
- property H
Hermitian adjoint.
Returns the Hermitian adjoint of self, aka the Hermitian conjugate or Hermitian transpose. For a complex matrix, the Hermitian adjoint is equal to the conjugate transpose.
Can be abbreviated self.H instead of self.adjoint().
- Returns
A_H – Hermitian adjoint of self.
- Return type
LinearOperator
- property T
Transpose this linear operator.
Returns a LinearOperator that represents the transpose of this one. Can be abbreviated self.T instead of self.transpose().
- adjoint()
Hermitian adjoint.
Returns the Hermitian adjoint of self, aka the Hermitian conjugate or Hermitian transpose. For a complex matrix, the Hermitian adjoint is equal to the conjugate transpose.
Can be abbreviated self.H instead of self.adjoint().
- Returns
A_H – Hermitian adjoint of self.
- Return type
LinearOperator
- dot(x)
Matrix-matrix or matrix-vector multiplication.
- Parameters
x (array_like) – 1-d or 2-d array, representing a vector or matrix.
- Returns
Ax – 1-d or 2-d array (depending on the shape of x) that represents the result of applying this linear operator on x.
- Return type
array
- matmat(X)
Matrix-matrix multiplication.
Performs the operation y=A*X where A is an MxN linear operator and X dense N*K matrix or ndarray.
- Parameters
X ({matrix, ndarray}) – An array with shape (N,K).
- Returns
Y – A matrix or ndarray with shape (M,K) depending on the type of the X argument.
- Return type
{matrix, ndarray}
Notes
This matmat wraps any user-specified matmat routine or overridden _matmat method to ensure that y has the correct type.
- matvec(x)
Matrix-vector multiplication.
Performs the operation y=A*x where A is an MxN linear operator and x is a column vector or 1-d array.
- Parameters
x ({matrix, ndarray}) – An array with shape (N,) or (N,1).
- Returns
y – A matrix or ndarray with shape (M,) or (M,1) depending on the type and shape of the x argument.
- Return type
{matrix, ndarray}
Notes
This matvec wraps the user-specified matvec routine or overridden _matvec method to ensure that y has the correct shape and type.
- rmatmat(X)
Adjoint matrix-matrix multiplication.
Performs the operation y = A^H * x where A is an MxN linear operator and x is a column vector or 1-d array, or 2-d array. The default implementation defers to the adjoint.
- Parameters
X ({matrix, ndarray}) – A matrix or 2D array.
- Returns
Y – A matrix or 2D array depending on the type of the input.
- Return type
{matrix, ndarray}
Notes
This rmatmat wraps the user-specified rmatmat routine.
- rmatvec(x)
Adjoint matrix-vector multiplication.
Performs the operation y = A^H * x where A is an MxN linear operator and x is a column vector or 1-d array.
- Parameters
x ({matrix, ndarray}) – An array with shape (M,) or (M,1).
- Returns
y – A matrix or ndarray with shape (N,) or (N,1) depending on the type and shape of the x argument.
- Return type
{matrix, ndarray}
Notes
This rmatvec wraps the user-specified rmatvec routine or overridden _rmatvec method to ensure that y has the correct shape and type.
- transpose()
Transpose this linear operator.
Returns a LinearOperator that represents the transpose of this one. Can be abbreviated self.T instead of self.transpose().
Sparse + Low Rank
- class sknetwork.linalg.SparseLR(*args, **kwargs)[source]
Class for matrices with “sparse + low rank” structure. Example:
\(A + xy^T\)
- Parameters
sparse_mat (scipy.spmatrix) – Sparse component. Is converted to csr format automatically.
low_rank_tuples (list) – Single tuple of arrays of list of tuples, representing the low rank components [(x1, y1), (x2, y2),…]. Each low rank component is of the form \(xy^T\).
Examples
>>> from scipy import sparse >>> from sknetwork.linalg import SparseLR >>> adjacency = sparse.eye(2, format='csr') >>> slr = SparseLR(adjacency, (np.ones(2), np.ones(2))) >>> x = np.ones(2) >>> slr.dot(x) array([3., 3.]) >>> slr.sum(axis=0) array([3., 3.]) >>> slr.sum(axis=1) array([3., 3.]) >>> slr.sum() 6.0
References
De Lara (2019). The Sparse + Low Rank trick for Matrix Factorization-Based Graph Algorithms. Proceedings of the 15th International Workshop on Mining and Learning with Graphs (MLG).
- property H
Hermitian adjoint.
Returns the Hermitian adjoint of self, aka the Hermitian conjugate or Hermitian transpose. For a complex matrix, the Hermitian adjoint is equal to the conjugate transpose.
Can be abbreviated self.H instead of self.adjoint().
- Returns
A_H – Hermitian adjoint of self.
- Return type
LinearOperator
- property T
Transpose this linear operator.
Returns a LinearOperator that represents the transpose of this one. Can be abbreviated self.T instead of self.transpose().
- adjoint()
Hermitian adjoint.
Returns the Hermitian adjoint of self, aka the Hermitian conjugate or Hermitian transpose. For a complex matrix, the Hermitian adjoint is equal to the conjugate transpose.
Can be abbreviated self.H instead of self.adjoint().
- Returns
A_H – Hermitian adjoint of self.
- Return type
LinearOperator
- dot(x)
Matrix-matrix or matrix-vector multiplication.
- Parameters
x (array_like) – 1-d or 2-d array, representing a vector or matrix.
- Returns
Ax – 1-d or 2-d array (depending on the shape of x) that represents the result of applying this linear operator on x.
- Return type
array
- left_sparse_dot(matrix: scipy.sparse.csr.csr_matrix)[source]
Left dot product with a sparse matrix.
- matmat(X)
Matrix-matrix multiplication.
Performs the operation y=A*X where A is an MxN linear operator and X dense N*K matrix or ndarray.
- Parameters
X ({matrix, ndarray}) – An array with shape (N,K).
- Returns
Y – A matrix or ndarray with shape (M,K) depending on the type of the X argument.
- Return type
{matrix, ndarray}
Notes
This matmat wraps any user-specified matmat routine or overridden _matmat method to ensure that y has the correct type.
- matvec(x)
Matrix-vector multiplication.
Performs the operation y=A*x where A is an MxN linear operator and x is a column vector or 1-d array.
- Parameters
x ({matrix, ndarray}) – An array with shape (N,) or (N,1).
- Returns
y – A matrix or ndarray with shape (M,) or (M,1) depending on the type and shape of the x argument.
- Return type
{matrix, ndarray}
Notes
This matvec wraps the user-specified matvec routine or overridden _matvec method to ensure that y has the correct shape and type.
- right_sparse_dot(matrix: scipy.sparse.csr.csr_matrix)[source]
Right dot product with a sparse matrix.
- rmatmat(X)
Adjoint matrix-matrix multiplication.
Performs the operation y = A^H * x where A is an MxN linear operator and x is a column vector or 1-d array, or 2-d array. The default implementation defers to the adjoint.
- Parameters
X ({matrix, ndarray}) – A matrix or 2D array.
- Returns
Y – A matrix or 2D array depending on the type of the input.
- Return type
{matrix, ndarray}
Notes
This rmatmat wraps the user-specified rmatmat routine.
- rmatvec(x)
Adjoint matrix-vector multiplication.
Performs the operation y = A^H * x where A is an MxN linear operator and x is a column vector or 1-d array.
- Parameters
x ({matrix, ndarray}) – An array with shape (M,) or (M,1).
- Returns
y – A matrix or ndarray with shape (N,) or (N,1) depending on the type and shape of the x argument.
- Return type
{matrix, ndarray}
Notes
This rmatvec wraps the user-specified rmatvec routine or overridden _rmatvec method to ensure that y has the correct shape and type.
- sum(axis=None)[source]
Row-wise, column-wise or total sum of operator’s coefficients.
- Parameters
axis – If 0, return column-wise sum. If 1, return row-wise sum. Otherwise, return total sum.
- transpose()
Transpose this linear operator.
Returns a LinearOperator that represents the transpose of this one. Can be abbreviated self.T instead of self.transpose().
Operators
- class sknetwork.linalg.Regularizer(*args, **kwargs)[source]
Regularized matrix as a Scipy LinearOperator.
Defined by \(A + \alpha \frac{11^T}n\) where \(A\) is the input matrix and \(\alpha\) the regularization factor.
- Parameters
input_matrix – Input matrix.
regularization (float) – Regularization factor. Default value = 1.
Examples
>>> from sknetwork.data import house >>> adjacency = house() >>> regularizer = Regularizer(adjacency) >>> regularizer.dot(np.ones(5)) array([3., 4., 3., 3., 4.])
- property H
Hermitian adjoint.
Returns the Hermitian adjoint of self, aka the Hermitian conjugate or Hermitian transpose. For a complex matrix, the Hermitian adjoint is equal to the conjugate transpose.
Can be abbreviated self.H instead of self.adjoint().
- Returns
A_H – Hermitian adjoint of self.
- Return type
LinearOperator
- property T
Transpose this linear operator.
Returns a LinearOperator that represents the transpose of this one. Can be abbreviated self.T instead of self.transpose().
- adjoint()
Hermitian adjoint.
Returns the Hermitian adjoint of self, aka the Hermitian conjugate or Hermitian transpose. For a complex matrix, the Hermitian adjoint is equal to the conjugate transpose.
Can be abbreviated self.H instead of self.adjoint().
- Returns
A_H – Hermitian adjoint of self.
- Return type
LinearOperator
- astype(dtype: Union[str, numpy.dtype])
Change dtype of the object.
- dot(x)
Matrix-matrix or matrix-vector multiplication.
- Parameters
x (array_like) – 1-d or 2-d array, representing a vector or matrix.
- Returns
Ax – 1-d or 2-d array (depending on the shape of x) that represents the result of applying this linear operator on x.
- Return type
array
- left_sparse_dot(matrix: scipy.sparse.csr.csr_matrix)
Left dot product with a sparse matrix.
- matmat(X)
Matrix-matrix multiplication.
Performs the operation y=A*X where A is an MxN linear operator and X dense N*K matrix or ndarray.
- Parameters
X ({matrix, ndarray}) – An array with shape (N,K).
- Returns
Y – A matrix or ndarray with shape (M,K) depending on the type of the X argument.
- Return type
{matrix, ndarray}
Notes
This matmat wraps any user-specified matmat routine or overridden _matmat method to ensure that y has the correct type.
- matvec(x)
Matrix-vector multiplication.
Performs the operation y=A*x where A is an MxN linear operator and x is a column vector or 1-d array.
- Parameters
x ({matrix, ndarray}) – An array with shape (N,) or (N,1).
- Returns
y – A matrix or ndarray with shape (M,) or (M,1) depending on the type and shape of the x argument.
- Return type
{matrix, ndarray}
Notes
This matvec wraps the user-specified matvec routine or overridden _matvec method to ensure that y has the correct shape and type.
- right_sparse_dot(matrix: scipy.sparse.csr.csr_matrix)
Right dot product with a sparse matrix.
- rmatmat(X)
Adjoint matrix-matrix multiplication.
Performs the operation y = A^H * x where A is an MxN linear operator and x is a column vector or 1-d array, or 2-d array. The default implementation defers to the adjoint.
- Parameters
X ({matrix, ndarray}) – A matrix or 2D array.
- Returns
Y – A matrix or 2D array depending on the type of the input.
- Return type
{matrix, ndarray}
Notes
This rmatmat wraps the user-specified rmatmat routine.
- rmatvec(x)
Adjoint matrix-vector multiplication.
Performs the operation y = A^H * x where A is an MxN linear operator and x is a column vector or 1-d array.
- Parameters
x ({matrix, ndarray}) – An array with shape (M,) or (M,1).
- Returns
y – A matrix or ndarray with shape (N,) or (N,1) depending on the type and shape of the x argument.
- Return type
{matrix, ndarray}
Notes
This rmatvec wraps the user-specified rmatvec routine or overridden _rmatvec method to ensure that y has the correct shape and type.
- sum(axis=None)
Row-wise, column-wise or total sum of operator’s coefficients.
- Parameters
axis – If 0, return column-wise sum. If 1, return row-wise sum. Otherwise, return total sum.
- transpose()
Transpose this linear operator.
Returns a LinearOperator that represents the transpose of this one. Can be abbreviated self.T instead of self.transpose().
- class sknetwork.linalg.Normalizer(*args, **kwargs)[source]
Normalized matrix as a Scipy LinearOperator.
Defined by \(D^{-1}A\) where \(A\) is the regularized adjacency matrix and \(D\) the corresponding diagonal matrix of degrees (sums over rows).
- Parameters
adjacency – Adjacency matrix of the graph.
regularization (float) – Regularization factor. Default value = 0.
Examples
>>> from sknetwork.data import house >>> adjacency = house() >>> normalizer = Normalizer(adjacency) >>> normalizer.dot(np.ones(5)) array([1., 1., 1., 1., 1.])
- property H
Hermitian adjoint.
Returns the Hermitian adjoint of self, aka the Hermitian conjugate or Hermitian transpose. For a complex matrix, the Hermitian adjoint is equal to the conjugate transpose.
Can be abbreviated self.H instead of self.adjoint().
- Returns
A_H – Hermitian adjoint of self.
- Return type
LinearOperator
- property T
Transpose this linear operator.
Returns a LinearOperator that represents the transpose of this one. Can be abbreviated self.T instead of self.transpose().
- adjoint()
Hermitian adjoint.
Returns the Hermitian adjoint of self, aka the Hermitian conjugate or Hermitian transpose. For a complex matrix, the Hermitian adjoint is equal to the conjugate transpose.
Can be abbreviated self.H instead of self.adjoint().
- Returns
A_H – Hermitian adjoint of self.
- Return type
LinearOperator
- dot(x)
Matrix-matrix or matrix-vector multiplication.
- Parameters
x (array_like) – 1-d or 2-d array, representing a vector or matrix.
- Returns
Ax – 1-d or 2-d array (depending on the shape of x) that represents the result of applying this linear operator on x.
- Return type
array
- matmat(X)
Matrix-matrix multiplication.
Performs the operation y=A*X where A is an MxN linear operator and X dense N*K matrix or ndarray.
- Parameters
X ({matrix, ndarray}) – An array with shape (N,K).
- Returns
Y – A matrix or ndarray with shape (M,K) depending on the type of the X argument.
- Return type
{matrix, ndarray}
Notes
This matmat wraps any user-specified matmat routine or overridden _matmat method to ensure that y has the correct type.
- matvec(x)
Matrix-vector multiplication.
Performs the operation y=A*x where A is an MxN linear operator and x is a column vector or 1-d array.
- Parameters
x ({matrix, ndarray}) – An array with shape (N,) or (N,1).
- Returns
y – A matrix or ndarray with shape (M,) or (M,1) depending on the type and shape of the x argument.
- Return type
{matrix, ndarray}
Notes
This matvec wraps the user-specified matvec routine or overridden _matvec method to ensure that y has the correct shape and type.
- rmatmat(X)
Adjoint matrix-matrix multiplication.
Performs the operation y = A^H * x where A is an MxN linear operator and x is a column vector or 1-d array, or 2-d array. The default implementation defers to the adjoint.
- Parameters
X ({matrix, ndarray}) – A matrix or 2D array.
- Returns
Y – A matrix or 2D array depending on the type of the input.
- Return type
{matrix, ndarray}
Notes
This rmatmat wraps the user-specified rmatmat routine.
- rmatvec(x)
Adjoint matrix-vector multiplication.
Performs the operation y = A^H * x where A is an MxN linear operator and x is a column vector or 1-d array.
- Parameters
x ({matrix, ndarray}) – An array with shape (M,) or (M,1).
- Returns
y – A matrix or ndarray with shape (N,) or (N,1) depending on the type and shape of the x argument.
- Return type
{matrix, ndarray}
Notes
This rmatvec wraps the user-specified rmatvec routine or overridden _rmatvec method to ensure that y has the correct shape and type.
- transpose()
Transpose this linear operator.
Returns a LinearOperator that represents the transpose of this one. Can be abbreviated self.T instead of self.transpose().
- class sknetwork.linalg.Laplacian(*args, **kwargs)[source]
Laplacian matrix as a Scipy LinearOperator.
Defined by \(L = D - A\) where \(A\) is the regularized adjacency matrix and \(D\) the corresponding diagonal matrix of degrees.
If normalized, defined by \(L = I - D^{-1/2}AD^{-1/2}\).
- Parameters
adjacency – Adjacency matrix of the graph.
regularization (float) – Regularization factor. Default value = 0.
normalized_laplacian (bool) – If
True
, use normalized Laplacian. Default value =False
.
Examples
>>> from sknetwork.data import house >>> adjacency = house() >>> laplacian = Laplacian(adjacency) >>> laplacian.dot(np.ones(5)) array([0., 0., 0., 0., 0.])
- property H
Hermitian adjoint.
Returns the Hermitian adjoint of self, aka the Hermitian conjugate or Hermitian transpose. For a complex matrix, the Hermitian adjoint is equal to the conjugate transpose.
Can be abbreviated self.H instead of self.adjoint().
- Returns
A_H – Hermitian adjoint of self.
- Return type
LinearOperator
- property T
Transpose this linear operator.
Returns a LinearOperator that represents the transpose of this one. Can be abbreviated self.T instead of self.transpose().
- adjoint()
Hermitian adjoint.
Returns the Hermitian adjoint of self, aka the Hermitian conjugate or Hermitian transpose. For a complex matrix, the Hermitian adjoint is equal to the conjugate transpose.
Can be abbreviated self.H instead of self.adjoint().
- Returns
A_H – Hermitian adjoint of self.
- Return type
LinearOperator
- dot(x)
Matrix-matrix or matrix-vector multiplication.
- Parameters
x (array_like) – 1-d or 2-d array, representing a vector or matrix.
- Returns
Ax – 1-d or 2-d array (depending on the shape of x) that represents the result of applying this linear operator on x.
- Return type
array
- matmat(X)
Matrix-matrix multiplication.
Performs the operation y=A*X where A is an MxN linear operator and X dense N*K matrix or ndarray.
- Parameters
X ({matrix, ndarray}) – An array with shape (N,K).
- Returns
Y – A matrix or ndarray with shape (M,K) depending on the type of the X argument.
- Return type
{matrix, ndarray}
Notes
This matmat wraps any user-specified matmat routine or overridden _matmat method to ensure that y has the correct type.
- matvec(x)
Matrix-vector multiplication.
Performs the operation y=A*x where A is an MxN linear operator and x is a column vector or 1-d array.
- Parameters
x ({matrix, ndarray}) – An array with shape (N,) or (N,1).
- Returns
y – A matrix or ndarray with shape (M,) or (M,1) depending on the type and shape of the x argument.
- Return type
{matrix, ndarray}
Notes
This matvec wraps the user-specified matvec routine or overridden _matvec method to ensure that y has the correct shape and type.
- rmatmat(X)
Adjoint matrix-matrix multiplication.
Performs the operation y = A^H * x where A is an MxN linear operator and x is a column vector or 1-d array, or 2-d array. The default implementation defers to the adjoint.
- Parameters
X ({matrix, ndarray}) – A matrix or 2D array.
- Returns
Y – A matrix or 2D array depending on the type of the input.
- Return type
{matrix, ndarray}
Notes
This rmatmat wraps the user-specified rmatmat routine.
- rmatvec(x)
Adjoint matrix-vector multiplication.
Performs the operation y = A^H * x where A is an MxN linear operator and x is a column vector or 1-d array.
- Parameters
x ({matrix, ndarray}) – An array with shape (M,) or (M,1).
- Returns
y – A matrix or ndarray with shape (N,) or (N,1) depending on the type and shape of the x argument.
- Return type
{matrix, ndarray}
Notes
This rmatvec wraps the user-specified rmatvec routine or overridden _rmatvec method to ensure that y has the correct shape and type.
- transpose()
Transpose this linear operator.
Returns a LinearOperator that represents the transpose of this one. Can be abbreviated self.T instead of self.transpose().
- class sknetwork.linalg.CoNeighbor(*args, **kwargs)[source]
Co-neighborhood adjacency as a LinearOperator.
\(\tilde{A} = AF^{-1}A^T\), or \(\tilde{B} = BF^{-1}B^T\).
where F is a weight matrix.
- Parameters
adjacency – Adjacency or biadjacency of the input graph.
normalized – If
True
, F is the diagonal in-degree matrix \(F = \text{diag}(A^T1)\). Otherwise, F is the identity matrix.
Examples
>>> from sknetwork.data import star_wars >>> biadjacency = star_wars(metadata=False) >>> d_out = biadjacency.dot(np.ones(3)) >>> coneigh = CoNeighbor(biadjacency) >>> np.allclose(d_out, coneigh.dot(np.ones(4))) True
- property H
Hermitian adjoint.
Returns the Hermitian adjoint of self, aka the Hermitian conjugate or Hermitian transpose. For a complex matrix, the Hermitian adjoint is equal to the conjugate transpose.
Can be abbreviated self.H instead of self.adjoint().
- Returns
A_H – Hermitian adjoint of self.
- Return type
LinearOperator
- property T
Transpose this linear operator.
Returns a LinearOperator that represents the transpose of this one. Can be abbreviated self.T instead of self.transpose().
- adjoint()
Hermitian adjoint.
Returns the Hermitian adjoint of self, aka the Hermitian conjugate or Hermitian transpose. For a complex matrix, the Hermitian adjoint is equal to the conjugate transpose.
Can be abbreviated self.H instead of self.adjoint().
- Returns
A_H – Hermitian adjoint of self.
- Return type
LinearOperator
- dot(x)
Matrix-matrix or matrix-vector multiplication.
- Parameters
x (array_like) – 1-d or 2-d array, representing a vector or matrix.
- Returns
Ax – 1-d or 2-d array (depending on the shape of x) that represents the result of applying this linear operator on x.
- Return type
array
- matmat(X)
Matrix-matrix multiplication.
Performs the operation y=A*X where A is an MxN linear operator and X dense N*K matrix or ndarray.
- Parameters
X ({matrix, ndarray}) – An array with shape (N,K).
- Returns
Y – A matrix or ndarray with shape (M,K) depending on the type of the X argument.
- Return type
{matrix, ndarray}
Notes
This matmat wraps any user-specified matmat routine or overridden _matmat method to ensure that y has the correct type.
- matvec(x)
Matrix-vector multiplication.
Performs the operation y=A*x where A is an MxN linear operator and x is a column vector or 1-d array.
- Parameters
x ({matrix, ndarray}) – An array with shape (N,) or (N,1).
- Returns
y – A matrix or ndarray with shape (M,) or (M,1) depending on the type and shape of the x argument.
- Return type
{matrix, ndarray}
Notes
This matvec wraps the user-specified matvec routine or overridden _matvec method to ensure that y has the correct shape and type.
- right_sparse_dot(matrix: scipy.sparse.csr.csr_matrix)[source]
Right dot product with a sparse matrix
- rmatmat(X)
Adjoint matrix-matrix multiplication.
Performs the operation y = A^H * x where A is an MxN linear operator and x is a column vector or 1-d array, or 2-d array. The default implementation defers to the adjoint.
- Parameters
X ({matrix, ndarray}) – A matrix or 2D array.
- Returns
Y – A matrix or 2D array depending on the type of the input.
- Return type
{matrix, ndarray}
Notes
This rmatmat wraps the user-specified rmatmat routine.
- rmatvec(x)
Adjoint matrix-vector multiplication.
Performs the operation y = A^H * x where A is an MxN linear operator and x is a column vector or 1-d array.
- Parameters
x ({matrix, ndarray}) – An array with shape (M,) or (M,1).
- Returns
y – A matrix or ndarray with shape (N,) or (N,1) depending on the type and shape of the x argument.
- Return type
{matrix, ndarray}
Notes
This rmatvec wraps the user-specified rmatvec routine or overridden _rmatvec method to ensure that y has the correct shape and type.
- transpose()
Transpose this linear operator.
Returns a LinearOperator that represents the transpose of this one. Can be abbreviated self.T instead of self.transpose().
Solvers
- class sknetwork.linalg.LanczosEig(which='LM', n_iter: Optional[int] = None, tol: float = 0.0)[source]
Eigenvalue solver using Lanczos method.
- Parameters
which (str) –
Which eigenvectors and eigenvalues to find:
'LM'
: Largest (in modulus) eigenvalues.'SM'
: Smallest (in modulus) eigenvalues.'LA'
: Largest (algebraic) eigenvalues.'SA'
: Smallest (algebraic) eigenvalues.
n_iter (int) – Maximum number of Arnoldi update iterations allowed. Default = 10 * nb of rows.
tol (float) – Relative accuracy for eigenvalues (stopping criterion). Default = 0 (machine precision).
- Variables
eigenvectors_ (np.ndarray) – Two-dimensional array, each column is an eigenvector of the input.
eigenvalues_ (np.ndarray) – Eigenvalues associated to each eigenvector.
See also
scipy.sparse.linalg.eigsh
- fit(matrix: Union[scipy.sparse.csr.csr_matrix, scipy.sparse.linalg.interface.LinearOperator], n_components: int = 2)[source]
Perform spectral decomposition on symmetric input matrix.
- Parameters
matrix (sparse.csr_matrix or linear operator) – Matrix to decompose.
n_components (int) – Number of eigenvectors to compute
- Returns
self
- Return type
EigSolver
- class sknetwork.linalg.LanczosSVD(n_iter: Optional[int] = None, tol: float = 0.0)[source]
SVD solver using Lanczos method on \(AA^T\) or \(A^TA\).
- Parameters
n_iter (int) – Maximum number of Arnoldi update iterations allowed. Default = 10 * nb or rows or columns.
tol (float) – Relative accuracy for eigenvalues (stopping criterion). Default = 0 (machine precision).
- Variables
singular_vectors_left_ (np.ndarray) – Two-dimensional array, each column is a left singular vector of the input.
singular_vectors_right_ (np.ndarray) – Two-dimensional array, each column is a right singular vector of the input.
singular_values_ (np.ndarray) – Singular values.
See also
scipy.sparse.linalg.svds
- fit(matrix: Union[scipy.sparse.csr.csr_matrix, scipy.sparse.linalg.interface.LinearOperator], n_components: int, init_vector: Optional[numpy.ndarray] = None)[source]
Perform singular value decomposition on input matrix.
- Parameters
matrix – Matrix to decompose.
n_components (int) – Number of singular values to compute
init_vector (np.ndarray) – Starting vector for iteration. Default = random.
- Returns
self
- Return type
SVDSolver
- sknetwork.linalg.ppr_solver.get_pagerank(adjacency: Union[scipy.sparse.csr.csr_matrix, scipy.sparse.linalg.interface.LinearOperator], seeds: numpy.ndarray, damping_factor: float, n_iter: int, tol: float = 1e-06, solver: str = 'piteration') numpy.ndarray [source]
Solve the Pagerank problem. Formally,
\(x = \alpha Px + (1-\alpha)y\),
where \(P = (D^{-1}A)^T\) is the transition matrix and \(y\) is the personalization probability vector.
- Parameters
adjacency (sparse.csr_matrix) – Adjacency matrix of the graph.
seeds (np.ndarray) – Personalization array. Must be a valid probability vector.
damping_factor (float) – Probability to continue the random walk.
n_iter (int) – Number of iterations for some of the solvers such as
'piteration'
or'diteration'
.tol (float) – Tolerance for the convergence of some solvers such as
'bicgstab'
or'lanczos'
or'push'
.solver (
str
) – Which solver to use:'piteration'
,'diteration'
,'bicgstab'
,'lanczos'
,̀'RH'
,'push'
.
- Returns
pagerank – Probability vector.
- Return type
np.ndarray
Examples
>>> from sknetwork.data import house >>> adjacency = house() >>> seeds = np.array([1, 0, 0, 0, 0]) >>> scores = get_pagerank(adjacency, seeds, damping_factor=0.85, n_iter=10) >>> np.round(scores, 2) array([0.29, 0.24, 0.12, 0.12, 0.24])
References
Hong, D. (2012). Optimized on-line computation of pagerank algorithm. arXiv preprint arXiv:1202.6158.
Van der Vorst, H. A. (1992). Bi-CGSTAB: A fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems. SIAM Journal on scientific and Statistical Computing, 13(2), 631-644.
Lanczos, C. (1950). An iteration method for the solution of the eigenvalue problem of linear differential and integral operators. Los Angeles, CA: United States Governm. Press Office.
Whang, J. , Lenharth, A. , Dhillon, I. , & Pingali, K. . (2015). Scalable Data-Driven PageRank: Algorithms, System Issues, and Lessons Learned. 9233, 438-450. <https://www.cs.utexas.edu/users/inderjit/public_papers/scalable_pagerank_europar15.pdf>
Miscellaneous
- sknetwork.linalg.diag_pinv(weights: numpy.ndarray) scipy.sparse.csr.csr_matrix [source]
Compute \(W^+ = \text{diag}(w)^+\), the pseudo inverse of the diagonal matrix with diagonal the weights \(w\).
- Parameters
weights – The weights to invert.
- Returns
\(W^+\)
- Return type
sparse.csr_matrix
- sknetwork.linalg.normalize(matrix: Union[scipy.sparse.csr.csr_matrix, numpy.ndarray, scipy.sparse.linalg.interface.LinearOperator], p=1)[source]
Normalize rows of a matrix. Null rows remain null.
- Parameters
matrix – Input matrix.
p – Order of the norm
- Returns
normalized matrix
- Return type
same as input