<jupyter_start><jupyter_text>Introduction; Machine Learning for Graphs<jupyter_code>import random
from typing import List, Optional

import matplotlib.pyplot as plt
import networkx as nx
import numpy as np
def seed_everything(seed: Optional[int] = None) -> None:
    random.seed(seed)
    np.random.seed(seed)


seed_everything(42)<jupyter_output><empty_output><jupyter_text>Components of a Network<jupyter_code>edge_list = [(0, 1), (1, 2), (1, 3), (2, 3), (3, 4), (3, 5), (5, 6), (5, 7)]
G = nx.Graph(edge_list)
nx.draw(G, node_color="tab:blue", node_size=400, width=3)
G.nodes
G.edges<jupyter_output><empty_output><jupyter_text>Directed vs. Unidirected Graphs  Undirected<jupyter_code>edge_list = [
    ("A", "D"),
    ("B", "B"),
    ("B", "D"),
    ("C", "D"),
    ("C", "D"),
    ("D", "F"),
    ("F", "G"),
    ("G", "H"),
    ("H", "I"),
    ("L", "M"),
]
G = nx.Graph(edge_list)

plt.figure(figsize=(4, 3))
# NetworkX does not represent multiple edges between two nodes well
nx.draw(G, node_color="tab:orange", node_size=150, with_labels=True)<jupyter_output><empty_output><jupyter_text>Directed<jupyter_code>edge_list = [("A", "B"), ("A", "C"), ("B", "A"), ("B", "C"), ("D", "C"), ("E", "D"), ("F", "E"), ("G", "F")]
G = nx.MultiDiGraph(edge_list)

plt.figure(figsize=(4, 3))
nx.draw(G, node_color="tab:blue", with_labels=True, connectionstyle="arc3, rad = 0.1")<jupyter_output><empty_output><jupyter_text>Heterogeneous Graphs<jupyter_code>edge_list = [
    ("Marge", "Homer", {"relation_type": "Married"}),
    ("Marge", "Lisa", {"relation_type": "First degree relatives"}),
    ("Marge", "Bart", {"relation_type": "First degree relatives"}),
    ("Marge", "Maggie", {"relation_type": "First degree relatives"}),
    ("Homer", "Lisa", {"relation_type": "First degree relatives"}),
    ("Homer", "Bart", {"relation_type": "First degree relatives"}),
    ("Homer", "Maggie", {"relation_type": "First degree relatives"}),
    ("Lisa", "Bart", {"relation_type": "Sibling"}),
    ("Lisa", "Maggie", {"relation_type": "Sibling"}),
    ("Bart", "Maggie", {"relation_type": "Sibling"}),
]
G = nx.Graph(edge_list)
node_attributes = {
    "Marge": {"node_type": "Adult"},
    "Homer": {"node_type": "Adult"},
    "Lisa": {"node_type": "Child"},
    "Bart": {"node_type": "Child"},
    "Maggie": {"node_type": "Child"},
}
nx.set_node_attributes(G, node_attributes)

node_type_to_color = {"Adult": "tab:blue", "Child": "tab:orange"}
node_colors = [node_type_to_color[node_type] for label, node_type in nx.get_node_attributes(G, "node_type").items()]
pos = nx.spring_layout(G)
edge_labels = nx.get_edge_attributes(G, "relation_type")

plt.figure(figsize=(8, 6))
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
nx.draw(G, pos=pos, node_color=node_colors, node_size=2500, with_labels=True)<jupyter_output><empty_output><jupyter_text>Node Degrees  Undirected<jupyter_code>edge_list = [
    (0, 1),
    (2, 3),
    (3, 4),
    (5, 6),
    (6, 7),
    (8, 9),
    (9, 10),
    (10, "A"),
    (10, 12),
    ("A", 12),
    ("A", 13),
    ("A", 14),
    (13, 14),
    (14, 15),
]
G = nx.Graph(edge_list)
avg_degree = 2 * G.number_of_edges() / G.number_of_nodes()

label_to_color = {10: "tab:blue", "A": "tab:orange", 12: "tab:blue", 13: "tab:blue", 14: "tab:blue"}
node_colors = [label_to_color.get(node, "tab:grey") for node in G.nodes()]

plt.figure(figsize=(4, 3))
nx.draw(G, node_size=150, node_color=node_colors, with_labels=True)
plt.show()

print(f"\nNode degree, kA: {G.degree['A']}")
print(f"Avg. degree: {avg_degree:.2f}")<jupyter_output><empty_output><jupyter_text>Directed<jupyter_code>edge_list = [("A", "B"), ("A", "C"), ("B", "A"), ("C", "B"), ("D", "C"), ("E", "D"), ("F", "E"), ("G", "F")]
G = nx.DiGraph(edge_list)
avg_degree = G.number_of_edges() / G.number_of_nodes()

label_to_color = {"C": "tab:orange"}
node_colors = [label_to_color.get(node, "tab:blue") for node in G.nodes()]

plt.figure(figsize=(4, 3))
nx.draw(G, node_size=150, node_color=node_colors, with_labels=True)
plt.show()

print(f"\nNode in-degree, kC: {G.in_degree['C']}")
print(f"Node out-degree, kC: {G.out_degree['C']}")
print(f"Node degree, kC: {G.degree['C']}")
print(f"Avg. degree: {avg_degree:.2f}")<jupyter_output><empty_output><jupyter_text>Bipartite Graph<jupyter_code>def draw_bipartite(
    G: nx.Graph,
    node1_color: str = "tab:orange",
    node2_color: str = "tab:blue",
    node1_shape: str = "o",
    node2_shape: str = "s",
    set1_name: str = "U",
    set2_name: str = "V",
    text_size: int = 16,
    font_weight: str = "bold",
) -> None:
    U, V = nx.bipartite.sets(G)
    len_U = len(U)
    len_V = len(V)
    len_max = max(len_U, len_V)
    offset = (len_U - len_V) / 2

    pos = dict()
    pos.update((n, (1, i)) for i, n in enumerate(sorted(U, reverse=True), 1)) # put nodes from U at x=1
    pos.update((n, (2, i + offset)) for i, n in enumerate(sorted(V, reverse=True), 1)) # put nodes from V at x=2

    nx.draw_networkx_nodes(U, pos=pos, node_color=node1_color, node_shape=node1_shape)
    nx.draw_networkx_nodes(V, pos=pos, node_color=node2_color, node_shape=node2_shape)
    nx.draw_networkx_labels(G, pos=pos)
    nx.draw_networkx_edges(G, pos=pos, width=2)

    plt.text(0.95, len_max + 0.75, set1_name, size=text_size, fontweight=font_weight)
    plt.text(1.95, len_max + 0.75, set2_name, size=text_size, fontweight=font_weight)

    plt.axis("off")
G = nx.Graph()
# Add nodes with the node attribute "bipartite"
G.add_nodes_from(["A", "B", "C", "D", "E"], bipartite=0)
G.add_nodes_from([1, 2, 3, 4], bipartite=1)
# Add edges only between nodes of opposite node sets
G.add_edges_from([("A", 1), ("A", 2), ("B", 1), ("B", 3), ("C", 3), ("D", 2), ("D", 4), ("E", 4)])

plt.figure(figsize=(3, 4))
draw_bipartite(G)
plt.show()<jupyter_output><empty_output><jupyter_text>Folded/Projected Bipartite Graphs<jupyter_code>G = nx.Graph()
# Add nodes with the node attribute "bipartite"
G.add_nodes_from([1, 2, 3, 4, 5, 6, 7], bipartite=0)
G.add_nodes_from(["A", "B", "C", "D"], bipartite=1)
# Add edges only between nodes of opposite node sets
G.add_edges_from([(1, "A"), (2, "A"), (2, "B"), (3, "A"), (4, "C"), (5, "B"), (5, "C"), (5, "D"), (6, "D"), (7, "D")])

U, V = nx.bipartite.sets(G)
U_proj = nx.algorithms.bipartite.projected_graph(G, V)
V_proj = nx.algorithms.bipartite.projected_graph(G, U)

plt.figure(figsize=(9, 4))

plt.subplot(131)
plt.title("Projection U", size=16, fontweight="bold")
nx.draw(V_proj, with_labels=True, node_color="tab:orange", node_shape="o")

plt.subplot(132)
draw_bipartite(G)

plt.subplot(133)
plt.title("Projection V", size=16, fontweight="bold")
nx.draw(U_proj, with_labels=True, node_color="tab:blue", node_shape="s")

plt.show()<jupyter_output><empty_output><jupyter_text>Representing Graphs: Adjacency Matrix  Undirected<jupyter_code>edge_list = [(1, 2), (1, 4), (2, 4), (4, 3)]
G = nx.Graph(edge_list)
A = nx.adjacency_matrix(G).todense()
ki = A.sum(axis=0).flatten()
kj = A.sum(axis=1).flatten()
L = 0.5 * ki.sum()

plt.figure(figsize=(3, 2))
nx.draw(G, node_color="tab:orange", node_size=500, width=2, with_labels=True)
plt.show()

print(f"\nA:\n{A}")
print(f"\nki: {ki}")
print(f"kj: {kj}")
print(f"# of edges (L): {L}")<jupyter_output><empty_output><jupyter_text>Directed<jupyter_code>edge_list = [(1, 4), (2, 1), (4, 2), (4, 3)]
G = nx.DiGraph(edge_list)
A = nx.adjacency_matrix(G).todense()
ki_out = A.sum(axis=1).flatten()
kj_in = A.sum(axis=0).flatten()
L = kj_in.sum()

plt.figure(figsize=(3, 2))
nx.draw(G, node_color="tab:orange", node_size=500, width=2, with_labels=True)
plt.show()

print(f"\nA:\n{A}")
print(f"\nki_out: {ki_out}")
print(f"kj_in: {kj_in}")
print(f"# of edges (L): {L}")<jupyter_output><empty_output><jupyter_text>Representing Graphs: Edge list<jupyter_code>edge_list = [(2, 3), (2, 4), (3, 2), (3, 4), (4, 5), (5, 2), (5, 1)]
G = nx.DiGraph(edge_list)

plt.figure(figsize=(3, 2))
nx.draw(G, node_color="tab:orange", node_size=500, width=2, with_labels=True)
A = nx.adjacency_matrix(G)
plt.show()

print(f"\nEdge list: {G.edges}")<jupyter_output><empty_output><jupyter_text>Representing Graphs: Adjacency list<jupyter_code>def print_adjacency_list(G: nx.Graph) -> None:
    print("Adjacency list:")
    for item in sorted(nx.generate_adjlist(G)):
        item = item.split(" ")
        key = item[0]
        values = ", ".join(item[1:])
        print(f"{key}: {values}")
edge_list = [(2, 3), (2, 4), (3, 2), (3, 4), (4, 5), (5, 2), (5, 1)]
G = nx.DiGraph(edge_list)

plt.figure(figsize=(3, 2))
nx.draw(G, node_color="tab:orange", node_size=500, width=2, with_labels=True)
plt.show()

print()
print_adjacency_list(G)<jupyter_output><empty_output><jupyter_text>More Types of Graphs  Unweighted(undirected)<jupyter_code>edge_list = [(1, 2), (1, 3), (2, 3), (2, 4)]
G = nx.Graph(edge_list)
A = nx.adjacency_matrix(G).todense()
E = A.sum() / 2
avg_degree = 2 * E / G.number_of_nodes()

plt.figure(figsize=(3, 2))
nx.draw(G, node_color="tab:orange", node_size=500, width=2, with_labels=True)
plt.show()

print(f"\nA:\n{A}")
print(f"\nAvg. degree: {avg_degree:.2f}")<jupyter_output><empty_output><jupyter_text>Weighted(undirected)<jupyter_code>edge_list = [(1, 2, {"weight": 2}), (1, 3, {"weight": 0.5}), (2, 3, {"weight": 1}), (2, 4, {"weight": 4})]
G = nx.Graph(edge_list)
A = nx.adjacency_matrix(G).todense()
E = A.sum() / 2
avg_degree = 2 * E / G.number_of_nodes()

width = list(nx.get_edge_attributes(G, "weight").values())

plt.figure(figsize=(3, 2))
nx.draw(G, node_color="tab:orange", node_size=500, width=width, with_labels=True)
plt.show()

print(f"\nA:\n{A}")
print(f"\nAvg. degree: {avg_degree:.2f}")<jupyter_output><empty_output><jupyter_text>Self-edges (self-loops)(undirected)<jupyter_code>edge_list = [(1, 1), (1, 2), (1, 3), (2, 3), (2, 4), (4, 4)]
G = nx.Graph(edge_list)
A = nx.adjacency_matrix(G).todense()
E = 0.5 * (A.sum() + np.diagonal(A).sum())
avg_degree = 2 * E / G.number_of_nodes()

plt.figure(figsize=(3, 2))
nx.draw(G, node_color="tab:orange", node_size=500, width=2, with_labels=True)
plt.show()

print(f"\nA:\n{A}")
print(f"\nAvg. degree: {avg_degree:.2f}")<jupyter_output><empty_output><jupyter_text>Multigraph(undirected)<jupyter_code>edge_list = [(1, 2), (1, 2), (1, 3), (2, 3), (2, 4), (2, 4), (2, 4)]
G = nx.MultiGraph(edge_list)
A = nx.adjacency_matrix(G).todense()
E = 0.5 * A.sum()
avg_degree = 2 * E / G.number_of_nodes()

plt.figure(figsize=(3, 2))
nx.draw(G, node_color="tab:orange", node_size=500, width=2, with_labels=True)
plt.show()

print(f"\nA:\n{A}")
print(f"\nAvg. degree: {avg_degree:.2f}")<jupyter_output><empty_output><jupyter_text>Connectivity of Undirected Graphs  Connected<jupyter_code>edge_list = [("A", "B"), ("A", "C"), ("A", "D"), ("A", "F"), ("B", "C"), ("F", "G"), ("F", "H"), ("G", "H")]
G = nx.Graph(edge_list)

plt.figure(figsize=(3, 2))
nx.draw(G, node_color="tab:orange", node_size=150, width=2, with_labels=True)
plt.show()<jupyter_output><empty_output><jupyter_text>Disconnected<jupyter_code>edge_list = [("A", "B"), ("A", "C"), ("A", "D"), ("B", "C"), ("F", "G")]
G = nx.Graph(edge_list)
G.add_node("H")
connected_components = sorted(nx.connected_components(G), key=len, reverse=True)
giant_component = connected_components[0]
isolated_nodes = [cc for cc in connected_components if len(cc) == 1]

plt.figure(figsize=(3, 2))
nx.draw(G, node_color="tab:orange", node_size=150, width=2, with_labels=True)
plt.show()

print(f"\nGiant Component: {giant_component}")
print(f"Isolated nodes: {isolated_nodes}")<jupyter_output><empty_output><jupyter_text>Connectivity: Example  Disconnected<jupyter_code>edge_list = [(1, 2), (1, 3), (2, 3), (4, 7), (5, 6), (5, 7), (6, 7)]
G = nx.Graph(edge_list)
A = nx.adjacency_matrix(G).todense()

node_colors = ["tab:orange" if node in {1, 2, 3} else "tab:blue" for node in G.nodes]

plt.figure(figsize=(6, 2))
nx.draw(G, node_color=node_colors, node_size=500, width=2, with_labels=True)
plt.show()

print(f"\nA:\n{A}")<jupyter_output><empty_output><jupyter_text>Connected<jupyter_code>edge_list = [(1, 2), (1, 3), (2, 3), (2, 4), (4, 7), (5, 6), (5, 7), (6, 7)]
G = nx.Graph(edge_list)
A = nx.adjacency_matrix(G).todense()

node_colors = ["tab:orange" if node in {1, 2, 3} else "tab:blue" for node in G.nodes]
edge_colors = ["tab:red" if edge == (2, 4) else "black" for edge in G.edges]

plt.figure(figsize=(6, 2))
nx.draw(G, node_color=node_colors, node_size=500, edge_color=edge_colors, width=2, with_labels=True)
plt.show()

print(f"\nA:\n{A}")<jupyter_output><empty_output><jupyter_text>Connectivity of Directed Graphs<jupyter_code>edge_list = [("A", "B"), ("B", "C"), ("C", "A"), ("E", "A"), ("A", "D"), ("B", "F"), ("G", "C")]
G = nx.DiGraph(edge_list)

plt.figure(figsize=(6, 2))
nx.draw(G, node_color="tab:orange", node_size=500, width=2, with_labels=True)
plt.show()

print(f"\nIs strongly connected? {nx.is_strongly_connected(G)}")
print(f"Is weakly connected? {nx.is_weakly_connected(G)}")
def get_strongly_connected_components(G: nx.Graph) -> List[dict]:
    return sorted([scc for scc in nx.strongly_connected_components(G) if len(scc) > 1], key=len, reverse=True)
edge_list1 = [
    ("A", "B"),
    ("A", "D"),
    ("B", "C"),
    ("C", "A"),
    ("E", "A"),
    ("A", "D"),
    ("G", "E"),
    ("E", "F"),
    ("F", "G"),
]
G1 = nx.DiGraph(edge_list1)
SCCs1 = get_strongly_connected_components(G1)

edge_list2 = [("A", "B"), ("B", "C"), ("C", "A"), ("E", "A"), ("A", "D"), ("B", "F"), ("G", "C")]
G2 = nx.DiGraph(edge_list2)
SCCs2 = get_strongly_connected_components(G2)

plt.figure(figsize=(10, 6))

plt.subplot(121)
nx.draw(G1, edgecolors="tab:red", node_color="none", node_size=500, width=2, with_labels=True)

plt.subplot(122)
nx.draw(G2, edgecolors="tab:red", node_color="none", node_size=500, width=2, with_labels=True)

plt.show()

print(f"\nG1 strongly connected components (excluding isolated nodes): {SCCs1}")
print(f"G2 strongly connected components (excluding isolated nodes): {SCCs2}")<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.22315532586850417, 'fraction_numerical': 0.03172552397358599, 'mean_word_length': 5.918073485600795, 'pattern_counts': {'":': 28, '<': 89, '<?xml version=': 0, '>': 94, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 26, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '22', 'dir': 'jupyter-structured-clean-dedup', 'id': '367004', 'license': 'MIT', 'n_tokens_mistral': 6291, 'n_tokens_neox': 5935, 'n_words': 1188, 'path': 'notebooks/01-introduction-machine-learning-for-graphs.ipynb', 'repo_name': 'mnslarcher/cs224w-slides-to-code', 'size': '13932'}