examples/community-detection.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "5b60d8ba",
   "metadata": {},
   "source": [
    "# Community Detection"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3e2fb927",
   "metadata": {
    "colab_type": "text",
    "id": "view-in-github"
   },
   "source": [
    "<a target=\"_blank\" href=\"https://colab.research.google.com/github/neo4j/graph-data-science-client/blob/main/examples/community-detection.ipynb\">\n",
    "  <img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/>\n",
    "</a>"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "f083f11b",
   "metadata": {},
   "source": [
    "This Jupyter notebook is hosted [here](https://github.com/neo4j/graph-data-science-client/blob/main/examples/community-detection.ipynb) in the Neo4j Graph Data Science Client Github repository.\n",
    "\n",
    "The notebook shows the usage of the `graphdatascience` library for community detection on the Reddit Hyperlink Network dataset that can be downloaded [here](https://snap.stanford.edu/data/soc-RedditHyperlinks.html). We will use the `soc-redditHyperlinks-body.tsv` file.\n",
    "\n",
    "The tasks we cover here include performing initial graph preprocessing using Weakly Connected Components and then performing community detection on the largest component using the Louvain algorithm.\n",
    "\n",
    "### Setup\n",
    "\n",
    "We start by importing our dependencies and setting up our GDS client connection to the database."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3953e353",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Install necessary dependencies\n",
    "%pip install graphdatascience pandas"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2fcadffb",
   "metadata": {},
   "outputs": [],
   "source": [
    "from graphdatascience import GraphDataScience\n",
    "import pandas as pd\n",
    "import os"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "46b33d2d",
   "metadata": {},
   "outputs": [],
   "source": [
    "NEO4J_URI = os.environ.get(\"NEO4J_URI\", \"bolt://localhost:7687\")\n",
    "NEO4J_AUTH = None\n",
    "if os.environ.get(\"NEO4J_USER\") and os.environ.get(\"NEO4J_PASSWORD\"):\n",
    "    NEO4J_AUTH = (\n",
    "        os.environ.get(\"NEO4J_USER\"),\n",
    "        os.environ.get(\"NEO4J_PASSWORD\"),\n",
    "    )\n",
    "\n",
    "gds = GraphDataScience(NEO4J_URI, auth=NEO4J_AUTH)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9a78c6bc",
   "metadata": {
    "tags": [
     "verify-version"
    ]
   },
   "outputs": [],
   "source": [
    "from graphdatascience.server_version.server_version import ServerVersion\n",
    "\n",
    "assert gds.server_version() >= ServerVersion(1, 8, 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "48bd8af1",
   "metadata": {},
   "source": [
    "### Importing the dataset\n",
    "\n",
    "We import the dataset as a pandas dataframe first. We work with only a subset of the dataset. The sampled data is only till 1st March 2014. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a8e677aa",
   "metadata": {},
   "outputs": [],
   "source": [
    "df = pd.read_csv(\"https://snap.stanford.edu/data/soc-redditHyperlinks-body.tsv\", sep=\"\\t\")\n",
    "df = df[df[\"TIMESTAMP\"] < \"2014-03-01 02:51:13\"]\n",
    "df.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "be7b1c5d",
   "metadata": {},
   "source": [
    "The `LINK_SENTIMENT` column tells if there is a positive (+1) or negative (-1) relationship from the source subreddit to destination subreddit. We filter out the negative sentiment relationships as they won't add to any meaningful communities. We also drop duplicate relationships."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2f153da1",
   "metadata": {},
   "outputs": [],
   "source": [
    "relationship_df = df[df[\"LINK_SENTIMENT\"] == 1]\n",
    "columns = [\"SOURCE_SUBREDDIT\", \"TARGET_SUBREDDIT\"]\n",
    "relationship_df = relationship_df[columns]\n",
    "relationship_df = relationship_df.drop_duplicates()\n",
    "relationship_df.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "59e6a5e9",
   "metadata": {},
   "source": [
    "Next, we get a list of all the distinct nodes (source or destination) and load them as a dataframe."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6266953f",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Get unique nodes for each column\n",
    "source_nodes = pd.Series(df[\"SOURCE_SUBREDDIT\"])\n",
    "target_nodes = pd.Series(df[\"TARGET_SUBREDDIT\"])\n",
    "# Get unique nodes for both columns\n",
    "all_nodes = pd.Series(pd.concat([df[\"SOURCE_SUBREDDIT\"], df[\"TARGET_SUBREDDIT\"]])).unique()\n",
    "\n",
    "# Create new dataframe with distinct nodes\n",
    "nodes_df = pd.DataFrame({\"SUBREDDIT\": all_nodes})\n",
    "nodes_df.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c30a4378",
   "metadata": {},
   "source": [
    "Finally, we load this data (nodes and edges) into a Graph Database and a GDS graph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0b18e522",
   "metadata": {},
   "outputs": [],
   "source": [
    "gds.run_cypher(\n",
    "    \"UNWIND $nodes AS node CREATE (n:Subreddit {name: node.SUBREDDIT})\",\n",
    "    params={\"nodes\": nodes_df.to_dict(\"records\")},\n",
    ")\n",
    "\n",
    "gds.run_cypher(\n",
    "    \"\"\"\n",
    "    UNWIND $rels AS rel \n",
    "    MATCH (source:Subreddit {name: rel.SOURCE_SUBREDDIT}), (target:Subreddit {name: rel.TARGET_SUBREDDIT}) \n",
    "    CREATE (source)-[:HYPERLINKED_TO]->(target)\n",
    "    \"\"\",\n",
    "    params={\"rels\": relationship_df.to_dict(\"records\")},\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7a3509e8",
   "metadata": {},
   "outputs": [],
   "source": [
    "G, result = gds.graph.project(\"reddit\", \"Subreddit\", \"HYPERLINKED_TO\")\n",
    "\n",
    "print(f\"The projection took {result['projectMillis']} ms\")\n",
    "\n",
    "# We can use convenience methods on `G` to check if the projection looks correct\n",
    "print(f\"Graph '{G.name()}' node count: {G.node_count()}\")\n",
    "print(f\"Graph '{G.name()}' node labels: {G.node_labels()}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "61aa6afe",
   "metadata": {},
   "outputs": [],
   "source": [
    "gds.graph.list()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9c259471",
   "metadata": {},
   "source": [
    "### Weakly Connected Components\n",
    "\n",
    "A graph dataset need not always be connected. That is, there may not exist a path from every node to \n",
    "every other node in the graph dataset (subgraphs in it may not be connected to each other at all). Hence, we \n",
    "need to find the total number of nodes in each subgraph to see if it is big enough for further graph analysis. \n",
    "Smaller subgraphs or lone nodes will not contribute to the community detection task and should be \n",
    "eliminated. Weakly Connected Components is often used as one of the early steps of graph preprocessing.\n",
    "\n",
    "We use the [Weakly Connected Components](https://neo4j.com/docs/graph-data-science/current/algorithms/wcc/) algorithm to find sets of connected nodes and assign each set a component ID."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7a114af1",
   "metadata": {},
   "outputs": [],
   "source": [
    "result = gds.wcc.mutate(G, mutateProperty=\"componentId\")\n",
    "\n",
    "print(f\"Components found: {result.componentCount}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "04fd557e",
   "metadata": {},
   "outputs": [],
   "source": [
    "# We can verify that the componentId was mutated\n",
    "G.node_properties()"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "23a0a487",
   "metadata": {},
   "source": [
    "Next, we will see the size of each connected component and depending on that, we can pick the subgraph that needs further analysis.\n",
    "\n",
    "We use `run_cypher` here instead of the direct GDS client call since we want to see the size of the connected components."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2274a19a",
   "metadata": {},
   "outputs": [],
   "source": [
    "query = \"\"\"\n",
    "    CALL gds.graph.nodeProperties.stream('reddit', 'componentId')\n",
    "    YIELD nodeId, propertyValue\n",
    "    WITH gds.util.asNode(nodeId).name AS node, propertyValue AS componentId\n",
    "    WITH componentId, collect(node) AS subreddits\n",
    "    WITH componentId, subreddits, size(subreddits) AS componentSize\n",
    "    RETURN componentId, componentSize, subreddits\n",
    "    ORDER BY componentSize DESC\n",
    "\"\"\"\n",
    "\n",
    "components = gds.run_cypher(query)\n",
    "components"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "28f76422",
   "metadata": {},
   "outputs": [],
   "source": [
    "largest_component = components[\"componentId\"][0]\n",
    "\n",
    "print(f\"The largest component has the id {largest_component} with {components['componentSize'][0]} subreddits.\")"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "9a2355cb",
   "metadata": {},
   "source": [
    "For our further analysis we will work only with that subgraph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d1994b04",
   "metadata": {},
   "outputs": [],
   "source": [
    "largest_component_graph, _ = gds.beta.graph.project.subgraph(\n",
    "    \"largest_connected_components\", G, f\"n.componentId={largest_component}\", \"*\"\n",
    ")\n",
    "largest_component_graph"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "17942d04",
   "metadata": {},
   "source": [
    "### Community Detection using Louvain\n",
    "\n",
    "We use the [Louvain](https://neo4j.com/docs/graph-data-science/current/algorithms/louvain/) algorithm to detect communities in our subgraph and assign a `louvainCommunityId` to each community."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "def26464",
   "metadata": {},
   "outputs": [],
   "source": [
    "gds.louvain.mutate(largest_component_graph, mutateProperty=\"louvainCommunityId\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7563e824",
   "metadata": {},
   "source": [
    "We get a modularity score of 0.5898 for our community detection algorithm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "858c65be",
   "metadata": {},
   "outputs": [],
   "source": [
    "gds.graph.nodeProperties.write(largest_component_graph, [\"louvainCommunityId\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "afb104e0",
   "metadata": {},
   "source": [
    "We can also check that the property was written by the below command."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "22f73aea",
   "metadata": {},
   "outputs": [],
   "source": [
    "gds.run_cypher(\n",
    "    \"\"\"\n",
    "    MATCH (n) WHERE 'louvainCommunityId' IN keys(n) \n",
    "    RETURN n.name, n.louvainCommunityId LIMIT 10\n",
    "    \"\"\"\n",
    ")"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "113dff42",
   "metadata": {},
   "source": [
    "Now we want to inspect the communities produced by Louvain."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "19ccfcb8",
   "metadata": {},
   "outputs": [],
   "source": [
    "query = \"\"\"\n",
    "    CALL gds.graph.nodeProperties.stream('largest_connected_components', 'louvainCommunityId')\n",
    "    YIELD nodeId, propertyValue\n",
    "    WITH gds.util.asNode(nodeId).name AS node, propertyValue AS communityId\n",
    "    WITH communityId, collect(node) AS subreddits\n",
    "    WITH communityId, subreddits, size(subreddits) AS communitySize\n",
    "    RETURN communityId, communitySize, subreddits\n",
    "    ORDER BY communitySize DESC\n",
    "\"\"\"\n",
    "\n",
    "communities = gds.run_cypher(query)\n",
    "communities"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "5ed56f82",
   "metadata": {},
   "source": [
    "### Further ideas\n",
    "\n",
    "* Inspect the produced communities using [Bloom](https://neo4j.com/docs/bloom-user-guide/current/). You can use rule-based styling based on the community property.\n",
    "* Try to tune more parameters of Louvain and see how the communities differ.\n",
    "* Try to use other community detection algorithms listed in the [GDS docs](https://neo4j.com/docs/graph-data-science/current/algorithms/community/)."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "6e00ed7b",
   "metadata": {},
   "source": [
    "### Cleanup\n",
    "\n",
    "Before finishing we can clean up the example data from both the GDS in-memory state and the database."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1882307b",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Cleanup GDS\n",
    "largest_component_graph.drop()\n",
    "G.drop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "73f94984",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Cleanup database\n",
    "gds.run_cypher(\"MATCH (n:Subreddit) DETACH DELETE n\")"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "65dcb952",
   "metadata": {},
   "source": [
    "### References\n",
    "\n",
    "Srijan Kumar, William L. Hamilton, Jure Leskovec, and Dan Jurafsky. 2018. Community Interaction and Conflict on the Web. In Proceedings of the 2018 World Wide Web Conference (WWW '18). International World Wide Web Conferences Steering Committee, Republic and Canton of Geneva, CHE, 933–943. https://doi.org/10.1145/3178876.3186141"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}