Introduction to Complex Network Analysis with Python/

...

/

Basic Graph Types

Basic Graph Types

Explore various types of graphs such as weighted graphs, directed graphs, directed acyclical graphs (DAGs), and trees.

We'll cover the following...

Let’s explore various types of graphs and the differences between them.

Weighted graphs

As we know, a graph is made of nodes and edges. Usually, the type of edge we’re dealing with changes the kind of graph we’re working with.

Let’s start by analyzing a scenario. Let’s say that someone has three friends, but their level of friendship is not the same for everyone. Maybe one is their best friend, and the other two are just good friends from work.

In that case, the connection node X for each one of them is going to be different. In this case, we say that the edge that connects X to them is weighted, creating a weighted graph such as shown below:

Press + to interact
A weighted graph
A weighted graph

Here, we can see that their level of friendship with Friend 3 is equal to 3, while with the others, it is only 1. This gives a sense of the strength of the connection and can be very useful to represent a variety of phenomena.

Let’s look at how to create this kind of graph in NetworkX.

Press + to interact
import networkx as nx
# Now we add an extra value to the tuple: the weight
edges = [
  ('X', 'Friend 1', 1),
  ('Friend 1', 'Friend 2', 1),
  ('Friend 2', 'X', 1),
  ('Friend 3', 'X', 3)
]
G = nx.Graph()
# Here we add weighted edges
G.add_weighted_edges_from(edges)
# We use data=True to show the attributes for each edge
print('Edges: ', G.edges(data=True))

  • Line 1: We import the NetworkX (networkx) library.

  • Lines 4–9: We define the edges containing tuples of three elements. The first two elements are the nodes being connected, and the third element is the weight of the connection.

  • Line 11: We instantiate a Graph object.

  • Line 14: We explicitly say that the edges are weighted.

Exercise

Try to build a weighted graph by yourself. Implement the same structure as the graph above but with an additional element of a weight of 5 on the edge connecting X to Friend 1 and to Friend 2. The edge between Friend 1 and Friend 2 should have a weight of 4. Other edges should have the same value.

Press + to interact
import networkx as nx
edges = [
]
# Now create your graph
print(G.edges(data=True))

Important structures

Paths and cycles

Two concepts widely used in graphs and in complex network analysis are the concepts of paths and cycles.

A path is a sequence of edges that are transversed in a graph to go from one node to another. For example, the image below shows a path connecting nodes ...