2.1 Cliques

The most common method to detect cliques in the network data is to find complete subgraphs. The algorithm searching for complete subgraphs in a larger structure is one of simplest method to trace cliques in social networks.

An igraph package provides a few useful functions for detecting clique. The main function is cliques which returns a list (as a vector of vertex id’s) of all cliques found in the graph. We could set min argument to 3 to remove vertices and edges.

cliques <- cliques(graph, min = 3)
length(cliques)

## [1] 199

table(sapply(cliques, length))

## 
##  3  4  5  6  7 
## 98 63 29  8  1

We could see that there are a lot of cliques even in rather small network. However we must remember that those cliques could overlap. In particular, a clique of size $N$ includes $N-1$ cliques of size $N-1$, $N \choose 2$ cliques of size $N-2$ and so on. Usually we are more interested in cliques, that are not part of some bigger ones. To find them we may use function maximal.clique.

maximal.cliques.count(graph, min = 3)

## [1] 23

max_cliques <- maximal.cliques(graph, min = 3)
table(sapply(max_cliques, length))

## 
##  3  4  5  6  7 
## 14  5  2  1  1

Now there are only 23 cliques. Some of them may overlap, but not completely. We could also directly find the largest cliques in the graph. Function clique.number(graph) gives us a size of the largest clique.

clique.number(graph)

## [1] 7

largest.cliques(graph)

## [[1]]
## [1] 10  4  5  6  7  8  9

On the figure below maximal cliques of size at least 5 are highlighted.

groups <- maximal.cliques(graph, min = 5)
par(mar = rep(0,4))
plot(graph, mark.groups = groups, vertex.label = NA, margin = 0)

Two cliques of size 5 (yellow and red) are partially included in cliques of size 6 (blue), while the largest clique (violet) forms isolated group.

In package network there is a function clique.census, which finds all maximal cliques and additionally returns clique count and co-membership matrix for vertices. It also performs symmetrization step for undirected graphs.

2.2 N-cliques

As we mentioned above, the geodesic distances among members of cohesive groups should be small. To make the idea of clique more flexible it is possible to specify the cutoff value $n$ as the maximum length of geodesic distance linking pairs of actors within the cohesive subgroup [Wasserman & Faust 1994: 254]. Thus, the $n$-clique is a subgraph with paths of $n$ length as maximum value allowed between pairs of actors. Formally, $n$-clique is made of geodesics $d(i,j) =< n$ equal or lesser than $n$ value. When $n=1$ identified subgroup is a complete subgraph.

2.3 N-clans

The idea of n-cliques has its limitations that led to the idea of n-clans. Two problems might arise when we deal with n-cliques: 1. It may happen that the diameter of n-clique is greater than n value. 2. It may also happen that n-clique is disconnected as n-path connecting two nodes in analyzed n-clique goes through nodes outside of that n-clique. The solution to the first problem send us to the idea of n-clans. A n-clan is a n-clique in which the geodesic distance between all nodes is no greater than n [Ibidem: 260]. All n-clans in a subgraph are n-cliques, but not all n-cliques are n-clans.

2.4 K-plexes

Cohesive subgroups are often identified on adjacency of subgroup members. Such a subgroup is made of actors being adjacent to relatively numerous other members of the subgroup. In other words, all subgroup members must be adjacent to some minimum k number of other members belonging to that subgroup. If k=N-1, where N is the size of the subgraph, the subgraph is a clique. As k is getting smaller, each node is allowed to have more missing ties within the subgroup.

3.1 Edge betweenness

One of the most popular algorithms detecting communities in a social networks has been given by Michelle Girvan and Mark Newman. The Girvan-Newman algorithm is a hierarchical method used in complex systems. Progressive removing of edges from the original network leads to the connected components of the remaining network which are the communities. This algorithm does not search for the most central edges of the whole structure. It focuses on the edge that is the most between and removes it. The most between edge is defined by the highest number of shortests paths running through the pair of nodes. The algorithm can be summarized by the following steps:

1. Betweenness of all edges is calculated as a first.
2. Edge with the highest betweenness level is removed.
3. Betweenness of all remaining edges is recalculated.
4. Steps 2 and 3 are repeated until no edges remain in a network.

The Girvan-Newman algorithm is based on the divisive approach in finding communities in network structures. In igraph package the function edge.betweenness.community is based on this algorithm.

edge_comm <- edge.betweenness.community(graph_c)

Algorithm is running until all edges are removed. However, we are interested in the best community structure obtained by the algorithm, which usually occurs in some intermediate step. Fortunately igraph finds the best division for us, so we could easily analyse properties of community structure or plot it. As for plotting, we need to provide our original graph as a second argument to appropiate plot method.

par(mar = rep(0, 4))
plot(edge_comm, graph_c, vertex.label = NA)

You could see how graph was divided at every step of the algorithm with dendPlot function. This function works for all communities that have a full hierarchical structure. We could check this with is.hierarchical. The coloured rectangles show the best community structure.

is.hierarchical(edge_comm)

## [1] TRUE

dendPlot(edge_comm)

3.2 Modularity

Modularitty can be refered to the quality of divisions that can be turned into communities within a network. Clauset, Newman and Moore explain that “modularity is a property of a network and a specific proposed division of that network into communities” (Clauset, Newman, and Moore 2004). It is defined as

$$Q = \frac{1}{2m} \sum_{ij}\left(A_{ij} - \frac{k_i k_j}{2m} \right) \delta(ci,cj),$$

where $m$ is the number of edges, $A$ is the adjacency matrix, $k_i$ is the degree of node $i$, $c_i$ is the type (or component) of node $i$ and $\delta(x,y) = 1$ if $x = y$ and $0$ otherwise. When modularity score is positive it means that there are more edges within communities than expected in random network with the same degree sequence.

One problem with this measure is a lack of fixed range. Maximum (and minimum too) values depend on a structure of particular network, though they will always lie between $-1$ and $1$. Values over $0.3$ seem to be a good indicator of significant community structure.

Modularity could ba calculated in igraph with modularity function. It has methods for objects of class igraph or communities. In former case you need to provide also a vector of class membership, in the latter the maximum value of modularity obtained by community detection algorithm is returned.

On the following figure you could see how modularity score changes across different division of nodes.

g <- graph(c(1,2, 1,3, 2,3, 1,4, 1,5, 5,6, 6,7, 5,7), directed = FALSE)
g$layout <- layout.auto(g)
par(mfrow=c(1, 6), mar = rep(0, 4))

plot(g, vertex.color = c(1, 2, 3, 2, 3, 2, 1) + 1, vertex.label = NA)
text(0, -1.2, round(modularity(g, c(1, 2, 3, 2, 3, 2, 1)), 3))

plot(g, vertex.color = c(1, 2, 2, 1, 2, 1, 2) + 1, vertex.label = NA)
text(0, -1.2, round(modularity(g, c(1, 2, 2, 1, 2, 1, 2)), 3))

plot(g, vertex.color = c(1, 1, 1, 1, 1, 1, 1) + 1, vertex.label = NA)
text(0, -1.2, round(modularity(g, c(1, 1, 1, 1, 1, 1, 1)), 3))

plot(g, vertex.color = c(1, 1, 2, 1, 2, 2, 2) + 1, vertex.label = NA)
text(0, -1.2, round(modularity(g, c(1, 1, 2, 1, 2, 2, 2)), 3))

plot(g, vertex.color = c(1, 1, 1, 3, 2, 2, 2) + 1, vertex.label = NA)
text(0, -1.2, round(modularity(g, c(1, 1, 1, 3, 2, 2, 2)), 3))

plot(g, vertex.color = c(1, 1, 1, 1, 2, 2, 2) + 1, vertex.label = NA)
text(0, -1.2, round(modularity(g, c(1, 1, 1, 1, 2, 2, 2)), 3))

We could see that the modularity score is the lowest if there is no edge within any community. On the other hand the highest modularity is obtained for reasonable division, with only one edge between communities. However, when there is only one community, modularity is always $0$.

We could see how modularity score was changing throughout the Girvan-Newman algorithm applied to our network of judges.

plot(edge_comm$modularity, xlab = "Step", ylab = "Modularity")
abline(v = which.max(edge_comm$modularity))
text(10, 0.4, paste("max modularity = ", round(modularity(edge_comm), 3)))

In general it is difficult to find the best (according to modularity score) division of nodes, but there are many approximative algorithms aimed at maximising modularity. Further in this chapter we will describe greedy optimization, random walks, statistical mechanics and Louvain method.

greed_comm <- fastgreedy.community(graph_c)
is.hierarchical(greed_comm)

## [1] TRUE

dendPlot(greed_comm)

multim_comm <- multilevel.community(graph_c)

3.3 Walktrap community

The idea behind this algorithm is that random walker on a graph tends to be trapped in a dense part of a network structure, which corresponds to some community, because there are few edges leading outside (Pons and Latapy 2005). It starts with every node as a single community, then iteratively calculates distances between communities by means of short random walks and connects the nearest communities.

The walktrap community could be calculated with walktrap.community function. The default length of random walks is 4 but you could change it with steps argument.

walktrap_comm <- walktrap.community(graph_c)
is.hierarchical(walktrap_comm)

## [1] TRUE

dendPlot(walktrap_comm)

3.4 Spinglass community

Last algorithm we focus on can be applied to directed and weighted networks. In this model, each element of the network (node) can be in one of $N$ spin states. Interactions between elements (the edges of the graph) define which pairs of nodes would stay in the same spin state and which have different spin states. The model is then simulated for a given number of steps. In the end the spin states of elements define the communities in a network. The number of communities is never greater than $N$. Some spin states might be empty, so the number of communities in a network is often lesser than $N$ (Reichardt and Bornholdt 2006). spinglass.community is an implementation of this algorithm.

set.seed(12345)
spinglass_comm <- spinglass.community(graph_c)

3.5 Comparison of different algorithms.

par(mfrow = c(2,2), mar = c(1,0,1,0))
plot(greed_comm, graph_c, vertex.label = NA, 
     main = paste("Greedy", round(modularity(greed_comm), dig = 4)))
plot(walktrap_comm, graph_c, vertex.label = NA, 
     main = paste("Walktrap", round(modularity(walktrap_comm), dig = 4)))
plot(multim_comm, graph_c, vertex.label = NA, 
     main = paste("Multilevel", round(modularity(multim_comm), dig = 4)))
plot(spinglass_comm, graph_c, vertex.label = NA,
     main = paste("Spinglass", round(modularity(spinglass_comm), dig = 4)))

We could see that all four algorithms return almost the same results. Spinglass and walktrap divided the smallest community (in the other two methods) into two triads and spinglass additionally separate two nodes from big community. Nevertheless, the highest modularity score is obtained for simple division with three communities.

4.1 Cohesive subgroups in two-mode networks

Detecting cohesive subgroups in two-mode networks is a bit more complicated than in ordinary networks. There are couple of methods to do that. The choice of method should mainly depend on properties of our data and on a target we want to achieve by finding communities. The easiest way is to convert two-mode data into one-mode. When data is converted methods designed for one-mode networks can be used to detect communities. Further in this chapter we will describe the projection procedure in detail.

4.2 Projection procedure

As we mentioned above, to conduct certain types of analysis researchers transform two-mode data into one-mode. One of few transformation techniques is called projection. In the projection procedure one type of nodes are removed from the two-mode network. Two nodes from the other class are connected if they were connected with the same node from the removed class.

Let’s say we have the network with two sets of nodes $A=\{a,b,c,d\}$ and $B=\{1,2,3\}$ and relations depicted below.

g <- graph.bipartite(c(TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE),
                     c(1,5, 1,6, 2,5, 2,7, 3,7, 4,5, 4,7))
V(g)$name <- c("a", "b", "c", "d", "1", "2", "3")
par(mar = rep(0,4))
plot(g, layout = layout.bipartite, vertex.size = 20)

If we remove nodes $B$ and apply the projection procedure, relations in $A$ set of nodes will look like: $a$ is connected to $\{b,d\}$, $b$ is connected to $\{a,c,d\}$, $c$ to $\{b,d\}$ and $d$ to $\{a,b,c\}$. We could analogically remove nodes $A$ and obtain second projection. Both are show below.

par(mar = rep(0,4), mfrow=c(1,2))
plot(graph.data.frame(data.frame(c("a","a","b","b","c"), c("b","d","c","d","d")), directed = FALSE),
     vertex.size = 20)
plot(graph(c(1,2, 1,3), directed = FALSE), vertex.size = 20)

Projection procedure is fortunately implemented igraph in bipartite.projection. Firstly we could check how the result of projection will look without constructing it.

bipartite.projection.size(g)

## $vcount1
## [1] 3
## 
## $ecount1
## [1] 2
## 
## $vcount2
## [1] 4
## 
## $ecount2
## [1] 5

We want projection to be binary graphs, so we set multiplicity argument to FALSE to simplify multiple edges.

We see that these networks are exactly the same as we’ve constructed by hand.

Now let’s calculate projection of judges–judgments network. We are more interested in a network between judges, therefore we could restrict projection procedure to construct network only between TRUEs. We want binary graph, so we set multiplicity argument to FALSE to simplify multiple edges. The resulting network is exactly our co–judging network.

graph_proj <- bipartite.projection(graph_bip, multiplicity = FALSE, which = "true")
graph_proj

## IGRAPH UN-- 40 94 -- 
## + attr: name (v/c), JudgeSex (v/c), DivisionCode (v/c)

graph

## IGRAPH UN-- 40 94 -- 
## + attr: layout (g/n), name (v/c), JudgeSex (v/c), DivisionCode
##   (v/x)