Network substructures

1. Network substructures

In the previous sections we focused on assessing some overall features of network structure such as density and average path length. In this video you will learn about microstructural features of social networks that can be informative as to how a network functions.

2. Transitivity

An important measure of local connectivity involves investigating the triangles (also known as triads) that exist in a network. For every group of three vertices in a network there exists three potential edges. If all edges exist, then the triad is said to be closed. On the left is the example network from before. Looking at this network we can identify three closed triangles. They are illustrated on the top row on the right. The triangles A-E-F, A-F-H and A-D-H are all closed having all three edges. Other triangles have two edges. For instance, E-F-G is one example. A-B-C is another. Some triangles have only one edge. C-K-M is an example, as is G-E-I. Other triangles have no edges. H-L-M is one such triangle. With igraph, all closed triangles of a network can be found using the triangles() function.

3. Global transitivity

We can formally assess how interconnected a group of three vertices are by calculating the transitivity of a network. Transitivity measures the probability that the adjacent vertices of a given vertex are connected. It can be calculated in igraph using the transitivity() function.

4. Local transitivity

It is also possible to determine the transitivity at the local level for each vertex. This metric calculates the proportion of closed triangles that a vertex is a part of, out of the theoretical number of closed triangles it could be a part of given its connections. You can count the number of closed triangles for each vertex using count_triangles() in igraph. This function takes the graph object and then a vector of vertex ids. The local transitivity can be calculated by using transitivity() and supplying the vertex id and setting the parameter 'type' to 'local'. In this example network, the local transitivity of F is slightly higher than that of A. This is because a higher proportion of the connections of F lead to closed triangles than those connections made by A.

5. Cliques

Identifying cliques is another commonly utilized method for assessing network substructure. In a clique, every vertex is connected to every other vertex. The entire network on the left is a clique as all vertices connect to each other. In practice, it is very rare for a network to look like this. More often, cliques exist within networks such as the example on the right. In this network the largest clique that exists has four vertices - B, C, E and F. These four vertices are all interconnected with each other. These are shown in blue. Another way of thinking about this is that all the triangles they make together are closed.

6. Identifying cliques

The largest clique in a network can be identified in igraph using the largest_cliques() function. It will return how many vertices are in that clique and the ids of those vertices. Here, it returns C, F, B and E. It is also possible to identify the cliques of any size from two up to the largest clique size using the max_cliques() function. This function returns a list of cliques of each size. In the example network, you can see that there are two cliques of size 3. A, B, E and I, C, F are these cliques. They are all interconnected and not part of a larger clique together.

7. Let's practice!

Time to put this into practice.

Create Your Free Account

By continuing, you accept our Terms of Use, our Privacy Policy and that your data is stored in the USA.