analysis.rst

igraph

Graph analysis

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/index for details on each function and class.

The context for the following examples will be to import (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/index 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. 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:

• Graph.shortest_paths or Graph.get_shortest_paths
• Graph.get_all_shortest_paths
• Graph.get_all_simple_paths
• Graph.spanning_tree finds a minimum spanning tree

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:

• Graph.degree_distribution
• Graph.path_length_hist

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:

• 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 (directed graphs)
• Graph.isoclass (only 3 or 4 vertices)
• Graph.biconnected_components aka Graph.blocks

Boolean properties:

• Graph.is_bipartite
• Graph.is_connected
• Graph.is_dag
• Graph.is_directed
• Graph.is_named
• Graph.is_simple
• Graph.is_weighted
• Graph.has_multiple

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

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

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