• motifs are structural patterns of networks
• if a motif occurs more than expected in a networks, it signals something
• for instance, in genetic regulatory networks and neural networks researchers have found certain small motifs that occurred far more often than expected on the basis of chance
• they conjectured that these motifs were playing the role of functional circuit elements, and that they might be an evolutionary result of their usefulness to the organisms involved

• transitivity is the simplest motif on undirected graphs
• it refers to the extent to which the edge relation is transitive
• perfect transitivity implies that, if \(x\) is connected (through an edge) to \(y\), and \(y\) is connected to \(z\), then \(x\) is connected to \(z\) as well
• it is very rare in real networks, since it implies that each component is a clique, that is, each pair of reachable nodes in the graph would be connected by an edge
• however, partial transitivity is useful. In many networks, particularly social ones, the fact that \(x\) knows \(y\) and \(y\) knows \(z\) does not guarantee that \(x\) knows \(z\) as well, but makes it much more likely
• the friend of my friend is not necessarily my friend, but is far more likely to be my friend than some randomly chosen member of the population

• in the context of social networks, three individuals \(x, y, z\) such \(x\) and \(z\) are both friends of \(y\) are called a triad centered at \(y\)
• the triad is said open if the link from \(x\) to \(z\) is missing
• a closed triad centered at \(y\) is a particular triad centered at \(y\) with the additional link from \(x\) to \(z\)
• transitivity coefficient \(T\) for a network corresponds to the fraction of triads that are closed, that is the fraction of pairs of people with a common friend who are themselves friends, or equivalently, the mean probability that two people with a common friend are themselves friends
• \(T = 1\) implies perfect transitivity, i.e., a network whose components are all cliques
• \(T=0\) implied no closed triad, which happens for various topologies, such as a tree or a square lattice

In the example below, for instance, there are 5 triads: one centered at \(x\), one at \(y\), and three at \(z\).

Three of them are closed triads (the ones on the triangle), and two are open (the ones centered at \(z\) that include \(w\)). Hence the transitivity coefficient is \(T = 3/5 = 0.6\).

library(igraph)
g = make_graph("Zachary")
transitivity(g, type = "global")

## [1] 0.2556818

• as for directed networks, smallest motiv is the loop of length 2: a sequence \(x,y,x\) of nodes such that the directed edges \((x,y)\) e \((y,x)\) belong to the graph
• we can thus measure the frequency of loops of length two in a directed network, which is called reciprocity
• it measures how likely it is that a vertex that you point to also points back at you.

Formally, the reciprocity of a directed network is the fraction of edges that belong to a loop of length two, or:

\[R = \frac{1}{m} \sum_{i,j} A_{i,j} A_{j,i} = \frac{1}{m} \mathrm{Tr} \, A^2\]

where \(m\) the the number of edges and \(A\) the adjacency matrix of the graph. Notice that \(A_{i,j} A_{j,i} = 1\) if and only if \(i\) links to \(j\) and vice versa.

library(igraph)

edges = c(1,3, 1,4, 2,5, 3,2,4,5, 5,3, 5,6, 5,4, 6,5, 5,2)
g = graph(edges, directed=TRUE)
layout = layout_nicely(g)
plot(g,
     layout = layout,
     vertex.size = 20, vertex.color = "lightblue", 
     edge.width = 3, edge.color = "black") 

reciprocity(g)

## [1] 0.6

Compute reciprocity using the trace of the square of the adjacency matrix of the graph.

library(igraph)

plot(g,
     layout = layout,
     vertex.size = 20, vertex.color = "lightblue", 
     edge.width = 3, edge.color = "black") 

A = as_adjacency_matrix(g, sparse = FALSE)
sum(diag(A %*% A)) / sum(A)

## [1] 0.6

reciprocity(g)

## [1] 0.6

Consider the sale network of digital gallery SuperRare (nodes and edges). Nodes are users of the gallery and there is an edge from user A to user B if A has bought an artwork from B.

1. What are reciprocal edges? Will reciprocity be large or small in your opinion?
2. Compute the reciprocity of the network. Is your guess confirmed or refuted?

library(igraph)

# read data
nodes = read.csv("nodes.csv")
edges = read.csv("edges.csv")

# igraph network
g = graph_from_data_frame(edges, vertices = nodes)


reciprocity(g)

## [1] 0.03451109