Graph analysis

igraph enables analysis of graphs/networks from simple operations such as adding and removing nodes to complex theoretical constructs such as community detection. Read the API reference for details on each function and class.

The context for the following examples will be to import igraph (commonly as ig), have the Graph class and to have one or more graphs available:

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

To get a summary representation of the graph, use Graph.summary(). For instance:

>>> g.summary(verbosity=1)

will provide a fairly detailed description.

To copy a graph, use Graph.copy(). This is a “shallow” copy: any mutable objects in the attributes are not copied (they would refer to the same instance). If you want to copy a graph including all its attributes, use Python’s deepcopy module.

Vertices and edges

Vertices are numbered 0 to n-1, where n is the number of vertices in the graph. These are called the “vertex ids”. To count vertices, use Graph.vcount():

>>> n = g.vcount()

Edges also have ids from 0 to m-1 and are counted by Graph.ecount():

>>> m = g.ecount()

To get a sequence of vertices, use their ids and Graph.vs:

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

Similarly for edges, use Graph.es:

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

You can index and slice vertices and edges like indexing and slicing a list:

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

Note

The vs and es attributes are special sequences with their own useful methods. See the API reference for a full list.

If you prefer a vanilla edge list, you can use Graph.get_edge_list().

Incidence

To get the vertices at the two ends of an edge, use Edge.source and Edge.target:

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

Vice versa, to get the edge if from the source and target vertices, you can use Graph.get_eid() or, for multiple pairs of source/targets, Graph.get_eids(). The boolean version, asking whether two vertices are directly connected, is Graph.are_adjacent().

To get the edges incident on a vertex, you can use Vertex.incident(), Vertex.out_edges() and Vertex.in_edges(). The three are equivalent on undirected graphs but not directed ones of course:

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

The Graph.incident() function fulfills the same purpose with a slightly different syntax based on vertex IDs:

>>> edges = g.incident(0)

To get the full adjacency/incidence list representation of the graph, use Graph.get_adjlist(), Graph.g.get_inclist() or, for a bipartite graph, Graph.get_biadjacency().

Neighborhood

To compute the neighbors, successors, and predecessors, the methods Graph.neighbors(), Graph.successors() and Graph.predecessors() are available. The three give the same answer in undirected graphs and have a similar dual syntax:

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

To get the list of vertices within a certain distance from one or more initial vertices, you can use Graph.neighborhood():

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

and to find the neighborhood size, there is Graph.neighborhood_size().

Degrees

To compute the degree, in-degree, or out-degree of a node, use Vertex.degree(), Vertex.indegree(), and Vertex.outdegree():

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

To compute the max degree in a list of vertices, use Graph.maxdegree().

Graph.knn() computes the average degree of the neighbors.

Adding and removing vertices and edges

To add nodes to a graph, use Graph.add_vertex() and Graph.add_vertices():

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

This changes the graph g in place. You can specify the name of the vertices if you wish.

To remove nodes, use Graph.delete_vertices():

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

Again, you can specify the names or the actual Vertex objects instead.

To add edges, use Graph.add_edge() and Graph.add_edges():

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

To remove edges, use Graph.delete_edges():

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

You can also remove edges between source and target nodes.

To contract vertices, use Graph.contract_vertices(). Edges between contracted vertices will become loops.

Graph operators

It is possible to compute the union, intersection, difference, and other set operations (operators) between graphs.

To compute the union of the graphs (nodes/edges in either are kept):

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

Similarly for the intersection (nodes/edges present in all are kept):

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

These two operations preserve attributes and can be performed with a few variations. The most important one is that vertices can be matched across the graphs by id (number) or by name.

These and other operations are also available as methods of the Graph class:

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

and even as numerical operators:

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

Topological sorting

To sort a graph topologically, use Graph.topological_sorting():

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

Graph traversal

A common operation is traversing the graph. igraph currently exposes breadth-first search (BFS) via Graph.bfs() and Graph.bfsiter():

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

Depth-first search has a similar infrastructure via Graph.dfs() and Graph.dfsiter():

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

To perform a random walk from a certain vertex, use Graph.random_walk():

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

Pathfinding and cuts

Several pathfinding algorithms are available:

As well as functions related to cuts and paths:

  • Graph.mincut() calculates the minimum cut between the source and target vertices

  • Graph.st_mincut() - as previous one, but returns a simpler data structure

  • Graph.mincut_value() - as previous one, but returns only the value

  • Graph.all_st_cuts()

  • Graph.all_st_mincuts()

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

  • Graph.vertex_connectivity() or Graph.cohesion()

See also the section on flow.

Global properties

A number of global graph measures are available.

Basic:

  • Graph.diameter() or Graph.get_diameter()

  • Graph.girth()

  • Graph.radius()

  • Graph.average_path_length()

Distributions:

Connectedness:

  • Graph.all_minimal_st_separators()

  • Graph.minimum_size_separators()

  • Graph.cut_vertices() or Graph.articulation_points()

Cliques and motifs:

  • Graph.clique_number() (aka Graph.omega())

  • Graph.cliques()

  • Graph.maximal_cliques()

  • Graph.largest_cliques()

  • Graph.motifs_randesu() and Graph.motifs_randesu_estimate()

  • Graph.motifs_randesu_no() counts the number of motifs

Directed acyclic graphs:

  • Graph.is_dag()

  • Graph.feedback_arc_set()

  • Graph.topological_sorting()

Optimality:

  • Graph.farthest_points()

  • Graph.modularity()

  • Graph.maximal_cliques()

  • Graph.largest_cliques()

  • Graph.independence_number() (aka 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() (bipartite graphs)

Other complex measures are:

Boolean properties:

Vertex properties

A spectrum of vertex-level properties can be computed. Similarity measures include:

  • Graph.similarity_dice()

  • Graph.similarity_jaccard()

  • Graph.similarity_inverse_log_weighted()

  • Graph.diversity()

Structural:

  • Graph.authority_score()

  • Graph.hub_score()

  • Graph.betweenness()

  • Graph.bibcoupling()

  • Graph.closeness()

  • Graph.constraint()

  • Graph.cocitation()

  • Graph.coreness() (aka Graph.shell_index())

  • Graph.eccentricity()

  • Graph.eigenvector_centrality()

  • Graph.harmonic_centrality()

  • Graph.pagerank()

  • Graph.personalized_pagerank()

  • Graph.strength()

  • Graph.transitivity_local_undirected()

Connectedness:

  • Graph.subcomponent()

  • Graph.is_separator()

  • Graph.is_minimal_separator()

Edge properties

As for vertices, edge properties are implemented. Basic properties include:

  • Graph.is_loop()

  • Graph.is_multiple()

  • Graph.is_mutual()

  • Graph.count_multiple()

and more complex ones:

  • Graph.edge_betweenness()

Matrix representations

Matrix-related functionality includes:

  • Graph.get_adjacency()

  • Graph.get_adjacency_sparse() (sparse CSR matrix version)

  • Graph.laplacian()

Clustering

igraph includes several approaches to unsupervised graph clustering and community detection:

  • Graph.components() (aka Graph.connected_components()): the 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_leiden()

  • Graph.community_multilevel() (a version of Louvain)

  • Graph.community_optimal_modularity() (exact solution, < 100 vertices)

  • Graph.community_spinglass()

  • Graph.community_walktrap()

Simplification, permutations and rewiring

To check is a graph is simple, you can use Graph.is_simple():

>>> g.is_simple()

To simplify a graph (remove multiedges and loops), use Graph.simplify():

>>> g_simple = g.simplify()

To return a directed/undirected copy of the graph, use Graph.as_directed() and Graph.as_undirected(), respectively.

To permute the order of vertices, you can use Graph.permute_vertices():

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

The canonical permutation can be obtained via Graph.canonical_permutation(), which can then be directly passed to the function above.

To rewire the graph at random, there are:

  • Graph.rewire() - preserves the degree distribution

  • Graph.rewire_edges() - fixed rewiring probability for each endpoint

Line graph

To compute the line graph of a graph g, which represents the connectedness of the edges of g, you can use Graph.linegraph():

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

In this case, the line graph has two vertices, representing the two edges of the original graph, and one edge, representing the point where those two original edges touch.

Composition and subgraphs

The function Graph.decompose() decomposes the graph into subgraphs. Vice versa, the function Graph.compose() returns the composition of two graphs.

To compute the subgraph spannes by some vertices/edges, use Graph.subgraph() (aka Graph.induced_subgraph()) and Graph.subgraph_edges():

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

To compute the minimum spanning tree, use Graph.spanning_tree().

To compute graph k-cores, the method Graph.k_core() is available.

The dominator tree from a given node can be obtained with Graph.dominator().

Bipartite graphs can be decomposed using Graph.bipartite_projection(). The size of the projections can be computed using Graph.bipartite_projection_size().

Morphisms

igraph enables comparisons between graphs:

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

Flow

Flow is a characteristic of directed graphs. The following functions are available:

  • Graph.maxflow() between two nodes

  • Graph.maxflow_value() - similar to the previous one, but only the value is returned

  • Graph.gomory_hu_tree()

Flow and cuts are closely related, therefore you might find the following functions useful as well:

  • Graph.mincut() calculates the minimum cut between the source and target vertices

  • Graph.st_mincut() - as previous one, but returns a simpler data structure

  • Graph.mincut_value() - as previous one, but returns only the value

  • Graph.all_st_cuts()

  • Graph.all_st_mincuts()

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

  • Graph.vertex_connectivity() or Graph.cohesion()