<jupyter_start><jupyter_text>Graphs<jupyter_code>import numpy as np<jupyter_output><empty_output><jupyter_text>Definitions Path* $A \rightarrow B \iff \text{There is a path from A to B}$ Ancestor and Descendant* The nodes $A$ such that $A \rightarrow B$ and $B \nrightarrow A$ are the **ancestors** of B.* The nodes $A$ such that $A \nrightarrow B$ and $B \rightarrow A$ are the **descendants** of B. DAG* Graph $G$ is a DAG $\iff \forall A,B \in G, \big [ A \rightarrow B \iff (\text{A is an ancestor of B}) \land (\text{B is a descendant of A}) \big ]$ Family and Markov Blanket* The **family** of a node is  1. itself  2. its parents* The **Markov blanket** of a node is  1. its parents  2. its children  3. parents of its children (**excluding itself**)   Clique* Given an undirected graph, a **clique** is a fully connected subset of nodes. All the members of the clique are neighbors.  * A graph is **fully connected (complete)** iff each pair of vertices is connected by an edge.* For a maximal clique, there is no larger clique that contains the clique. Singly Connected Graph (Tree)* A graph is singly connected if there is only one path from any node $A$ to any node $B$.  Adjacency Matrix of a Directed GraphIf the nodes are labelled in ancestral (topological) order, then the corresponding adjacency matrix is upper triangular.  * Consider a row of the adjacency matrix. Since the nodes are labelled in topological order, all the nodes that receive an edge from the current node are listed below the current node. Hence, their indices must be greater than the current index. Then, each nonzero element in the current row must be after the diagonal entry. Since all nonzero entries on each row must come after the diagonal entry of that row, the resulting adjacency matrix must be upper-triangular.   Adjacency Matrix PowersFor an unweighted $N \times N$ adjacency matrix $A$, $\big[A^k_{ij}\big]$ specify how many paths there are from node $i$ to node $j$ in $k$ hops.This is related to Markov Chains and state transitions. Assume a person is standing at each node and that if a node contains multiple outgoing edges, this person gets cloned and goes to all the target nodes. Then, start from a single node and make state transitions. $k^{th}$ state corresponds to the row of the starting node in $A^k$.<jupyter_code>x = np.array([[0, 1, 0, 0],
              [0, 0, 1, 0],
              [0, 0, 0, 1],
              [0, 1, 0, 1]])
x
x@x
x@x@x<jupyter_output><empty_output><jupyter_text>Persons get cloned because the column sums of the adjacency matrix were not equal to 1. If we adjust the columns to get summed to 1, then column sums of $A^k$ are always 1, for $k \in \mathbb{Z}^+$, and nobody gets cloned. They get split up, or rather, be in certain nodes with certain probabilities.<jupyter_code>x = np.array([[0, 0.6, 0, 0],
              [0, 0, 1, 0],
              [1, 0, 0, 0.2],
              [0, 0.4, 0, 0.8]])
x
x@x
x@x@x<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.09249915909855365, 'fraction_numerical': 0.014799865455768583, 'mean_word_length': 3.7356687898089174, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 13, 'https://': 0, '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': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '540300', 'license': 'MIT', 'n_tokens_mistral': 923, 'n_tokens_neox': 864, 'n_words': 471, 'path': 'BRML/notebooks/chapter2.ipynb', 'repo_name': 'eozd/brml-notes', 'size': '2973'}