{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Centrality measures experiments\n",
"\n",
"Author: [picorana](https://picorana.github.io/)\n",
"\n",
"Github repository: [link](https://github.com/picorana/Graph_Centrality_Measures)\n",
"\n",
"If you are looking at this via github, please use this link to visualize it in the proper way: [this notebook on nbviewer](https://nbviewer.jupyter.org/github/picorana/Graph_Centrality_Measures/blob/master/notebook.ipynb)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Centrality\n",
"\n",
"Centrality measures address the question of defining the concept of importance of a node in a graph. \n",
"We can answer to the question of \"what node is the most important in a graph?\" in many different ways, depending on the context. \n",
"\n",
"The question is infact perfectly comparable to asking \"Which one of my friends is the most famous one in my circle of friends?\", \"Which research paper is the most relevant?\", or \"Which github repository is better?\"\n",
"\n",
"For this purpose, we can choose among different ways of measuring it. \n",
"Possible types of measures are:\n",
"* Degree centrality\n",
"* Closeness centrality\n",
"* Betweeness centrality\n",
"* Eigenvector centrality\n",
"* PageRank centrality\n",
"\n",
"The aim of this notebook is to explain a possible implementation for computing eigenvector centrality, and showing a comparison with degree centrality."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Initial setup\n",
"\n",
"We are going to use the networkx library for storing and managing the graph, plus scipy and numpy for working with matrices."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": true,
"scrolled": true
},
"outputs": [],
"source": [
"import networkx as nx\n",
"import scipy as sc\n",
"import numpy as np"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"For the sake of visualization, we are going to use plotly. Since talking about visualization is not the purpose of this notebook, I made a module to manage all the visualization-related functions and to store plotly configurations. The code of this module can still be found in the same repository of this notebook, if you are interested in taking a look."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"import plotly_config as pc"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Degree Centrality\n",
"\n",
"The degree of a node is just the number of connections it has with other nodes. In the context of a social network, if an user is a node, its degree could be interpreted as the number of friends he has.\n",
"\n",
"Degree Centrality is a simple form of interpreting how relevant a node is."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let us play with a toy graph in the beginning, here we define it:"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"test_G = nx.Graph()\n",
"test_G.add_edge(0, 1)\n",
"test_G.add_edge(1, 2)\n",
"test_G.add_edge(2, 3)\n",
"test_G.add_edge(2, 10)\n",
"test_G.add_edge(3, 0)\n",
"test_G.add_edge(3, 1)\n",
"test_G.add_edge(1, 4)\n",
"test_G.add_edge(4, 5)\n",
"test_G.add_edge(5, 6)\n",
"test_G.add_edge(5, 7)\n",
"test_G.add_edge(5, 8)\n",
"test_G.add_edge(5, 9)\n",
"test_G.add_edge(5, 11)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"And here we draw it:"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
""
],
"text/vnd.plotly.v1+html": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"application/vnd.plotly.v1+json": {
"data": [
{
"hoverinfo": "none",
"line": {
"color": "#888",
"width": 0.5
},
"mode": "lines",
"type": "scatter",
"x": [
0.2954329608033906,
0.6670758765768787,
null,
0.2954329608033906,
0.5091362871779276,
null,
0.6670758765768787,
0.8535278692020176,
null,
0.6670758765768787,
0.5091362871779276,
null,
0.6670758765768787,
0.5850381425437822,
null,
0.8535278692020176,
1,
null,
0.8535278692020176,
0.5091362871779276,
null,
0.5850381425437822,
0.35455603281319603,
null,
0.35455603281319603,
0.7236622285006333,
null,
0.35455603281319603,
0,
null,
0.35455603281319603,
0.45224420021414996,
null,
0.35455603281319603,
0.16213570918033285,
null,
0.35455603281319603,
0.08408074385910709,
null
],
"y": [
0.9756311605321513,
0.9787035876170551,
null,
0.9756311605321513,
0.9742789274413045,
null,
0.9787035876170551,
0.8207797759924323,
null,
0.9787035876170551,
0.9742789274413045,
null,
0.9787035876170551,
0.5947158078446857,
null,
0.8207797759924323,
0.5387905680982064,
null,
0.8207797759924323,
0.9742789274413045,
null,
0.5947158078446857,
0.27398643267149325,
null,
0.27398643267149325,
0.05901741607186094,
null,
0.27398643267149325,
0.33954802505200304,
null,
0.27398643267149325,
0,
null,
0.27398643267149325,
0.10861725657105659,
null,
0.27398643267149325,
0.5660456567553163,
null
]
},
{
"hoverinfo": "text",
"marker": {
"color": [
2,
4,
3,
3,
2,
6,
1,
1,
1,
1,
1,
1
],
"colorbar": {
"thickness": 15,
"title": "Node Connections",
"titleside": "right",
"xanchor": "left"
},
"colorscale": "Portland",
"line": {
"width": 2
},
"reversescale": true,
"showscale": true,
"size": [
20,
20,
20,
20,
20,
20,
20,
20,
20,
20,
20,
20
]
},
"mode": "markers",
"text": [
"# degree: 2\n node number: 0",
"# degree: 4\n node number: 1",
"# degree: 3\n node number: 2",
"# degree: 3\n node number: 3",
"# degree: 2\n node number: 4",
"# degree: 6\n node number: 5",
"# degree: 1\n node number: 6",
"# degree: 1\n node number: 7",
"# degree: 1\n node number: 8",
"# degree: 1\n node number: 9",
"# degree: 1\n node number: 10",
"# degree: 1\n node number: 11"
],
"type": "scatter",
"x": [
0.2954329608033906,
0.6670758765768787,
0.8535278692020176,
0.5091362871779276,
0.5850381425437822,
0.35455603281319603,
0.7236622285006333,
0,
0.45224420021414996,
0.16213570918033285,
1,
0.08408074385910709
],
"y": [
0.9756311605321513,
0.9787035876170551,
0.8207797759924323,
0.9742789274413045,
0.5947158078446857,
0.27398643267149325,
0.05901741607186094,
0.33954802505200304,
0,
0.10861725657105659,
0.5387905680982064,
0.5660456567553163
]
}
],
"layout": {
"annotations": [
{
"showarrow": false,
"text": "Link to the code on Github: https://github.com/picorana/Graph_Centrality_Measures",
"x": 0.005,
"xref": "paper",
"y": -0.002,
"yref": "paper"
}
],
"hovermode": "closest",
"margin": {
"b": 20,
"l": 5,
"r": 5,
"t": 40
},
"showlegend": false,
"title": "
Network graph made with Python",
"titlefont": {
"size": 16
},
"xaxis": {
"showgrid": false,
"showticklabels": false,
"zeroline": false
},
"yaxis": {
"showgrid": false,
"showticklabels": false,
"zeroline": false
}
}
},
"text/html": [
"