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
Douglas, B. L. (2011). The Weisfeiler-Lehman Method and Graph Isomorphism Testing.
Shervashidze, N., Schweitzer, P., van Leeuwen, E. J., Melhorn, K., Borgwardt, K. M. (2011) Weisfeiler-Lehman graph kernels. Journal of Machine Learning Research 12, 2011.
- 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
Douglas, B. L. (2011). The Weisfeiler-Lehman Method and Graph Isomorphism Testing.
Shervashidze, N., Schweitzer, P., van Leeuwen, E. J., Melhorn, K., Borgwardt, K. M. (2011) Weisfeiler-Lehman graph kernels. Journal of Machine Learning Research 12, 2011.