dedensify(G, threshold, prefix=None, copy=True)
Reduces the number of edges to high-degree nodes by adding compressor nodes that summarize multiple edges of the same type to high-degree nodes (nodes with a degree greater than a given threshold). Dedensification also has the added benefit of reducing the number of edges around high-degree nodes. The implementation currently supports graphs with a single edge type.
According to the algorithm in , removes edges in a graph by compressing/decompressing the neighborhoods around high degree nodes by adding compressor nodes that summarize multiple edges of the same type to high-degree nodes. Dedensification will only add a compressor node when doing so will reduce the total number of edges in the given graph. This implementation currently supports graphs with a single edge type.
A networkx graph
Minimum degree threshold of a node to be considered a high degree node. The threshold must be greater than or equal to 2.
An optional prefix for denoting compressor nodes
Indicates if dedensification should be done inplace
2-tuple of the dedensified graph and set of compressor nodes
Compresses neighborhoods around high-degree nodes
>>> original_graph = nx.DiGraph()
>>> original_graph.add_nodes_from(
... ["1", "2", "3", "4", "5", "6", "A", "B", "C"]
... )
>>> original_graph.add_edges_from(
... [
... ("1", "C"), ("1", "B"),
... ("2", "C"), ("2", "B"), ("2", "A"),
... ("3", "B"), ("3", "A"), ("3", "6"),
... ("4", "C"), ("4", "B"), ("4", "A"),
... ("5", "B"), ("5", "A"),
... ("6", "5"),
... ("A", "6")
... ]
... )
>>> c_graph, c_nodes = nx.dedensify(original_graph, threshold=2)
>>> original_graph.number_of_edges()
15
>>> c_graph.number_of_edges()
14>>> original_graph = nx.DiGraph()
>>> original_graph.add_nodes_from(
... ["1", "2", "3", "4", "5", "6", "A", "B", "C"]
... )
>>> original_graph.add_edges_from(
... [
... ("1", "C"), ("1", "B"),
... ("2", "C"), ("2", "B"), ("2", "A"),
... ("3", "B"), ("3", "A"), ("3", "6"),
... ("4", "C"), ("4", "B"), ("4", "A"),
... ("5", "B"), ("5", "A"),
... ("6", "5"),
... ("A", "6")
... ]
... )
>>> c_graph, c_nodes = nx.dedensify(original_graph, threshold=2)
>>> # re-densifies the compressed graph into the original graph
>>> for c_node in c_nodes:
... all_neighbors = set(nx.all_neighbors(c_graph, c_node))
... out_neighbors = set(c_graph.neighbors(c_node))
... for out_neighbor in out_neighbors:
... c_graph.remove_edge(c_node, out_neighbor)
... in_neighbors = all_neighbors - out_neighbors
... for in_neighbor in in_neighbors:
... c_graph.remove_edge(in_neighbor, c_node)
... for out_neighbor in out_neighbors:
... c_graph.add_edge(in_neighbor, out_neighbor)
... c_graph.remove_node(c_node)
...
>>> nx.is_isomorphic(original_graph, c_graph)
TrueHover to see nodes names; edges to Self not shown, Caped at 50 nodes.
Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)
SVG is more flexible but power hungry; and does not scale well to 50 + nodes.
All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them