networkit.algebraic¶

This module deals with the conversion of graphs into matrices and linear algebra operations on graphs

networkit.algebraic.PageRankMatrix(G, damp=0.85)¶

Builds the PageRank matrix of the undirected Graph G. This matrix corresponds with the PageRank matrix used in the C++ backend.

Parameters:

• G (networkit.Graph) – The graph.

• damp (float, optional) – Damping factor of the PageRank algorithm. Default: 0.85

Returns:

The N x N page rank matrix of graph.

Return type:

ndarray

networkit.algebraic.adjacencyEigenvector(G, i, reverse=False)¶

Compute a certain eigenvector and eigenvalue of the Adjacency matrix of G.

Parameters:

• G (networkit.Graph) – The input graph.

• i (int) – Computes the eigenvector and value of index i.

• reverse (bool, optional) – If set to true, the smaller eigenvalues will be computed before the larger ones. Default: False

Returns:

A pair of values, the first containing the eigenvalue, the second one holding the corresponding eigenvector

Return type:

tuple( float, ndarray )

networkit.algebraic.adjacencyEigenvectors(G, cutoff=-1, reverse=False)¶

Computes eigenvectors and -values of the Adjacency matrix of G.

Parameters:

• G (networkit.Graph) – The graph.

• cutoff (int, optional) – The maximum (or minimum) number of eigenvectors needed. Default: -1

• reverse (bool, optional) – If set to true, the smaller eigenvalues will be computed before the larger ones. Default: False

Returns:

A tuple of ordered lists, the first containing the eigenvalues in descending (ascending) magnitude, the second one holding the corresponding eigenvectors

Return type:

tuple(list(float), list(ndarray))

networkit.algebraic.adjacencyMatrix(G, matrixType='sparse')¶

Get the adjacency matrix of the graph G.

Parameters:

• G (networkit.Graph) – The graph.

• matrixType (str, optional) – Either “sparse” or “dense”. Default: “sparse”

Returns:

The adjacency matrix of the graph.

Return type:

scipy.sparse.csr_matrix

networkit.algebraic.column(matrix, i)¶

Get the ith column of a matrix

Parameters:

• matrix (scipy.sparse.csr_matrix) – The matrix to compute the eigenvectors of.

• i (int) – Column index.

Returns:

Column i of matrix.

Return type:

list(float)

networkit.algebraic.eigenvectors(matrix, cutoff=-1, reverse=False)¶

Computes eigenvectors and -values of matrices.

Parameters:

• matrix (scipy.sparse.csr_matrix) – The matrix to compute the eigenvectors of.

• cutoff (int, optional) – The maximum (or minimum) number of eigenvectors needed. Default: -1

• reverse (bool, optional) – If set to true, the smaller eigenvalues will be computed before the larger ones. Default: False

Returns:

A tuple of ordered lists, the first containing the eigenvalues in descending (ascending) magnitude, the second one holding the corresponding eigenvectors

Return type:

tuple(list(float), list(ndarray))

networkit.algebraic.laplacianEigenvector(G, i, reverse=False)¶

Compute a certain eigenvector and -value of the Laplician matrix of G.

Parameters:

• G (networkit.Graph) – The input graph.

• i (int) – Computes the eigenvector and value of index i.

• reverse (bool, optional) – If set to true, the smaller eigenvalues will be computed before the larger ones. Default: False

Returns:

A pair of values, the first containing the eigenvalue, the second one holding the corresponding eigenvector

Return type:

tuple(float, ndarray)

networkit.algebraic.laplacianEigenvectors(G, cutoff=-1, reverse=False)¶

Computes eigenvectors and -values of the Laplician matrix of G.

Parameters:

• G (networkit.Graph) – The input graph.

• cutoff (int, optional) – The maximum (or minimum) number of eigenvectors needed. Default: -1

• reverse (bool, optional) – If set to true, the smaller eigenvalues will be computed before the larger ones. Default: False

Returns:

A tuple of ordered lists, the first containing the eigenvalues in descending (ascending) magnitude, the second one holding the corresponding eigenvectors

Return type:

tuple(list(float), list(ndarray))

networkit.algebraic.laplacianMatrix(G)¶

Get the laplacian matrix of the graph G.

Parameters:

G (networkit.Graph) – The graph.

Returns:

• scipy.sparse.csr_matrix

• The N x N laplacian matrix of csgraph. It will be a scipy.sparse.csr_matrix.

networkit.algebraic.symmetricEigenvectors(matrix, cutoff=-1, reverse=False)¶

Computes eigenvectors and -values of symmetric matrices.

Parameters:

• matrix (scipy.sparse.csr_matrix) – The matrix to compute the eigenvectors of.

• cutoff (int, optional) – The maximum (or minimum) magnitude of the eigenvectors needed. Default: -1

• reverse (boolean, optional) – If set to true, the smaller eigenvalues will be computed before the larger ones. Default: False

Returns:

A tuple of ordered lists, the first containing the eigenvalues in descending (ascending) magnitude, the second one holding the corresponding eigenvectors.

Return type:

tuple(list(float), list(ndarray))