图分析

igraph 支持对图/网络进行分析，从添加和移除节点等简单操作到社区检测等复杂的理论构建。请阅读 API 参考 以获取每个函数和类的详细信息。

以下示例的上下文是导入 igraph（通常命名为 ig），拥有 Graph 类，并拥有一个或多个可用的图。

>>> import igraph as ig
>>> from igraph import Graph
>>> g = Graph(edges=[[0, 1], [2, 3]])

要获取图的摘要表示，请使用 Graph.summary()。例如

>>> g.summary(verbosity=1)

将提供相当详细的描述。

要复制图，请使用 Graph.copy()。这是一个“浅”复制：属性中的任何可变对象都不会被复制（它们将引用相同的实例）。如果您想复制一个包含所有属性的图，请使用 Python 的 deepcopy 模块。

顶点和边

顶点编号从 0 到 n-1，其中 n 是图中顶点的数量。这些被称为“顶点 ID”。要计算顶点数量，请使用 Graph.vcount()

>>> n = g.vcount()

边也具有从 0 到 m-1 的 ID，并通过 Graph.ecount() 计算。

>>> m = g.ecount()

要获取顶点序列，请使用它们的 ID 和 Graph.vs

>>> for v in g.vs:
>>>     print(v)

类似地，对于边，请使用 Graph.es

>>> for e in g.es:
>>>     print(e)

您可以像索引和切片列表一样索引和切片顶点和边

>>> g.vs[:4]
>>> g.vs[0, 2, 4]
>>> g.es[3]

注意

vs 和 es 属性是特殊的序列，它们有自己有用的方法。请参阅 API 参考 以获取完整列表。

如果您偏好简单的边列表，可以使用 Graph.get_edge_list()。

关联

要获取一条边两端的顶点，请使用 Edge.source 和 Edge.target

>>> e = g.es[0]
>>> v1, v2 = e.source, e.target

反之，要从源顶点和目标顶点获取边，可以使用 Graph.get_eid()；或者，对于多对源/目标，使用 Graph.get_eids()。布尔版本，询问两个顶点是否直接连接，是 Graph.are_adjacent()。

要获取顶点上的关联边，可以使用 Vertex.incident()、Vertex.out_edges() 和 Vertex.in_edges()。这三者在无向图上是等价的，但在有向图上则不然。

>>> v = g.vs[0]
>>> edges = v.incident()

Graph.incident() 函数实现相同目的，但语法略有不同，基于顶点 ID。

>>> edges = g.incident(0)

要获取图的完整邻接/关联列表表示，请使用 Graph.get_adjlist()、Graph.g.get_inclist() 或者，对于二部图，使用 Graph.get_biadjacency()。

邻域

要计算邻居、后继和前驱，可以使用方法 Graph.neighbors()、Graph.successors() 和 Graph.predecessors()。这三者在无向图中给出相同结果，但在有向图中则不然。

>>> neis = g.vs[0].neighbors()
>>> neis = g.neighbors(0)

要获取距离一个或多个初始顶点在一定距离内的顶点列表，可以使用 Graph.neighborhood()

>>> g.neighborhood([0, 1], order=2)

要查找邻域大小，有 Graph.neighborhood_size()。

度

要计算节点的度、入度或出度，请使用 Vertex.degree()、Vertex.indegree() 和 Vertex.outdegree()

>>> deg = g.vs[0].degree()
>>> deg = g.degree(0)

要计算顶点列表中最大度，请使用 Graph.maxdegree()。

Graph.knn() 计算邻居的平均度。

添加和移除顶点与边

要向图添加节点，请使用 Graph.add_vertex() 和 Graph.add_vertices()

>>> g.add_vertex()
>>> g.add_vertices(5)

这会就地更改图 g。如果需要，可以指定顶点的名称。

要移除节点，请使用 Graph.delete_vertices()

>>> g.delete_vertices([1, 2])

同样，您可以指定名称或实际的 Vertex 对象。

要添加边，请使用 Graph.add_edge() 和 Graph.add_edges()

>>> g.add_edge(0, 2)
>>> g.add_edges([(0, 2), (1, 3)])

要移除边，请使用 Graph.delete_edges()

>>> g.delete_edges([0, 5]) # remove by edge id

您也可以移除源节点和目标节点之间的边。

要收缩顶点，请使用 Graph.contract_vertices()。收缩顶点之间的边将变成自环。

图操作

可以计算图之间的并集、交集、差集以及其他集合操作（运算符）。

要计算图的并集（保留任一图中的节点/边）

>>> gu = ig.union([g, g2, g3])

类似地，对于交集（保留所有图中都存在的节点/边）

>>> gu = ig.intersection([g, g2, g3])

这两个操作保留属性，并可以有几种变体。最重要的一点是，顶点可以在图中通过 ID（数字）或名称进行匹配。

这些及其他操作也可作为 Graph 类的方法使用

>>> g.union(g2)
>>> g.intersection(g2)
>>> g.disjoint_union(g2)
>>> g.difference(g2)
>>> g.complementer()  # complement graph, same nodes but missing edges

甚至作为数值运算符

>>> g |= g2
>>> g_intersection = g and g2

拓扑排序

要对图进行拓扑排序，请使用 Graph.topological_sorting()

>>> g = ig.Graph.Tree(10, 2, mode=ig.TREE_OUT)
>>> g.topological_sorting()

图遍历

一个常见的操作是遍历图。igraph 当前通过 Graph.bfs() 和 Graph.bfsiter() 公开广度优先搜索（BFS）。

>>> [vertices, layers, parents] = g.bfs()
>>> it = g.bfsiter()  # Lazy version

深度优先搜索通过 Graph.dfs() 和 Graph.dfsiter() 具有类似的架构。

>>> [vertices, parents] = g.dfs()
>>> it = g.dfsiter()  # Lazy version

要从某个顶点执行随机游走，请使用 Graph.random_walk()

>>> vids = g.random_walk(0, 3)

路径查找与割

有几种路径查找算法可用

以及与割和路径相关的函数

  • Graph.mincut() 计算源顶点和目标顶点之间的最小割

  • Graph.st_mincut() - 与前一个类似，但返回一个更简单的数据结构

  • Graph.mincut_value() - 与前一个类似，但仅返回值

  • Graph.all_st_cuts()

  • Graph.all_st_mincuts()

  • Graph.edge_connectivity() 或 Graph.edge_disjoint_paths() 或 Graph.adhesion()

  • Graph.vertex_connectivity() 或 Graph.cohesion()

另请参阅关于流的部分。

全局属性

提供了一些全局图度量。

基本

  • Graph.diameter() 或 Graph.get_diameter()

  • Graph.girth()

  • Graph.radius()

  • Graph.average_path_length()

分布

连通性

  • Graph.all_minimal_st_separators()

  • Graph.minimum_size_separators()

  • Graph.cut_vertices() 或 Graph.articulation_points()

团和模体

  • Graph.clique_number() （又称 Graph.omega()）

  • Graph.cliques()

  • Graph.maximal_cliques()

  • Graph.largest_cliques()

  • Graph.motifs_randesu() 和 Graph.motifs_randesu_estimate()

  • Graph.motifs_randesu_no() 计算模体的数量

有向无环图

  • Graph.is_dag()

  • Graph.feedback_arc_set()

  • Graph.topological_sorting()

最优性

  • Graph.farthest_points()

  • Graph.modularity()

  • Graph.maximal_cliques()

  • Graph.largest_cliques()

  • Graph.independence_number() （又称 Graph.alpha()）

  • Graph.maximal_independent_vertex_sets()

  • Graph.largest_independent_vertex_sets()

  • Graph.mincut()

  • Graph.mincut_value()

  • Graph.feedback_arc_set()

  • Graph.maximum_bipartite_matching() （二部图）

其他复杂度量包括

布尔属性

顶点属性

可以计算一系列顶点级别的属性。相似性度量包括

  • Graph.similarity_dice()

  • Graph.similarity_jaccard()

  • Graph.similarity_inverse_log_weighted()

  • Graph.diversity()

结构

  • Graph.authority_score()

  • Graph.hub_score()

  • Graph.betweenness()

  • Graph.bibcoupling()

  • Graph.closeness()

  • Graph.constraint()

  • Graph.cocitation()

  • Graph.coreness() （又称 Graph.shell_index()）

  • Graph.eccentricity()

  • Graph.eigenvector_centrality()

  • Graph.harmonic_centrality()

  • Graph.pagerank()

  • Graph.personalized_pagerank()

  • Graph.strength()

  • Graph.transitivity_local_undirected()

连通性

  • Graph.subcomponent()

  • Graph.is_separator()

  • Graph.is_minimal_separator()

边属性

与顶点类似，边属性也已实现。基本属性包括

  • Graph.is_loop()

  • Graph.is_multiple()

  • Graph.is_mutual()

  • Graph.count_multiple()

以及更复杂的属性

  • Graph.edge_betweenness()

矩阵表示

与矩阵相关的功能包括

聚类

igraph 包含几种无监督图聚类和社区检测方法

简化、置换和重布线

要检查图是否简单，可以使用 Graph.is_simple()

>>> g.is_simple()

要简化图（移除多重边和自环），请使用 Graph.simplify()

>>> g_simple = g.simplify()

要返回图的有向/无向副本，请分别使用 Graph.as_directed() 和 Graph.as_undirected()。

要置换顶点的顺序，可以使用 Graph.permute_vertices()

>>> g = ig.Tree(6, 2)
>>> g_perm = g.permute_vertices([1, 0, 2, 3, 4, 5])

可以通过 Graph.canonical_permutation() 获取规范置换，然后可以直接传递给上述函数。

要随机重布线图，有以下方法：

  • Graph.rewire() - 保留度分布

  • Graph.rewire_edges() - 每个端点的重布线概率固定

线图

要计算图 g 的线图（表示 g 的边的连通性），可以使用 Graph.linegraph()

>>> g = Graph(n=4, edges=[[0, 1], [0, 2]])
>>> gl = g.linegraph()

在这种情况下，线图有两个顶点，代表原始图的两条边，以及一条边，代表这两条原始边接触的点。

组合和子图

函数 Graph.decompose() 将图分解为子图。反之，函数 Graph.compose() 返回两个图的组合。

要计算由某些顶点/边张成的子图，请使用 Graph.subgraph() （又称 Graph.induced_subgraph()）和 Graph.subgraph_edges()

>>> g_sub = g.subgraph([0, 1])
>>> g_sub = g.subgraph_edges([0])

要计算最小生成树，请使用 Graph.spanning_tree()。

要计算图 k 核，可以使用方法 Graph.k_core()。

可以从给定节点使用 Graph.dominator() 获取支配树。

可以使用 Graph.bipartite_projection() 分解二部图。投影的大小可以使用 Graph.bipartite_projection_size() 计算。

同态

igraph 支持图之间的比较

  • Graph.isomorphic()

  • Graph.isomorphic_vf2()

  • Graph.subisomorphic_vf2()

  • Graph.subisomorphic_lad()

  • Graph.get_isomorphisms_vf2()

  • Graph.get_subisomorphisms_vf2()

  • Graph.get_subisomorphisms_lad()

  • Graph.get_automorphisms_vf2()

  • Graph.count_isomorphisms_vf2()

  • Graph.count_subisomorphisms_vf2()

  • Graph.count_automorphisms_vf2()

流

流是有向图的一个特性。提供以下函数

流和割密切相关，因此您可能会发现以下函数也很有用

  • Graph.mincut() 计算源顶点和目标顶点之间的最小割

  • Graph.st_mincut() - 与前一个类似，但返回一个更简单的数据结构

  • Graph.mincut_value() - 与前一个类似，但仅返回值

  • Graph.all_st_cuts()

  • Graph.all_st_mincuts()

  • Graph.edge_connectivity() 或 Graph.edge_disjoint_paths() 或 Graph.adhesion()

  • Graph.vertex_connectivity() 或 Graph.cohesion()