Topology
Functions related to 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
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: 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).
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
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
Core decomposition
- class sknetwork.topology.get_core_decomposition
Get the k-core decomposition of a graph.
- Parameters
adjacency – 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
Count the number of triangles in a graph.
- Parameters
adjacency – Adjacency matrix of the graph.
parallelize – 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
Get the clustering coefficient of a graph.
- Parameters
adjacency – Adjacency matrix of the graph.
parallelize – 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
Count the number of cliques of some size.
- Parameters
adjacency – 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: Union[scipy.sparse._csr.csr_matrix, numpy.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: 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.
- 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.