snap_aggregation#

snap_aggregation(G, node_attributes, edge_attributes=(), prefix='Supernode-', supernode_attribute='group', superedge_attribute='types')[source]#

基于属性和连接性创建摘要图。

此函数使用基于节点属性和成对边分组的摘要（SNAP）算法，通过将节点按节点属性和边属性分组为摘要图中的超节点来汇总给定图。此名称SNAP不应与斯坦福网络分析项目（SNAP）混淆。

以下是该算法的高级视图：

  1. 按节点属性值对节点进行分组。

  2. 迭代地分割组，直到每个组中的所有节点都与同一组中的节点有边。也就是说，直到所有组在其成员节点与其他组的边方面都是同质的。例如，如果组A中的所有节点仅与组B中的节点有边，则该组是同质的，不需要分割。如果组B中的所有节点与组{A, C}中的节点有边，但有些节点也与组B中的其他节点有边，则组B不是同质的，需要分割为与{A, C}有边的组和与{A, B, C}有边的组。这样，摘要图的观察者可以假设组中的所有节点具有完全相同的节点属性和完全相同的边。

  3. 构建输出摘要图，其中组由超节点表示。边表示每个相应组中所有节点共享的边。

SNAP摘要图可用于可视化或视觉分析太大而无法显示的图，或基于图中的指定节点和/或边属性高效识别具有相似连接模式到其他相似节点集的相似节点集。

Parameters:
G: graph

要汇总的Networkx图

node_attributes: iterable, 必需

用于在汇总过程中对节点进行分组的节点属性可迭代对象。具有相同这些属性值的节点将在摘要图中分组在一起。

edge_attributes: iterable, 可选

在汇总过程中考虑的边属性可迭代对象。如果提供，图中的属性值的唯一组合用于确定图中的边类型。如果未提供，则所有边都被视为同一类型。

prefix: str

用于在摘要图中表示超节点的前缀。默认为’Supernode-’。

supernode_attribute: str

用于记录节点超节点分组的节点属性。默认为’group’。

superedge_attribute: str

用于记录多条边的边类型的边属性。默认为’types’。

Returns:
networkx.Graph: 摘要图

Notes

生成的摘要图称为最大属性-边兼容（AR-compatible）分组。根据[1]，AR-compatible分组意味着每个组中的所有节点具有完全相同的节点属性值和完全相同的边及边类型到一个或多个相同组中的节点。最大AR-compatible分组是具有最小基数的分组。

AR-compatible分组是由任何SNAP算法提供的最详细的分组。

References

[1]

Y. Tian, R. A. Hankins, and J. M. Patel. Efficient aggregation for graph summarization. In Proc. 2008 ACM-SIGMOD Int. Conf. Management of Data (SIGMOD’08), pages 567–580, Vancouver, Canada, June 2008.

Examples

SNAP聚合接受一个图并在用户提供的节点和边属性的上下文中对其进行汇总，以便观察者可以更容易地提取和分析图所表示的信息。

>>> nodes = {
...     "A": dict(color="Red"),
...     "B": dict(color="Red"),
...     "C": dict(color="Red"),
...     "D": dict(color="Red"),
...     "E": dict(color="Blue"),
...     "F": dict(color="Blue"),
... }
>>> edges = [
...     ("A", "E", "Strong"),
...     ("B", "F", "Strong"),
...     ("C", "E", "Weak"),
...     ("D", "F", "Weak"),
... ]
>>> G = nx.Graph()
>>> for node in nodes:
...     attributes = nodes[node]
...     G.add_node(node, **attributes)
>>> for source, target, type in edges:
...     G.add_edge(source, target, type=type)
>>> node_attributes = ("color",)
>>> edge_attributes = ("type",)
>>> summary_graph = nx.snap_aggregation(
...     G, node_attributes=node_attributes, edge_attributes=edge_attributes
... )
On this page