snap_aggregation#

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

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

此函数使用基于属性和成对边的节点分组（SNAP）算法，通过将节点按节点属性及其边属性分组为摘要图中的超节点来对给定图进行摘要。此名称 SNAP 不应与 Stanford Network Analysis Project (SNAP) 混淆。

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

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

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

3) 构建输出摘要图，其中组由超节点表示。边表示各组中所有节点之间共享的边。

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

参数：
G: 图

要进行摘要的 NetworkX 图。

node_attributes: 可迭代，必需

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

edge_attributes: 可迭代，可选

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

prefix: str

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

supernode_attribute: str

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

superedge_attribute: str

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

返回：
networkx.Graph: 摘要图

注意

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

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

参考文献

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

示例

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
... )
在本页