Network Analysis for web-based hosting service [view code]

The code is available here or by clicking on the [view code] link above.

Quick Introduction • Libraries • Examples

Quick introduction

From Wikipedia:

Network theory is the study of graphs as a representation of either symmetric relations or asymmetric relations between discrete objects. In computer science and network science, network theory is a part of graph theory: a network can be defined as a graph in which nodes and/or edges have attributes (e.g. names).

Applications of network theory include logistical networks, the World Wide Web, Internet, gene regulatory networks, metabolic networks, social networks, epistemological networks, etc.; see List of network theory topics for more examples.

An Eulerian path, is a path which crosses every edge exactly once. It exists if and only if:

• Every vertex has even degree
• Exactly two nodes have odd degree

The degree of a vertex is the number of edges incident to the vertex (loops count twice).

Types of Networks

• Undirected: connections extends in both directions.
• Directed: connections may only flow in one direction.
• Cyclic: contains at least one cycle (node can be connected to itself by traversing at least one edge).
• Acyclic: one that contains no cycles
• Multigraph: multiple links connecting the same pair of nodes.

Properties

Some important properties of networks are:

• The degree of a node is given by the number of links of that node.
• The minimum path length is the minimum number of edges needed to traverse to connect two nodes
• The diameter is the length of maximum shortest path of a given network.
• Two nodes are connected if there exists a path between them
• Isomorphism between graphs exists one graph can be "twisted" into the other cutting and/or gluing.

Libraries

Using the networkx library we can work with graphs.

import networkx as nx
import matplotlib.pyplot as plt
%matplotlib inline

Simple examples

From the docs, nx.Graph is:

A base class for undirected graphs. A Graph stores nodes and edges with optional data, or attributes. Graphs hold undirected edges. Self loops are allowed but multiple (parallel) edges are not. Nodes can be arbitrary (hashable) Python objects with optional key/value attributes. By convention None is not used as a node. Edges are represented as links between nodes with optional key/value attributes.

The weight is a numerical value, assigned as a label to a vertex or edge of a graph. From here, we learn that:

In mobile call networks the weight can represent the total number of minutes two individuals talk with each other on the phone; on the power grid the weight is the amount of current flowing through a transmission line.

We can build a network with networkx where all nodes are connected as follows.

nodes = ['A','B','C','D']
combs = [list((nodes[i],nodes[j])) for i in range(len(nodes)) for j in range(i+1, len(nodes))]
g = nx.Graph()

w = 0.1
for comb in combs:
    g.add_edge(comb[0],comb[1],weight=w)
    w += 1
nx.draw_networkx(g)

There are many more important properties that are not mentioned here. For a detailed treatment see the great book by Barabasi. We will now apply the concept of network analysis to social networks.