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)
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:
the top users by Kleinberg authority score are:
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:
the graph radius is 13. There are (way) too many central users to list6; 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:
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.
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! 😉
CG barely counts. 🙉↩︎
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.↩︎
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. 😈↩︎
And I’m discovering there’s an even more complete one, though older. Still, that might have saved me quite a bit of tweaking. 😍↩︎
They actually took less than two hours. But I didn’t wait that long. 😴↩︎
I can tell you their cardinality, though. It’s 452.↩︎
Or had? I haven’t seen any of them in quite some time. 🤔↩︎