Skip to main content
`Ctrl`+`K`

# dedensify

dedensify(G, threshold, prefix=None, copy=True)

  Compresses neighborhoods around high-degree nodes

  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.

  Parameters:
    G: graph

      A networkx graph

    threshold: int

      Minimum degree threshold of a node to be considered a high degree node. The threshold must be greater than or equal to 2.

    prefix: str or None, optional (default: None)

      An optional prefix for denoting compressor nodes

    copy: bool, optional (default: True)

      Indicates if dedensification should be done inplace

  Returns:
    dedensified networkx graph(graph, set)

      2-tuple of the dedensified graph and set of compressor nodes

  Notes

  According to the algorithm in [1], 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.

  References

  [1]

  Maccioni, A., & Abadi, D. J. (2016, August). Scalable pattern matching over compressed graphs via dedensification. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 1755-1764). http://www.cs.umd.edu/~abadi/papers/graph-dedense.pdf

  Examples

  Dedensification will only add compressor nodes when doing so would result in fewer edges:

      >>> 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

  A dedensified, directed graph can be “densified” to reconstruct the original graph:

      >>> 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)
      True