{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"# What is this?\n",
"\n",
"This notebook is an almost one to one copy from Marks Needham's [Neo4j Graph Algorithms Jupyter Notebooks](https://github.com/mneedham/graph-algorithms-notebooks).\n",
"\n",
"The purpose of this notebook is to demonstrate how the original Jupyter Python notebooks culd look like with the Cypher kernel.\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"# Contents\n",
"\n",
"**Path finding**\n",
"\n",
" * [All Pairs Shortest Path](#All-Pairs-Shortest-Path)\n",
" * [Single Source Shortest Path](#Single-Source-Shortest-Path)\n",
"\n",
"**Centrality**\n",
"\n",
" * [Degree Centrality](#Degree-Centrality)\n",
" * [Closeness Centrality](#Closeness-Centrality)\n",
" * [Betweenness Centrality](#Betweenness-Centrality)\n",
"\n",
"**Community Detection**\n",
"\n",
" * [Strongly Connected Components](#Strongly-Connected-Components)\n",
" * [Weighted Union Find](#Weighted-Union-Find)\n",
" * [Unweighted Union Find](#Unweighted-Union-Find)\n",
" * [Label Propagation](#Label-Propagation)\n",
" * [Louvain](#Louvain)\n",
" * [Triangle Counting](#Triangle-Counting)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"# The Setup\n",
"\n",
"If you do not have a Neo4j database running with APOC installed, then you could use the following:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"%%bash\n",
"rm -rf plugins\n",
"mkdir plugins\n",
"cd plugins\n",
"echo \"Downloading APOC plugin\"\n",
"wget https://github.com/neo4j-contrib/neo4j-apoc-procedures/releases/download/3.3.0.1/apoc-3.3.0.1-all.jar\n",
"echo \"Downloading algorithms plugin\"\n",
"wget https://github.com/neo4j-contrib/neo4j-graph-algorithms/releases/download/3.3.2.0/graph-algorithms-algo-3.3.2.0.jar\n",
"cd .."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"data": {
"text/plain": [
"dd8ea088ca50b68f80129a1805e351e1ce9404ad055bc0a58993e08ac62d9f80\r\n"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"%%bash\n",
"docker run \\\n",
" -d --name myneo4j \\\n",
" --publish=7474:7474 \\\n",
" --publish=7687:7687 \\\n",
" --volume=$(pwd)/plugins:/plugins \\\n",
" --env NEO4J_AUTH=neo4j/class \\\n",
" --env=NEO4J_dbms_security_procedures_unrestricted=apoc.\\\\\\*,algo.\\\\\\* \\\n",
" neo4j"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"# All Pairs Shortest Path\n",
"\n",
"All Pairs Shortest Path (APSP) calculates the shortest (weighted) path between all pairs of nodes. This algorithm has optimisations that make it quicker than calling the SSSP algorithm for every pair of nodes in the graph."
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"data": {
"text/plain": []
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"CREATE (a:Loc{name:'A'}), (b:Loc{name:'B'}), (c:Loc{name:'C'}), \n",
" (d:Loc{name:'D'}), (e:Loc{name:'E'}), (f:Loc{name:'F'}),\n",
" (a)-[:ROAD {cost:50}]->(b),\n",
" (a)-[:ROAD {cost:50}]->(c),\n",
" (a)-[:ROAD {cost:100}]->(d),\n",
" (a)-[:RAIL {cost:50}]->(d),\n",
" (b)-[:ROAD {cost:40}]->(d),\n",
" (c)-[:ROAD {cost:40}]->(d),\n",
" (c)-[:ROAD {cost:80}]->(e),\n",
" (d)-[:ROAD {cost:30}]->(e),\n",
" (d)-[:ROAD {cost:80}]->(f),\n",
" (e)-[:ROAD {cost:40}]->(f),\n",
" (e)-[:RAIL {cost:20}]->(f);"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"data": {
"text/plain": [
"+-----------------+\n",
"| labels | count |\n",
"+-----------------+\n",
"| [\"Loc\"] | 6 |\n",
"+-----------------+\n",
"\n",
"1 row available after 1 ms, consumed after another 0 ms"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"MATCH (n) \n",
"RETURN labels(n) AS labels, COUNT(*) AS count\n",
"ORDER BY count DESC"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [
{
"data": {
"application/javascript": [
"require([\"https://cdnjs.cloudflare.com/ajax/libs/vis/4.21.0/vis.min.js\"], function(vis) {\n",
" var nodes = new vis.DataSet([\n",
" { id: 47, label: \"Loc\", title: \"{name:B,
_id:47}\", color: 'rgba(118,150,34,0.5)'},\n",
" { id: 46, label: \"Loc\", title: \"{name:A,
_id:46}\", color: 'rgba(118,150,34,0.5)'},\n",
" { id: 51, label: \"Loc\", title: \"{name:F,
_id:51}\", color: 'rgba(118,150,34,0.5)'},\n",
" { id: 48, label: \"Loc\", title: \"{name:C,
_id:48}\", color: 'rgba(118,150,34,0.5)'},\n",
" { id: 50, label: \"Loc\", title: \"{name:E,
_id:50}\", color: 'rgba(118,150,34,0.5)'},\n",
" { id: 49, label: \"Loc\", title: \"{name:D,
_id:49}\", color: 'rgba(118,150,34,0.5)'},\n",
" \n",
" ]);\n",
"\n",
" // create an array with edges\n",
" var edges = new vis.DataSet([\n",
" { from: 49,to: 51, arrows:'to', title: \"{cost:80, _id:59,}\" },\n",
" { from: 49,to: 50, arrows:'to', title: \"{cost:30, _id:58,}\" },\n",
" { from: 48,to: 49, arrows:'to', title: \"{cost:40, _id:56,}\" },\n",
" { from: 46,to: 47, arrows:'to', title: \"{cost:50, _id:51,}\" },\n",
" { from: 46,to: 48, arrows:'to', title: \"{cost:50, _id:52,}\" },\n",
" { from: 46,to: 49, arrows:'to', title: \"{cost:100, _id:53,}\" },\n",
" { from: 47,to: 49, arrows:'to', title: \"{cost:40, _id:55,}\" },\n",
" { from: 48,to: 50, arrows:'to', title: \"{cost:80, _id:57,}\" },\n",
" { from: 50,to: 51, arrows:'to', title: \"{cost:20, _id:61,}\" },\n",
" { from: 50,to: 51, arrows:'to', title: \"{cost:40, _id:60,}\" },\n",
" { from: 46,to: 49, arrows:'to', title: \"{cost:50, _id:54,}\" },\n",
" \n",
" ]);\n",
"\n",
" // create a network\n",
" var container = document.getElementById('f3dd7152-5734-4f1e-81a1-631833e95ad6');\n",
" var data = {\n",
" nodes: nodes,\n",
" edges: edges\n",
" };\n",
"\n",
" var options = {\n",
" edges: {\n",
" arrows: {\n",
" to: {\n",
" scaleFactor: 0.5\n",
" }\n",
" }\n",
" },\n",
" width: '100%',\n",
" height: '500px',\n",
" interaction: {hover: true}\n",
" };\n",
"\n",
" var network = new vis.Network(container, data, options);});"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/html": [
"\n",
"