`shift+enter`

), or all at once (via the `Cell->Run All`

command). Try running all cells now to verify that NetworKit has been properly built and installed.

```
In [1]:
```%matplotlib inline
import matplotlib.pyplot as plt

```
In [2]:
```from networkit import *

```
```

```
In [3]:
```cd ../../

```
```

Let us start by reading a network from a file on disk: PGPgiantcompo.graph. In the course of this tutorial, we are going to work 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. It is distributed with NetworKit as a good starting point.

There is a convenient function in the top namespace which tries to guess the input format and select the appropriate reader:

```
In [4]:
```G = readGraph("input/PGPgiantcompo.graph", Format.METIS)

`readGraph`

function tries to be an intelligent wrapper for various reader classes. In this example, it uses the `METISGraphReader`

which is located in the `graphio`

submodule, alongside other readers. These classes can also be used explicitly:

```
In [5]:
```graphio.METISGraphReader().read("input/PGPgiantcompo.graph")
# is the same as: readGraph("input/PGPgiantcompo.graph", Format.METIS)

```
Out[5]:
```

It is also possible to specify the format for `readGraph()`

and `writeGraph()`

. Supported formats can be found via `[graphio.]Format`

. However, graph formats are most likely only supported as far as the NetworKit::Graph can hold and use the data. Please note, that not all graph formats are supported for reading and writing.

Thus, it is possible to use NetworKit to convert graphs between formats. Let's say I need the previously read PGP graph in the Graphviz format:

```
In [6]:
```graphio.writeGraph(G,"output/PGPgiantcompo.graphviz", Format.GraphViz)

NetworKit also provides a function to convert graphs directly:

```
In [7]:
```graphio.convertGraph(Format.LFR, Format.GML, "input/example.edgelist", "output/example.gml")

```
```

`Graph`

is the central class of NetworKit. An object of this type represents an undirected, optionally weighted network. Let us inspect several of the methods which the class provides.

```
In [8]:
```n = G.numberOfNodes()
m = G.numberOfEdges()
print(n, m)

```
```

```
In [9]:
```G.toString()

```
Out[9]:
```

Nodes are simply integer indices, and edges are pairs of such indices.

```
In [10]:
```V = G.nodes()
print(V[:10])
E = G.edges()
print(E[:10])

```
```

```
In [11]:
```G.hasEdge(42,11)

```
Out[11]:
```

This network is unweighted, meaning that each edge has the default weight of 1.

```
In [12]:
```G.weight(42,11)

```
Out[12]:
```

```
In [13]:
```cc = components.ConnectedComponents(G)
cc.run()
print("number of components ", cc.numberOfComponents())
v = 0
print("component of node ", v , ": " , cc.componentOfNode(0))
#print("map of component sizes: ", cc.getComponentSizes())

```
```

```
In [14]:
```dd = sorted(centrality.DegreeCentrality(G).run().scores(), reverse=True)
plt.xscale("log")
plt.xlabel("degree")
plt.yscale("log")
plt.ylabel("number of nodes")
plt.plot(dd)

```
Out[14]:
```

A simple breadth-first search from a starting node can be performed as follows:

```
In [15]:
```v = 0
bfs = graph.BFS(G, v)
bfs.run()
bfsdist = bfs.getDistances()

`v`

to other nodes - indexed by node id. For example, we can now calculate the mean distance from the starting node to all other nodes:

```
In [16]:
```sum(bfsdist) / len(bfsdist)

```
Out[16]:
```

`PGPgiantcompo`

is an unweighted graph, the result is the same here:

```
In [17]:
```dijkstra = graph.Dijkstra(G, v)
dijkstra.run()
spdist = dijkstra.getDistances()
sum(spdist) / len(spdist)

```
Out[17]:
```

```
In [18]:
```K = readGraph("input/karate.graph",Format.METIS)
coreDec = centrality.CoreDecomposition(K)
coreDec.run()

```
Out[18]:
```

```
In [19]:
```set(coreDec.scores())

```
Out[19]:
```

```
In [20]:
```viztasks.drawGraph(K, nodeSizes=[(k**2)*20 for k in coreDec.scores()])

```
```

`community`

module. The module provides a top-level function to quickly perform community detection with a suitable algorithm and print some stats about the result.

```
In [21]:
```community.detectCommunities(G)

```
Out[21]:
```

```
In [22]:
```communities = community.detectCommunities(G)

```
```

*Modularity* is the primary measure for the quality of a community detection solution. The value is in the range `[-0.5,1]`

and usually depends both on the performance of the algorithm and the presence of distinctive community structures in the network.

```
In [23]:
```community.Modularity().getQuality(communities, G)

```
Out[23]:
```

`Partition`

data strucure, which provides several methods for inspecting and manipulating a partition of a set of elements (which need not be the nodes of a graph).

```
In [24]:
```type(communities)

```
Out[24]:
```

```
In [25]:
```print("{0} elements assigned to {1} subsets".format(communities.numberOfElements(), communities.numberOfSubsets()))

```
```

```
In [26]:
```print("the biggest subset has size {0}".format(max(communities.subsetSizes())))

```
```

*i* contains the subset id of node *i*.

```
In [27]:
```community.writeCommunities(communities, "output/communties.partition")

```
```

*PLM*, our parallel implementation of the well-known Louvain method. It yields a high-quality solution at reasonably fast running times. Let us now apply a variation of this algorithm.

```
In [28]:
```community.detectCommunities(G, algo=community.PLP(G))

```
Out[28]:
```

```
In [29]:
```sizes = communities.subsetSizes()
sizes.sort(reverse=True)
ax1 = plt.subplot(2,1,1)
ax1.set_ylabel("size")
ax1.plot(sizes)
ax2 = plt.subplot(2,1,2)
ax2.set_xscale("log")
ax2.set_yscale("log")
ax2.set_ylabel("size")
ax2.plot(sizes)

```
Out[29]:
```

```
In [30]:
```from networkit.graph import Subgraph
c2 = communities.getMembers(2)
sg = Subgraph()
g2 = sg.fromNodes(G,c2)

```
In [31]:
```communities.subsetSizeMap()[2]

```
Out[31]:
```

```
In [32]:
```g2.numberOfNodes()

```
Out[32]:
```

```
In [33]:
```communities2 = community.detectCommunities(g2)

```
```

`centrality`

module.

```
In [34]:
```K = readGraph("input/karate.graph", Format.METIS)

```
In [35]:
```bc = centrality.Betweenness(K)
bc.run()

```
Out[35]:
```

```
In [36]:
```bc.ranking()[:10] # the 10 most central nodes

```
Out[36]:
```

`PGPgiantcompo`

, with a probabilistic guarantee that the error is no larger than an additive constant $\epsilon$.

```
In [37]:
```abc = centrality.ApproxBetweenness(G, epsilon=0.1)
abc.run()

```
Out[37]:
```

The 10 most central nodes according to betweenness are then

```
In [38]:
```abc.ranking()[:10]

```
Out[38]:
```

```
In [39]:
```# Eigenvector centrality
ec = centrality.EigenvectorCentrality(K)
ec.run()
ec.ranking()[:10] # the 10 most central nodes

```
Out[39]:
```

```
In [40]:
```# PageRank
pr = centrality.PageRank(K, 1e-6)
pr.run()
pr.ranking()[:10] # the 10 most central nodes

```
Out[40]:
```

```
In [41]:
```import networkx as nx
nxG = nxadapter.nk2nx(G) # convert from NetworKit.Graph to networkx.Graph
print(nx.degree_assortativity_coefficient(nxG))

```
```

**Erdös-Renyi model** is the most basic random graph model, in which each edge exists with the same uniform probability. NetworKit provides an efficient generator:

```
In [42]:
```ERG = generators.ErdosRenyiGenerator(1000, 0.1).generate()

**random graph with community structure** is to use the `ClusteredRandomGraphGenerator`

. It uses a simple variant of the Erdös-Renyi model: The node set is partitioned into a given number of subsets. Nodes within the same subset have a higher edge probability.

```
In [43]:
```CRG = generators.ClusteredRandomGraphGenerator(200, 4, 0.2, 0.002).generate()

```
In [44]:
```community.detectCommunities(CRG)

```
Out[44]:
```

**Chung-Lu model** (also called **configuration model**) generates a random graph which corresponds to a given degree sequence, i.e. has the same expected degree sequence. It can therefore be used to replicate some of the properties of a given real networks, while others are not retained, such as high clustering and the specific community structure.

```
In [45]:
```degreeSequence = [G.degree(v) for v in G.nodes()]
clgen = generators.ChungLuGenerator(degreeSequence)

In this section we discuss global settings.

`FATAL`

, `ERROR`

, `WARN`

, `INFO`

, `DEBUG`

and `TRACE`

. (Currently, logging is only available on the console and not visible in the IPython Notebook).

```
In [46]:
```getLogLevel() # the default loglevel

```
Out[46]:
```

```
In [47]:
```setLogLevel("TRACE") # set to most verbose mode
setLogLevel("ERROR") # set back to default

`--optimize=Opt`

) and thus, every LOG statement below INFO is removed. If you need DEBUG and TRACE statements, please build the extension module by appending `--optimize=Dbg`

when calling the setup script.

The degree of parallelism can be controlled and monitored in the following way:

```
In [48]:
```setNumberOfThreads(4) # set the maximum number of available threads

```
In [49]:
```getMaxNumberOfThreads() # see maximum number of available threads

```
Out[49]:
```

```
In [50]:
```getCurrentNumberOfThreads() # the number of threads currently executing

```
Out[50]:
```

`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.

```
In [ ]:
```