Distance Closure: the distance backbone of complex networks#

Description#

This package implements methods for the calculation of the Distance Closure on Complex Networks, including its metric and ultrametric backbone.

The distance backbone is a principled graph reduction technique. It is a small subgraph sufficicent to compute all shortest paths. This method is suited for undirected weighted graphs, also known as proximity (similarity) or distance (dissimilarity) graphs.

Quick Install#

$pip install distanceclosure

Simple usage#

import networkx as nx
import distanceclosure as dc

# Instanciate a (weighted) graph
edgelist = {
    ('s', 'a'): 8,
    ('s', 'c'): 6,
    ('s', 'd'): 5,
    ('a', 'd'): 2,
    ('a', 'e'): 1,
    ('b', 'e'): 6,
    ('c', 'd'): 3,
    ('c', 'f'): 9,
    ('d', 'f'): 4,
    ('e', 'g'): 4,
    ('f', 'g'): 0,
}
G = nx.from_edgelist(edgelist)
# Make sure there an edge attribute with the distance value
nx.set_edge_attributes(G, name='distance', values=edgelist)

# Compute closure (note this will be a fully connected graph. It can be slow for large graphs)
C = dc.distance_closure(G, kind='metric', weight='distance')

# You can now access the new `metric_distance` value and whether the edge is part of the metric backbone.
C['s']['c']
> {'distance': 6, 'metric_distance': 6, 'is_metric': True}

If you are only interested in the metric backbone, you might want to only include distance values for edges already in the graph.

C2 = dc.distance_closure(G, kind='metric', weight='distance', only_backbone=True)

C.number_of_edges()
> 28
C2.number_of_edges()
> 11

Formal definition#

For the formal definition of the distance backbone, please refer to

Recent papers from our group that have used or built upon this method:

Additional papers [CSR+15, CAW+22, CBR22, CLR16, Roc02, RSR+05, SCR21, SR12, SR15] can be found in the Bibliography page.

Citation#

@article{Simas:2021,
    author = {Tiago Simas and Rion Brattig Correia and Luis M. Rocha},
    doi = {10.1093/comnet/cnab021},
    issue = {6},
    journal = {Journal of Complex Networks},
    pages = {cnab021},
    title = {The distance backbone of complex networks},
    volume = {9},
    year = {2021}
}

Documentation:#

Table of Contents:

Indices and tables#