Calculate probability that nodes between two communities link to each other

I am new in Network Science.
I have graph with community structure.
How can I calculate probability that nodes from community i are connected with nodes from community j?
Using igraph, of course.

Have you found the solution to your problem? Your problem is old and maybe you have figured out something beneficial for the rest of us.

It is not entirely clear what you are looking for here. Possibly, you are simply interested in the proportion of links of community i that connect to community j? That is, if in total community i has K_i links and A_{ij} links between community i and j, you are looking for \frac{A_{ij}}{K_i}?

One you have the result of one of the cluster_xxx functions, you get a result of a communities structure. You can then contract the graph, so that each cluster becomes a new node, and use that to count things.

Suppose that the clustering is available from cl. You can then contract the graph as

G_contracted <- contract(G, cl$membership)

In the contracted graph, there will only be as many nodes as there are clusters in cl, that is,length(cl). In this contracted graph you can get the adjacency matrix by doing

A <- as_adjacency_matrix(G_contracted)

Doing this on the graph.famous('Zachary') graph, with some clustering result, you obtain for instance this result

> A
3 x 3 sparse Matrix of class "dgCMatrix"
[1,] 24 4 10
[2,]  4 6  .
[3,] 10 . 34

Now it is simply a matter of dividing this matrix by the row sums.

> A / Matrix::rowSums(A)
3 x 3 sparse Matrix of class "dgCMatrix"
[1,] 0.6315789 0.1052632 0.2631579
[2,] 0.4000000 0.6000000 .        
[3,] 0.2272727 .         0.7727273
1 Like

@vtraag Pretty useful answer. Let me see what results I get after following this method.