顶点和边¶

顶点编号从 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]

如果您更喜欢原始的边列表，可以使用 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_connected()。

要获取与顶点关联的边，可以使用 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_incidence()。

邻域¶

要计算邻居、后继和前驱，可以使用方法 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.shortest_paths() 或 Graph.get_shortest_paths()

• Graph.get_all_shortest_paths()

• Graph.get_all_simple_paths()

• Graph.spanning_tree() 找到最小生成树

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

• 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.degree_distribution()

• Graph.path_length_hist()

连通性

• 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.assortativity()

• Graph.assortativity_degree()

• Graph.assortativity_nominal()

• Graph.density()

• Graph.transitivity_undirected()

• Graph.transitivity_avglocal_undirected()

• Graph.dyad_census()

• Graph.triad_census()

• Graph.reciprocity()（有向图）

• Graph.isoclass()（仅 3 或 4 个顶点）

• Graph.biconnected_components() 也称为 Graph.blocks()

布尔属性

• Graph.is_bipartite()

• Graph.is_connected()

• Graph.is_dag()

• Graph.is_directed()

• Graph.is_named()

• Graph.is_simple()

• Graph.is_weighted()

• Graph.has_multiple()

顶点属性¶

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

• 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()

矩阵表示¶

与矩阵相关的功能包括

• Graph.get_adjacency()

• Graph.get_adjacency_sparse()（稀疏 CSR 矩阵版本）

• Graph.laplacian()

聚类¶

igraph 包括几种用于无监督图聚类和社群检测的方法

• Graph.components() (也称为 Graph.connected_components())：连通分量

• Graph.cohesive_blocks()

• Graph.community_edge_betweenness()

• Graph.community_fastgreedy()

• Graph.community_infomap()

• Graph.community_label_propagation()

• Graph.community_leading_eigenvector()

• Graph.community_leading_eigenvector_naive()

• Graph.community_leiden()

• Graph.community_multilevel()（Louvain 的一个版本）

• Graph.community_optimal_modularity()（精确解，< 100 个顶点）

• Graph.community_spinglass()

• Graph.community_walktrap()

简化、排列和重连¶

要检查图是否简单，可以使用 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.maxflow() 两个节点之间

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

• Graph.gomory_hu_tree()

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

• 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()