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?


1 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.

  • $\begingroup$ I think for the made-up terms "in-follow" and "out-follow", the intended distinction is between insiders (members of a clique) and outsiders, not sources and sinks. $\endgroup$ Commented Sep 7, 2021 at 13:38
  • 1
    $\begingroup$ I was guessing that JnBrymn could have been reaching for the technical terms "in-degree" and "out-degree", the number of links directed towards or away from the node respectively. You're implying that we're looking at all the links in or out of the community, which is the "strong definition of community" given in Radicchi PNAS 2004, which is also good. $\endgroup$
    – Boyd
    Commented Sep 7, 2021 at 22:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.