Topology

Functions related to graph topology.

Connectivity

sknetwork.topology.get_connected_components(input_matrix: csr_matrix, connection: str = 'weak', force_bipartite: bool = False) 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: 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: csr_matrix, connection: str = 'weak', force_bipartite: bool = False, return_index: bool = False) csr_matrix | Tuple[csr_matrix, ndarray][source]

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

Parameters:
  • input_matrix – Adjacency matrix or 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.

  • 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

sknetwork.topology.is_bipartite(adjacency: csr_matrix, return_biadjacency: bool = False) bool | Tuple[bool, csr_matrix | None, ndarray | None, ndarray | None][source]

Check whether a graph is bipartite.

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

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

Cycles

sknetwork.topology.is_acyclic(adjacency: csr_matrix, directed: bool | None = None) bool[source]

Check whether a graph has no cycle.

Parameters:
  • adjacency – Adjacency matrix of the graph.

  • 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
sknetwork.topology.get_cycles(adjacency: csr_matrix, directed: bool | None = None) List[List[int]][source]

Get all possible cycles of a graph.

Parameters:
  • adjacency – Adjacency matrix of the graph.

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

Returns:

cycles – List of cycles, each cycle represented as a list of nodes.

Return type:

list

Example

>>> from sknetwork.topology import get_cycles
>>> from sknetwork.data import cyclic_digraph
>>> graph = cyclic_digraph(4, metadata=True)
>>> get_cycles(graph.adjacency, directed=True)
[[0, 1, 2, 3]]
sknetwork.topology.break_cycles(adjacency: csr_matrix, root: int | List[int], directed: bool | None = None) csr_matrix[source]

Break cycles of a graph from given roots.

Parameters:
  • adjacency – Adjacency matrix of the graph.

  • root – The root node or list of root nodes to break cycles from.

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

Returns:

adjacency – Adjacency matrix of the acyclic graph.

Return type:

sparse.csr_matrix

Example

>>> from sknetwork.topology import break_cycles, is_acyclic
>>> from sknetwork.data import cyclic_digraph
>>> adjacency = cyclic_digraph(4)
>>> dag = break_cycles(adjacency, root=0, directed=True)
>>> is_acyclic(dag, directed=True)
True

Core decomposition

class sknetwork.topology.get_core_decomposition(adjacency: ndarray | csr_matrix)

Get the k-core decomposition of a graph.

Parameters:

adjacency (numpy.ndarray | scipy.sparse._csr.csr_matrix) – Adjacency matrix of the graph.

Returns:

Core value of each node.

Return type:

core_values

Example

>>> from sknetwork.data import karate_club
>>> adjacency = karate_club()
>>> core_values = get_core_decomposition(adjacency)
>>> len(core_values)
34

Triangles

class sknetwork.topology.count_triangles(adjacency: csr_matrix, parallelize: bool = False)

Count the number of triangles in a graph. The graph is considered undirected.

Parameters:
  • adjacency (scipy.sparse._csr.csr_matrix) – Adjacency matrix of the graph.

  • parallelize (bool) – If True, use a parallel range while listing the triangles.

Returns:

n_triangles – Number of triangles.

Return type:

int

Example

>>> from sknetwork.data import karate_club
>>> adjacency = karate_club()
>>> count_triangles(adjacency)
45
class sknetwork.topology.get_clustering_coefficient(adjacency: csr_matrix, parallelize: bool = False)

Get the clustering coefficient of a graph.

Parameters:
  • adjacency (scipy.sparse._csr.csr_matrix) – Adjacency matrix of the graph.

  • parallelize (bool) – If True, use a parallel range while listing the triangles.

Returns:

coefficient – Clustering coefficient.

Return type:

float

Example

>>> from sknetwork.data import karate_club
>>> adjacency = karate_club()
>>> np.round(get_clustering_coefficient(adjacency), 2)
0.26

Cliques

class sknetwork.topology.count_cliques(adjacency: csr_matrix, clique_size: int = 3)

Count the number of cliques of some size.

Parameters:
  • adjacency (scipy.sparse._csr.csr_matrix) – Adjacency matrix of the graph.

  • clique_size (int) – Clique size (default = 3, corresponding to triangles.

Returns:

n_cliques – Number of cliques.

Return type:

int

Example

>>> from sknetwork.data import karate_club
>>> adjacency = karate_club()
>>> count_cliques(adjacency, 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).

Isomorphism

class sknetwork.topology.color_weisfeiler_lehman(adjacency: csr_matrix | ndarray, max_iter: int = -1)[source]

Color nodes using Weisfeiler-Lehman algorithm.

Parameters:
  • adjacency (sparse.csr_matrix) – Adjacency matrix of the graph

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

Returns:

labels – Label of each node.

Return type:

np.ndarray

Example

>>> from sknetwork.data import house
>>> adjacency = house()
>>> labels = color_weisfeiler_lehman(adjacency)
>>> print(labels)
[0 2 1 1 2]

References

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

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

Parameters:
  • adjacency1 – First adjacency matrix.

  • adjacency2 – Second adjacency matrix.

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

Returns:

test_result

Return type:

bool

Example

>>> from sknetwork.data import house, bow_tie
>>> are_isomorphic(house(), bow_tie())
False

References