Today I want to tell a story about how sometimes science leads you to unexpected places. The main character of this story is the paper “Multilayer Network Backboning” (MNB to its friends), which I will present later this year at the CIKM conference. This was joint work with the excellent Valerio Siniscalco.
Network scientists know network backboning as the problem of identifying which edges in a weighted network are statistically significant, i.e. which ones we’re sure they actually exist. Network scientists also know other things — they’re a smart bunch — for instance that multilayer networks are networks where edges have different types. In this paper, these two worlds collide.
MNB, as a paper, didn’t really know what it wanted to do once it grew up. It was the child of another paper I wrote a while ago, about gender discrimination in the inclusion of women in Wikipedia biographies. Like all loving children, it looked at its parent with reverence, and thought it was going to go in the same line of business. See, the original paper’s entire argument relied on using network backboning to estimate the significance of edges: women had edges with greater significance than men, which suggested they were treated differently. When Valerio first proposed to write MNB, he pointed out that this was only done on the English language version of Wikipedia. Valerio wanted to see if the result also held when looking at multiple language versions.
The path for MNB, then, was clear: build the networks for a few other language versions (French, German, Italian, Spanish), redo the backboning analysis, and voila. “Voila” it was not, because as soon as you make a multilayer network you have to start asking yourself pesky questions. For instance: are we really really sure that person A linking to person B in the English edition bears no influence whatsoever on the likelihood of this A-B link existing in, say, the French edition? The entire multilayer network analysis business rests on the assumption that layers do influence each other one way or another, so we have to take such cross-pollination factors into account when estimating the likelihood of an edge truly existing. In short, we need a multilayer version of backboning.
“This is easy,” I told Valerio. “We just have to use one of the already-existing multilayer backboning methods. I’ll type in ‘Multilayer network backboning‘ on Google Scholar, pick the first random result that strikes my fancy* among the dozens available, and MNB can grow up and emulate its parent.” I did just that, and got zero hits. “Oh.”
See, maybe a normal person’s second thought after “Oh.” might be “Damn”. Not for a scientist. A scientist instead starts thanking the Gods of Science for their generous gift, and maybe does a little dance. “We know now what MNB will be. It’ll be the first backboning method that takes multilayer networks as input!” I said. “But the discrimination on Wikip…” Valerio tried to say. “The first backboning method that takes multilayer networks as input,” I kept repeating, in ecstasy, staring in the distance.
MNB, from that point onward, wrote itself. The starting point was the paper I published a while ago on single layer backboning, which established a null model based on how the two nodes linked by the edge we are testing connect in the rest of the network. One can apply it to multilayer networks as is, because one can represent them as multigraphs. But doing so results in an algorithm that considers layers independent and indistinguishable: you lose the information of which edge belongs to which layer.
MNB expands the original algorithm in two ways. First, we create a distinct null model per layer, which allows us to distinguish each layer. Then, we create an expectation estimate for each node pair to be connected which takes all layer information into account, allowing us to make the null models dependent on each other. This is based on the correlations between edge appearances in different layers, and our strategy is flexible enough to work also in the presence of anticorrelations. These happen when being connected in a layer makes the connection in another layer less likely — for instance if we have friendship and enmity layers.
We can demonstrate that this works by creating synthetic networks where we control exactly which edges are signal and which are noise. The multilayer version of the backboning algorithm consistently outperforms single layer versions in recovering signal edges regardless of how much noise there is, how correlated the layers are, and other factors — as you can see from the figure above.
And the Wikipedia question? That turns out to have an interesting answer as well. In a world without MNB, we would apply the single layer backboning independently to each layer, as well as to a super-network pulling information from all languages. Doing so, funnily enough, results in a confusing puzzle: each language in isolation does not show any bias (and if anything, it is biased against men) while the aggregated version clearly shows an anti-woman bias. How could it be that the aggregated version shows the opposite of what its layers support?
By applying the multilayer version of the backboning, MNB in the end shows a consistent picture, where the bias is absent both in the aggregate and in each of the layers. As a result, the contradiction we got from single layer backboning disappears, although it is obviously not the final answer to the bias question — here we focus on the method, leaving in the background a number of choices that were instead the main focus of the previous paper.
So while the jury is still out about Wikipedia biases, one thing is for certain: extracting multilayer backbones is useful; it solves problems that would be difficult to handle with single layer backboning. In the end, MNB’s story has a happy ending: the paper has found its place in the world. If you want to play with the new multilayer backboning algorithm, you can find its implementation here. I’m looking forward to seeing its legacy: dozens of better multilayer network backboning algorithms in the future.
* Kids, don’t try this at home.
