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

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.

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

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

Structure

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

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: 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(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].

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

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

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

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

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

References