$2\mathrm{.}3.$ Graph Representation

The adjacency matrix is a useful graph representation for many analytical calculations. However, when we need to store a network in a computer, we can save computer memory by offering the list of links in a Lx$2$ matrix, whose rows contain the starting and end point $\backslash ($ i $\backslash )$ and $\backslash ($ j $\backslash )$ of each link.

Construct for the networks $($a$)$ and $($b$)$ in Figure $2\mathrm{.}20$:

GRAPH THEORY

$30$

$($a$)$ The corresponding adjacency matrices.

$($b$)$ The corresponding link lists.

$($c$)$ Determine the average clustering coefficient of the network shown in Figure $2\mathrm{.}20$a$.$

$($d$)$ If you switch the labels of nodes $5$ and $6$ in Figure $2\mathrm{.}20$a$,$ how does that move change the adjacency matrix? And the link list?

$($e$)$ What kind of information can you not infer from the link list representation of the network that you can infer from the adjacency matrix?

$($f$)$ In the $($a$)$ network, how many paths $($with possible repetition of nodes and links$)$ of length $3$ exist starting from node $1$ and ending at node $3?$ And in $($b$)?$

$($g$)$ With the help of a computer, count the number of cycles of length $4$ in both networks.

Figure $2\mathrm{.}20$

Graph Representation

$($a$)$ Undirected graph of $6$ nodes and $7$ links.

$($b$)$ Directed graph of $6$ nodes and $8$ directed links.