dedensify

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

压缩高度节点周围的邻域

通过添加压缩节点来减少与高度节点的边数，这些压缩节点汇总了相同类型到高度节点的多条边（节点度数大于给定阈值的节点）。去密集化还具有减少高度节点周围边数的额外好处。当前实现支持具有单一边类型的图。

Parameters:

G: 图

一个 networkx 图

threshold: int

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

prefix: str 或 None, 可选 (默认: None)

表示压缩节点的可选前缀

copy: bool, 可选 (默认: True)

指示去密集化是否应在原地进行

Returns:

去密集化的 networkx 图(图, 集合)

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

Notes

根据[1]中的算法，通过添加压缩节点来压缩/解压缩高度节点周围的邻域，从而删除图中的边。去密集化仅在这样做会减少给定图中的总边数时才添加压缩节点。当前实现支持具有单一边类型的图。

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

去密集化仅在这样做会导致更少的边时才添加压缩节点:

>>> 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)
>>> # 将压缩图重新密集化为原始图
>>> 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