脱密

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

压缩高度节点周围的邻域

通过将将相同类型的多条边汇总为高度节点(度数大于给定阈值的节点)的压缩器节点添加到高度节点，将边的数量减少到高度节点。去敏化还有一个额外的好处，那就是减少高度节点周围的边数。该实现目前支持具有单一边类型的图。

参数

G: graph

网络X图

threshold: int

被视为高度节点的节点的最小度数阈值。阈值必须大于或等于2。

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

表示压缩机节点的可选前缀

copy: bool, optional (default: True)

指示是否应就地进行去密化

返回

dedensified networkx graph(图表，集合)

去密图和压缩器节点集的2元组

笔记

根据中的算法 [1], 通过将将同一类型的多条边汇总到高度节点的压缩器节点添加到高度节点来压缩/解压缩高度节点周围的邻域，从而删除图形中的边。去敏化只会添加压缩器节点，而这样做会减少给定图中的总边数。此实现目前支持具有单一边类型的图。

工具书类

1

Maccioni，A.和Abadi，D.J.(2016，8月)。压缩图上的可伸缩模式匹配算法。见第22届ACM SIGKDD知识发现和数据挖掘国际会议论文集(1755-1764页)。Http://www.cs.umd.edu/~abadi/papers/graph-dedense.pdf

实例

去敏化仅在这样做会导致更少的边时才添加压缩机节点：

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