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 input graph.

Returns

  • ndarray or scipy.sparse.csr_matrix

  • The N x N laplacian matrix of csgraph. It will be a NumPy array (dense) if the input was dense, or a sparse matrix otherwise.

  • ndarray

  • The length-N diagonal of the Laplacian matrix. For the normalized Laplacian, this is the array of square roots of vertex degrees or 1 if the degree is zero.

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))