A5.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "bfbbb352",
   "metadata": {},
   "source": [
    "# Assignment 5: Network Models and Statistical Analysis"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "cab11e82",
   "metadata": {},
   "outputs": [],
   "source": [
    "import networkx as nx\n",
    "from networkx.algorithms.community import louvain_communities\n",
    "import numpy as np\n",
    "\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "from typing import Tuple, List, Dict, Union"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "47d6ba46",
   "metadata": {},
   "source": [
    "## Part 1: Structural Properties of the Graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "9c0d210c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def load_football_graph() -> nx.Graph:    \n",
    "    G = nx.read_gml(\"football.gml\")\n",
    "    return G    "
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "f777a5c8",
   "metadata": {},
   "source": [
    "### 1.1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4ea39834",
   "metadata": {},
   "outputs": [],
   "source": [
    "def calculate_graph_statistics(G: nx.Graph) -> Dict[str, Union[float, List[int]]]:\n",
    "    \"\"\"\n",
    "    Inputs:\n",
    "    G: NetworkX graph object\n",
    "    \n",
    "    Returns:\n",
    "    Dictionary of graph statistics\n",
    "    \n",
    "    \"\"\"\n",
    "    \n",
    "    return graph_statistics"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "9169b13e",
   "metadata": {},
   "source": [
    "### 1.2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "426dea1f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sweep_louvain_resolutions(G: nx.Graph, min_resolution: int=1, max_resolution: int=10) -> Tuple[List[int], List[float]]:\n",
    "    \"\"\"\n",
    "    Inputs:\n",
    "    G: NetworkX graph object\n",
    "    min_resolution : integer\n",
    "    max_resolution : integer\n",
    "    \n",
    "    Returns:\n",
    "    Tuple of list of resolutions and list of NMIs\n",
    "    \n",
    "    \"\"\"\n",
    "\n",
    "\n",
    "    return resolutions, nmis\n",
    "\n",
    "\n",
    "def plot_nmi_vs_resolution(resolutions: List[int], nmis: List[float], save: bool=False) -> None:\n",
    "    \"\"\"\n",
    "    Inputs:\n",
    "    min_resolution : integer\n",
    "    max_resolution : integer\n",
    "    save: boolean\n",
    "    \n",
    "    Returns:\n",
    "    None\n",
    "    \n",
    "    \"\"\"\n",
    "    \n",
    "\n",
    "\n",
    "    if save:\n",
    "        plt.savefig('1_2_1.png')\n",
    "\n",
    "    plt.show()"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "2f229030",
   "metadata": {},
   "source": [
    "### 1.3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4986ef32",
   "metadata": {},
   "outputs": [],
   "source": [
    "def calculate_best_partition(G: nx.Graph, resolutions: List[int], nmis: List[float]) -> Tuple[int, List[str]]:\n",
    "    \"\"\"\n",
    "    Inputs:\n",
    "    G: NetworkX graph object\n",
    "    resolutions : a list of integer\n",
    "    nmis :a list of float\n",
    "    \n",
    "    Returns:\n",
    "    Tuple of resolution and partition\n",
    "    \n",
    "    \"\"\"\n",
    "\n",
    "\n",
    "    return resolution, partition\n",
    "\n",
    "def plot_best_partition(G: nx.Graph, partition: List[str], save: bool=False) -> None:\n",
    "    \"\"\"\n",
    "    Inputs:\n",
    "    G: NetworkX graph object\n",
    "    partition : List[str]\n",
    "    save: boolean\n",
    "    \n",
    "    Returns:\n",
    "    None\n",
    "    \n",
    "    \"\"\"\n",
    "\n",
    "\n",
    "    if save:\n",
    "        plt.savefig('1_2_2.png')\n",
    "\n",
    "    plt.show()"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "de52560b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def calculate_inter_community_density(G: nx.Graph, partition: list) -> Tuple[np.ndarray, List[int]]:\n",
    "    \"\"\"\n",
    "    Inputs:\n",
    "    G: NetworkX graph object\n",
    "    partition : list\n",
    "    \n",
    "    Returns:\n",
    "    Tuple of np array and List[int], intercommunity connection density matrix\n",
    "    \n",
    "    \"\"\"\n",
    "\n",
    "\n",
    "    return p, sizes\n",
    "\n",
    "def plot_p_matrix(p: np.ndarray, save: bool=False):\n",
    "    \"\"\"\n",
    "    Inputs:\n",
    "    p: np array, intercommunity connection density matrix\n",
    "    save: boolean\n",
    "    \n",
    "    Returns:\n",
    "    None\n",
    "    \"\"\"\n",
    "    \n",
    "\n",
    "    if save:\n",
    "        plt.savefig('1_3.png')\n",
    "\n",
    "    plt.show()"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "0c11a046",
   "metadata": {},
   "source": [
    "### 1.5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Run the code in the 1.5 cell. How does the resolution impact the NMI? Is the partition for the best NMI a good match to the ground truth? Justify your answer based on the visual plot and the NMI value itself."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "eaf4ea0e",
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "1.5 cell\n",
    "\"\"\"\n",
    "G = load_football_graph()\n",
    "\n",
    "# 1.1\n",
    "graph_stats = calculate_graph_statistics(G)\n",
    "\n",
    "# 1.2 \n",
    "resolutions, nmis = sweep_louvain_resolutions(G)\n",
    "best_resolution, partition = calculate_best_partition(G, resolutions, nmis)\n",
    "plot_nmi_vs_resolution(resolutions, nmis)\n",
    "plot_best_partition(G, partition)\n",
    "\n",
    "# 1.3\n",
    "p, sizes = calculate_inter_community_density(G, partition)\n",
    "plot_p_matrix(p)\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "6f30dbc0",
   "metadata": {},
   "source": [
    "### 1.5 Written Response\n",
    "\n",
    "Answer:"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "ee2dd50b",
   "metadata": {},
   "source": [
    "## Part 2: Graph Generators\n",
    "### 2.1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "428ad247",
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_configuration_graphs(degree_sequence: List[int], n_graphs: int=100) -> List[nx.Graph]:\n",
    "    \"\"\"\n",
    "    Inputs:\n",
    "    degree_sequence: List[int]\n",
    "    n_graphs: int\n",
    "    \n",
    "    Returns:\n",
    "    a list of graph\n",
    "    \"\"\"\n",
    "    \n",
    "\n",
    "    return graphs\n",
    "\n",
    "def generate_sbm_graphs(p: np.ndarray, sizes: List[int], n_graphs: int=100) -> List[nx.Graph]:\n",
    "    \"\"\"\n",
    "    Inputs:\n",
    "    p: np.ndarray, element (r,s) gives the density of edges going from the nodes of group r to nodes of group s.\n",
    "    degree_sequence: List[int]\n",
    "    n_graphs: int\n",
    "    \n",
    "    Returns:\n",
    "    a list of graph\n",
    "    \"\"\"\n",
    "\n",
    "\n",
    "    return graphs\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "81fee1af",
   "metadata": {},
   "source": [
    "### 2.2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "973fb500",
   "metadata": {},
   "outputs": [],
   "source": [
    "def calculate_edge_probability(dendrogram: nx.DiGraph) -> Dict[str, Dict[str, float]]:\n",
    "    \"\"\"\n",
    "    Inputs:\n",
    "    dendrogram: NetworkX graph object    \n",
    "    \n",
    "    Returns:\n",
    "    a dictionary of edge probabilities between all pairs of leaf nodes.\n",
    "    \"\"\"\n",
    "    \n",
    "\n",
    "\n",
    "    return edge_probs\n",
    "\n",
    "def generate_graph_from_prob(edge_probs: Dict[str, Dict[str, float]]) -> nx.Graph:\n",
    "    \"\"\"\n",
    "    Inputs:\n",
    "    edge_probs: a dictionary of edge probabilities between all pairs of leaf nodes.\n",
    "    \n",
    "    Returns:\n",
    "    H: NetworkX graph object\n",
    "    \"\"\"\n",
    "\n",
    "\n",
    "    return H\n",
    "\n",
    "def generate_hrg_graphs(edge_probs: Dict[str, Dict[str, float]], n_graphs: int=100) -> List[nx.Graph]:\n",
    "    \"\"\"\n",
    "    Inputs:\n",
    "    edge_probs: a dictionary of edge probabilities between all pairs of leaf nodes.\n",
    "    n_graphs: int\n",
    "    \n",
    "    Returns:\n",
    "    a list of NetworkX graph object\n",
    "    \"\"\"\n",
    "\n",
    "\n",
    "    return graphs"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "783ca711",
   "metadata": {},
   "source": [
    "### 2.3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "319ff4ba",
   "metadata": {},
   "outputs": [],
   "source": [
    "def calculate_generated_statistics(graphs: List[nx.Graph]) -> Dict[str, list]:\n",
    "    \"\"\"\n",
    "    Inputs:\n",
    "    graphs: a list of NetworkX graph object\n",
    "    \n",
    "    Returns:\n",
    "    a dictionary of graph statistics\n",
    "    \"\"\"\n",
    "\n",
    "\n",
    "    return graph_statistics\n",
    "\n",
    "def compare_generated_to_ground_truth(ground_truth_features: Dict[str, float], generated_features: Dict[str, List[float]]) -> Dict[str, float]:\n",
    "    \"\"\"\n",
    "    Inputs:\n",
    "    ground_truth_features: a dictionary of graph statistics\n",
    "    generated_features: a dictionary of graph statistics\n",
    "    \n",
    "    Returns:\n",
    "    a dictionary of one-sample t-test\n",
    "    \"\"\"\n",
    "\n",
    "\n",
    "    return p_vals\n",
    "\n",
    "\n",
    "def plot_graph_statistics(graph_statistics: List[Dict[str, list]], save: bool=False) -> None:\n",
    "    \"\"\"\n",
    "    Inputs:\n",
    "    graph_statistics: a dictionary of graph statistics\n",
    "    \n",
    "    Returns:\n",
    "    None\n",
    "    \"\"\"\n",
    "\n",
    "\n",
    "    if save:\n",
    "        plt.savefig('2_3.png')\n",
    "\n",
    "    plt.show()"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "96edf829",
   "metadata": {},
   "source": [
    "### 2.4\n",
    "This code reruns some calculations from 1.5 to avoid errors, but you can comment it out if you already have the values stored in memory."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b3a1eea1",
   "metadata": {},
   "outputs": [],
   "source": [
    "G = load_football_graph()\n",
    "graph_stats = calculate_graph_statistics(G)\n",
    "\n",
    "# Configuration Model\n",
    "config_graphs = generate_configuration_graphs(graph_stats['degree_sequence'])\n",
    "\n",
    "# Stochastic Block Model\n",
    "resolutions, nmis = sweep_louvain_resolutions(G)\n",
    "best_resolution, partition = calculate_best_partition(G, resolutions, nmis)\n",
    "p, sizes = calculate_inter_community_density(G, partition)\n",
    "sbm_graphs = generate_sbm_graphs(p, sizes)\n",
    "\n",
    "# Hierarchical Random Graph Model\n",
    "dendrogram = nx.read_gml(\"football-hrg.gml\")\n",
    "edge_probs = calculate_edge_probability(dendrogram)\n",
    "hrg_graphs = generate_hrg_graphs(edge_probs)\n",
    "\n",
    "# Calculating network characteristic statistics\n",
    "config_stats = calculate_generated_statistics(config_graphs)\n",
    "sbm_stats = calculate_generated_statistics(sbm_graphs)\n",
    "hrg_stats = calculate_generated_statistics(hrg_graphs)\n",
    "\n",
    "# Hypothesis Test Stats\n",
    "print('Configuration Model t-test')\n",
    "print(compare_generated_to_ground_truth(graph_stats, config_stats))\n",
    "\n",
    "print('Stochastic Block Model t-test')\n",
    "print(compare_generated_to_ground_truth(graph_stats, sbm_stats))\n",
    "\n",
    "print('HRG Model t-test')\n",
    "print(compare_generated_to_ground_truth(graph_stats, hrg_stats))\n",
    "\n",
    "plot_graph_statistics([graph_stats, config_stats, sbm_stats, hrg_stats])"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "e37c5e0f",
   "metadata": {},
   "source": [
    "### 2.4 Written Response\n",
    "\n",
    "Answer: "
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "dcfd0af5",
   "metadata": {},
   "source": [
    "## Part 3: Slashdot Network"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "09eadd6c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def load_slashdot_graph() -> nx.Graph:\n",
    "    # import \"slashdot.txt\"\n",
    "    G = nx.read_edgelist(\"slashdot.txt\", delimiter=\"\\t\", create_using=nx.DiGraph)\n",
    "    G.remove_edges_from(nx.selfloop_edges(G))\n",
    "\n",
    "    return G"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "66bd4497",
   "metadata": {},
   "source": [
    "### 3.1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fc3dc5cc",
   "metadata": {},
   "outputs": [],
   "source": [
    "def estimate_network_size(G, sample_sizes: List[int]=[500, 1000, 2000, 5000, 10000], n_iter: int=1000) -> Dict[str, List[int]]:\n",
    "    \"\"\"\n",
    "    Inputs:\n",
    "    G: NetworkX graph object\n",
    "    sample_sizes: List[int]\n",
    "    n_iter: int\n",
    "\n",
    "    Returns:\n",
    "    a dictionary where key is the sample size and the value is a list of the estimated network sizes for each trial\n",
    "    \"\"\"\n",
    "\n",
    "\n",
    "    return results\n",
    "\n",
    "def plot_estimate_histogram(estimated_sizes: List[int], true_size: int, save: bool=False) -> None:\n",
    "    \"\"\"\n",
    "    Inputs:\n",
    "    estimated_sizes: List[int]\n",
    "    true_size: int\n",
    "    save:boolean\n",
    "\n",
    "    Returns:\n",
    "    None\n",
    "    \"\"\"\n",
    "\n",
    "\n",
    "    if save:\n",
    "        plt.savefig('3_1_1.png')\n",
    "\n",
    "    plt.show()\n",
    "\n",
    "def plot_sample_size_error(results: Dict[str, List[int]], true_size: int,\n",
    "                           sample_sizes: List[int]=[500, 1000, 2000, 5000, 10000], save: bool=False) -> None:\n",
    "    \"\"\"\n",
    "    Inputs:\n",
    "    results: Dict[str, List[int]]\n",
    "    true_size: int\n",
    "    sample_sizes: List[int]\n",
    "    save:boolean\n",
    "\n",
    "    Returns:\n",
    "    None\n",
    "    \"\"\"\n",
    "\n",
    "\n",
    "    if save:\n",
    "         plt.savefig('3_1_2.png')\n",
    "\n",
    "    plt.show()\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "97f18b7d",
   "metadata": {},
   "source": [
    "### 3.2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f177d82f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def estimate_edges(G: nx.Graph, n_sample: int=5000, n_iter: int=100) -> List[int]:\n",
    "    \"\"\"\n",
    "    Inputs:\n",
    "    G: NetworkX graph object\n",
    "    n_sample: int\n",
    "    n_iter: int\n",
    "\n",
    "    Returns:\n",
    "    a list of estimated_edges\n",
    "    \"\"\"\n",
    "\n",
    "\n",
    "    return estimated_edges\n",
    "\n",
    "def plot_edge_estimate_distribution(estimated_edges: List[int], true_edges: int, save: bool=False) -> None:\n",
    "    \"\"\"\n",
    "    Inputs:\n",
    "    estimated_edges: List[int]\n",
    "    true_edges: int\n",
    "    save: boolean\n",
    "\n",
    "    Returns:\n",
    "    None\n",
    "    \"\"\"\n",
    "\n",
    "\n",
    "    if save:\n",
    "        plt.savefig('3_2.png')\n",
    "\n",
    "    plt.show()"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "0e7d2dd9",
   "metadata": {},
   "source": [
    "### 3.3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "92c90d94",
   "metadata": {},
   "outputs": [],
   "source": [
    "G = load_slashdot_graph()\n",
    "\n",
    "network_size_estimates = estimate_network_size(G)\n",
    "\n",
    "plot_estimate_histogram(network_size_estimates[2000], len(G.nodes()))\n",
    "plot_sample_size_error(network_size_estimates, len(G.nodes()))\n",
    "\n",
    "edge_estimates = estimate_edges(G)\n",
    "plot_edge_estimate_distribution(edge_estimates, len(G.edges()))\n",
    "\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "ce2266da",
   "metadata": {},
   "source": [
    "### 3.3 Written Response\n",
    "\n",
    "Answer:"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.18"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}