improve backbone extraction

[jboynyc]

It would be nice to move away from Serrano et al. to something more robust in a future release.

Possibly relevant literature: 1, 2

[jboynyc]

I will focus on implementing Liebig & Rao (2016).

[jboynyc]

https://arxiv.org/abs/2105.13396

[BradKML]

Can one say that a "backbone" in a network operates as a "keyword" in a document-term graph? Or maybe a "top person" in a document-author or author-term graph?

[jboynyc]

No, sorry, by backbone extraction I mean the process of eliminating edges from a graph to find relevant connections. Currently I use a filtering technique that doesn't take the bipartite structure of the initial network into consideration.

[BradKML]

@jboynyc Apologies, but connections on which context?

[BradKML]

Backbone seemed be dependent on scale, weightedness and directedness

• https://www.proquest.com/docview/2129402194
• https://www.mendeley.com/catalogue/bc2fcbd1-a538-31ef-af84-7b28ad9ed359/
• https://etd.ohiolink.edu/apexprod/rws_etd/send_file/send?accession=kent1334516240&disposition=inline
• https://sci-hub.se/10.1007/s13278-011-0021-0
• https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.147.3258&rep=rep1&type=pdf
• https://www.nature.com/articles/s41598-020-71876-0
• https://www.pnas.org/content/106/16/6483
• https://arxiv.org/pdf/2012.05216.pdf
• https://sci-hub.se/https://ieeexplore.ieee.org/document/6921564
• https://sci-hub.se/10.1371/journal.pone.0100428
• https://www.osti.gov/pages/servlets/purl/1624425

[jboynyc]

Sorry, in other words it's about finding significant edges and discarding insignificant ones. (connections = edges)

[BradKML]

Define "significant". Would it see edges that form rings to be less significant (optimizing for spanning trees)? Would methods based on weighted edges weight stronger edges better? Would it want disconnected edges?

If this is hard to describe, would this extraction method apply to topic, terms, or author graphs?

[jboynyc]

The definition of "significance" differs by technique. Usually there's a comparison to a null model, with different techniques using different null models.

My question on this issue is specifically about techniques that use information about the bipartite network to aid backbone extraction of projections. Liebig & Rao and this paper outline some techniques, but so far I haven't found any usable implementations.

[jboynyc]

Here is an implementation of the bipartite configuration model: https://github.com/mat701/BiCM

I hesitate to add a dependency to this package until I get a chance to study it more closely.

• How does it perform?
• Is it a problem that the BiCM does not consider edge weights?
• How well maintained is it? It has some recent commits, but doesn't seem to have been tested beyond Python 3.8.
• Dependencies are mostly overlapping with current dependencies, but it would pull in numba as an additional dependency. If I remove the disparity filter, I would no longer have to depend on cython, so this could be zero sum.

[jboynyc]

Another relevant citation supporting my impression that using the disparity filter on projected one-mode networks is not a great idea: https://doi.org/10.1038/s42005-022-00856-9