Skip to content

Instantly share code, notes, and snippets.

@melvincabatuan

melvincabatuan/NetworKit_Tutorial_Part_1.ipynb

Created March 17, 2015 23:48
Show Gist options
  • Save melvincabatuan/c5285d064578cdb7e8ee to your computer and use it in GitHub Desktop.
Save melvincabatuan/c5285d064578cdb7e8ee to your computer and use it in GitHub Desktop.
Download ZIP
NetworKit_Tutorial_Part_1.ipynb
Display the source blob
Display the rendered blob
Raw
NetworKit_Tutorial_Part_1.ipynb
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Tutorial \"Algorithmic Methods for Network Analysis with NetworKit\" (Part 1)\n",
"Welcome to the hands-on session of our tutorial! This tutorial is based on the user guide of NetworKit, our network analysis software. You will learn in this tutorial how to use NetworKit for fundamental tasks in network analysis.\n",
"\n",
"NetworKit can run in your browser (thanks to IPython notebooks) and is still very fast (thanks to C++ code in the background). It is easy to mix text with code and solutions in this environment. Thus, you should be able to obtain your results in a convenient and quick manner. This is not only true for the rather small graphs we use for this tutorial, but for larger instances in production runs as well. In particular you can mix text, code, plots and other rich media in this environment. Since this allows a simplified execution and interpretation of experiments, the interactive approach followed by NetworKit can simplify the cyclic algorithm engineering process significantly (without compromising algorithm performance).\n",
"\n",
"## Preparation\n",
"Let's start by making NetworKit available in your session. Click into the cell below and hit space-return or click the \"Play\" button or select \"Cell -> Run\" in the menu."
]
},
{
"cell_type": "code",
"execution_count": 61,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"from networkit import * \n",
"%matplotlib inline\n",
"import matplotlib.pyplot as plt"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In case a Python warning appears that recommends an update to Python 3.4, simply ignore it for this tutorial. Python 3.3 works just as fine for our purposes.\n",
"\n",
"IPython lets us use familiar shell commands in a Python interpreter. Use one of them now to change into the main directory of your NetworKit installation:"
]
},
{
"cell_type": "code",
"execution_count": 62,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"/home/cobalt/iPython/NetworKit\n"
]
}
],
"source": [
"cd /home/cobalt/iPython/NetworKit/"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Reading Graphs\n",
"Let us start by reading a network from a file on disk: [PGPgiantcompo.graph](http://www.cc.gatech.edu/dimacs10/archive/data/clustering/PGPgiantcompo.graph.bz2). NetworKit supports a number of popular file formats. There is a convenient function in the top namespace which tries to guess the input format and select the appropriate reader:"
]
},
{
"cell_type": "code",
"execution_count": 63,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"G = readGraph(\"input/PGPgiantcompo.graph\", Format.METIS)\n",
"# is the same as: G = readGraph(\"input/PGPgiantcompo.graph\", Format.METIS)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In the course of this tutorial, we are going to work (among others) on the `PGPgiantcompo` network, a social network/web of trust in which nodes are PGP keys and an edge represents a signature from one key on another (web of trust). It is distributed with NetworKit as a good starting point.\n",
"\n",
"## The Graph Object\n",
"\n",
"`Graph` is the central class of NetworKit. An object of this type represents an optionally weighted network. In this tutorial we work with undirected graphs, but NetworKit supports directed graphs as well.\n",
"\n",
"Let us inspect several of the methods which the class provides. Maybe the most basic information is the number of nodes and edges in as well as the name of the network."
]
},
{
"cell_type": "code",
"execution_count": 64,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"10680 24316\n"
]
}
],
"source": [
"n = G.numberOfNodes()\n",
"m = G.numberOfEdges()\n",
"print(n, m)"
]
},
{
"cell_type": "code",
"execution_count": 65,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"b'Graph(name=PGPgiantcompo, n=10680, m=24316)'"
]
},
"execution_count": 65,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"G.toString()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"NetworKit stores nodes simply as integer indices. Edges are pairs of such indices. The following prints the indices of the first ten nodes and edges, respectively."
]
},
{
"cell_type": "code",
"execution_count": 66,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
"[(42, 11), (101, 28), (111, 92), (128, 87), (141, 0), (165, 125), (169, 111), (176, 143), (187, 38), (192, 105)]\n"
]
}
],
"source": [
"V = G.nodes()\n",
"print(V[:10])\n",
"E = G.edges()\n",
"print(E[:10])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Another very useful feature is to determine if an edge is present and what its weight is. In case of unweighted graphs, edges have the default weight 1."
]
},
{
"cell_type": "code",
"execution_count": 67,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Weight of existing edge: 1.0\n",
"Weight of nonexisting edge: 0.0\n"
]
}
],
"source": [
"edgeExists = G.hasEdge(42,11)\n",
"if edgeExists:\n",
" print(\"Weight of existing edge:\", G.weight(42,11))\n",
"print(\"Weight of nonexisting edge:\", G.weight(42,12))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Many graph algorithms can be expressed with iterators over nodes or edges. As an example, let us iterate over the nodes to determine how many of them have more than 100 neighbors."
]
},
{
"cell_type": "code",
"execution_count": 68,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Number of nodes with more than 100 neighbors: 6\n"
]
}
],
"source": [
"count = 0 # counts number of nodes with more than 100 neighbors\n",
"for v in G.nodes():\n",
" if G.degree(v) > 100:\n",
" count = count + 1\n",
"print(\"Number of nodes with more than 100 neighbors: \", count)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Interesting Features of a Network\n",
"Let us become more concrete: In the talk that accompanies this tutorial you learned about basic network features. Go back to the 'Analytics' section of the slides and answer the following questions within the box below, including the code which found your answer (click on the box to enter text). If you need information on method prototypes, you have at least two options: Use the built-in code completion (tab) or the project website, which offers documentation in the form of an automatically generated reference: https://networkit.iti.kit.edu/documentation/ (Python/C++ Documentation in the left navigation bar).\n",
"\n",
"**After** you answered the questions, go on with Tutorial #2."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"##### Network Properties Overview"
]
},
{
"cell_type": "code",
"execution_count": 69,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Calculating best minimal value for power law fit\n",
"<_NetworKit.PLM object at 0xad5a7a4c>\n",
"\n",
"Network Properties: PGPgiantcompo\n",
"==================\n",
"Basic Properties\n",
"------------------------- ----------------\n",
"nodes, edges 10680, 24316\n",
"directed? False\n",
"weighted? False\n",
"isolated nodes 0\n",
"self-loops 0\n",
"density 0.000426\n",
"clustering coefficient 0.432815\n",
"max. core number 31\n",
"connected components 1\n",
"size of largest component 10680 (100.00 %)\n",
"estimated diameter range (24, 24)\n",
"------------------------- ----------------\n",
"Node Degree Properties\n",
"----------------------------- --------------------\n",
"min./max. degree (1, 205)\n",
"avg. degree 4.553558\n",
"power law?, likelihood, gamma True, 2.0415, 4.4185\n",
"degree assortativity 0.2382\n",
"----------------------------- --------------------\n",
"Community Structure\n",
"------------------------- ----------- --------\n",
"community detection (PLM)\n",
" communities 99\n",
" modularity 0.882436\n",
"------------------------- ----------- --------\n",
"Degree Distribution\n",
"-------------------\n",
"0- : ▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇9394.00\n",
"9- : ▇▇▇▇ 781.00\n",
"18- : ▇ 240.00\n",
"27- : | 101.00\n",
"36- : | 91.00\n",
"45- : | 28.00\n",
"54- : | 17.00\n",
"63- : | 12.00\n",
"72- : | 5.00\n",
"81- : | 3.00\n",
"90- : | 2.00\n",
"99- : | 1.00\n",
"108- : | 2.00\n",
"117- : | 0.00\n",
"126- : | 1.00\n",
"135- : | 0.00\n",
"144- : | 0.00\n",
"153- : | 0.00\n",
"162- : | 1.00\n",
"171- : | 0.00\n",
"180- : | 0.00\n",
"189- : | 0.00\n",
"198- : | 1.00\n",
"207- : | 0.00\n",
"216- : | 0.00\n",
"\n"
]
},
{
"name": "stderr",
"output_type": "stream",
"text": [
"/home/cobalt/iPython/NetworKit/networkit/powerlaw.py:546: FutureWarning: comparison to `None` will result in an elementwise object comparison in the future.\n",
" if data!=None and not (parameter_range and self.parent_Fit):\n",
"/home/cobalt/iPython/NetworKit/networkit/powerlaw.py:1047: FutureWarning: comparison to `None` will result in an elementwise object comparison in the future.\n",
" if data==None and hasattr(self, 'parent_Fit'):\n",
"/home/cobalt/iPython/NetworKit/networkit/powerlaw.py:598: FutureWarning: comparison to `None` will result in an elementwise object comparison in the future.\n",
" if data==None and hasattr(self, 'parent_Fit'):\n",
"/home/cobalt/iPython/NetworKit/networkit/powerlaw.py:671: FutureWarning: comparison to `None` will result in an elementwise object comparison in the future.\n",
" if data==None and hasattr(self, 'parent_Fit'):\n",
"/home/cobalt/iPython/NetworKit/networkit/powerlaw.py:556: FutureWarning: comparison to `None` will result in an elementwise object comparison in the future.\n",
" if data==None and hasattr(self, 'parent_Fit'):\n",
"/home/cobalt/iPython/NetworKit/networkit/powerlaw.py:1166: FutureWarning: comparison to `None` will result in an elementwise object comparison in the future.\n",
" if data==None and hasattr(self, 'parent_Fit'):\n",
"/home/cobalt/iPython/NetworKit/networkit/powerlaw.py:725: FutureWarning: comparison to `None` will result in an elementwise object comparison in the future.\n",
" if data==None and hasattr(self, 'parent_Fit'):\n"
]
}
],
"source": [
"properties.overview(G);"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Q&A Session #1\n",
"1. Who (which vertex) has the least/most 'friends' and how many?\n",
"**Answer:**\n",
"\n",
"2. How many neighbors does a vertex have on average?\n",
"**Answer:** \n",
"\n",
"3. Does the degree distribution follow a power law?\n",
"**Answer:** \n",
"\n",
"4. How often is the friend of a friend also a friend? Let's go for the average fraction here, other definitions are possible...\n",
"**Answer:**\n",
"\n",
"5. How many connected components does the graph have?\n",
"**Answer:** "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"##### Vertex with least friends:"
]
},
{
"cell_type": "code",
"execution_count": 70,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Vertex 0 has the least connection with 1 friend/s.\n"
]
}
],
"source": [
"dmin = G.numberOfNodes() \n",
"for v in G.nodes():\n",
" if G.degree(v) < dmin:\n",
" dmin = G.degree(v)\n",
" vmin = v \n",
"print(\"Vertex {0} has the least connection with {1} friend/s.\".format(vmin, dmin))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"##### Vertex with most friends:"
]
},
{
"cell_type": "code",
"execution_count": 71,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Vertex 1143 has the most connection with 205 friend/s.\n"
]
}
],
"source": [
"dmax = -1 \n",
"for v in G.nodes():\n",
" if G.degree(v) > dmax:\n",
" dmax = G.degree(v)\n",
" vmax = v \n",
"print(\"Vertex {0} has the most connection with {1} friend/s.\".format(vmax, dmax))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"##### Average Number of Neighbors on Average"
]
},
{
"cell_type": "code",
"execution_count": 72,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Average = 4.5535580524344565\n"
]
}
],
"source": [
"degsum = 0\n",
"for v in G.nodes():\n",
" degsum = degsum + G.degree(v)\n",
"ave = degsum / G.numberOfNodes()\n",
"print(\"Average = \", ave)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"##### Does the degree distribution follow a power law?"
]
},
{
"cell_type": "code",
"execution_count": 73,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/png": [
"iVBORw0KGgoAAAANSUhEUgAAAYwAAAEYCAYAAABPzsEfAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\n",
"AAALEgAACxIB0t1+/AAAIABJREFUeJzt3XmYHFW9xvFvEsgCBJB9EURZfoKAwLCEXEB2FSiKxauI\n",
"giK7KIslXBSVRREFCnEBQQRFQETWshSCLAEkmIiDGNkOm1FBQPYEQghJ5v5xqk2nM0vN0l1VPe/n\n",
"efJUd3VVz2/Sybxzzqk6Z0RXVxciIiJ9GVl0ASIiUg0KDBERyUWBISIiuSgwREQkFwWGiIjkosAQ\n",
"EZFcShUYZraqmd1fdB0iIrK40gSGmY0ATgRmFFyKiIh0ozSBARwFXAnMKboQERFZ3BKt+CJmtg3w\n",
"HefcTmY2ErgQ2BR4GzjMOfcUsGu2b2sz2985d30rahMRkXya3sIws5OAS4Ax2a59gNHOuYnAyUAM\n",
"4Jzb3zl3NDBNYSEiUj6t6JJ6EtgPGJE93w6YBOCcmwZsWX+wc+7gFtQkIiL91PTAcM7dAMyr2zUe\n",
"mFn3fH7WTSUiIiXWkjGMBjPxoVEz0jm3oL9v0tnZqWl2RUQGoKOjY0TfRy2uiMCYAgTAtWY2AZg+\n",
"0Dca6Dctxevs7OzS51dN+uyqbTC/bLcyMGpF3gjsZmZTsueHtLAGEREZoJYEhnNuBjAxe9wFHN2K\n",
"rysiIkNHg80iIpKLAkNERHJRYIiISC4KDBERyUWBISIiuSgwREQkFwWGiIjkosAQEZFcFBgiIpKL\n",
"AkNERHJRYIiISC4KDBERyUWBISIiuSgwREQkFwWGiIjkUunACKJEq36JiLRIpQMDmBZEyS5FFyEi\n",
"MhxUPTC2Am4PouS2IEq2KroYEZF2VvXA6ABuBXYF/hREyXVBlLy/4JpERNpSpQMjjcMH0jj8CLAT\n",
"MBXYH3g4iJKfBlGyVrHViYi0l0oHRk0ah3cBE4F9gMeAQ4EngiiJgyhZqcjaRETaRVsEBkAah11p\n",
"HCbApsBngReALwFPB1HyjSBKxhdZn4hI1bVNYNSkcTg/jcPLgQ2A44A5wOnAU0GUHBtEyZhCCxQR\n",
"qai2C4yaNA7fTuPwB8C6wKnAWOD7gAui5OAgSkYVWqCISMW0bWDUpHE4K43DM4D3AecBqwGXA38N\n",
"oiTUzX8iIvm0fWDUpHH4UhqHEb6r6jJgQ+Am4L4gSnYssjYRkSoYNoFRk8bhP9M4PBTYGLgemABM\n",
"DqJkUhAlWxRbnYhIeQ27wKhJ4/DRNA4/BmwN3A58GOgMouSaIEo2KLY6EZHyGbaBUZPG4f1pHO4G\n",
"7Ab8Gfg48EgQJRcHUbJmsdWJiJTHsA+MmjQOb8e3Nj4GPAkcATwZRMnZQZSsUGhxIiIloMCok938\n",
"dz1+fONQ4CXgRPzNf6cEUbJ0oQWKiBRIgdGNNA7npXF4GbA+EAHzgG/hb/47JoiS0YUWKCJSAAVG\n",
"L9I4nJPG4Xn4ezjOAJYBfgQ8FkTJp3Xzn4gMJwqMHNI4nJnG4an44Pg+sCZwBfCXIEq2LbQ4EZEW\n",
"UWD0QxqH/0nj8HjA8HeLbwz8IYiSr6m1ISLtToExAGkczkjj8LP4dTieA74J3Kk1OESknSkwBiGN\n",
"w7uBDwI3ADvg56fav9iqRESaQ4ExSGkcvoK/d+MI/Iy41wVR8hNdgisi7UaBMQSy+zcuAbYAHgQO\n",
"x08zsnmxlYmIDB0FxhBK4/Ax/GSG5+MHxqcGUXJCECX6exaRytMPsiGWLdx0ArAH8Bp+DY6bgyhZ\n",
"rdjKREQGR4HRJGkc3oJfX3wSfibcvwZR8tFiqxIRGTgFRhOlcfgCsCdwArA8vqVxfhAlY4utTESk\n",
"/xQYTZbG4YI0Ds8HtgEeA47Dj21sWGxlIiL9o8BokTQOHwS2BH6Cv3ejM4iSI7WmuIhURWkCw8w6\n",
"zOxnZvZzM1ul6HqaIY3DN9M4PBLYH5gDXARcH0TJisVWJiLSt9IEBjAGOB74HdDWE/qlcXgDvpVx\n",
"N7AvfkB8p2KrEhHpXWkCwzl3H7AR8GX8zW9tLY3DfwG7AKcAqwF3BFFypiYxFJGyaklgmNk2ZjY5\n",
"ezzSzC4ys/vMbLKZrZvt3wq/pvZHgS+1oq6ipXE4P43DbwPbATOAr+K7qDStiIiUTtMDw8xOAi7B\n",
"dzkB7AOMds5NBE4G4mz/MsBlwDnAVc2uq0zSOJyKn1bkTiAE7g6iZPViqxIRWVQrWhhPAvsBtauB\n",
"tsPfzIZzbhr+yiGcc5Odcwc55w51zv2pBXWVShqHr+FbV5cBHcC0IEo2KbYqEZGFlmj2F3DO3WBm\n",
"69TtGg/MrHs+38xGOucW9Pe9Ozs7uwZbX5mcduC76erq4t5HZnHHX2euNXqJEdOvSaew3hrteZ9f\n",
"u31+w4k+u+Gp6YHRjZn40KgZUFgAdHR0tOU9DFtuCXdEySfmzuu6/Mq7XloC+Hwahz8puq6h1NnZ\n",
"2dWun1+702dXbYMJ+yKukpqCn5gPM5sATC+ghtJL4/AaYGfgVeDiIErO1qy3IlKkVv4AqqXajcAc\n",
"M5uCH/A+oYU1VEoah/fhp0t3wInAtUGULFVsVSIyXLWkS8o5NwOYmD3uAo5uxddtB2kcPhVEybb4\n",
"ZWD3A9YKomTvNA6fL7g0ERlm1MVRAWkcvoqfIv1yYCv85IUfKLYqERluFBgVkcbhXOAQ4OvAe4D7\n",
"gijZtdiqRGQ4UWBUSLZ2+LeAA4GxwC1BlBxWcFkiMkwoMCoojcOr8fNQvQ5cEkTJWZomXUSaTYFR\n",
"UWkc3ou/guoJ/BQrlwVRUsR9NSIyTCgwKiyNwyfxV5/dD3wWP3HhuEKLEpG2pcCouDQOX8J3T90O\n",
"7A1MCqJkuWKrEpF2pMBoA2kczgL2Aq4FdsDPdrtasVWJSLtRYLSJNA7fBj6JX/b1g8C9QZS8r9iq\n",
"RKSdKDDaSBqH84HPA98E1gWmBFGyabFViUi7UGC0mexejW8Ax+GXfr0niJLtCi5LRNpArsAwszHZ\n",
"dn0z29PMFDQll8bhD4BPA0sDtwVRslfBJYlIxfX5g9/MvgH81MzeA9yNn1324mYXJoOXxuFV+Cun\n",
"uoCbgig5uOCSRKTC8rQUQuAw/IDqVc65XfHrT0sFpHF4C7ArMAu4PIiSU4Moac8l/ESkqfIExijn\n",
"3Nv4yzZvNrNRgNZkqJBsXY3tgX8DpwGPBVHyKS3IJCL9kecHxu1m9hAwBt8ldReQNrMoGXppHD4E\n",
"bAycC6wOXAncH0TJzoUWJiKV0WdgOOe+jF9SdUK29vYxzrmTml6ZDLk0Dl9N4/BEwICr8F2LdwRR\n",
"cnMQJZsUW52IlF2eQe8V8Gsw3G5mKwMnmNm7ml6ZNE0ahzPSOPw00AHcCXwUeDCIkkuDKFmz2OpE\n",
"pKzydEldAvwZWBE/cPosvjtDKi6NwwfwA+J7AI8AnwOeCKLkyEILE5FSyhMY73XOXQzMd87Ncc59\n",
"DViryXVJi2Q3+t0CbIYPjDeAi3QJrog0yhMY75jZf2c/NbP1gfnNK0mKkMbh/DQOfwbsDLyKX18j\n",
"LLgsESmRPIFxKv7KqLXNLAGm4Mc0pA1lV1PtAcwBrgmiZMdiKxKRsshzldQkYHfgYOBSYBPn3G+b\n",
"XZgUJ43DqcC++H8fvwmiZMuCSxKREugxMMzs1Nof4GhgS2Bz4MhsuhBpY2kc3gYciJ+LalIQJRsW\n",
"XJKIFKy3Fsab+AHQzfF3eb8OvIJf3c2aX5oULY3D64Aj8VfI/T6IkrULLklECtRjYDjnznXOxfgp\n",
"sndwzp3vnPshsBuwfqsKlGKlcfhT4CTg3fhZb1cpuCQRKUieQe8VgFF1z8cBWjN6GEnj8Bzgu8AG\n",
"wK0KDZHhKU9gXAx0mtm5ZnYe0Al8r7llSQl9Bf9vYTNgqsY0RIafPFdJxfiFeJ4DngH2d85d1OzC\n",
"pFzSOOzCX/xwGvBe4I+auFBkeMkzl9RIYGtgIvAhYEetuDc8ZXeFnw4chJ/i/tYgSj5XcFki0iJ5\n",
"fvCfjb8P43Kgdifwec0sSsotjcMr8XNQzQQuDaLk21pbQ6T95flPvju+G+o3zrmbgP2BjzS3LCm7\n",
"NA7vASYAT+LHN34VRMm4YqsSkWbKteIesETd8yWAec0pR6okjcMn8KFxL/C/+JmNRaRN5QmMq4C7\n",
"zOyLZnYsMBm4urllSVWkcfgyvnvqfuBTQZTsWnBJItIkea6S+jbwTWBt4D3At5xzZza7MKmONA7f\n",
"Bo4CFgAXBlEytuCSRKQJ8g5U/hO/jvdvgDfMbIfmlSRVlC3G9CP8LABawlekDeW5rPYC4GbgDPw1\n",
"+KcBpze1Kqmqr+Pv1/lqECWaPkakzeS9Ssqcczs653aq/Wl2YVI9aRzOBI4DxgAXBFEyouCSRGQI\n",
"5QmMp3MeJwJwHTAJP0nlxwuuRUSGUJ4geBV4xMyuNrOfZX8ua3ZhUk3ZFCJfwK/Yd34QJZqoUqRN\n",
"5AmMSfhlWm/FL9V6d/ZHpFtpHD4FnImfGv9bBZcjIkNkib4OcM79vAV1SPs5Bz9p5TFBlFyXxqF+\n",
"yRCpOI1NSFNk92YcDswHbgqiZKOCSxKRQeptTe/1WlmItJ80Dv8AHAosD9wSRMkaBZckIoPQWwvj\n",
"1wBmdlOLapE2lMbhL4BT8DMF3BxEybIFlyQiA9TbGMYCM5sCbGpmkxte63LODeniOWa2C/AJ/DoL\n",
"Zzvnpg/l+0uhzsIHxpHAdUGU7Hnage8uuCQR6a/eAmNn/HKcl+Hv7h4BdNVth9o459wRZrYZ/mZB\n",
"BUabSOOwK4iSLwBrAnsBl3R1NeOfkIg0U49dUs65mc65e4BtgUeB8cC7gEedc0N+xYtz7rdmtjRw\n",
"LPDzoX5/KVYah/OAA/Cz2n7mmj+8TBAlKxdcloj0Q56rpLYA/gIcAnwG+JuZBf35Ima2Ta1by8xG\n",
"mtlFZnafmU02s3Wz/SsBPwS+4Zx7qV/fhVRCGodv4lsY9zz2zByAh4Mo2afYqkQkrzyB8W1gO+fc\n",
"fs65ffEL5uS+GcvMTsIvrDMm27UPMNo5NxE4GYiz/TGwKnCWme2f9/2lWtI4/A+w04e3WA5gWeDG\n",
"IEp+EUTJ8sVWJiJ9yRMYSzjn/l574px7Gj+OkdeTwH5152yHv3sc59w0YMvs8Wecc3s65w5yzl3f\n",
"j/eXiknjcMG27x8PsDnwZ+Ag4LEgSk4MomR8ocWJSI/6vNMb+JeZHQ9civ+hfyjwj7xfwDl3g5mt\n",
"U7drPDCz7vl8MxvpnFuQ9z1rOjs7NXJaYacd+O5H5i/oYsojs7j3kVmrzp3XdfbYJUecfc7P7mSb\n",
"DZZh6bGjii5ReqD/e8NTnsA4FD+2cAq+RXIncMQgvuZMfGjUDCgsADo6OjR9dkV1dnZ21T6/rbeC\n",
"O32X1DFz3uk6/p6HZq10z0Oz3gSOSuPwymIrlUb1n51Uz2DCPs9cUi8wtNNUTwEC4Fozm4AunxUg\n",
"jcPXgDODKPkecBh+WeArgijZGvhyGodzCy1QRFo6l1Qt1W4E5mQ3BcbACS2sQUoujcPZaRz+ANgK\n",
"eBj4InBnECWrF1uZiOTpkho059wMYGL2uAs4uhVfV6orjcPHgyiZAPwUPwNAZxAl22dTp4tIAfKs\n",
"6a31DKQQaRy+AXwS+AqwOvC7IEreVWxVIsNXni6pvc1M06BLIdI47Erj8DvAuYABNwRRMrrgskSG\n",
"pTxdUi8Dj5nZA8Bb2b4u59znmleWyGL+D1gX2Be4OJubajcgBEYBh6Zx+E6B9Ym0vTyBcXm2rQ1a\n",
"N2vyQZEepXG4IIiST+OXCf4s8ClgybpDbgGubn1lIsNHn11N2RKtd+NbGr8E7nHOXd7rSSJNkMbh\n",
"bGBv4CHgcfy06fvhf4GJgijRvQEiTdRnC8PMDsDftLcU8D/AFDM7yTl3RbOLE2mUxuHzwCb1+4Io\n",
"uQnfVbUD/pcbEWmCPIPZ/4cPipnOuefxs9d+palVifRPbQLLLxVahUibyxMY851z/537yTn3HDC/\n",
"eSWJ9Nt9wDQgCKJkg6KLEWlXeQLjYTP7IjDazDYzs58ADza5LpHc0jjswrcyRqCZA0SaJk9gHINf\n",
"WvMt/HKtM4HPN7MokQG4EZgBfDaIkk36OFZEBiDPVVJvAF/Hr7j3KeBk59ysZhcm0h/ZErCnAmOB\n",
"PwZR8rGCSxJpO3mmBtkeeAK/zvZVwKNmtlWT6xLptzQOfwHUVmu8NoiS7wZRMrbImkTaSZ4uqfOB\n",
"vZ1zHc65LfBz+1zQ3LJEBiaNwxuAbfArPZ4EuCBKPhVESbf/1oMoWTKIkgM13YhI33LNEeWcm173\n",
"+M8seoetSKmkcfgwfunfc4DVgCuBX/dw+OH4lvPBralOpLp6vHHPzLbAX3XysJl9Hz/N9Hz8OMbU\n",
"1pQnMjBpHL4OnBREyYXAb4H9gyhZPluoqd4e2XazlhYoUkG9tTDOw88QuhbwQeAH+K6o/wHe3/zS\n",
"RAYvjcMZwG+yp4uMvQVRMgbYKXv6gRaWJVJJPbYwnHM7trAOkWaqtYgnALfV7Z+In/IGYKOWViRS\n",
"QXnmktoBOB6oX7imyzm3c9OqEhla07LthIb9H862rwOrBFGyUhqHL7WuLJFqyTPo/XPgJuD0uj9n\n",
"NLEmkSGVxuELwN+BbRpmtN0dmAvUJtJUt5RIL/Ksh/GMc+4XTa9EpLmmAQfgF2F6MoiSVYHNgTuB\n",
"P2XHfADNdivSozyB8QMzuxL/H6s26WCXQkQqZio+MCbg79HYLdt/K/Bw9lgtDJFe5AmM2rxR2zfs\n",
"V2BIldQPfF8J7JU9/z1+MaYuFBgivcoTGKs75zZseiUizfUgfrxiQhAlE4CPA48A07PlX59GgSHS\n",
"qzyD3n8ws8DM8oSLSCmlcfg28Bf8PUWX4G9KPSqNwwXZIQ8DKwVRskpBJYqUXp7A2BtIgLlmtiD7\n",
"owWUpIqm4lvVGwM/TePwD3WvaRxDpA99thqcc6u1ohCRFpgKHAe8iF96uF59YExuZVEiVZHnxr1T\n",
"8QOCi3DO6V4MqZpJwO3A99I4fKXhNbUwRPqQZ1yi/kan0cBH0OSDUkHZxIO79fCyw/9iZK2rSKRa\n",
"8nRJnVb/3MzOYNH5eEQqL43Dt4Io+ScKDJEe5VoPo8F4/Ay2Iu3mcWCNIErGF12ISBnlGcP4e93T\n",
"EfhJCM9pWkUixXH4Lqv1gQcKrkWkdPKMYexU93gB8JpzbmaT6hEpksu2hgJDZDF5AuNZ/DTQ7yIb\n",
"ADczNJeUtKHHs63GMUS6kScwfgmsDTzKopfXKjCk3dS3MPotiJINgROBL6RxOHvIqhIpiTyBsQmw\n",
"oXNusXsxRNrMv4C3gA0GeP7BwCHADfh1xEXaSp6rpB4FVm92ISJFy+aVegLYoGGhpbxWzrardvdi\n",
"ECWrDPB9RUohTwtjacCZ2UPAnGyflmiVdvU4sCmwBn78rj96DIwgSgw/O+4XgQsHU6BIUfIExre7\n",
"2afuKWlX9eMY/w2MrGXwY+D+NA4v7eHcWmB0N//aRvgW/R4oMKSi8tzpfVcL6hApi1pgbIBfZbJm\n",
"U+BIYK8gSi5L47C7X5p665KqvTYhiJIRPZwvUmoDudNbpJ31dGntntl2TXqeoLC3FkbttRXx64qL\n",
"VI4CQ2RRtRbGNkGU1LfA96x7/JHGk4IoGQ0slz3trYUBfplYkcpRYIjUyWa0nQJsC0wKomTFIEpW\n",
"xP+Qfyw7bLHAAFaqe7waQBAlo+r2KTCk8hQYIovbA/gNsAt+Kv+j8P9XfoGfMmT7IEqWaTinPhCW\n",
"C6LkQGBOECUbZ/tqgfIOsF2zChdpJgWGSIM0DmcC+wJnAesB38pe+h1wK35dmB0bTmtcC/wQ/EUl\n",
"u2TPVwbeBO4APhhEyXrdfe0gSsbUhYxIqSgwRLqRxuGCNA6/ChyLv4z8n8Df8IEBsGvDKbUWxhvZ\n",
"dvtsu2nd6y8Cv8qeH9DDlz4G+FsQJRsNvHqR5ihdYJjZzmZ2SdF1iACkcfhDfGsizC6FvR8/a/OW\n",
"DYfWAqO21OuYbLtJdg/HysBLwE3A2/QcGLVpSdYZbO0iQ61UgWFm6wKbAWOLrkWkJo3De9I4fDB7\n",
"PBt/x/ZmPQxqP9Rw+geAZfEB8mIah6/j1xb/QBAl63Tz5VbMtst185pIofLc6d0yzrmngPPM7Iqi\n",
"axHpRSewMb418Gi2r7vAmA8sBWydPX8x204HQvz9GDMAgihZDhjHwsBYtgl1iwxKy1oYZraNmU3O\n",
"Ho80s4vM7D4zm5y1LESqora40hZ1+2qB8be6fbdl29rAdy0waqtYvrfu2MeB51ALQ0qsJYFhZicB\n",
"l7CwX3cfYLRzbiJwMhC3og6RIdKZbTvq9q2MHxx/tG7fldm2NlFnb4FRu8qqdvWUAkNKp1UtjCeB\n",
"/chW7MNfhz4JwDk3jYYBROfcQS2qS2Qg/ooPh8YWxsvAC/hB8WeBu7LXtsq2vQVGzVLZVoEhpTOi\n",
"q6s1c6CZ2TrA1c65bbOroK53zk3KXvsH8F7n3IK879fZ2anJ26QwP/rt88ycPZ+T/3cNRo4YwXev\n",
"+zdLjx3JF/ZajcnTX2f8uFF0rLc0F0/6D8+/+g4AB+ywIu9/9zjmL+jizGueZY0VR3PY7r5hcdov\n",
"n1nk/TddZyn2m7hCy78vGR46OjoGtC5LUYPeM4Hxdc9H9icsagb6TUvxOjs7u6r8+b30y+QK4NNn\n",
"XP2sAU8D77w1d8E9HR0dH+qo66g6/epkd7J7N351z8sT0zj8I8CCXz379DMvzR3X0dHhFyf75TOL\n",
"/AI0fcbs9Mwv7rZ3S76Zfqr6ZzfcDeaX7aIuq52Cn34BM5uAv2pEpEpq4xgTgLWyx883HpTG4e/x\n",
"91+Av/mv5u/AakGUjGu4PLdGXVJSOq1uYdSS7UZgNzObkj0/pMV1iAzWHdn2w/ipQgDu7eHY9wEb\n",
"pXFYv4JfbRxjHbpf2U+BIaXTssBwzs0AJmaPu4CjW/W1RZrgIeDfwO4sDIzbujswjcNZwLSG3fUD\n",
"3693c5ruw5DSKdWd3iJVkU0Tcit+Ftp9gWdYuJZGHrXuqbWAxplvQS0MKSEFhsjATcq2o4Df93PZ\n",
"1dq4xgosegFIzXLZHFQipaHAEBm42/H3XEAP3VG9eDnbrsjiLYz/4ENoKURKRIEhMkBpHL4C/BE/\n",
"Z9QdfRzeqKfAWMDClf3ULSWlosAQGZyDgZ3TOHyxzyMXVQuMFVgYGN8EdkOBISWlwBAZhDQOn07j\n",
"8J4BnDoT35qob2E8kcbhnSy8akqBIaWiwBApQBqHC4BXWDQwaqv1KTCklBQYIsV5mUWvkqoFxqxs\n",
"293ltiKFUWCIFOcVFg2MWlC8nW1HL3aGSIEUGCLFeRk/28Ia2fNaC2Nuth2z2BkiBVJgiBSndqXU\n",
"2tm2MTBGB1GyWLdUECUjgihZvtnFiTRSYIgUpxYY78m2tcCodUntDMwKouTzDed9E3g1iJJtmlyf\n",
"yCIUGCLFeSXbNgZGrYXxsWx7QcN5p2Tb3ZtUl0i3FBgixXm57vE8FrYsaoHxT3r3zpBXJNILBYZI\n",
"ceoD4426yQsXG/TuYZGlec0qTKQ7CgyR4rxS9/iNuse1lkb9mhjrd3O+WhjSUgoMkeIs0sKoe1xr\n",
"YdRfIfWXIEqs4XwFhrSUAkOkOE+ycJzi7rr9c7s5diywV8M+dUlJS7V6TW8RyaRx+AYLr5Cq93bD\n",
"8/OAL3VzXHfjGiJNoxaGSPk0tjAaA6RGU4dISykwRMpHgSGlpMAQKR8FhpSSAkOkfBoDQoEhpaBB\n",
"b5Hy6bGFEUTJiLr9S2b7RgE/Ah4GtgWOSOPwzWYXKcOPAkOkfBoDo/752LrHtRbGdsBRdfv/Bnyn\n",
"CXXJMKcuKZGSSeNwPjC/bld9l9RSdY9rgVEfIjScKzJkFBgi5VTfqqgPjKXrHtcCo3FtjJlNqUiG\n",
"PQWGSDn1JzBWaTh3TlMqkmFPgSFSTrXAmAcsqNvfXZdUY2BoaVdpCgWGSDm93bCtydPCUGBIUygw\n",
"RMppbsO2Jk9gNA6CiwwJBYZIOdWCorGFkadLSoEhTaHAECmn/nRJrdxwjAJDmkI37omUU08tjPrA\n",
"2CWIkpnA+IZjVgii5GngXOBD2b4HgFOAt4AVgAvTODxuaEuWdqfAECmnngKjMRzG48PgBuAz+KVc\n",
"dwHeC1xQd9xK2bG1848FFBjSLwoMkXLqKTCWbXg+J43DDoAgSn4NPA6s2M37Ld3NPpF+0RiGSDn1\n",
"NIbRGBiz6h7XbthboZv3U2DIoCkwRMqpp8tql2t4Xj8NSE/ToIMCQ4aAAkOknPrqknoj29YHRm9T\n",
"gigwZNAUGCLl1FeX1CvZtrsuqe4s1bijYW0NkT4pMETKqbcWxltA7Yd9fQvjnV7er7sWhlbsk35R\n",
"YIiUU0+BsRzwOgtvzvtvCyONwy56bmV015pYrNUh0hsFhkg59dYlNZOFgdG49kV/pjZXYEi/KDBE\n",
"yqmnq6QGExiNrykwpF9Kc+OemU0EjsieHuece73IekQK1l2X1JLAOHyX1JLZvtkN5/V2ae2bLDrP\n",
"lAJD+qVMLYzD8YFxKfCJgmsRKVp3gVG7Qqq3S2l7a2G82fBcgSH9UqbAGOWcmws8B6xedDEiBetu\n",
"DKO7wGhsUfQWGI2tEQWG9EtLuqTMbBvgO865ncxsJHAhsCn+H/thzrmngNlmNhpYA3i+FXWJlFh3\n",
"LYzaXd713bWNAdFXl1Q9BYb0S9NbGGZ2EnAJC5eN3AcY7ZybCJwMxNn+nwAX47umrmh2XSIl14ou\n",
"Kd39Lf3SihbGk8B+LAyB7YBJAM65aWa2Zfb4AeCQFtQjUgV5u6QGExhrBFGyBDAmjcM3gyhZAz+o\n",
"/nR2TwdBlCyHn4ZkXBqHb9SfnL02M6trNrBkGoezG45ZFphVe7++BFEyHpidxuH8HMcuBcxL47Dx\n",
"SjJpkqa3MJxzNwDz6naNZ9F/8POzbioRWeithi0sGhi1H5IvNpzXGAr1GscwYuAfwBtBlGwHPIv/\n",
"Be/LAEGU7A68hv//OysLF7LXDsxem51t5zZ+7SBK1sR3n/2ql5rqjx+bfW9T8hwPTAWuz3msDIER\n",
"XV25gn9QzGwd4Grn3LZmFgNTnXPXZq/9yzm3Vn/fs7Ozs/mFi4i0oY6OjgHNI1bEfRhTgAC41swm\n",
"ANMH8iYD148MAAADuElEQVQD/YZFRGRgWhkYtRbBjcBuZlZrdmrcQkSkAlrSJSUiItWnwWYREclF\n",
"gSEiIrkoMEREJBcFhoiI5FKa6c0HS9OjV5+Z7Qx80jl3eNG1SH5mtgt+humlgLOdcwO6VF5az8w6\n",
"gC/gV2Q8yTn3n96Ob6cWhqZHrzAzWxfYjEXXa5BqGOecOwI4F9i96GKkX8YAxwO/A7bt6+B2CgxN\n",
"j15hzrmnnHPnFV2H9J9z7rdmtjRwLPDzgsuRfnDO3QdshJ8O5sG+jq9El5SmR6+2nJ+flFCez87M\n",
"VgLOBr7hnHupwHKlTs7Pbivgz8BHgVOB43p7z9K3MDQ9erX14/OTkunHZxcDqwJnmdn+LS9UFtOP\n",
"z24Z4DLgHOCqvt63Ci0MTY9ebbk+vxrn3EGtLU96kff/3meKKU96kfezmwxMzvumpW9haHr0atPn\n",
"V1367KqrWZ9dFT/smfhvvmakc25BUcVIv+nzqy59dtU1JJ9dFQNjCrAHwGCmR5fC6POrLn121TUk\n",
"n10VxjBqND16tenzqy59dtU1pJ+dpjcXEZFcqtglJSIiBVBgiIhILgoMERHJRYEhIiK5KDBERCQX\n",
"BYaIiOSiwBARkVwUGCIikosCQ6QPZvYjM9OMrDLsKTBE+qbpEETQ1CAi3TKzc4EAeAGYi19XoAu/\n",
"ItlIoBM4xjn3tpl9HDgdmA38Bb9c8CFmNgOYil+rfHv8qmbdnf+R7Pwlgb8DhzvnXmnRtyqSm1oY\n",
"Ig2yVeO2xK91HALrAUsDhwHbOuc2B14EvmxmKwPfA3bOznkXC1skXcDNzrn3A6v0cv5ZwO7OuS2A\n",
"3wPfbck3KtJPVZqtVqRVdgSuc87NB141s5uAEcD6wDQzAxiNbyVsB/zROfccgJldDuxb917Tsu1O\n",
"PZy/NbA2cFe2fxTwchO/N5EBU2CILK6LRVvf8/A/yH/tnDsOwMyWwf//2aHh2BEN7/VWth3Zy/n3\n",
"OufCbP9YFl3oRqQ01CUlsrjbgAPMbLSZLQvsle3f18xWNrMRwI+BY4H7gK3MbLVs/wFAdyuZ3dXD\n",
"+dOAbc1s/ey4rwFnN+sbExkMBYZIA+dcig+Nh4BbgMeA1/AD03dm+wG+45x7Cf+D/zbgT/hWw1vd\n",
"vOf0Hs5/Afgc8Gszmw5sDnypOd+ZyODoKimRQTCzFfCBcbpzrsvMvg887py7oODSRIacWhgig5Bd\n",
"/ro88JCZ/RU//nBJsVWJNIdaGCIikotaGCIikosCQ0REclFgiIhILgoMERHJRYEhIiK5/D8JPofv\n",
"cAO4LQAAAABJRU5ErkJggg==\n"
],
"text/plain": [
"<matplotlib.figure.Figure at 0xad5dc74c>"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"dd = properties.degreeDistribution(G)\n",
"plt.xscale(\"log\")\n",
"plt.xlabel(\"degree\")\n",
"plt.yscale(\"log\")\n",
"plt.ylabel(\"number of nodes\")\n",
"plt.plot(dd);\n",
"# plf = properties.degreePowerLaw(G, dd)\n",
"# print(\"Power law fit? \", plf);"
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true
},
"source": [
"Note: properties 'module' object has no attribute 'powerLawExponent', thus, properties.powerLawExponent(G, dd) doesn't work anymore. The same case with properties.powerLawFit."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"##### How often is the friend of a friend also a friend? Let's go for the average fraction here, other definitions are possible."
]
},
{
"cell_type": "code",
"execution_count": 74,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Exact average local clustering coefficient: 0.4402875516253531\n"
]
}
],
"source": [
"alcc = properties.ClusteringCoefficient.avgLocal(G)\n",
"print(\"Exact average local clustering coefficient: \", alcc)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"##### How many connected components does the graph have?"
]
},
{
"cell_type": "code",
"execution_count": 75,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"1-5) Number of components: 1\n"
]
}
],
"source": [
"n = properties.ConnectedComponents(G)\n",
"n.run()\n",
"print(\"1-5) Number of components: \", n.numberOfComponents())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This means that all nodes are connected."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Support"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"NetworKit is an open-source project that improves with suggestions and contributions from its users. The email list `networkit@ira.uni-karlsruhe.de` is the place for general discussion and questions. Also feel free to contact the authors with questions on how NetworKit can be applied to your research.\n",
"\n",
"-- [Christian L. Staudt](mailto:christian.staudt@kit.edu) and [Henning Meyerhenke](mailto:meyerhenke@kit.edu)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Q&A 3 answer modified by [mkc](mailto:melvin.cabatuan@dlsu.edu.ph)"
]
}
],
"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.4.3"
}
},
"nbformat": 4,
"nbformat_minor": 0
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment