Flushing the Closet Clash Clique

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 10⁵ for both, so ouch. Then again, there’s no harm in trying.

I occasionally partake in competitive coding¹, 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 cruisade² of his to try and convince me R is any good³, 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.⁴

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.

diameter

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.

radius

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.⁵ I know I was, anyway. Here’s to reliable languages and libraries! Without further ado:

• the graph radius is 13. There are (way) too many central users to list⁶; I’ll try and come up with an objective measure to extract a podium.

• the average path is 5.72 steps long.

• the graph diameter is 24. Here’s a longest chain: TimurTimur ↔︎ RaphaelYoshiga ↔︎ gbico → MarcioGoda → LeonFernandes ← Mauricio32 → Gibras ← FlavioFraschetti → PedroCahu ← JuliaLopes → (Anonymous) ← AlainBearez → mind → [CG]SaiksyApo ← SirGalahad → cdtx ← SidAhmed → LamineBoutaleb ← Bamlou ← bertyn99 → TaisJuhel → yxssi → AurianeLabille ← Siagrin ← Mindeufair → Folwolf

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

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! 😉