Topology

Algorithms for the analysis of graph topology.

Structure

sknetwork.topology.connected_components(adjacency: scipy.sparse.csr.csr_matrix, connection: str = 'weak') → numpy.ndarray[source]

Extract the connected components of the graph.

  • Graphs

  • Digraphs

Based on SciPy (scipy.sparse.csgraph.connected_components).

Parameters
  • adjacency – Adjacency matrix of the graph.

  • connection – Must be 'weak' (default) or 'strong'. The type of connection to use for directed graphs.

Returns

labels – Connected component of each node.

Return type

np.ndarray

sknetwork.topology.largest_connected_component(adjacency: Union[scipy.sparse.csr.csr_matrix, numpy.ndarray], return_labels: bool = False)[source]

Extract the largest connected component of a graph. Bipartite graphs are treated as undirected.

  • Graphs

  • Digraphs

  • Bigraphs

Parameters
  • adjacency – Adjacency or biadjacency matrix of the graph.

  • return_labels (bool) – Whether to return the indices of the new nodes in the original graph.

Returns

  • new_adjacency (sparse.csr_matrix) – Adjacency or biadjacency matrix of the largest connected component.

  • indices (array or tuple of array) – Indices of the nodes in the original graph. For biadjacency matrices, indices[0] corresponds to the rows and indices[1] to the columns.

class sknetwork.topology.CoreDecomposition

K-core decomposition algorithm.

  • Graphs

Variables
  • labels_ (np.ndarray) – Core value of each node.

  • core_value_ (int) – Maximum core value of the graph

Example

>>> from sknetwork.topology import CoreDecomposition
>>> from sknetwork.data import karate_club
>>> kcore = CoreDecomposition()
>>> adjacency = karate_club()
>>> kcore.fit(adjacency)
>>> kcore.core_value_
4
fit(adjacency: scipy.sparse.csr.csr_matrix) → sknetwork.topology.kcore.CoreDecomposition

K-core decomposition.

Parameters

adjacency – Adjacency matrix of the graph.

Returns

self

Return type

CoreDecomposition

fit_transform(adjacency: scipy.sparse.csr.csr_matrix)

Fit algorithm to the data and return the core value of each node. Same parameters as the fit method.

Returns

Core value of the nodes.

Return type

labels

sknetwork.topology.is_bipartite(adjacency: scipy.sparse.csr.csr_matrix, return_biadjacency: bool = False) → Union[bool, Tuple[bool, Optional[scipy.sparse.csr.csr_matrix], Optional[numpy.ndarray], Optional[numpy.ndarray]]][source]

Check whether an undirected graph is bipartite.

  • Graphs

Parameters
  • adjacency – Adjacency matrix of the graph (symmetric).

  • return_biadjacency – If True, return a biadjacency matrix of the graph if bipartite.

Returns

  • is_bipartite (bool) – A boolean denoting if the graph is bipartite.

  • biadjacency (sparse.csr_matrix) – A biadjacency matrix of the graph if bipartite (optional).

  • rows (np.ndarray) – Index of rows in the original graph (optional).

  • cols (np.ndarray) – Index of columns in the original graph (optional).

sknetwork.topology.is_acyclic(adjacency: scipy.sparse.csr.csr_matrix) → bool[source]

Check whether a graph has no cycle.

Parameters

adjacency – Adjacency matrix of the graph.

Returns

is_acyclic – A boolean with value True if the graph has no cycle and False otherwise

Return type

bool

class sknetwork.topology.DAG(ordering: str = None)[source]

Build a Directed Acyclic Graph from an adjacency.

  • Graphs

  • DiGraphs

Parameters

ordering (str) –

A method to sort the nodes.

  • If None, the default order is the index.

  • If 'degree', the nodes are sorted by ascending degree.

Variables
  • indptr_ (np.ndarray) – Pointer index as for CSR format.

  • indices_ (np.ndarray) – Indices as for CSR format.

fit(adjacency: scipy.sparse.csr.csr_matrix, sorted_nodes=None)[source]

Fit algorithm to the data.

Parameters
  • adjacency – Adjacency matrix of the graph.

  • sorted_nodes (np.ndarray) – An order on the nodes such that the DAG only contains edges (i, j) such that sorted_nodes[i] < sorted_nodes[j].

Counting

class sknetwork.topology.Triangles(parallelize: bool = False)

Count the number of triangles in a graph, and evaluate the clustering coefficient.

  • Graphs

Parameters

parallelize – If True, use a parallel range while listing the triangles.

Variables
  • n_triangles_ (int) – Number of triangles.

  • clustering_coef_ (float) – Global clustering coefficient of the graph.

Example

>>> from sknetwork.data import karate_club
>>> triangles = Triangles()
>>> adjacency = karate_club()
>>> triangles.fit_transform(adjacency)
45
fit(adjacency: scipy.sparse.csr.csr_matrix) → sknetwork.topology.triangles.Triangles

Count triangles.

Parameters

adjacency – Adjacency matrix of the graph.

Returns

self

Return type

Triangles

fit_transform(adjacency: scipy.sparse.csr.csr_matrix) → int

Fit algorithm to the data and return the number of triangles. Same parameters as the fit method.

Returns

n_triangles_ – Number of triangles.

Return type

int

class sknetwork.topology.Cliques(k: int)

Clique counting algorithm.

  • Graphs

Parameters

k (int) – k value of cliques to list

Variables

n_cliques_ (int) – Number of cliques

Example

>>> from sknetwork.data import karate_club
>>> cliques = Cliques(k=3)
>>> adjacency = karate_club()
>>> cliques.fit_transform(adjacency)
45

References

Danisch, M., Balalau, O., & Sozio, M. (2018, April). Listing k-cliques in sparse real-world graphs. In Proceedings of the 2018 World Wide Web Conference (pp. 589-598).

fit(adjacency: scipy.sparse.csr.csr_matrix) → sknetwork.topology.kcliques.Cliques

K-cliques count.

Parameters

adjacency – Adjacency matrix of the graph.

Returns

self

Return type

Cliques

fit_transform(adjacency: scipy.sparse.csr.csr_matrix) → int

Fit algorithm to the data and return the number of cliques. Same parameters as the fit method.

Returns

n_cliques – Number of k-cliques.

Return type

int

Coloring

class sknetwork.topology.WeisfeilerLehman(max_iter: int = - 1)[source]

Weisfeiler-Lehman algorithm for coloring/labeling graphs in order to check similarity.

Parameters

max_iter (int) – Maximum number of iterations. Negative value means until convergence.

Variables

labels_ (np.ndarray) – Label of each node.

Example

>>> from sknetwork.topology import WeisfeilerLehman
>>> from sknetwork.data import house
>>> weisfeiler_lehman = WeisfeilerLehman()
>>> adjacency = house()
>>> labels = weisfeiler_lehman.fit_transform(adjacency)
>>> labels
array([0, 2, 1, 1, 2], dtype=int32)

References

fit(adjacency: Union[scipy.sparse.csr.csr_matrix, numpy.ndarray]) → sknetwork.topology.weisfeiler_lehman.WeisfeilerLehman[source]

Fit algorithm to the data.

Parameters

adjacency (Union[sparse.csr_matrix, np.ndarray]) – Adjacency matrix of the graph.

Returns

self

Return type

WeisfeilerLehman

fit_transform(adjacency: Union[scipy.sparse.csr.csr_matrix, numpy.ndarray]) → numpy.ndarray[source]

Fit algorithm to the data and return the labels. Same parameters as the fit method.

Returns

labels – Labels.

Return type

np.ndarray

Similarity

sknetwork.topology.are_isomorphic(adjacency1: scipy.sparse.csr.csr_matrix, adjacency2: scipy.sparse.csr.csr_matrix, max_iter: int = - 1) → bool[source]

Weisfeiler-Lehman isomorphism test. If the test is False, the graphs cannot be isomorphic, otherwise, they might be.

Parameters
  • adjacency1 – First adjacency matrix.

  • adjacency2 – Second adjacency matrix.

  • max_iter (int) – Maximum number of coloring iterations. Negative value means until convergence.

Returns

test_result

Return type

bool

Example

>>> from sknetwork.topology import are_isomorphic
>>> from sknetwork.data import house
>>> adjacency_1 = house()
>>> adjacency_2 = house()
>>> are_isomorphic(adjacency_1, adjacency_2)
True

References