Theory of Complex Networks
Tutorial 1
1.Simple and directed graphs and their vertex and edge setssolved 15 Octobersolution
Which of the three graphs below is simple? Which of them is directed? Give for each of them the vertex set
and the edge set .Fig. 1. The three graphs of Tutorial 1: is directed, and are not.2.Adjacency matrices of the Tutorial 1 graphssolved 15 Octobersolution
Calculate the adjacency matrices of the three graphs of exercise 1, after relabelling the nodes of the left graph so that its vertex set becomes
.3.Graph of a local street neighbourhood and its length-three pathssolution
Draw a graph corresponding with your local street neighbourhood, and determine its adjacency matrix. How many paths of length three does your graph have? Register an account on Edstem following the link https://edstem.org/us/join/CguTku. Optional: post your result on the forum in the category "Tutorials: Week1".
4.In- and out-degrees of the Tutorial 1 graphssolved 15 Octobersolution
Calculate all in-degrees and all out-degrees of the three graphs of exercise 1.
5.Neighbourhood sets of the directed Tutorial 1 graphsolved 15 Octobersolution
Determine the neighbourhood sets of the left graph of exercise 1.
6.In-degree equals out-degree in undirected graphssolved 15 Octobersolution
Prove that in non-directed graphs
, and that .7.Sum of in-degrees equals sum of out-degreessolved 15 Octobersolution
Prove that in directed graphs
.
Solutions
1.Simple and directed graphs and their vertex and edge sets
None of the graphs has a self-interaction, so all three are simple. Only
has arrows, so it is the only directed one.An edge
is the link , in line with iff . Undirected links are written once as and count as both and . : , with links , , , , , , , , . : , with the eight links for . : , with links , , , , .
2.Adjacency matrices of the Tutorial 1 graphs
Convention:
iff there is a link , so and .Relabel the left graph by sending the nodes that point at the hub to
, the hub to , and the nodes the hub points at to , so that the link becomes :old 2 10 6 11 3 9 5 7 4 new 1 6 7 8 9 2 3 4 5 The middle graph is already labelled
: for every , and all other entries are .The right graph is already labelled
:3.Graph of a local street neighbourhood and its length-three paths
No solution yet.
4.In- and out-degrees of the Tutorial 1 graphs
Convention:
iff there is a link , so and .The left graph is directed, so its in- and out-degrees differ (original labels):
2 3 4 5 6 7 9 10 11 0 4 1 1 0 2 1 0 0 1 4 1 0 1 0 0 1 1 The other two graphs are not directed, so
, the sum of row of .- Middle:
, and for the other eight nodes. - Right:
, , .
- Middle:
5.Neighbourhood sets of the directed Tutorial 1 graph
The in-neighbourhood
holds the nodes with a link into , and the out-neighbourhood the nodes links to:2 3 4 5 6 7 9 10 11 6.In-degree equals out-degree in undirected graphs
With the convention
iff there is a link , and .In-degree equals out-degree. A non-directed graph has
, soDegree as a diagonal of
. Using and for ,7.Sum of in-degrees equals sum of out-degrees
Both sums count every link exactly once. Relabelling the dummy indices
in the second sum,