Unit 2 Homework: Graphs and Networks

Course: Algorithmic Information Dynamics: A Computational Approach to Causality and Living Systems From Networks to Cells

Hector Zenil and Narsis A. Kiani

Course available at the Sta Fe Institute MOOC platform the Complexity Explorer at: https://www.complexityexplorer.org/courses/63-algorithmic-information-dynamics-a-computational-approach-to-causality-and-living-systems-from-networks-to-cells

DateString[]

Question 1

What is the adjacency matrix of the following graph:

Answer:

{{0,1,1},{1,0,1},{1,1,0}}//MatrixForm

Question 2

Can you determine from looking at this adjacency matrix if it represents a directed or an undirected graph?

AdjacencyGraph[(({{0, 1, 0, 0}, {1, 0, 0, 0}, {1, 1, 0, 0}, {1, 1, 0, 0}}))]

Answer:

Yes. It is directed, because the matrix is not symmetric.

Question 3

Write down the adjacency matrix of a completely disconnected graph of 5 nodes in which every node has only a self-loop.

Answer:

A disconnected graph of size 5  with all its nodes only connected to themselves is a matrix with all entries zero except for its diagonal:

{{1,0,0,0,0},{0,1,0,0,0},{0,0,1,0,0},{0,0,0,1,0},{0,0,0,0,1}}//MatrixForm

Question 4

What is the degree distribution of the following graph? Sort the result from greatest to lowest degree.

g=;

Answer:

Reverse@Sort[VertexDegree[g]]

Question 5

If relaxing the low degree requirement and only caring about node distance, can the following graph be called a small-world graph?

CompleteGraph[5,ImageSize->Small,PlotTheme->"Web"]

Answer:

The maximum (and also minimum) distance between any 2 different nodes in any complete graph is always 1, which is the minimum distance and way lower than the requirement of a distance proportional to log(N) where N are the number of nodes. Here is the code showing this for all complete graphs from 3 (triangle) to 20 nodes:

Table[Max[Flatten@GraphDistanceMatrix[CompleteGraph[i]]],{i,3,20}]

And how log(N) grows

N/@Table[Log[VertexCount[CompleteGraph[i]]],{i,3,20}]

Clearly the maximum (and minimum) graph distance of a complete graph between any two different nodes is always below log(N).

Thread[Table[Max[Flatten@GraphDistanceMatrix[CompleteGraph[i]]],{i,3,20}]≤N/@Table[Log[VertexCount[CompleteGraph[i]]],{i,3,20}]]

This is, however, not a typical example of small-world graph, because it does not comply with other possible requirements such as a low degree and clustering coefficient requirements.

Question 6

Is the following en example of a scale-free network?

g=;

With degree distribution sorted from largest to smallest degree:

Reverse[Sort[VertexDegree[g]]]

Answer:

It is a good candidate, the degree distribution approximates a power law. These plots provide evidence:

Row[{ListLogLogPlot[Reverse@Sort@VertexDegree[g],Joined->True,Frame->True,ImageSize->310,PlotTheme->"Web",Frame->True,FrameLabel->(Style[#,14,Black]&/@{"node from higher to lower degree","node degree"})],Histogram[VertexDegree[g],Frame->True,ImageSize->310,FrameLabel->(Style[#,14,Black]&/@{"degree bins","node count"})]}]

Question 7

What is the graph spectrum of the Tetrahedral graph (sort it from largest to lowest eigen value)?

Graph[EdgeList@GraphData["TetrahedralGraph"],PlotTheme->"Web"]

Answer:

Here is the calculation:

GraphData["TetrahedralGraph","AdjacencyMatrix"]//Normal

Eigenvalues[GraphData["TetrahedralGraph","AdjacencyMatrix"]]

Alternatively,

Reverse@Sort[GraphData["TetrahedralGraph","Spectrum"]]

Question 8

Are g and h isomorphic graphs? Justify (or provide mapping)

g=;h=;

Answer:

Yes, here the Wolfram Language code proving it:

IsomorphicGraphQ[g,h]

And here is a mapping:

First[Normal[FindGraphIsomorphism[g,h]]]

Question 9

Are these two graphs co-spectral?

g=;h=;

Answer:

Yes, because they are isomorphic. All isomorphic graphs are also cospectral (not the other way around).

Question 10

Is h a subgraph of g?

g=;

h=;

Answer:

Yes, it can be seen as the result of extracting 3 nodes from the complete graph together with its edges:

h=Subgraph[CompleteGraph[5,VertexLabels->Automatic],{1,2,3},VertexLabels->Automatic,PlotTheme->"Web",ImageSize->Small]

And here is subgraph highlighted inside the graph:

HighlightGraph[g,h,GraphHighlightStyle->"Thick",VertexLabels->Automatic,PlotTheme->"Detailed"]