Graph analysis ¶

Graph analysis

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 documentation 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 similar to 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 API documentation 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_connected().

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_incidence().

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:

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

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¶

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

Graph.components() (aka Graph.clusters()): 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_leading_eigenvector_naive()
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()

python-igraph Manual

Graph analysis ¶

Graph analysis¶

Vertices and edges¶

Incidence¶

Neighborhood¶

Degrees¶

Adding and removing vertices and edges¶

Graph operators¶

Topological sorting¶

Graph traversal¶

Pathfinding and cuts¶

Global properties¶

Vertex properties¶

Edge properties¶

Matrix representations¶

Clustering¶

Simplification, permutations and rewiring¶

Line graph¶

Composition and subgraphs¶

Morphisms¶

Flow¶