dependency between communities(clusters) in igraph

0
votes

Is there any measure that computes the dependency between communities of a graph in igraph? I am looking for a measure of dependency between communities.

1
graphigraph
Could you explain in more details what you mean exactly by dependency? - Vincent Labatut
I know how to find communities in the graph. I need a measure that tells me how much community A and community B are dependent. Also I need a measure of something like proportion of within-community dependency over between-community dependency. I can come up with some ideas myself but wanted to make sure there does not exist any standard measures in graph theory or so. - iBM

1 Answers

0
votes

You could use the inter- and intra-cluster densities, as defined for undirected graphs in Fortunato'10. Both are based on the notion of graph density, but processed by considering only certain subgraphs.

The intra-cluster density is the proportion of existing links inside a community, relatively to the possible number of such links, if all nodes of the community were connected. If there are m_C links and n_C nodes in community C, then the intra-cluster density is: d_intra(C)=m_C/(n_C(n_C-1)/2).

The inter-cluster density is the proportion of existing links between a community and the rest of the graph, relatively to the possible number of such links if each community node was connected to the rest of the graph. If there are n nodes in the whole graph, and if m_C' is the number of links connecting a node of community C to a node located in another community, then the inter-cluster density of community C is: d_inter(C)=m_C'/(n_C(n-n_C)).

If you need to, the inter-cluster density can be easily modified to characterize the connection between two specific communities (by opposition to: a community and the rest of the graph). If we note m_C1C2 the number of links between communities C1 and C2, and n_C1 and n_C2 their respective numbers of nodes, then we get: d_inter(C1,C2)=m_C1C2/(n_C1*n_C2)

I don't think these measures are directly implemented in igraph (or any other software, for that matter).