A3.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "53df3869",
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "import scipy\n",
    "import math\n",
    "\n",
    "import networkx as nx\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "import seaborn as sns\n",
    "\n",
    "from networkx.algorithms.community import k_clique_communities\n",
    "from networkx.algorithms.community import greedy_modularity_communities\n",
    "from networkx.algorithms.community import louvain_communities, louvain_partitions\n",
    "\n",
    "from sklearn.metrics.cluster import adjusted_rand_score\n",
    "from sklearn.metrics.cluster import mutual_info_score\n",
    "\n",
    "\n",
    "plt.rcParams.update({\n",
    "    \"figure.facecolor\":  (1.0, 1.0, 1.0, 1.0),  # red   with alpha = 30%\n",
    "    \"axes.facecolor\":    (1.0, 1.0, 1.0, 1.0),  # green with alpha = 50%\n",
    "    \"savefig.facecolor\": (1.0, 1.0, 1.0, 1.0),  # blue  with alpha = 20%\n",
    "})"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "0ab9b123",
   "metadata": {},
   "source": [
    "# Part 1: Centrality [30 points]"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "451dbc44",
   "metadata": {},
   "source": [
    "### 1.1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "426a96e6",
   "metadata": {},
   "outputs": [],
   "source": [
    "def load_graphs():\n",
    "    \"\"\"\n",
    "    \n",
    "    Returns:\n",
    "    G_airport: NetworkX Graph Object\n",
    "    G_yeast: NetworkX Graph Object\n",
    "    \n",
    "    \"\"\"\n",
    "\n",
    "    \n",
    "    return G_airport, G_yeast"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "7cf3e1fa",
   "metadata": {},
   "source": [
    "### 1.2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d4bb4c26",
   "metadata": {},
   "outputs": [],
   "source": [
    "def top_10_nodes(G):\n",
    "    \"\"\"\n",
    "    Inputs:\n",
    "    G: NetworkX Graph Object\n",
    "    \n",
    "    Returns:\n",
    "    top_10_nodes_dict: dict[list[int]]\n",
    "    \n",
    "    \"\"\"\n",
    "\n",
    "    top_10_nodes_dict = {\n",
    "                    'eigen': eigen,\n",
    "                    'katz': katz,\n",
    "                    'page_rank': page_rank,\n",
    "                    'closeness': closeness,\n",
    "                    'harmonic': harmonic,\n",
    "                    'betweeness': betweeness\n",
    "                    }\n",
    "\n",
    "\n",
    "\n",
    "    return top_10_nodes_dict \n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "8bc26e5b",
   "metadata": {},
   "source": [
    "### 1.3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5a7d7a4e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def calculate_similarity_matrix(top_nodes_dict):\n",
    "    \"\"\"\n",
    "    Inputs:\n",
    "    top_nodes_dict: dict[list[int]]\n",
    "    \n",
    "    Returns:\n",
    "    similarity_matrix: np.array\n",
    "    \n",
    "    \"\"\"\n",
    "\n",
    "\n",
    "\n",
    "    return similarity_matrix\n",
    "\n",
    "def plot_similarity_heatmap(similarity_matrix, data_name, save=False):\n",
    "    \"\"\"\n",
    "    Inputs:\n",
    "    similarity_matrix: np.array\n",
    "    data_name: str\n",
    "    \n",
    "    \"\"\"\n",
    "    plt.figure(figsize=(7, 7))\n",
    "\n",
    "\n",
    "\n",
    "    plt.show()\n",
    "    \n",
    "    if save:\n",
    "        plt.savefig(f'{data_name}_similarity_matrix.png')\n",
    "\n",
    "    plt.close()\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "ad45c5a0",
   "metadata": {},
   "source": [
    "### 1.4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bcac4f44",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Load the networks\n",
    "G_airport, G_yeast = load_graphs()\n",
    "\n",
    "# Get the top nodes\n",
    "top_airport_nodes = top_10_nodes(G_airport)\n",
    "top_yeast_nodes = top_10_nodes(G_yeast)\n",
    "\n",
    "# Generate the similarity matrcies\n",
    "node_similarity_airport = calculate_similarity_matrix(top_airport_nodes)\n",
    "node_similarity_yeast = calculate_similarity_matrix(top_yeast_nodes)\n",
    "\n",
    "# Generate the heatmaps\n",
    "plot_similarity_heatmap(node_similarity_airport, 'Airport')\n",
    "plot_similarity_heatmap(node_similarity_yeast, 'Yeast')\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "3be60c35",
   "metadata": {},
   "source": [
    "## Written Response for 1.4\n",
    "\n",
    "Answer:"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "43d443f7",
   "metadata": {},
   "source": [
    "# Part 2: Community Detection with Zachary’s Karate Club [25 points]"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "2532ba54",
   "metadata": {},
   "source": [
    "### 2.1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "12362e6e",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "def compute_cfinder_communities(G, k):\n",
    "    \"\"\"\n",
    "    Inputs: G: NetworkX Graph Object\n",
    "\n",
    "    Returns:\n",
    "    community_assignments: list[int]\n",
    "    \"\"\"\n",
    "\n",
    "\n",
    "    return community_assignments\n",
    "\n",
    "def compute_greedy_communities(G):\n",
    "    \"\"\"\n",
    "    Inputs: G: NetworkX Graph Object\n",
    "\n",
    "    Returns:\n",
    "    community_assignments: list[int]\n",
    "    \"\"\"\n",
    "\n",
    "\n",
    "    return community_assignments\n",
    "    \n",
    "\n",
    "def compute_louvain_communities(G):\n",
    "    \"\"\"\n",
    "    Inputs: G: NetworkX Graph Object\n",
    "\n",
    "    Returns:\n",
    "    community_assignments: list[int]\n",
    "    \"\"\"\n",
    "\n",
    "\n",
    "    return community_assignments\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "3ab4e8d7",
   "metadata": {},
   "source": [
    "### 2.2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "db4690e0",
   "metadata": {},
   "outputs": [],
   "source": [
    "def plot_network_communities(G, community_assignments, algorithm_name, save=False):\n",
    "    \"\"\"\n",
    "    Inputs:\n",
    "    G: NetworkX Graph Object\n",
    "    community_assignments: list[int]\n",
    "    algorithm_name: str\n",
    "    \"\"\"\n",
    "    random.seed(1)\n",
    "    np.random.seed(1)\n",
    "    \n",
    "    plt.figure(figsize=(5, 5))\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    plt.show()\n",
    "    if save:\n",
    "        plt.savefig(f'karate_communities_{algorithm_name}.png')\n",
    "    plt.close()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c6e155de",
   "metadata": {},
   "outputs": [],
   "source": [
    "G = nx.karate_club_graph()\n",
    "ground_truth = [0, 0, 0, 0, 0, \n",
    "                0, 0, 0, 1, 1, \n",
    "                0, 0, 0, 0, 1, \n",
    "                1, 0, 0, 1, 0, \n",
    "                1, 0, 1, 1, 1,\n",
    "                1, 1, 1, 1, 1,\n",
    "                1, 1, 1, 1]\n",
    "\n",
    "\n",
    "# Chose a reasonable value for k in the cfinder algorithm \n",
    "cfinder_assignments = compute_cfinder_communities(G, k=4)\n",
    "greedy_assignments = compute_greedy_communities(G)\n",
    "louvain_assignments = compute_louvain_communities(G)\n",
    "\n",
    "\n",
    "# Compare resulting community assignments with the ground truth\n",
    "plot_network_communities(G, ground_truth, 'Ground Truth')\n",
    "plot_network_communities(G, cfinder_assignments, 'C-Finder')\n",
    "plot_network_communities(G, greedy_assignments, 'Greedy Modularity')\n",
    "plot_network_communities(G, louvain_assignments, 'Louvain')\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "23132919",
   "metadata": {},
   "source": [
    "## Written Response for 2.3\n",
    "\n",
    "Answer:"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ac22c0ea",
   "metadata": {},
   "source": [
    "# Part 3: Community Detection with LFR Networks [25 points]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a3a5f910",
   "metadata": {},
   "source": [
    "### 3.1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "16bdf7e6",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Generating the LFR Benchmark Network\n",
    "def generate_lfr_benchmark(mu):\n",
    "    \"\"\"\n",
    "    Inputs:\n",
    "    mu: float\n",
    "\n",
    "    Returns:\n",
    "    G: NetworkX Graph Object\n",
    "    community_assignments: list[int]\n",
    "    \"\"\"\n",
    "    \n",
    "    n = 500\n",
    "    tau1 = 2.5\n",
    "    tau2 = 2\n",
    "    min_degree = 3\n",
    "    min_community = 40\n",
    "    seed = 10\n",
    "    \n",
    "\n",
    "\n",
    "    return G, community_assignments\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "9450e997",
   "metadata": {},
   "source": [
    "### 3.2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ef19586f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def normalized_mutual_information(y_true, y_pred):\n",
    "    \"\"\"\n",
    "    Inputs:\n",
    "    y_true: list[int]\n",
    "    y_pred: list[int]\n",
    "\n",
    "    Returns:\n",
    "    NMI: float\n",
    "    \"\"\"\n",
    "\n",
    "\n",
    "    return NMI"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "89dfb53f",
   "metadata": {},
   "source": [
    "### 3.3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bb06246c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sweep_mu_values():\n",
    "    \"\"\"\n",
    "    \n",
    "    Returns:\n",
    "    greedy_nmis: list[float]\n",
    "    louvain_nmis: list[float]\n",
    "    \n",
    "    \"\"\"\n",
    "\n",
    "\n",
    "    return greedy_nmis, louvain_nmis"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "8541d60f",
   "metadata": {},
   "source": [
    "### 3.4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bf4afbb7",
   "metadata": {},
   "outputs": [],
   "source": [
    "def plot_nmi_values(greedy_nmis, louvain_nmis, save=False):\n",
    "    \"\"\"\n",
    "    Inputs:\n",
    "    greedy_nmis: list[int]\n",
    "    louvain_nmis: list[int]\n",
    "    \"\"\"\n",
    "    plt.figure(figsize=(8,6))\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    plt.show()\n",
    "    \n",
    "    if save:\n",
    "        plt.savefig('3_4.png')\n",
    "    plt.close()"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "8a5fc603",
   "metadata": {},
   "source": [
    "### 3.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d9a2f6d1",
   "metadata": {},
   "outputs": [],
   "source": [
    "greedy_nmis, louvain_nmis = sweep_mu_values()\n",
    "\n",
    "plot_nmi_values(greedy_nmis, louvain_nmis)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "4b222836",
   "metadata": {},
   "source": [
    "## Written Response for 3.5\n",
    "\n",
    "Answer:"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "01a6210b",
   "metadata": {},
   "source": [
    "# Part 4: Community Detection on Real World Data [15 points]"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "c6b9fc36",
   "metadata": {},
   "source": [
    "### 4.1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a9767108",
   "metadata": {},
   "outputs": [],
   "source": [
    "def calculate_community_sizes(G):\n",
    "    \"\"\"\n",
    "    Inputs:\n",
    "    G: NetworkX Graph Object\n",
    "\n",
    "    Returns: \n",
    "    greedy_sizes: list[int]\n",
    "    louvain_sizes: list[int]\n",
    "    \"\"\"\n",
    "\n",
    "\n",
    "    return greedy_sizes, louvain_sizes"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "aad3160c",
   "metadata": {},
   "source": [
    "### 4.2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "529d4abb",
   "metadata": {},
   "outputs": [],
   "source": [
    "def plot_community_size_distributions(greedy_sizes, louvain_sizes, data_name, save=False):\n",
    "    \"\"\"\n",
    "    Inputs:\n",
    "    greedy_sizes: list[int]\n",
    "    louvain_sizes: list[int]\n",
    "    data_name: str\n",
    "    \"\"\"\n",
    "\n",
    "    plt.figure(figsize=(8,6))\n",
    "\n",
    "    \n",
    "\n",
    "\n",
    "    plt.show()\n",
    "    \n",
    "    if save:\n",
    "        plt.savefig('4_2.png')\n",
    "    plt.close()\n",
    "    "
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "53a820aa",
   "metadata": {},
   "source": [
    "### 4.3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7eaca81a",
   "metadata": {},
   "outputs": [],
   "source": [
    "G_airport, G_yeast = load_graphs()\n",
    "\n",
    "# Airport\n",
    "greedy_sizes, louvain_sizes = calculate_community_sizes(G_airport)\n",
    "plot_community_size_distributions(greedy_sizes, louvain_sizes, 'Airport')\n",
    "\n",
    "# Yeast\n",
    "greedy_sizes, louvain_sizes = calculate_community_sizes(G_yeast)\n",
    "plot_community_size_distributions(greedy_sizes, louvain_sizes, 'Yeast')"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "cc5d5290",
   "metadata": {},
   "source": [
    "## Written Response for 4.3\n",
    "\n",
    "Answer:"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "093f4dbe",
   "metadata": {},
   "source": [
    "## Response for 5\n",
    "\n",
    "\n",
    "\n",
    "### Partition 1:\n",
    "\n",
    "Image:\n",
    "\n",
    "Modularity:\n",
    "\n",
    "### Partition 2:\n",
    "\n",
    "Image:\n",
    "\n",
    "Modularity:\n",
    "\n",
    "### Partition 3:\n",
    "\n",
    "Image:\n",
    "\n",
    "Modularity:\n",
    "\n",
    "### Partition 4:\n",
    "\n",
    "Image:\n",
    "\n",
    "Modularity:"
   ]
  }
 ],
 "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.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}