Topology

Algorithms for the analysis of graph topology.

Connectivity

sknetwork.topology.get_connected_components(input_matrix: scipy.sparse._csr.csr_matrix, connection: str = 'weak', force_bipartite: bool = False) numpy.ndarray[source]

Extract the connected components of a graph.

Parameters
• input_matrix – Input matrix (either the adjacency matrix or the biadjacency matrix of the graph).

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

• force_bipartite (bool) – If `True`, consider the input matrix as the biadjacency matrix of a bipartite graph.

Returns

Connected component of each node. For bipartite graphs, rows and columns are concatenated (rows first).

Return type

labels

Example

```>>> from sknetwork.topology import get_connected_components
>>> from sknetwork.data import house
>>> get_connected_components(house())
array([0, 0, 0, 0, 0], dtype=int32)
```
sknetwork.topology.is_connected(input_matrix: scipy.sparse._csr.csr_matrix, connection: str = 'weak', force_bipartite: bool = False) bool[source]

Check whether the graph is connected.

Parameters
• input_matrix – Input matrix (either the adjacency matrix or the biadjacency matrix of the graph).

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

• force_bipartite (bool) – If `True`, consider the input matrix as the biadjacency matrix of a bipartite graph.

Example

```>>> from sknetwork.topology import is_connected
>>> from sknetwork.data import house
>>> is_connected(house())
True
```
sknetwork.topology.get_largest_connected_component(input_matrix: scipy.sparse._csr.csr_matrix, connection: str = 'weak', force_bipartite: bool = False, return_index: bool = False) Union[scipy.sparse._csr.csr_matrix, Tuple[scipy.sparse._csr.csr_matrix, numpy.ndarray]][source]

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

Parameters

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

• force_bipartite (bool) – If `True`, consider the input matrix as the biadjacency matrix of a bipartite graph.

• return_index (bool) – Whether to return the index of the nodes of the largest connected component in the original graph.

Returns

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

• index (array) – Indices of the nodes in the original graph. For bipartite graphs, rows and columns are concatenated (rows first).

Example

```>>> from sknetwork.topology import get_largest_connected_component
>>> from sknetwork.data import house
>>> get_largest_connected_component(house()).shape
(5, 5)
```

Structure

Check whether a graph is bipartite.

Parameters

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

Example

```>>> from sknetwork.topology import is_bipartite
>>> from sknetwork.data import cyclic_graph
>>> is_bipartite(cyclic_graph(4))
True
>>> is_bipartite(cyclic_graph(3))
False
```
sknetwork.topology.is_acyclic(adjacency: scipy.sparse._csr.csr_matrix, directed: Optional[bool] = None) bool[source]

Check whether a graph has no cycle.

Parameters

• directed – Whether to consider the graph as directed (inferred if not specified).

Returns

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

Return type

bool

Example

```>>> from sknetwork.topology import is_acyclic
>>> from sknetwork.data import star, grid
>>> is_acyclic(star())
True
>>> is_acyclic(grid())
False
```
class sknetwork.topology.DAG(ordering: Optional[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 algorithm to the data.

Parameters

• 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]`.

Core decomposition

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()
>>> kcore.core_value_
4
```

K-core decomposition.

Parameters

Returns

self

Return type

`CoreDecomposition`

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

Cliques

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()
45
```

Count triangles.

Parameters

Returns

self

Return type

`Triangles`

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.

Parameters

k (int) – Clique order (e.g., k = 3 means triangles).

Variables

n_cliques_ (int) – Number of cliques.

Example

```>>> from sknetwork.data import karate_club
>>> cliques = Cliques(k=3)
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).

K-cliques count.

Parameters

Returns

self

Return type

`Cliques`

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

Isomorphism

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()
>>> labels
array([0, 2, 1, 1, 2], dtype=int32)
```

References

Fit algorithm to the data.

Parameters

Returns

self

Return type

`WeisfeilerLehman`

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

Returns

labels – Labels.

Return type

np.ndarray

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

Parameters

• 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, bow_tie
>>> are_isomorphic(house(), bow_tie())
False
```

References