dynamicalab.algorithms.onion_decomposition

dynamicalab.algorithms.onion_decomposition(graph)

This function extracts the onion decomposition and the k-core decomposition of a simple undirected graph.

Parameters

graph : nx.Graph

A simple undirected graph without self-loops.

Warning

The algorithm only considers the simple (no multiedges), undirected and without self-loops version of the original graph.

Retuns

onion : dict

Dictionary mapping the vertices (identified by their name) to their layer in the onion decomposition.

kcore : dict

Dictionary mapping the vertices (identified by their name) to the maximal k-core to which they belong.

References

[1] L. Hébert-Dufresne, J. A. Grochow, and A. Allard, Multi-scale structure and topological anomaly detection via a new network statistic: The onion decomposition. Scientific Reports 6, 31708 (2016)

Example

import networkx as nx
import dynamicalab.algorithms as algo

G = nx.florentine_families_graph()
onion, kcore = algo.onion_decomposition(G)