{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# TP7 (Student version)\n",
"\n",
"In this practical, we consider algorithms for partitioning the nodes in the input graph into communities, except in exercise 4 where we consider an algorithm to compute overlapping communities.\n"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"import matplotlib.pyplot as plt\n",
"import sys"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercise 1: Simple bechmark\n",
"\n",
"Implement an algorithm to generate the following random graph.\n",
"- The graph has 400 nodes partitioned into 4 clusters of size 100.\n",
"- Each pair of nodes in the same cluster is connected with a probability $p$.\n",
"- Each pair of nodes in different clusters is connected with a probability $q < p$.\n",
"Draw the obtained graphs for various values of $p$ and $q$ using a software of your choice. For instance: https://networkx.github.io/documentation/stable/reference/drawing\n",
"What is the effect of increasing or decreasing $\\frac{p}{q}$ on the community structure?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercise 2: Label propagation\n",
"\n",
"**Question 1:** Implement the label propagation algorithm. \n",
"**Question 2 (Evaluate the accuracy):** Run your program on the benchmark graphs generated for Exercise 1. Draw the graphs and color the nodes using a different color for each community. Use some metrics to compare partitions (such as https://scikit-learn.org/stable/modules/clustering.html#clustering-performance-evaluation) and comment your results. \n",
"**Question 3 (Evaluate the scalability):** Run your program on the graphs considered in practical 2 and report the running time."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercise 3: New algorithm\n",
"\n",
"**Question 1:** Propose your own community detection method and implement it. Consider an algorithm significantly different from Label Propagation. Explain your algorithm: the intuition behind it and the implementation issues. \n",
"**Question 2:** Same as Exercise 2. \n",
"**Question 4:** Same as Exercise 3."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercise 4 — (Optional) Triangle percolation\n",
"\n",
"Implement an efficient algorithm for the k-clique percolation method (slide 31 of course 6) for $k = 3$. Make sure your algorithm is correct comparing the output of your algorithm with the output of the original algorithm (for k = 3): http://www.cfinder.org/, then compare the scalability of the two approaches."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"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.5"
}
},
"nbformat": 4,
"nbformat_minor": 2
}