<jupyter_start><jupyter_text>Connected Components Connected components are among the most basic, useful and important concepts ofgraph theory. It is common usage to decompose a graph into its connected components.If a graph is not connected, it can be divided into distinct connected components.Many properties, which involve computation of paths or communities, canbe computed independently on each connected component, thus enabling parallelexecution of numerous methods.Connected components were recently generalized to [stream graphs](https://arxiv.org/abs/1710.04073). These generalizedconnected components have a crucial feature: like graph connected componentsand unlike other generalizations available in the literature, they partition the set oftemporal nodes. This means that each node at each time instant is in one and only oneconnected component. This makes these generalized connected components particularlyappealing to capture important features of the vast variety of objects modeledby stream graphs.<jupyter_code>path_directory = "examples/"
S = sg.read_stream_graph(path_nodes=path_directory + "example_nodes.sg",
                         path_links=path_directory + "example_links.sg")<jupyter_output><empty_output><jupyter_text>Weakly Connected Components In a Stream Graph, $S = (T,V,W,E)$, weakly connected components represent elements of $W$connected together without any constraint on time.Intuitively, the weakly connected components correspond to the disconnected partsof a drawing of a stream graph.<jupyter_code>wcc = S.weakly_connected_components()
_ = S.plot(clusters=wcc,title="Weakly Connected Components")<jupyter_output>findfont: Font family ['Garamond'] not found. Falling back to DejaVu Sans.<jupyter_text>These elements can be analysed separately toobserve and compute some properties, allowing a parallel implementation of several methods.  Strongly Connected Components Inside a strongly connected component all nodes are reachable from any other at anytime instant.This definition is consistent with the one used in graph theory: for any time instant, ifwe take the induced Graph $G_t$ the SCC at $t$ corresponds to the connected componentsof $G_t$.<jupyter_code>scc = S.strongly_connected_components(format = "cluster")
_ = S.plot(clusters=scc,title="Strongly Connected Components")<jupyter_output><empty_output><jupyter_text>Stable Connected Components A stable connected component is a cluster $C = (I,X)$, $I = [b,e]$, $X \in V$ where interactions between the nodes have begun before $b$ or at the same time and have ended after $e$ or at the same time.The decomposition into stable connected components is afiner grain decomposition of the stream graph than the one into strongly connectedcomponents.A stable connected component, $C = (I,X)$, can be reduced to a static graph $G_C = (X,E_C)$ spanning $I$.<jupyter_code>stcc = S.stable_connected_components(format = "cluster")
_ = S.plot(clusters=stcc,title="Stable Connected Components")<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.0650298606502986, 'fraction_numerical': 0.0029860650298606504, 'mean_word_length': 6.265060240963855, 'pattern_counts': {'":': 0, '<': 16, '<?xml version=': 0, '>': 16, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '389062', 'license': 'Apache-2.0', 'n_tokens_mistral': 780, 'n_tokens_neox': 747, 'n_words': 334, 'path': 'docs/notebooks/Connected Components.ipynb', 'repo_name': 'busyweaver/Straph', 'size': '3014'}