Tiago Peixoto @tiago@social.skewed.de

New on the @arxiv@twitter.com: "Descriptive vs. inferential community detection: pitfalls, myths and half-truths"

This is a selected review of the many dangers of using descriptive methods (e.g. modularity) with inferential goals, and existing solutions. 1/2

https://arxiv.org/abs/2112.00183

New blog post: "Descriptive vs. inferential community detection"

A mini-thread for those too lazy to click the link! 1/7

(Based on recent pre-print: https://arxiv.org/abs/2112.00183)

https://skewed.de/tiago/blog/descriptive-inferential

New version of graph-tool is out!
https://graph-tool.skewed.de

(New: https://graph-tool.skewed.de/static/doc/demos/inference/inference.html#latent-triadic-closures)

Single-line install instructions:

Anaconda ⤵️
conda create --name gt -c conda-forge graph-tool

Homebrew ⤵️
brew install graph-tool

Debian/Ubuntu⤵️
apt-get install python3-graph-tool

New on the @arxiv_physics: "Disentangling homophily, community structure and triadic closure in networks", https://arxiv.org/abs/2101.02510

Homophily/communities and triadic closure (triangles) are conflated properties in network analysis, and this method tells them apart.

Does the NFL theorem tell us something important? YES!

It tells us that we need to be explicit about our inductive bias (i.e. what kind of problem we want to solve).

Compressibility is indeed an inductive bias, but one that relies only on Occam's razor, and nothing else! 9/9

And we should not interpret the eventual improved accuracy of a method that tends to work poorly overall as a *necessary* outcome of the NFL theorem. 8/9

So, we shouldn't use the NFL theorem to justify an algorithm ("it's as good as any other") — after all that argument would be valid even for trivial algorithms (e.g. same partition every time). 7/9

Indeed, there is a "free lunch" with compressive problems, since some algorithms will work better than others!

Is there a universal algorithm that will work better in every compressive instance, or a majority? It's unclear!

But the NFL theorem tells us nothing about this. 6/9

As soon as we limit ourselves to *compressive* problem instances, then we are out of scope of the NFL theorem.

Note that it is not necessary to specify *how* the problems are compressive (i.e. which model they come from), only that they can be compressed somehow. 5/9

More formally, a partition is informative if its knowledge can be used to *compress* the network, i.e. describe it with fewer bits than if we did not know it.

Below is an example of a compressive problem instance.

Looks familiar? This is the kind of problem we have in mind. 4/9

But what does that tell us about the problems we actually want to solve?

Can we make a general statement about what is an "interesting" community detection problem?

There is in fact, a very simple one: we require the partition to be *informative* of the network structure! 4/9

What's strange about this example? Well, there's no community *structure*. It's just a random network with a random partition.

The vast majority of instances accounted by the NFL theorem look like this.

OK, so all algorithms perform equally "well" in these cases. 🤷‍♂️

3/9

But what does "all problem instances" mean? For Leto et al, a problem instance is simply an arbitrary pairing of a network and a partition.

Any network, any partition.

How does such a typical problem instance look like?

We can see one below. 2/9