Flushing the Closet Clash Clique

Posted on 2020-08-30

I’ve been taking a look at the users lately. I was so bored, ok?

There are some graph algorithms that just have that lame-ass time complexity. Like a product of the edges’ and vertices’ cardinality. We’re around 105 for both, so ouch. Then again, there’s no harm in trying.

I occasionally partake in competitive coding1, so I’m always game when it comes to reimplementing the various graph algorithm classics. Yet the only interesting ones there tend to be on “abstract” graphs, whereas here it’s reified as heck. And large.

@BlaiseEbuth on #Fr, on a cruisade2 of his to try and convince me R is any good3, inadvertently made me aware of the awesome igraph package. Unbeknownst to him, some awesome Haskell bindings were already available on Hackage, so I didn’t even have to put up with that other language’s crazyness.4

Haskell’s kind of naturally great when it comes to:

  • working on the first try (provided it compiles)
  • concurrency

So I [hacked in the missing bindings, then] coded up diameter, max clique, radius and average path. And fired-and-forgot before going to bed.

longest shortest path between two vertices. “Longest shortest” makes it more confusing than it really is: the worst case graph distance between two nodes.
max clique
I’m really talking about the largest maximal clique. A clique is a set of vertices that all “point” (have an edge) to each other. A clique is maximal when there’s no vertex in the graph you could add to it such that it remains a clique. It’s the largest when it has the biggest vertex cardinality. (or edge cardinality, they grow in the same direction.) Note that being the largest doesn’t necessarily make it unique.
shortest longest path. Ok, that definition’s not as clean as diameter, more accurate would be minimal distance to furthest vertex. In lay terms, best case distance to the entire graph.
average path
average distance between two vertices.

I didn’t have much time to ponder whether any of this would actually work: the max clique came up pretty much instantly as far as launching that sort of process goes. So I’ll keep it for last, of course.

In the meantime, I coded the rest of the metrology, parts of which I wasn’t even aware of, but hey it’s in igraph so it’s probably good enough. So now you too will know fascinating trivia about my transitive CG closure, such as the fact:

  • it has 22 314 articulation points. For reference, an articulation point is a vertex whose removal would split the graph. That’s 22%, it’s huge. Either igraph and I have a different notion, or there are a crazy amount of chains that happen not to disturb the diameter too much. I’ll have to investigate this.

  • it has 51 848 bridges. For reference, a bridge is an edge whose removal would split the graph. That’s 16%, not as huge, but still huge. Same investigation ongoing.

  • the graph density is 2.92 × 10 − 5. That’s at least as low as expected, if you’ll consider you’d have to follow more than 10k lusers to reach even 0.1. Did I say 0.1? Sorry, I meant everyone will have to follow their 10k to have the graph as a whole reach it. And remember we’re talking about a biased graph where everyone already has a half-degree of 1 by construction.

  • the graph reciprocity is 0.44. That’s more interesting. 🙂 Reciprocity is the proportion of links that are bidirectional. (but remember the bias.)

  • the top users by Kleinberg hub score are:

    1. pythonlover
    2. Ivan_Derzhylo
    3. ship.org.ua
  • the top users by Kleinberg authority score are:

    1. Soc
    2. _Royale
    3. martin

You’ll be delighted to read my long algorithms answered correctly on the first try.5 I know I was, anyway. Here’s to reliable languages and libraries! Without further ado:

Last but not least: our long-awaited largest clique.

There are actually three of them, tied. They’re all 21 users broad. They do have a lot in common. Here’s a list of 23 users involved in a way or the other:

  1. [CPC]Karedas
  2. [CPC]Foudge
  3. [CPC]Madgic
  4. [CPC]Naity
  5. [CPC]Nattefrost
  6. [CPC]Herbert
  7. [CPC]MonsieurOdd
  8. [CPC]Max_well
  9. [CPC]Etheon
  10. [CPC]Jullebarge
  11. [CPC]Hideo
  12. [CPC]ds108j
  13. [CPC]Alab
  14. [CPC]Crayle
  15. [CPC]totoleharicotvert
  16. [CPC]Kesitem
  17. [CPC]PoussinJoyeux
  18. [CPC]BoZoin
  19. [CPC]ArcherHawke
  20. [CPC]raaaahman
  21. [CPC]Calys
  22. [CPC]rduburo
  23. [CPC]Bleuzaille

You got to give it to them, the CPC gang clique have some mad self-organizing skillz.7 Here’s a graph of their three superimposed 21-cliques. Can you find what’s missing to make them a united 23-person clique? Click on graph blank space to zoom; solution beneath.

The CPC Clique

If you omit Nattefrost, MonsieurOdd, Etheon and ds108j, they form a 19-user clique. Look to the right, that’s where all the action is. They’re missing:

  • Nattefrost ↔︎ Etheon
  • Nattefrost → ds108j
  • MonsieurOdd ↔︎ Etheon
  • MonsieurOdd ↔︎ ds108j
  • Etheon → ds108j

Well, now you know what to do, CPC. Your move! 😉

  1. CG barely counts. 🙉↩︎

  2. The official version of this shall be that this sentence is made up for greater litterary effect. As for facts, you can make up your own mind.↩︎

  3. Hint: it’s a lost cause. I have vivid memories of this paper on the topic, yet haven’t been able to retro-pin it down. The title sounded like: “Why R is not a reasonable programming language”. If anyone managed to dig it up again, I’d be truly grateful. (I just failed.) This is not it, though it’s a good read too. 😈↩︎

  4. And I’m discovering there’s an even more complete one, though older. Still, that might have saved me quite a bit of tweaking. 😍↩︎

  5. They actually took less than two hours. But I didn’t wait that long. 😴↩︎

  6. I can tell you their cardinality, though. It’s 452.↩︎

  7. Or had? I haven’t seen any of them in quite some time. 🤔↩︎