Is there a metric for "cliquiness" for social graphs?

Question

Regarding social network graphs, let us say that I am connected to 10 people, and that each of them are connected to 10 people. At one extreme this means that I have 100 unique $2^{nd}$ degree connections. However it is highly likely that in a real social network many of the connections of my first degree connections are following me back and following one another and following the same people outside of my direct connections. At the other extreme, if I am connected to 10 people, and each of them are connected to 10 people, my first degree connections might only be following me and one another. In this case I only have 10 unique $2^{nd}$ degree connections.

Here is my question, is there any metric – I do not know, "cliquiness" – that describes the degree to which people are likely to "in-follow" vs. "out-follow"? Here I am thinking that cliquiness=1.0 corresponds to my network being a fully connected, directed graph and cliquiness=0.0 means being my graph is a directed tree. I would like to look at real networks and be able to tell what their cliquiness number is. Any leads?

Answer 1

The formal definition of a clique is a fully connected subgraph (or cliquiness=1.0 in your example) where the shortest path between all the nodes in the clique is 1. To relax that, you have use the n-clique where the shortest path to all nodes is n or less.

If you're looking at "in-follow" vs "out-follow", a simple ratio of k_in / k_out would give you an indication of "flow", i.e. whether the node is a source or a sink of traffic.

There's a lot of work done on community detection despite the fact that there is no generally agreed definition of what a "community" is. Santo Fortunato provides an excellent review the different classes of algorithms that try to address this topic. You might be interested in the InfoMap algorithm as it concentrates on the flow of information and has nice visualization tools.