Package igraph :: Class GraphBase
[hide private]
[frames] | no frames]

Class GraphBase

source code

object --+
         |
        GraphBase
Known Subclasses:

Low-level representation of a graph.

Don't use it directly, use igraph.Graph instead.

Instance Methods [hide private]
 
Adjacency(matrix, mode=ADJ_DIRECTED)
Generates a graph from its adjacency matrix.
source code
 
Asymmetric_Preference(n, type_dist_matrix, pref_matrix, attribute=None, loops=False)
Generates a graph based on asymmetric vertex types and connection probabilities.
source code
 
Atlas(idx)
Generates a graph from the Graph Atlas.
source code
 
Barabasi(n, m, outpref=False, directed=False, power=1, zero_appeal=1, implementation="psumtree", start_from=None)
Generates a graph based on the Barabasi-Albert model.
source code
 
De_Bruijn(m, n)
Generates a de Bruijn graph with parameters (m, n)
source code
 
Degree_Sequence(out, in=None, method="simple")
Generates a graph with a given degree sequence.
source code
 
Erdos_Renyi(n, p, m, directed=False, loops=False)
Generates a graph based on the Erdos-Renyi model.
source code
 
Establishment(n, k, type_dist, pref_matrix, directed=False)
Generates a graph based on a simple growing model with vertex types.
source code
 
Famous(name)
Generates a famous graph based on its name.
source code
 
Forest_Fire(n, fw_prob, bw_factor=0.0, ambs=1, directed=False)
Generates a graph based on the forest fire model
source code
 
Full(n, directed=False, loops=False)
Generates a full graph (directed or undirected, with or without loops).
source code
 
Full_Citation(n, directed=False)
Generates a full citation graph
source code
 
Growing_Random(n, m, directed=False, citation=False)
Generates a growing random graph.
source code
 
Isoclass(n, class, directed=False)
Generates a graph with a given isomorphy class.
source code
 
K_Regular(n, k, directed=False, multiple=False)
Generates a k-regular random graph
source code
 
Kautz(m, n)
Generates a Kautz graph with parameters (m, n)
source code
 
LCF(n, shifts, repeats)
Generates a graph from LCF notation.
source code
 
Lattice(dim, nei=1, directed=False, mutual=True, circular=True)
Generates a regular lattice.
source code
 
Preference(n, type_dist, pref_matrix, attribute=None, directed=False, loops=False)
Generates a graph based on vertex types and connection probabilities.
source code
 
Read_DIMACS(f, directed=False)
Reads a graph from a file conforming to the DIMACS minimum-cost flow file format.
source code
 
Read_DL(f, directed=True)
Reads an UCINET DL file and creates a graph based on it.
source code
 
Read_Edgelist(f, directed=True)
Reads an edge list from a file and creates a graph based on it.
source code
 
Read_GML(f)
Reads a GML file and creates a graph based on it.
source code
 
Read_GraphDB(f, directed=False)
Reads a GraphDB format file and creates a graph based on it.
source code
 
Read_GraphML(f, directed=True, index=0)
Reads a GraphML format file and creates a graph based on it.
source code
 
Read_Lgl(f, names=True, weights="if_present", directed=True)
Reads an .lgl file used by LGL.
source code
 
Read_Ncol(f, names=True, weights="if_present", directed=True)
Reads an .ncol file used by LGL.
source code
 
Read_Pajek(f)
Reads a Pajek format file and creates a graph based on it.
source code
 
Recent_Degree(n, m, window, outpref=False, directed=False, power=1)
Generates a graph based on a stochastic model where the probability of an edge gaining a new node is proportional to the edges gained in a given time window.
source code
 
Ring(n, directed=False, mutual=False, circular=True)
Generates a ring graph.
source code
 
Star(n, mode="undirected", center=0)
Generates a star graph.
source code
 
Static_Fitness(m, fitness_out, fitness_in=None, loops=False, multiple=False)
Generates a non-growing graph with edge probabilities proportional to node fitnesses.
source code
 
Static_Power_Law(n, m, exponent_out, exponent_in=-1, loops=False, multiple=False, finite_size_correction=True)
Generates a non-growing graph with prescribed power-law degree distributions.
source code
 
Tree(n, children, type=TREE_UNDIRECTED)
Generates a tree in which almost all vertices have the same number of children.
source code
 
Watts_Strogatz(dim, size, nei, p, loops=False, multiple=False) source code
 
Weighted_Adjacency(matrix, mode=ADJ_DIRECTED, attr="weight", loops=True)
Generates a graph from its adjacency matrix.
source code
 
__and__(x, y)
x&y
source code
 
__delitem__(x, y)
del x[y]
source code
 
__getitem__(x, y)
x[y]
source code
 
__graph_as_cobject()
Returns the igraph graph encapsulated by the Python object as a PyCObject
source code
 
__init__(...)
x.__init__(...) initializes x; see help(type(x)) for signature
source code
 
__invert__(x)
~x
source code
a new object with type S, a subtype of T
__new__(T, S, ...) source code
 
__or__(x, y)
x|y
source code
 
__rand__(x, y)
y&x
source code
 
__register_destructor(destructor)
Registers a destructor to be called when the object is freed by Python.
source code
 
__ror__(x, y)
y|x
source code
 
__setitem__(x, i, y)
x[i]=y
source code
 
__str__(x)
str(x)
source code
 
add_edges(es)
Adds edges to the graph.
source code
 
add_vertices(n)
Adds vertices to the graph.
source code
 
all_minimal_st_separators()
Returns a list containing all the minimal s-t separators of a graph.
source code
 
all_st_cuts(source, target)
Returns all the cuts between the source and target vertices in a directed graph.
source code
 
all_st_mincuts(source, target)
Returns all minimum cuts between the source and target vertices in a directed graph.
source code
 
are_connected(v1, v2)
Decides whether two given vertices are directly connected.
source code
 
articulation_points()
Returns the list of articulation points in the graph.
source code
 
assortativity(types1, types2=None, directed=True)
Returns the assortativity of the graph based on numeric properties of the vertices.
source code
 
assortativity_degree(directed=True)
Returns the assortativity of a graph based on vertex degrees.
source code
 
assortativity_nominal(types, directed=True)
Returns the assortativity of the graph based on vertex categories.
source code
 
attributes()
Returns: the attribute name list of the graph
source code
 
authority_score(weights=None, scale=True, arpack_options=None, return_eigenvalue=False)
Calculates Kleinberg's authority score for the vertices of the graph
source code
 
average_path_length(directed=True, unconn=True)
Calculates the average path length in a graph.
source code
 
betweenness(vertices=None, directed=True, cutoff=None, weights=None, nobigint=True)
Calculates or estimates the betweenness of vertices in a graph.
source code
 
bfs(vid, mode=OUT)
Conducts a breadth first search (BFS) on the graph.
source code
 
bfsiter(vid, mode=OUT, advanced=False)
Constructs a breadth first search (BFS) iterator of the graph.
source code
 
bibcoupling(vertices=None)
Calculates bibliographic coupling scores for given vertices in a graph.
source code
 
biconnected_components(return_articulation_points=True)
Calculates the biconnected components of the graph.
source code
 
bipartite_projection(types, multiplicity=True, probe1=-1)
Internal function, undocumented.
source code
 
bipartite_projection_size(types)
Internal function, undocumented.
source code
 
clique_number()
Returns the clique number of the graph.
source code
 
cliques(min=0, max=0)
Returns some or all cliques of the graph as a list of tuples.
source code
 
closeness(vertices=None, mode=ALL, cutoff=None, weights=None)
Calculates the closeness centralities of given vertices in a graph.
source code
 
clusters(mode=STRONG)
Calculates the (strong or weak) clusters for a given graph.
source code
 
cocitation(vertices=None)
Calculates cocitation scores for given vertices in a graph.
source code
 
cohesive_blocks()
Calculates the cohesive block structure of the graph.
source code
 
community_edge_betweenness(directed=True, weights=None)
Community structure detection based on the betweenness of the edges in the network.
source code
 
community_fastgreedy(weights=None)
Finds the community structure of the graph according to the algorithm of Clauset et al based on the greedy optimization of modularity.
source code
 
community_infomap(edge_weights=None, vertex_weights=None, trials=10)
Finds the community structure of the network according to the Infomap method of Martin Rosvall and Carl T.
source code
 
community_label_propagation(weights=None, initial=None, fixed=None)
Finds the community structure of the graph according to the label propagation method of Raghavan et al.
source code
 
community_leading_eigenvector(n=-1)
A proper implementation of Newman's eigenvector community structure detection.
source code
 
community_multilevel(weights=None, return_levels=True)
Finds the community structure of the graph according to the multilevel algorithm of Blondel et al.
source code
 
community_optimal_modularity(verbose=False)
Calculates the optimal modularity score of the graph and the corresponding community structure.
source code
 
community_spinglass(weights=None, spins=25, parupdate=False, start_temp=1, stop_temp=0.01, cool_fact=0.99, update_rule="config", gamma=1, implementation="orig", lambda=1)
Finds the community structure of the graph according to the spinglass community detection method of Reichardt & Bornholdt.
source code
 
community_walktrap(weights=None, steps=None)
Finds the community structure of the graph according to the random walk method of Latapy & Pons.
source code
 
complementer(loops=False)
Returns the complementer of the graph
source code
 
compose(other)
Returns the composition of two graphs.
source code
 
constraint(vertices=None, weights=None)
Calculates Burt's constraint scores for given vertices in a graph.
source code
 
contract_vertices(mapping, combine_attrs=None)
Contracts some vertices in the graph, i.e.
source code
 
convergence_degree()
Undocumented (yet).
source code
 
convergence_field_size()
Undocumented (yet).
source code
 
copy()
Creates an exact deep copy of the graph.
source code
 
coreness(mode=ALL)
Finds the coreness (shell index) of the vertices of the network.
source code
 
count_isomorphisms_vf2(other=None, color1=None, color2=None, edge_color1=None, edge_color2=None, node_compat_fn=None, edge_compat_fn=None)
Determines the number of isomorphisms between the graph and another one
source code
 
count_multiple(edges=None)
Counts the multiplicities of the given edges.
source code
 
count_subisomorphisms_vf2(other, color1=None, color2=None, edge_color1=None, edge_color2=None, node_compat_fn=None, edge_compat_fn=None)
Determines the number of subisomorphisms between the graph and another one
source code
 
decompose(mode=STRONG, maxcompno=None, minelements=1)
Decomposes the graph into subgraphs.
source code
 
degree(vertices, mode=ALL, loops=True)
Returns some vertex degrees from the graph.
source code
 
delete_edges(es)
Removes edges from the graph.
source code
 
delete_vertices(vs)
Deletes vertices and all its edges from the graph.
source code
 
density(loops=False)
Calculates the density of the graph.
source code
 
diameter(directed=True, unconn=True, weights=None)
Calculates the diameter of the graph.
source code
 
difference(other)
Subtracts the given graph from the original
source code
 
disjoint_union(graphs)
Creates the disjoint union of two (or more) graphs.
source code
 
diversity(vertices=None, weights=None)
Calculates the structural diversity index of the vertices.
source code
 
dyad_census()
Dyad census, as defined by Holland and Leinhardt
source code
 
eccentricity(vertices=None, mode=ALL)
Calculates the eccentricities of given vertices in a graph.
source code
integer
ecount()
Counts the number of edges.
source code
 
edge_attributes()
Returns: the attribute name list of the graph's edges
source code
 
edge_betweenness(directed=True, cutoff=None, weights=None)
Calculates or estimates the edge betweennesses in a graph.
source code
 
edge_connectivity(source=-1, target=-1, checks=True)
Calculates the edge connectivity of the graph or between some vertices.
source code
 
eigenvector_centrality(directed=True, scale=True, weights=None, return_eigenvalue=False, arpack_options=None)
Calculates the eigenvector centralities of the vertices in a graph.
source code
 
farthest_points(directed=True, unconn=True, weights=None)
Returns two vertex IDs whose distance equals the actual diameter of the graph.
source code
 
feedback_arc_set(weights=None, method="eades")
Calculates an approximately or exactly minimal feedback arc set.
source code
 
get_adjacency(type=GET_ADJACENCY_BOTH, eids=False)
Returns the adjacency matrix of a graph.
source code
 
get_all_shortest_paths(v, to=None, weights=None, mode=OUT)
Calculates all of the shortest paths from/to a given node in a graph.
source code
 
get_diameter(directed=True, unconn=True, weights=None)
Returns a path with the actual diameter of the graph.
source code
 
get_edgelist()
Returns the edge list of a graph.
source code
 
get_eid(v1, v2, directed=True, error=True)
Returns the edge ID of an arbitrary edge between vertices v1 and v2
source code
 
get_eids(pairs=None, path=None, directed=True, error=True)
Returns the edge IDs of some edges between some vertices.
source code
 
get_incidence(types)
Internal function, undocumented.
source code
 
get_isomorphisms_vf2(other=None, color1=None, color2=None, edge_color1=None, edge_color2=None, node_compat_fn=None, edge_compat_fn=None)
Returns all isomorphisms between the graph and another one
source code
 
get_shortest_paths(v, to=None, weights=None, mode=OUT, output="vpath")
Calculates the shortest paths from/to a given node in a graph.
source code
 
get_subisomorphisms_vf2(other, color1=None, color2=None, edge_color1=None, edge_color2=None, node_compat_fn=None, edge_compat_fn=None)
Returns all subisomorphisms between the graph and another one
source code
 
girth(return_shortest_circle=False)
Returns the girth of the graph.
source code
boolean
has_multiple()
Checks whether the graph has multiple edges.
source code
 
hub_score(weights=None, scale=True, arpack_options=None, return_eigenvalue=False)
Calculates Kleinberg's hub score for the vertices of the graph
source code
 
incident(vertex, mode=OUT)
Returns the edges a given vertex is incident on.
source code
 
independence_number()
Returns the independence number of the graph.
source code
 
independent_vertex_sets(min=0, max=0)
Returns some or all independent vertex sets of the graph as a list of tuples.
source code
 
induced_subgraph(vertices, implementation="auto")
Returns a subgraph spanned by the given vertices.
source code
 
intersection(graphs)
Creates the intersection of two (or more) graphs.
source code
 
is_bipartite(return_types=False)
Decides whether the graph is bipartite or not.
source code
 
is_connected(mode=STRONG)
Decides whether the graph is connected.
source code
boolean
is_dag()
Checks whether the graph is a DAG (directed acyclic graph).
source code
boolean
is_directed()
Checks whether the graph is directed.
source code
 
is_loop(edges=None)
Checks whether a specific set of edges contain loop edges
source code
 
is_minimal_separator(vertices)
Decides whether the given vertex set is a minimal separator.
source code
 
is_multiple(edges=None)
Checks whether an edge is a multiple edge.
source code
 
is_mutual(edges=None)
Checks whether an edge has an opposite pair.
source code
 
is_separator(vertices)
Decides whether the removal of the given vertices disconnects the graph.
source code
boolean
is_simple()
Checks whether the graph is simple (no loop or multiple edges).
source code
 
isoclass(vertices)
Returns the isomorphy class of the graph or its subgraph.
source code
 
isomorphic(other)
Checks whether the graph is isomorphic to another graph.
source code
 
isomorphic_bliss(other, return_mapping_12=False, return_mapping_21=False, sh1="fm", sh2="fm")
Checks whether the graph is isomorphic to another graph, using the BLISS isomorphism algorithm.
source code
 
isomorphic_vf2(other=None, color1=None, color2=None, edge_color1=None, edge_color2=None, return_mapping_12=False, return_mapping_21=False, node_compat_fn=None, edge_compat_fn=None, callback=None)
Checks whether the graph is isomorphic to another graph, using the VF2 isomorphism algorithm.
source code
 
knn(vids=None, weights=None)
Calculates the average degree of the neighbors for each vertex, and the same quantity as the function of vertex degree.
source code
 
laplacian(weights=None, normalized=False)
Returns the Laplacian matrix of a graph.
source code
 
largest_cliques()
Returns the largest cliques of the graph as a list of tuples.
source code
 
largest_independent_vertex_sets()
Returns the largest independent vertex sets of the graph as a list of tuples.
source code
 
layout_circle(dim=2)
Places the vertices of the graph uniformly on a circle or a sphere.
source code
 
layout_drl(weights=None, fixed=None, seed=None, options=None, dim=2)
Places the vertices on a 2D plane or in the 3D space ccording to the DrL layout algorithm.
source code
 
layout_fruchterman_reingold(weights=None, maxiter=500, maxdelta=None, area=None, coolexp=1.5, repulserad=None, seed=None, minx=None, maxx=None, miny=None, maxy=None, minz=None, maxz=None, dim=2)
Places the vertices on a 2D plane or in the 3D space according to the Fruchterman-Reingold algorithm.
source code
 
layout_graphopt(niter=500, node_charge=0.001, node_mass=30, spring_length=0, spring_constant=1, max_sa_movement=5, seed=None)
This is a port of the graphopt layout algorithm by Michael Schmuhl.
source code
 
layout_grid(width=0, height=0, dim=2)
Places the vertices of a graph in a 2D or 3D grid.
source code
 
layout_grid_fruchterman_reingold(maxiter=500, maxdelta=None, area=None, coolexp=0.99, repulserad=maxiter*maxdelta, cellsize=None, seed=None)
Places the vertices on a 2D plane according to the Fruchterman-Reingold grid algorithm.
source code
 
layout_kamada_kawai(maxiter=1000, sigma=None, initemp=10, coolexp=0.99, kkconst=None, seed=None, minx=None, maxx=None, miny=None, maxy=None, minz=None, maxz=None, dim=2)
Places the vertices on a plane according to the Kamada-Kawai algorithm.
source code
 
layout_lgl(maxiter=150, maxdelta=-1, area=-1, coolexp=1.5, repulserad=-1, cellsize=-1, root=None)
Places the vertices on a 2D plane according to the Large Graph Layout.
source code
 
layout_mds(dist=None, dim=2, arpack_options=None)
Places the vertices in an Euclidean space with the given number of dimensions using multidimensional scaling.
source code
 
layout_random(dim=2)
Places the vertices of the graph randomly.
source code
 
layout_reingold_tilford(mode="out", root=None, rootlevel=None)
Places the vertices on a 2D plane according to the Reingold-Tilford layout algorithm.
source code
 
layout_reingold_tilford_circular(mode="out", root=None, rootlevel=None)
Circular Reingold-Tilford layout for trees.
source code
 
layout_star(center=0, order=None)
Calculates a star-like layout for the graph.
source code
 
linegraph()
Returns the line graph of the graph.
source code
 
maxdegree(vertices=None, mode=ALL, loops=False)
Returns the maximum degree of a vertex set in the graph.
source code
 
maxflow(source, target, capacity=None)
Returns the maximum flow between the source and target vertices.
source code
 
maxflow_value(source, target, capacity=None)
Returns the value of the maximum flow between the source and target vertices.
source code
 
maximal_cliques(min=0, max=0)
Returns the maximal cliques of the graph as a list of tuples.
source code
 
maximal_independent_vertex_sets()
Returns the maximal independent vertex sets of the graph as a list of tuples.
source code
 
mincut(capacity=None)
Calculates the minimum cut in a graph.
source code
 
mincut_value(source=-1, target=-1, capacity=None)
Returns the minimum cut between the source and target vertices.
source code
 
minimum_size_separators()
Returns a list containing all separator vertex sets of minimum size.
source code
 
modularity(membership, weights=None)
Calculates the modularity of the graph with respect to some vertex types.
source code
 
motifs_randesu(size=3, cut_prob=None, callback=None)
Counts the number of motifs in the graph
source code
 
motifs_randesu_estimate(size=3, cut_prob=None, sample)
Counts the total number of motifs in the graph
source code
 
motifs_randesu_no(size=3, cut_prob=None)
Counts the total number of motifs in the graph
source code
 
neighborhood(vertices=None, order=1, mode=ALL)
For each vertex specified by vertices, returns the vertices reachable from that vertex in at most order steps.
source code
 
neighborhood_size(vertices=None, order=1, mode=ALL)
For each vertex specified by vertices, returns the number of vertices reachable from that vertex in at most order steps.
source code
 
neighbors(vertex, mode=ALL)
Returns adjacent vertices to a given vertex.
source code
 
path_length_hist(directed=True)
Calculates the path length histogram of the graph
source code
 
permute_vertices(permutation)
Permutes the vertices of the graph according to the given permutation and returns the new graph.
source code
 
personalized_pagerank(vertices=None, directed=True, damping=0.85, reset=None, reset_vertices=None, weights=None, arpack_options=None)
Calculates the personalized PageRank values of a graph.
source code
 
predecessors(vertex)
Returns the predecessors of a given vertex.
source code
 
radius(mode=OUT)
Calculates the radius of the graph.
source code
 
reciprocity(ignore_loops=True, mode="default")
Reciprocity defines the proportion of mutual connections in a directed graph.
source code
 
rewire(n=1000, mode="simple")
Randomly rewires the graph while preserving the degree distribution.
source code
 
rewire_edges(prob, loops=False, multiple=False)
Rewires the edges of a graph with constant probability.
source code
 
shortest_paths(source=None, target=None, weights=None, mode=OUT)
Calculates shortest path lengths for given vertices in a graph.
source code
 
similarity_dice(vertices=None, pairs=None, mode=IGRAPH_ALL, loops=True)
Dice similarity coefficient of vertices.
source code
 
similarity_inverse_log_weighted(vertices=None, mode=IGRAPH_ALL)
Inverse log-weighted similarity coefficient of vertices.
source code
 
similarity_jaccard(vertices=None, pairs=None, mode=IGRAPH_ALL, loops=True)
Jaccard similarity coefficient of vertices.
source code
 
simplify(multiple=True, loops=True, combine_edges=None)
Simplifies a graph by removing self-loops and/or multiple edges.
source code
 
strength(vertices, mode=ALL, loops=True, weights=None)
Returns the strength (weighted degree) of some vertices from the graph
source code
 
subcomponent(v, mode=ALL)
Determines the indices of vertices which are in the same component as a given vertex.
source code
 
subgraph_edges(edges, delete_vertices=True)
Returns a subgraph spanned by the given edges.
source code
 
subisomorphic_vf2(other, color1=None, color2=None, edge_color1=None, edge_color2=None, return_mapping_12=False, return_mapping_21=False, callback=None, node_compat_fn=None, edge_compat_fn=None)
Checks whether a subgraph of the graph is isomorphic to another graph.
source code
 
successors(vertex)
Returns the successors of a given vertex.
source code
 
to_directed(mutual=True)
Converts an undirected graph to directed.
source code
 
to_undirected(mode="collapse", combine_edges=None)
Converts a directed graph to undirected.
source code
 
topological_sorting(mode=OUT)
Calculates a possible topological sorting of the graph.
source code
 
transitivity_avglocal_undirected(mode="nan")
Calculates the average of the vertex transitivities of the graph.
source code
 
transitivity_local_undirected(vertices=None, mode="nan", weights=None)
Calculates the local transitivity (clustering coefficient) of the given vertices in the graph.
source code
 
transitivity_undirected(mode="nan")
Calculates the global transitivity (clustering coefficient) of the graph.
source code
 
triad_census()
Triad census, as defined by Davis and Leinhardt
source code
 
unfold_tree(sources=None, mode=OUT)
Unfolds the graph using a BFS to a tree by duplicating vertices as necessary.
source code
 
union(graphs)
Creates the union of two (or more) graphs.
source code
integer
vcount()
Counts the number of vertices.
source code
 
vertex_attributes()
Returns: the attribute name list of the graph's vertices
source code
 
vertex_connectivity(source=-1, target=-1, checks=True, neighbors="error")
Calculates the vertex connectivity of the graph or between some vertices.
source code
 
write_dimacs(f, source, target, capacity=None)
Writes the graph in DIMACS format to the given file.
source code
 
write_dot(f)
Writes the graph in DOT format to the given file.
source code
 
write_edgelist(f)
Writes the edge list of a graph to a file.
source code
 
write_gml(f, creator=None, ids=None)
Writes the graph in GML format to the given file.
source code
 
write_graphml(f)
Writes the graph to a GraphML file.
source code
 
write_leda(f, names="name", weights="weights")
Writes the graph to a file in LEDA native format.
source code
 
write_lgl(f, names="name", weights="weights", isolates=True)
Writes the edge list of a graph to a file in .lgl format.
source code
 
write_ncol(f, names="name", weights="weights")
Writes the edge list of a graph to a file in .ncol format.
source code
 
write_pajek(f)
Writes the graph in Pajek format to the given file.
source code

Inherited from object: __delattr__, __format__, __getattribute__, __hash__, __reduce__, __reduce_ex__, __repr__, __setattr__, __sizeof__, __subclasshook__

Properties [hide private]

Inherited from object: __class__

Method Details [hide private]

Adjacency(matrix, mode=ADJ_DIRECTED)

source code 

Generates a graph from its adjacency matrix.

Parameters:
  • matrix - the adjacency matrix
  • mode - the mode to be used. Possible values are:
    • ADJ_DIRECTED - the graph will be directed and a matrix element gives the number of edges between two vertex.
    • ADJ_UNDIRECTED - alias to ADJ_MAX for convenience.
    • ADJ_MAX - undirected graph will be created and the number of edges between vertex i and j is max(A(i,j), A(j,i))
    • ADJ_MIN - like ADJ_MAX, but with min(A(i,j), A(j,i))
    • ADJ_PLUS - like ADJ_MAX, but with A(i,j) + A(j,i)
    • ADJ_UPPER - undirected graph with the upper right triangle of the matrix (including the diagonal)
    • ADJ_LOWER - undirected graph with the lower left triangle of the matrix (including the diagonal)

    These values can also be given as strings without the ADJ prefix.

Asymmetric_Preference(n, type_dist_matrix, pref_matrix, attribute=None, loops=False)

source code 

Generates a graph based on asymmetric vertex types and connection probabilities.

This is the asymmetric variant of Graph.Preference. A given number of vertices are generated. Every vertex is assigned to an "incoming" and an "outgoing" vertex type according to the given joint type probabilities. Finally, every vertex pair is evaluated and a directed edge is created between them with a probability depending on the "outgoing" type of the source vertex and the "incoming" type of the target vertex.

Parameters:
  • n - the number of vertices in the graph
  • type_dist_matrix - matrix giving the joint distribution of vertex types
  • pref_matrix - matrix giving the connection probabilities for different vertex types.
  • attribute - the vertex attribute name used to store the vertex types. If None, vertex types are not stored.
  • loops - whether loop edges are allowed.

Atlas(idx)

source code 

Generates a graph from the Graph Atlas.

Parameters:
  • idx - The index of the graph to be generated. Indices start from zero, graphs are listed:
    1. in increasing order of number of vertices;
    2. for a fixed number of vertices, in increasing order of the number of edges;
    3. for fixed numbers of vertices and edges, in increasing order of the degree sequence, for example 111223 < 112222;
    4. for fixed degree sequence, in increasing number of automorphisms.

Reference: An Atlas of Graphs by Ronald C. Read and Robin J. Wilson, Oxford University Press, 1998.

Barabasi(n, m, outpref=False, directed=False, power=1, zero_appeal=1, implementation="psumtree", start_from=None)

source code 

Generates a graph based on the Barabasi-Albert model.

Parameters:
  • n - the number of vertices
  • m - either the number of outgoing edges generated for each vertex or a list containing the number of outgoing edges for each vertex explicitly.
  • outpref - True if the out-degree of a given vertex should also increase its citation probability (as well as its in-degree), but it defaults to False.
  • directed - True if the generated graph should be directed (default: False).
  • power - the power constant of the nonlinear model. It can be omitted, and in this case the usual linear model will be used.
  • zero_appeal - the attractivity of vertices with degree zero.
  • implementation - the algorithm to use to generate the network. Possible values are:
    • "bag": the algorithm that was the default in igraph before 0.6. It works by putting the ids of the vertices into a bag (multiset) exactly as many times as their in-degree, plus once more. The required number of cited vertices are then drawn from the bag with replacement. It works only for power=1 and zero_appeal=1.
    • "psumtree": this algorithm uses a partial prefix-sum tree to generate the graph. It does not generate multiple edges and it works for any values of power and zero_appeal.
    • "psumtree_multiple": similar to "psumtree", but it will generate multiple edges as well. igraph before 0.6 used this algorithm for powers other than 1.
  • start_from - if given and not None, this must be another Graph object. igraph will use this graph as a starting point for the preferential attachment model.

Reference: Barabasi, A-L and Albert, R. 1999. Emergence of scaling in random networks. Science, 286 509-512.

De_Bruijn(m, n)

source code 

Generates a de Bruijn graph with parameters (m, n)

A de Bruijn graph represents relationships between strings. An alphabet of m letters are used and strings of length n are considered. A vertex corresponds to every possible string and there is a directed edge from vertex v to vertex w if the string of v can be transformed into the string of w by removing its first letter and appending a letter to it.

Please note that the graph will have m^n vertices and even more edges, so probably you don't want to supply too big numbers for m and n.

Parameters:
  • m - the size of the alphabet
  • n - the length of the strings

Degree_Sequence(out, in=None, method="simple")

source code 

Generates a graph with a given degree sequence.

Parameters:
  • out - the out-degree sequence for a directed graph. If the in-degree sequence is omitted, the generated graph will be undirected, so this will be the in-degree sequence as well
  • in - the in-degree sequence for a directed graph. If omitted, the generated graph will be undirected.
  • method - the generation method to be used. One of the following:
    • "simple" -- simple generator that sometimes generates loop edges and multiple edges. The generated graph is not guaranteed to be connected.
    • "no_multiple" -- similar to "simple" but avoids the generation of multiple and loop edges at the expense of increased time complexity. The method will re-start the generation every time it gets stuck in a configuration where it is not possible to insert any more edges without creating loops or multiple edges, and there is no upper bound on the number of iterations, but it will succeed eventually if the input degree sequence is graphical and throw an exception if the input degree sequence is not graphical.
    • "vl" -- a more sophisticated generator that can sample undirected, connected simple graphs uniformly. It uses Monte-Carlo methods to randomize the graphs. This generator should be favoured if undirected and connected graphs are to be generated and execution time is not a concern. igraph uses the original implementation of Fabien Viger; see the following URL and the paper cited on it for the details of the algorithm: http://www-rp.lip6.fr/~latapy/FV/generation.html.

Erdos_Renyi(n, p, m, directed=False, loops=False)

source code 

Generates a graph based on the Erdos-Renyi model.

Parameters:
  • n - the number of vertices.
  • p - the probability of edges. If given, m must be missing.
  • m - the number of edges. If given, p must be missing.
  • directed - whether to generate a directed graph.
  • loops - whether self-loops are allowed.

Establishment(n, k, type_dist, pref_matrix, directed=False)

source code 

Generates a graph based on a simple growing model with vertex types.

A single vertex is added at each time step. This new vertex tries to connect to k vertices in the graph. The probability that such a connection is realized depends on the types of the vertices involved.

Parameters:
  • n - the number of vertices in the graph
  • k - the number of connections tried in each step
  • type_dist - list giving the distribution of vertex types
  • pref_matrix - matrix (list of lists) giving the connection probabilities for different vertex types
  • directed - whether to generate a directed graph.

Famous(name)

source code 

Generates a famous graph based on its name.

Several famous graphs are known to igraph including (but not limited to) the Chvatal graph, the Petersen graph or the Tutte graph. This method generates one of them based on its name (case insensitive). See the documentation of the C interface of igraph for the names available: http://igraph.sourceforge.net/doc/html/igraph_famous.html.

Parameters:
  • name - the name of the graph to be generated.

Forest_Fire(n, fw_prob, bw_factor=0.0, ambs=1, directed=False)

source code 

Generates a graph based on the forest fire model

The forest fire model is a growin graph model. In every time step, a new vertex is added to the graph. The new vertex chooses an ambassador (or more than one if ambs>1) and starts a simulated forest fire at its ambassador(s). The fire spreads through the edges. The spreading probability along an edge is given by fw_prob. The fire may also spread backwards on an edge by probability fw_prob * bw_factor. When the fire ended, the newly added vertex connects to the vertices ``burned'' in the previous fire.

Parameters:
  • n - the number of vertices in the graph
  • fw_prob - forward burning probability
  • bw_factor - ratio of backward and forward burning probability
  • ambs - number of ambassadors chosen in each step
  • directed - whether the graph will be directed

Full(n, directed=False, loops=False)

source code 

Generates a full graph (directed or undirected, with or without loops).

Parameters:
  • n - the number of vertices.
  • directed - whether to generate a directed graph.
  • loops - whether self-loops are allowed.

Full_Citation(n, directed=False)

source code 

Generates a full citation graph

A full citation graph is a graph where the vertices are indexed from 0 to n-1 and vertex i has a directed edge towards all vertices with an index less than i.

Parameters:
  • n - the number of vertices.
  • directed - whether to generate a directed graph.

Growing_Random(n, m, directed=False, citation=False)

source code 

Generates a growing random graph.

Parameters:
  • n - The number of vertices in the graph
  • m - The number of edges to add in each step (after adding a new vertex)
  • directed - whether the graph should be directed.
  • citation - whether the new edges should originate from the most recently added vertex.

Isoclass(n, class, directed=False)

source code 

Generates a graph with a given isomorphy class.

Parameters:
  • n - the number of vertices in the graph (3 or 4)
  • class - the isomorphy class
  • directed - whether the graph should be directed.

K_Regular(n, k, directed=False, multiple=False)

source code 

Generates a k-regular random graph

A k-regular random graph is a random graph where each vertex has degree k. If the graph is directed, both the in-degree and the out-degree of each vertex will be k.

Parameters:
  • n - The number of vertices in the graph
  • k - The degree of each vertex if the graph is undirected, or the in-degree and out-degree of each vertex if the graph is directed
  • directed - whether the graph should be directed.
  • multiple - whether it is allowed to create multiple edges.

Kautz(m, n)

source code 

Generates a Kautz graph with parameters (m, n)

A Kautz graph is a labeled graph, vertices are labeled by strings of length n+1 above an alphabet with m+1 letters, with the restriction that every two consecutive letters in the string must be different. There is a directed edge from a vertex v to another vertex w if it is possible to transform the string of v into the string of w by removing the first letter and appending a letter to it.

Parameters:
  • m - the size of the alphabet minus one
  • n - the length of the strings minus one

LCF(n, shifts, repeats)

source code 

Generates a graph from LCF notation.

LCF is short for Lederberg-Coxeter-Frucht, it is a concise notation for 3-regular Hamiltonian graphs. It consists of three parameters, the number of vertices in the graph, a list of shifts giving additional edges to a cycle backbone and another integer giving how many times the shifts should be performed. See http://mathworld.wolfram.com/LCFNotation.html for details.

Parameters:
  • n - the number of vertices
  • shifts - the shifts in a list or tuple
  • repeats - the number of repeats

Lattice(dim, nei=1, directed=False, mutual=True, circular=True)

source code 

Generates a regular lattice.

Parameters:
  • dim - list with the dimensions of the lattice
  • nei - value giving the distance (number of steps) within which two vertices will be connected.
  • directed - whether to create a directed graph.
  • mutual - whether to create all connections as mutual in case of a directed graph.
  • circular - whether the generated lattice is periodic.

Preference(n, type_dist, pref_matrix, attribute=None, directed=False, loops=False)

source code 

Generates a graph based on vertex types and connection probabilities.

This is practically the nongrowing variant of Graph.Establishment. A given number of vertices are generated. Every vertex is assigned to a vertex type according to the given type probabilities. Finally, every vertex pair is evaluated and an edge is created between them with a probability depending on the types of the vertices involved.

Parameters:
  • n - the number of vertices in the graph
  • type_dist - list giving the distribution of vertex types
  • pref_matrix - matrix giving the connection probabilities for different vertex types.
  • attribute - the vertex attribute name used to store the vertex types. If None, vertex types are not stored.
  • directed - whether to generate a directed graph.
  • loops - whether loop edges are allowed.

Read_DIMACS(f, directed=False)

source code 

Reads a graph from a file conforming to the DIMACS minimum-cost flow file format.

For the exact description of the format, see http://lpsolve.sourceforge.net/5.5/DIMACS.htm

Restrictions compared to the official description of the format:

  • igraph's DIMACS reader requires only three fields in an arc definition, describing the edge's source and target node and its capacity.
  • Source vertices are identified by 's' in the FLOW field, target vertices are identified by 't'.
  • Node indices start from 1. Only a single source and target node is allowed.
Parameters:
  • f - the name of the file or a Python file handle
  • directed - whether the generated graph should be directed.
Returns:
the generated graph, the source and the target of the flow and the edge capacities in a tuple

Read_DL(f, directed=True)

source code 

Reads an UCINET DL file and creates a graph based on it.

Parameters:
  • f - the name of the file or a Python file handle
  • directed - whether the generated graph should be directed.

Read_Edgelist(f, directed=True)

source code 

Reads an edge list from a file and creates a graph based on it.

Please note that the vertex indices are zero-based.

Parameters:
  • f - the name of the file or a Python file handle
  • directed - whether the generated graph should be directed.

Read_GML(f)

source code 

Reads a GML file and creates a graph based on it.

Parameters:
  • f - the name of the file or a Python file handle

Read_GraphDB(f, directed=False)

source code 

Reads a GraphDB format file and creates a graph based on it.

GraphDB is a binary format, used in the graph database for isomorphism testing (see http://amalfi.dis.unina.it/graph/).

Parameters:
  • f - the name of the file or a Python file handle
  • directed - whether the generated graph should be directed.

Read_GraphML(f, directed=True, index=0)

source code 

Reads a GraphML format file and creates a graph based on it.

Parameters:
  • f - the name of the file or a Python file handle
  • index - if the GraphML file contains multiple graphs, specifies the one that should be loaded. Graph indices start from zero, so if you want to load the first graph, specify 0 here.

Read_Lgl(f, names=True, weights="if_present", directed=True)

source code 

Reads an .lgl file used by LGL.

It is also useful for creating graphs from "named" (and optionally weighted) edge lists.

This format is used by the Large Graph Layout program. See the documentation of LGL regarding the exact format description.

LGL originally cannot deal with graphs containing multiple or loop edges, but this condition is not checked here, as igraph is happy with these.

Parameters:
  • f - the name of the file or a Python file handle
  • names - If True, the vertex names are added as a vertex attribute called 'name'.
  • weights - If True, the edge weights are added as an edge attribute called 'weight', even if there are no weights in the file. If False, the edge weights are never added, even if they are present. "auto" or "if_present" means that weights are added if there is at least one weighted edge in the input file, but they are not added otherwise.
  • directed - whether the graph being created should be directed

Read_Ncol(f, names=True, weights="if_present", directed=True)

source code 

Reads an .ncol file used by LGL.

It is also useful for creating graphs from "named" (and optionally weighted) edge lists.

This format is used by the Large Graph Layout program. See the documentation of LGL regarding the exact format description.

LGL originally cannot deal with graphs containing multiple or loop edges, but this condition is not checked here, as igraph is happy with these.

Parameters:
  • f - the name of the file or a Python file handle
  • names - If True, the vertex names are added as a vertex attribute called 'name'.
  • weights - If True, the edge weights are added as an edge attribute called 'weight', even if there are no weights in the file. If False, the edge weights are never added, even if they are present. "auto" or "if_present" means that weights are added if there is at least one weighted edge in the input file, but they are not added otherwise.
  • directed - whether the graph being created should be directed

Read_Pajek(f)

source code 

Reads a Pajek format file and creates a graph based on it.

Parameters:
  • f - the name of the file or a Python file handle

Recent_Degree(n, m, window, outpref=False, directed=False, power=1)

source code 

Generates a graph based on a stochastic model where the probability of an edge gaining a new node is proportional to the edges gained in a given time window.

Parameters:
  • n - the number of vertices
  • m - either the number of outgoing edges generated for each vertex or a list containing the number of outgoing edges for each vertex explicitly.
  • window - size of the window in time steps
  • outpref - True if the out-degree of a given vertex should also increase its citation probability (as well as its in-degree), but it defaults to False.
  • directed - True if the generated graph should be directed (default: False).
  • power - the power constant of the nonlinear model. It can be omitted, and in this case the usual linear model will be used.

Ring(n, directed=False, mutual=False, circular=True)

source code 

Generates a ring graph.

Parameters:
  • n - the number of vertices in the ring
  • directed - whether to create a directed ring.
  • mutual - whether to create mutual edges in a directed ring.
  • circular - whether to create a closed ring.

Star(n, mode="undirected", center=0)

source code 

Generates a star graph.

Parameters:
  • n - the number of vertices in the graph
  • mode - Gives the type of the star graph to create. Should be either "in", "out", "mutual" or "undirected"
  • center - Vertex ID for the central vertex in the star.

Static_Fitness(m, fitness_out, fitness_in=None, loops=False, multiple=False)

source code 

Generates a non-growing graph with edge probabilities proportional to node fitnesses.

The algorithm randomly selects vertex pairs and connects them until the given number of edges are created. Each vertex is selected with a probability proportional to its fitness; for directed graphs, a vertex is selected as a source proportional to its out-fitness and as a target proportional to its in-fitness.

Parameters:
  • m - the number of edges in the graph
  • fitness_out - a numeric vector with non-negative entries, one for each vertex. These values represent the fitness scores (out-fitness scores for directed graphs). fitness is an alias of this keyword argument.
  • fitness_in - a numeric vector with non-negative entries, one for each vertex. These values represent the in-fitness scores for directed graphs. For undirected graphs, this argument must be None.
  • loops - whether loop edges are allowed.
  • multiple - whether multiple edges are allowed.
Returns:
a directed or undirected graph with the prescribed power-law degree distributions.

Static_Power_Law(n, m, exponent_out, exponent_in=-1, loops=False, multiple=False, finite_size_correction=True)

source code 

Generates a non-growing graph with prescribed power-law degree distributions.

Parameters:
  • n - the number of vertices in the graph
  • m - the number of edges in the graph
  • exponent_out - the exponent of the out-degree distribution, which must be between 2 and infinity (inclusive). When exponent_in is not given or negative, the graph will be undirected and this parameter specifies the degree distribution. exponent is an alias to this keyword argument.
  • exponent_in - the exponent of the in-degree distribution, which must be between 2 and infinity (inclusive) It can also be negative, in which case an undirected graph will be generated.
  • loops - whether loop edges are allowed.
  • multiple - whether multiple edges are allowed.
  • finite_size_correction - whether to apply a finite-size correction to the generated fitness values for exponents less than 3. See the paper of Cho et al for more details.
Returns:
a directed or undirected graph with the prescribed power-law degree distributions.
Reference:
  • Goh K-I, Kahng B, Kim D: Universal behaviour of load distribution in scale-free networks. Phys Rev Lett 87(27):278701, 2001.
  • Cho YS, Kim JS, Park J, Kahng B, Kim D: Percolation transitions in scale-free networks under the Achlioptas process. Phys Rev Lett 103:135702, 2009.

Tree(n, children, type=TREE_UNDIRECTED)

source code 

Generates a tree in which almost all vertices have the same number of children.

Parameters:
  • n - the number of vertices in the graph
  • children - the number of children of a vertex in the graph
  • type - determines whether the tree should be directed, and if this is the case, also its orientation. Must be one of TREE_IN, TREE_OUT and TREE_UNDIRECTED.

Watts_Strogatz(dim, size, nei, p, loops=False, multiple=False)

source code 
Parameters:
  • dim - the dimension of the lattice
  • size - the size of the lattice along all dimensions
  • nei - value giving the distance (number of steps) within which two vertices will be connected.
  • p - rewiring probability
  • loops - specifies whether loop edges are allowed
  • multiple - specifies whether multiple edges are allowed

See Also: Lattice(), rewire(), rewire_edges() if more flexibility is needed

Reference: Duncan J Watts and Steven H Strogatz: Collective dynamics of small world networks, Nature 393, 440-442, 1998

Weighted_Adjacency(matrix, mode=ADJ_DIRECTED, attr="weight", loops=True)

source code 

Generates a graph from its adjacency matrix.

Parameters:
  • matrix - the adjacency matrix
  • mode - the mode to be used. Possible values are:
    • ADJ_DIRECTED - the graph will be directed and a matrix element gives the number of edges between two vertex.
    • ADJ_UNDIRECTED - alias to ADJ_MAX for convenience.
    • ADJ_MAX - undirected graph will be created and the number of edges between vertex i and j is max(A(i,j), A(j,i))
    • ADJ_MIN - like ADJ_MAX, but with min(A(i,j), A(j,i))
    • ADJ_PLUS - like ADJ_MAX, but with A(i,j) + A(j,i)
    • ADJ_UPPER - undirected graph with the upper right triangle of the matrix (including the diagonal)
    • ADJ_LOWER - undirected graph with the lower left triangle of the matrix (including the diagonal)

    These values can also be given as strings without the ADJ prefix.

  • attr - the name of the edge attribute that stores the edge weights.
  • loops - whether to include loop edges. When False, the diagonal of the adjacency matrix will be ignored.

__graph_as_cobject()

source code 

Returns the igraph graph encapsulated by the Python object as a PyCObject

.A PyCObject is practically a regular C pointer, wrapped in a Python object. This function should not be used directly by igraph users, it is useful only in the case when the underlying igraph object must be passed to other C code through Python.

__init__(...)
(Constructor)

source code 

x.__init__(...) initializes x; see help(type(x)) for signature

Overrides: object.__init__

__new__(T, S, ...)

source code 
Returns: a new object with type S, a subtype of T
Overrides: object.__new__

__register_destructor(destructor)

source code 

Registers a destructor to be called when the object is freed by Python. This function should not be used directly by igraph users.

__str__(x)
(Informal representation operator)

source code 

str(x)

Overrides: object.__str__

add_edges(es)

source code 

Adds edges to the graph.

Parameters:
  • es - the list of edges to be added. Every edge is represented with a tuple, containing the vertex IDs of the two endpoints. Vertices are enumerated from zero.

add_vertices(n)

source code 

Adds vertices to the graph.

Parameters:
  • n - the number of vertices to be added

all_minimal_st_separators()

source code 

Returns a list containing all the minimal s-t separators of a graph.

A minimal separator is a set of vertices whose removal disconnects the graph, while the removal of any subset of the set keeps the graph connected.

Returns:
a list where each item lists the vertex indices of a given minimal s-t separator.

Reference: Anne Berry, Jean-Paul Bordat and Olivier Cogis: Generating all the minimal separators of a graph. In: Peter Widmayer, Gabriele Neyer and Stephan Eidenbenz (eds.): Graph-theoretic concepts in computer science, 1665, 167--172, 1999. Springer.

all_st_cuts(source, target)

source code 

Returns all the cuts between the source and target vertices in a directed graph.

This function lists all edge-cuts between a source and a target vertex. Every cut is listed exactly once.

Parameters:
  • source - the source vertex ID
  • target - the target vertex ID
Returns:
a tuple where the first element is a list of lists of edge IDs representing a cut and the second element is a list of lists of vertex IDs representing the sets of vertices that were separated by the cuts.

Attention: this function has a more convenient interface in class Graph which wraps the result in a list of Cut objects. It is advised to use that.

all_st_mincuts(source, target)

source code 

Returns all minimum cuts between the source and target vertices in a directed graph.

Parameters:
  • source - the source vertex ID
  • target - the target vertex ID

Attention: this function has a more convenient interface in class Graph which wraps the result in a list of Cut objects. It is advised to use that.

are_connected(v1, v2)

source code 

Decides whether two given vertices are directly connected.

Parameters:
  • v1 - the first vertex
  • v2 - the second vertex
Returns:
True if there exists an edge from v1 to v2, False otherwise.

articulation_points()

source code 

Returns the list of articulation points in the graph.

A vertex is an articulation point if its removal increases the number of connected components in the graph.

assortativity(types1, types2=None, directed=True)

source code 

Returns the assortativity of the graph based on numeric properties of the vertices.

This coefficient is basically the correlation between the actual connectivity patterns of the vertices and the pattern expected from the disribution of the vertex types.

See equation (21) in Newman MEJ: Mixing patterns in networks, Phys Rev E 67:026126 (2003) for the proper definition. The actual calculation is performed using equation (26) in the same paper for directed graphs, and equation (4) in Newman MEJ: Assortative mixing in networks, Phys Rev Lett 89:208701 (2002) for undirected graphs.

Parameters:
  • types1 - vertex types in a list or the name of a vertex attribute holding vertex types. Types are ideally denoted by numeric values.
  • types2 - in directed assortativity calculations, each vertex can have an out-type and an in-type. In this case, types1 contains the out-types and this parameter contains the in-types in a list or the name of a vertex attribute. If None, it is assumed to be equal to types1.
  • directed - whether to consider edge directions or not.
Returns:
the assortativity coefficient
Reference:
  • Newman MEJ: Mixing patterns in networks, Phys Rev E 67:026126, 2003.
  • Newman MEJ: Assortative mixing in networks, Phys Rev Lett 89:208701,

See Also: assortativity_degree() when the types are the vertex degrees

assortativity_degree(directed=True)

source code 

Returns the assortativity of a graph based on vertex degrees.

See assortativity() for the details. assortativity_degree() simply calls assortativity() with the vertex degrees as types.

Parameters:
  • directed - whether to consider edge directions for directed graphs or not. This argument is ignored for undirected graphs.
Returns:
the assortativity coefficient

See Also: assortativity()

assortativity_nominal(types, directed=True)

source code 

Returns the assortativity of the graph based on vertex categories.

Assuming that the vertices belong to different categories, this function calculates the assortativity coefficient, which specifies the extent to which the connections stay within categories. The assortativity coefficient is one if all the connections stay within categories and minus one if all the connections join vertices of different categories. For a randomly connected network, it is asymptotically zero.

See equation (2) in Newman MEJ: Mixing patterns in networks, Phys Rev E 67:026126 (2003) for the proper definition.

Parameters:
  • types - vertex types in a list or the name of a vertex attribute holding vertex types. Types should be denoted by numeric values.
  • directed - whether to consider edge directions or not.
Returns:
the assortativity coefficient

Reference: Newman MEJ: Mixing patterns in networks, Phys Rev E 67:026126, 2003.

attributes()

source code 
Returns:
the attribute name list of the graph

authority_score(weights=None, scale=True, arpack_options=None, return_eigenvalue=False)

source code 

Calculates Kleinberg's authority score for the vertices of the graph

Parameters:
  • weights - edge weights to be used. Can be a sequence or iterable or even an edge attribute name.
  • scale - whether to normalize the scores so that the largest one is 1.
  • arpack_options - an ARPACKOptions object used to fine-tune the ARPACK eigenvector calculation. If omitted, the module-level variable called arpack_options is used.
  • return_eigenvalue - whether to return the largest eigenvalue
Returns:
the authority scores in a list and optionally the largest eigenvalue as a second member of a tuple

See Also: hub_score()

average_path_length(directed=True, unconn=True)

source code 

Calculates the average path length in a graph.

Parameters:
  • directed - whether to consider directed paths in case of a directed graph. Ignored for undirected graphs.
  • unconn - what to do when the graph is unconnected. If True, the average of the geodesic lengths in the components is calculated. Otherwise for all unconnected vertex pairs, a path length equal to the number of vertices is used.
Returns:
the average path length in the graph

betweenness(vertices=None, directed=True, cutoff=None, weights=None, nobigint=True)

source code 

Calculates or estimates the betweenness of vertices in a graph.

Keyword arguments:

Parameters:
  • vertices - the vertices for which the betweennesses must be returned. If None, assumes all of the vertices in the graph.
  • directed - whether to consider directed paths.
  • cutoff - if it is an integer, only paths less than or equal to this length are considered, effectively resulting in an estimation of the betweenness for the given vertices. If None, the exact betweenness is returned.
  • weights - edge weights to be used. Can be a sequence or iterable or even an edge attribute name.
  • nobigint - if True, igraph uses the longest available integer type on the current platform to count shortest paths. For some large networks that have a specific structure, the counters may overflow. To prevent this, use nobigint=False, which forces igraph to use arbitrary precision integers at the expense of increased computation time.
Returns:
the (possibly estimated) betweenness of the given vertices in a list

bfs(vid, mode=OUT)

source code 

Conducts a breadth first search (BFS) on the graph.

Parameters:
  • vid - the root vertex ID
  • mode - either IN or OUT or ALL, ignored for undirected graphs.
Returns:
a tuple with the following items:
  • The vertex IDs visited (in order)
  • The start indices of the layers in the vertex list
  • The parent of every vertex in the BFS

bfsiter(vid, mode=OUT, advanced=False)

source code 

Constructs a breadth first search (BFS) iterator of the graph.

Parameters:
  • vid - the root vertex ID
  • mode - either IN or OUT or ALL.
  • advanced - if False, the iterator returns the next vertex in BFS order in every step. If True, the iterator returns the distance of the vertex from the root and the parent of the vertex in the BFS tree as well.
Returns:
the BFS iterator as an igraph.BFSIter object.

bibcoupling(vertices=None)

source code 

Calculates bibliographic coupling scores for given vertices in a graph.

Parameters:
  • vertices - the vertices to be analysed. If None, all vertices will be considered.
Returns:
bibliographic coupling scores for all given vertices in a matrix.

biconnected_components(return_articulation_points=True)

source code 

Calculates the biconnected components of the graph.

Parameters:
  • return_articulation_points - whether to return the articulation points as well
Returns:
a list of lists containing edge indices making up spanning trees of the biconnected components (one spanning tree for each component) and optionally the list of articulation points

bipartite_projection(types, multiplicity=True, probe1=-1)

source code 

Internal function, undocumented.

See Also: Graph.bipartite_projection()

bipartite_projection_size(types)

source code 

Internal function, undocumented.

See Also: Graph.bipartite_projection_size()

clique_number()

source code 

Returns the clique number of the graph.

The clique number of the graph is the size of the largest clique.

See Also: largest_cliques() for the largest cliques.

cliques(min=0, max=0)

source code 

Returns some or all cliques of the graph as a list of tuples.

A clique is a complete subgraph -- a set of vertices where an edge is present between any two of them (excluding loops)

Parameters:
  • min - the minimum size of cliques to be returned. If zero or negative, no lower bound will be used.
  • max - the maximum size of cliques to be returned. If zero or negative, no upper bound will be used.

closeness(vertices=None, mode=ALL, cutoff=None, weights=None)

source code 

Calculates the closeness centralities of given vertices in a graph.

The closeness centerality of a vertex measures how easily other vertices can be reached from it (or the other way: how easily it can be reached from the other vertices). It is defined as the number of the number of vertices minus one divided by the sum of the lengths of all geodesics from/to the given vertex.

If the graph is not connected, and there is no path between two vertices, the number of vertices is used instead the length of the geodesic. This is always longer than the longest possible geodesic.

Parameters:
  • vertices - the vertices for which the closenesses must be returned. If None, uses all of the vertices in the graph.
  • mode - must be one of IN, OUT and ALL. IN means that the length of the incoming paths, OUT means that the length of the outgoing paths must be calculated. ALL means that both of them must be calculated.
  • cutoff - if it is an integer, only paths less than or equal to this length are considered, effectively resulting in an estimation of the closeness for the given vertices (which is always an underestimation of the real closeness, since some vertex pairs will appear as disconnected even though they are connected).. If None, the exact closeness is returned.
  • weights - edge weights to be used. Can be a sequence or iterable or even an edge attribute name.
Returns:
the calculated closenesses in a list

clusters(mode=STRONG)

source code 

Calculates the (strong or weak) clusters for a given graph.

Parameters:
  • mode - must be either STRONG or WEAK, depending on the clusters being sought. Optional, defaults to STRONG.
Returns:
the component index for every node in the graph.

Attention: this function has a more convenient interface in class Graph which wraps the result in a VertexClustering object. It is advised to use that.

cocitation(vertices=None)

source code 

Calculates cocitation scores for given vertices in a graph.

Parameters:
  • vertices - the vertices to be analysed. If None, all vertices will be considered.
Returns:
cocitation scores for all given vertices in a matrix.

cohesive_blocks()

source code 

Calculates the cohesive block structure of the graph.

Attention: this function has a more convenient interface in class Graph which wraps the result in a CohesiveBlocks object. It is advised to use that.

community_edge_betweenness(directed=True, weights=None)

source code 

Community structure detection based on the betweenness of the edges in the network. This algorithm was invented by M Girvan and MEJ Newman, see: M Girvan and MEJ Newman: Community structure in social and biological networks, Proc. Nat. Acad. Sci. USA 99, 7821-7826 (2002).

The idea is that the betweenness of the edges connecting two communities is typically high. So we gradually remove the edge with the highest betweenness from the network and recalculate edge betweenness after every removal, as long as all edges are removed.

Parameters:
  • directed - whether to take into account the directedness of the edges when we calculate the betweenness values.
  • weights - name of an edge attribute or a list containing edge weights.
Returns:
a tuple with the merge matrix that describes the dendrogram and the modularity scores before each merge. The modularity scores use the weights if the original graph was weighted.

Attention: this function is wrapped in a more convenient syntax in the derived class Graph. It is advised to use that instead of this version.

community_fastgreedy(weights=None)

source code 

Finds the community structure of the graph according to the algorithm of Clauset et al based on the greedy optimization of modularity.

This is a bottom-up algorithm: initially every vertex belongs to a separate community, and communities are merged one by one. In every step, the two communities being merged are the ones which result in the maximal increase in modularity.

Parameters:
  • weights - name of an edge attribute or a list containing edge weights
Returns:
a tuple with the following elements:
  1. The list of merges
  2. The modularity scores before each merge

Attention: this function is wrapped in a more convenient syntax in the derived class Graph. It is advised to use that instead of this version.

Reference: A. Clauset, M. E. J. Newman and C. Moore: Finding community structure in very large networks. Phys Rev E 70, 066111 (2004).

See Also: modularity()

community_infomap(edge_weights=None, vertex_weights=None, trials=10)

source code 

Finds the community structure of the network according to the Infomap method of Martin Rosvall and Carl T. Bergstrom.

See http://www.mapequation.org for a visualization of the algorithm or one of the references provided below.

Parameters:
  • edge_weights - name of an edge attribute or a list containing edge weights.
  • vertex_weights - name of an vertex attribute or a list containing vertex weights.
  • trials - the number of attempts to partition the network.
Returns:
the calculated membership vector and the corresponding codelength in a tuple.
Reference:

community_label_propagation(weights=None, initial=None, fixed=None)

source code 

Finds the community structure of the graph according to the label propagation method of Raghavan et al.

Initially, each vertex is assigned a different label. After that, each vertex chooses the dominant label in its neighbourhood in each iteration. Ties are broken randomly and the order in which the vertices are updated is randomized before every iteration. The algorithm ends when vertices reach a consensus.

Note that since ties are broken randomly, there is no guarantee that the algorithm returns the same community structure after each run. In fact, they frequently differ. See the paper of Raghavan et al on how to come up with an aggregated community structure.

Parameters:
  • weights - name of an edge attribute or a list containing edge weights
  • initial - name of a vertex attribute or a list containing the initial vertex labels. Labels are identified by integers from zero to n-1 where n is the number of vertices. Negative numbers may also be present in this vector, they represent unlabeled vertices.
  • fixed - a list of booleans for each vertex. True corresponds to vertices whose labeling should not change during the algorithm. It only makes sense if initial labels are also given. Unlabeled vertices cannot be fixed. Note that vertex attribute names are not accepted here.
Returns:
the resulting membership vector

Reference: Raghavan, U.N. and Albert, R. and Kumara, S. Near linear time algorithm to detect community structures in large-scale networks. Phys Rev E 76:036106, 2007. http://arxiv.org/abs/0709.2938.

community_leading_eigenvector(n=-1)

source code 

A proper implementation of Newman's eigenvector community structure detection. Each split is done by maximizing the modularity regarding the original network. See the reference for details.

Parameters:
  • n - the desired number of communities. If negative, the algorithm tries to do as many splits as possible. Note that the algorithm won't split a community further if the signs of the leading eigenvector are all the same.
Returns:
a tuple where the first element is the membership vector of the clustering and the second element is the merge matrix.

Attention: this function is wrapped in a more convenient syntax in the derived class Graph. It is advised to use that instead of this version.

Reference: MEJ Newman: Finding community structure in networks using the eigenvectors of matrices, arXiv:physics/0605087

community_multilevel(weights=None, return_levels=True)

source code 

Finds the community structure of the graph according to the multilevel algorithm of Blondel et al. This is a bottom-up algorithm: initially every vertex belongs to a separate community, and vertices are moved between communities iteratively in a way that maximizes the vertices' local contribution to the overall modularity score. When a consensus is reached (i.e. no single move would increase the modularity score), every community in the original graph is shrank to a single vertex (while keeping the total weight of the incident edges) and the process continues on the next level. The algorithm stops when it is not possible to increase the modularity any more after shrinking the communities to vertices.

Parameters:
  • weights - name of an edge attribute or a list containing edge weights
  • return_levels - if True, returns the multilevel result. If False, only the best level (corresponding to the best modularity) is returned.
Returns:
either a single list describing the community membership of each vertex (if return_levels is False), or a list of community membership vectors, one corresponding to each level and a list of corresponding modularities (if return_levels is True).

Attention: this function is wrapped in a more convenient syntax in the derived class Graph. It is advised to use that instead of this version.

Reference: VD Blondel, J-L Guillaume, R Lambiotte and E Lefebvre: Fast unfolding of community hierarchies in large networks. J Stat Mech P10008 (2008), http://arxiv.org/abs/0803.0476

See Also: modularity()

community_optimal_modularity(verbose=False)

source code 

Calculates the optimal modularity score of the graph and the corresponding community structure.

This function uses the GNU Linear Programming Kit to solve a large integer optimization problem in order to find the optimal modularity score and the corresponding community structure, therefore it is unlikely to work for graphs larger than a few (less than a hundred) vertices. Consider using one of the heuristic approaches instead if you have such a large graph.

Returns:
the calculated membership vector and the corresponding modularity in a tuple.

community_spinglass(weights=None, spins=25, parupdate=False, start_temp=1, stop_temp=0.01, cool_fact=0.99, update_rule="config", gamma=1, implementation="orig", lambda=1)

source code 

Finds the community structure of the graph according to the spinglass community detection method of Reichardt & Bornholdt.

Parameters:
  • weights - edge weights to be used. Can be a sequence or iterable or even an edge attribute name.
  • spins - integer, the number of spins to use. This is the upper limit for the number of communities. It is not a problem to supply a (reasonably) big number here, in which case some spin states will be unpopulated.
  • parupdate - whether to update the spins of the vertices in parallel (synchronously) or not
  • start_temp - the starting temperature
  • stop_temp - the stop temperature
  • cool_fact - cooling factor for the simulated annealing
  • update_rule - specifies the null model of the simulation. Possible values are "config" (a random graph with the same vertex degrees as the input graph) or "simple" (a random graph with the same number of edges)
  • gamma - the gamma argument of the algorithm, specifying the balance between the importance of present and missing edges within a community. The default value of 1.0 assigns equal importance to both of them.
  • implementation - currently igraph contains two implementations for the spinglass community detection algorithm. The faster original implementation is the default. The other implementation is able to take into account negative weights, this can be chosen by setting implementation to "neg".
  • lambda - the lambda argument of the algorithm, which specifies the balance between the importance of present and missing negatively weighted edges within a community. Smaller values of lambda lead to communities with less negative intra-connectivity. If the argument is zero, the algorithm reduces to a graph coloring algorithm, using the number of spins as colors. This argument is ignored if the original implementation is used.
Returns:
the community membership vector.

community_walktrap(weights=None, steps=None)

source code 

Finds the community structure of the graph according to the random walk method of Latapy & Pons.

The basic idea of the algorithm is that short random walks tend to stay in the same community. The method provides a dendrogram.

Parameters:
  • weights - name of an edge attribute or a list containing edge weights
Returns:
a tuple with the list of merges and the modularity scores corresponding to each merge

Attention: this function is wrapped in a more convenient syntax in the derived class Graph. It is advised to use that instead of this version.

Reference: Pascal Pons, Matthieu Latapy: Computing communities in large networks using random walks, http://arxiv.org/abs/physics/0512106.

See Also: modularity()

complementer(loops=False)

source code 

Returns the complementer of the graph

Parameters:
  • loops - whether to include loop edges in the complementer.
Returns:
the complementer of the graph

constraint(vertices=None, weights=None)

source code 

Calculates Burt's constraint scores for given vertices in a graph.

Burt's constraint is higher if ego has less, or mutually stronger related (i.e. more redundant) contacts. Burt's measure of constraint, C[i], of vertex i's ego network V[i], is defined for directed and valued graphs as follows:

C[i] = sum( sum( (p[i,q] p[q,j])^2, q in V[i], q != i,j ), j in V[], j != i)

for a graph of order (ie. number od vertices) N, where proportional tie strengths are defined as follows:

p[i,j]=(a[i,j]+a[j,i]) / sum(a[i,k]+a[k,i], k in V[i], k != i), a[i,j] are elements of A and the latter being the graph adjacency matrix.

For isolated vertices, constraint is undefined.

Parameters:
  • vertices - the vertices to be analysed or None for all vertices.
  • weights - weights associated to the edges. Can be an attribute name as well. If None, every edge will have the same weight.
Returns:
constraint scores for all given vertices in a matrix.

contract_vertices(mapping, combine_attrs=None)

source code 

Contracts some vertices in the graph, i.e. replaces groups of vertices with single vertices. Edges are not affected.

Parameters:
  • mapping - numeric vector which gives the mapping between old and new vertex IDs. Vertices having the same new vertex ID in this vector will be remapped into a single new vertex. It is safe to pass the membership vector of a VertexClustering object here.
  • combine_attrs - specifies how to combine the attributes of the vertices being collapsed into a single one. If it is None, all the attributes will be lost. If it is a function, the attributes of the vertices will be collected and passed on to that function which will return the new attribute value that has to be assigned to the single collapsed vertex. It can also be one of the following string constants which define built-in collapsing functions: sum, prod, mean, median, max, min, first, last, random. You can also specify different combination functions for different attributes by passing a dict here which maps attribute names to functions. See Graph.simplify() for more details.
Returns:
None.

See Also: Graph.simplify()

coreness(mode=ALL)

source code 

Finds the coreness (shell index) of the vertices of the network.

The k-core of a graph is a maximal subgraph in which each vertex has at least degree k. (Degree here means the degree in the subgraph of course). The coreness of a vertex is k if it is a member of the k-core but not a member of the k+1-core.

Parameters:
  • mode - whether to compute the in-corenesses (IN), the out-corenesses (OUT) or the undirected corenesses (ALL). Ignored and assumed to be ALL for undirected graphs.
Returns:
the corenesses for each vertex.

Reference: Vladimir Batagelj, Matjaz Zaversnik: An O(m) Algorithm for Core Decomposition of Networks.

count_isomorphisms_vf2(other=None, color1=None, color2=None, edge_color1=None, edge_color2=None, node_compat_fn=None, edge_compat_fn=None)

source code 

Determines the number of isomorphisms between the graph and another one

Vertex and edge colors may be used to restrict the isomorphisms, as only vertices and edges with the same color will be allowed to match each other.

Parameters:
  • other - the other graph. If None, the number of automorphisms will be returned.
  • color1 - optional vector storing the coloring of the vertices of the first graph. If None, all vertices have the same color.
  • color2 - optional vector storing the coloring of the vertices of the second graph. If None, all vertices have the same color.
  • edge_color1 - optional vector storing the coloring of the edges of the first graph. If None, all edges have the same color.
  • edge_color2 - optional vector storing the coloring of the edges of the second graph. If None, all edges have the same color.
  • node_compat_fn - a function that receives the two graphs and two node indices (one from the first graph, one from the second graph) and returns True if the nodes given by the two indices are compatible (i.e. they could be matched to each other) or False otherwise. This can be used to restrict the set of isomorphisms based on node-specific criteria that are too complicated to be represented by node color vectors (i.e. the color1 and color2 parameters). None means that every node is compatible with every other node.
  • edge_compat_fn - a function that receives the two graphs and two edge indices (one from the first graph, one from the second graph) and returns True if the edges given by the two indices are compatible (i.e. they could be matched to each other) or False otherwise. This can be used to restrict the set of isomorphisms based on edge-specific criteria that are too complicated to be represented by edge color vectors (i.e. the edge_color1 and edge_color2 parameters). None means that every edge is compatible with every other node.
Returns:
the number of isomorphisms between the two given graphs (or the number of automorphisms if other is None.

count_multiple(edges=None)

source code 

Counts the multiplicities of the given edges.

Parameters:
  • edges - edge indices for which we want to count their multiplicity. If None, all edges are counted.
Returns:
the multiplicities of the given edges as a list.

count_subisomorphisms_vf2(other, color1=None, color2=None, edge_color1=None, edge_color2=None, node_compat_fn=None, edge_compat_fn=None)

source code 

Determines the number of subisomorphisms between the graph and another one

Vertex and edge colors may be used to restrict the isomorphisms, as only vertices and edges with the same color will be allowed to match each other.

Parameters:
  • other - the other graph.
  • color1 - optional vector storing the coloring of the vertices of the first graph. If None, all vertices have the same color.
  • color2 - optional vector storing the coloring of the vertices of the second graph. If None, all vertices have the same color.
  • edge_color1 - optional vector storing the coloring of the edges of the first graph. If None, all edges have the same color.
  • edge_color2 - optional vector storing the coloring of the edges of the second graph. If None, all edges have the same color.
  • node_compat_fn - a function that receives the two graphs and two node indices (one from the first graph, one from the second graph) and returns True if the nodes given by the two indices are compatible (i.e. they could be matched to each other) or False otherwise. This can be used to restrict the set of isomorphisms based on node-specific criteria that are too complicated to be represented by node color vectors (i.e. the color1 and color2 parameters). None means that every node is compatible with every other node.
  • edge_compat_fn - a function that receives the two graphs and two edge indices (one from the first graph, one from the second graph) and returns True if the edges given by the two indices are compatible (i.e. they could be matched to each other) or False otherwise. This can be used to restrict the set of isomorphisms based on edge-specific criteria that are too complicated to be represented by edge color vectors (i.e. the edge_color1 and edge_color2 parameters). None means that every edge is compatible with every other node.
Returns:
the number of subisomorphisms between the two given graphs

decompose(mode=STRONG, maxcompno=None, minelements=1)

source code 

Decomposes the graph into subgraphs.

Parameters:
  • mode - must be either STRONG or WEAK, depending on the clusters being sought.
  • maxcompno - maximum number of components to return. None means all possible components.
  • minelements - minimum number of vertices in a component. By setting this to 2, isolated vertices are not returned as separate components.
Returns:
a list of the subgraphs. Every returned subgraph is a copy of the original.

degree(vertices, mode=ALL, loops=True)

source code 

Returns some vertex degrees from the graph.

This method accepts a single vertex ID or a list of vertex IDs as a parameter, and returns the degree of the given vertices (in the form of a single integer or a list, depending on the input parameter).

Parameters:
  • vertices - a single vertex ID or a list of vertex IDs
  • mode - the type of degree to be returned (OUT for out-degrees, IN IN for in-degrees or ALL for the sum of them).
  • loops - whether self-loops should be counted.

delete_edges(es)

source code 

Removes edges from the graph.

All vertices will be kept, even if they lose all their edges. Nonexistent edges will be silently ignored.

Parameters:
  • es - the list of edges to be removed. Edges are identifed by edge IDs. EdgeSeq objects are also accepted here.

delete_vertices(vs)

source code 

Deletes vertices and all its edges from the graph.

Parameters:
  • vs - a single vertex ID or the list of vertex IDs to be deleted.

density(loops=False)

source code 

Calculates the density of the graph.

Parameters:
  • loops - whether to take loops into consideration. If True, the algorithm assumes that there might be some loops in the graph and calculates the density accordingly. If False, the algorithm assumes that there can't be any loops.
Returns:
the reciprocity of the graph.

diameter(directed=True, unconn=True, weights=None)

source code 

Calculates the diameter of the graph.

Parameters:
  • directed - whether to consider directed paths.
  • unconn - if True and the graph is unconnected, the longest geodesic within a component will be returned. If False and the graph is unconnected, the result is the number of vertices if there are no weights or infinity if there are weights.
  • weights - edge weights to be used. Can be a sequence or iterable or even an edge attribute name.
Returns:
the diameter

disjoint_union(graphs)

source code 

Creates the disjoint union of two (or more) graphs.

Parameters:
  • graphs - the list of graphs to be united with the current one.

diversity(vertices=None, weights=None)

source code 

Calculates the structural diversity index of the vertices.

The structural diversity index of a vertex is simply the (normalized) Shannon entropy of the weights of the edges incident on the vertex.

The measure is defined for undirected graphs only; edge directions are ignored.

Parameters:
  • vertices - the vertices for which the diversity indices must be returned. If None, uses all of the vertices in the graph.
  • weights - edge weights to be used. Can be a sequence or iterable or even an edge attribute name.
Returns:
the calculated diversity indices in a list, or a single number if a single vertex was supplied.

Reference: Eagle N, Macy M and Claxton R: Network diversity and economic development, Science 328, 1029--1031, 2010.

dyad_census()

source code 

Dyad census, as defined by Holland and Leinhardt

Dyad census means classifying each pair of vertices of a directed graph into three categories: mutual, there is an edge from a to b and also from b to a; asymmetric, there is an edge either from a to b or from b to a but not the other way and null, no edges between a and b.

Returns:
the number of mutual, asymmetric and null connections in a 3-tuple.

Attention: this function has a more convenient interface in class Graph which wraps the result in a DyadCensus object. It is advised to use that.

eccentricity(vertices=None, mode=ALL)

source code 

Calculates the eccentricities of given vertices in a graph.

The eccentricity of a vertex is calculated by measuring the shortest distance from (or to) the vertex, to (or from) all other vertices in the graph, and taking the maximum.

Parameters:
  • vertices - the vertices for which the eccentricity scores must be returned. If None, uses all of the vertices in the graph.
  • mode - must be one of IN, OUT and ALL. IN means that edge directions are followed; OUT means that edge directions are followed the opposite direction; ALL means that directions are ignored. The argument has no effect for undirected graphs.
Returns:
the calculated eccentricities in a list, or a single number if a single vertex was supplied.

ecount()

source code 

Counts the number of edges.

Returns: integer
the number of edges in the graph.

edge_attributes()

source code 
Returns:
the attribute name list of the graph's edges

edge_betweenness(directed=True, cutoff=None, weights=None)

source code 

Calculates or estimates the edge betweennesses in a graph.

Parameters:
  • directed - whether to consider directed paths.
  • cutoff - if it is an integer, only paths less than or equal to this length are considered, effectively resulting in an estimation of the betweenness values. If None, the exact betweennesses are returned.
  • weights - edge weights to be used. Can be a sequence or iterable or even an edge attribute name.
Returns:
a list with the (exact or estimated) edge betweennesses of all edges.

edge_connectivity(source=-1, target=-1, checks=True)

source code 

Calculates the edge connectivity of the graph or between some vertices.

The edge connectivity between two given vertices is the number of edges that have to be removed in order to disconnect the two vertices into two separate components. This is also the number of edge disjoint directed paths between the vertices. The edge connectivity of the graph is the minimal edge connectivity over all vertex pairs.

This method calculates the edge connectivity of a given vertex pair if both the source and target vertices are given. If none of them is given (or they are both negative), the overall edge connectivity is returned.

Parameters:
  • source - the source vertex involved in the calculation.
  • target - the target vertex involved in the calculation.
  • checks - if the whole graph connectivity is calculated and this is True, igraph performs some basic checks before calculation. If the graph is not strongly connected, then the connectivity is obviously zero. If the minimum degree is one, then the connectivity is also one. These simple checks are much faster than checking the entire graph, therefore it is advised to set this to True. The parameter is ignored if the connectivity between two given vertices is computed.
Returns:
the edge connectivity

eigenvector_centrality(directed=True, scale=True, weights=None, return_eigenvalue=False, arpack_options=None)

source code 

Calculates the eigenvector centralities of the vertices in a graph.

Parameters:
  • directed - whether to consider edge directions in a directed graph. Ignored for undirected graphs.
  • scale - whether to normalize the centralities so the largest one will always be 1.
  • weights - edge weights given as a list or an edge attribute. If None, all edges have equal weight.
  • return_eigenvalue - whether to return the actual largest eigenvalue along with the centralities
  • arpack_options - an ARPACKOptions object that can be used to fine-tune the calculation. If it is omitted, the module-level variable called arpack_options is used.
Returns:
the eigenvector centralities in a list and optionally the largest eigenvalue (as a second member of a tuple)

farthest_points(directed=True, unconn=True, weights=None)

source code 

Returns two vertex IDs whose distance equals the actual diameter of the graph.

If there are many shortest paths with the length of the diameter, it returns the first one it found.

Parameters:
  • directed - whether to consider directed paths.
  • unconn - if True and the graph is unconnected, the longest geodesic within a component will be returned. If False and the graph is unconnected, the result contains the number of vertices if there are no weights or infinity if there are weights.
  • weights - edge weights to be used. Can be a sequence or iterable or even an edge attribute name.
Returns:
a triplet containing the two vertex IDs and their distance. The IDs are None if the graph is unconnected and unconn is False.

feedback_arc_set(weights=None, method="eades")

source code 

Calculates an approximately or exactly minimal feedback arc set.

A feedback arc set is a set of edges whose removal makes the graph acyclic. Since this is always possible by removing all the edges, we are in general interested in removing the smallest possible number of edges, or an edge set with as small total weight as possible. This method calculates one such edge set. Note that the task is trivial for an undirected graph as it is enough to find a spanning tree and then remove all the edges not in the spanning tree. Of course it is more complicated for directed graphs.

Parameters:
  • weights - edge weights to be used. Can be a sequence or iterable or even an edge attribute name. When given, the algorithm will strive to remove lightweight edges in order to minimize the total weight of the feedback arc set.
  • method - the algorithm to use. "eades" uses the greedy cycle breaking heuristic of Eades, Lin and Smyth, which is linear in the number of edges but not necessarily optimal; however, it guarantees that the number of edges to be removed is smaller than |E|/2 - |V|/6. "ip" uses an integer programming formulation which is guaranteed to yield an optimal result, but is too slow for large graphs.
Returns:
the IDs of the edges to be removed, in a list.

Reference: Eades P, Lin X and Smyth WF: A fast and effective heuristic for the feedback arc set problem. In: Proc Inf Process Lett 319-323, 1993.

get_adjacency(type=GET_ADJACENCY_BOTH, eids=False)

source code 

Returns the adjacency matrix of a graph.

Parameters:
  • type - either GET_ADJACENCY_LOWER (uses the lower triangle of the matrix) or GET_ADJACENCY_UPPER (uses the upper triangle) or GET_ADJACENCY_BOTH (uses both parts). Ignored for directed graphs.
  • eids - if True, the result matrix will contain zeros for non-edges and the ID of the edge plus one for edges in the appropriate cell. If False, the result matrix will contain the number of edges for each vertex pair.
Returns:
the adjacency matrix.

get_all_shortest_paths(v, to=None, weights=None, mode=OUT)

source code 

Calculates all of the shortest paths from/to a given node in a graph.

Parameters:
  • v - the source/destination for the calculated paths
  • to - a vertex selector describing the destination/source for the calculated paths. This can be a single vertex ID, a list of vertex IDs, a single vertex name, a list of vertex names or a VertexSeq object. None means all the vertices.
  • weights - edge weights in a list or the name of an edge attribute holding edge weights. If None, all edges are assumed to have equal weight.
  • mode - the directionality of the paths. IN means to calculate incoming paths, OUT means to calculate outgoing paths, ALL means to calculate both ones.
Returns:
all of the shortest path from the given node to every other reachable node in the graph in a list. Note that in case of mode=IN, the vertices in a path are returned in reversed order!

get_diameter(directed=True, unconn=True, weights=None)

source code 

Returns a path with the actual diameter of the graph.

If there are many shortest paths with the length of the diameter, it returns the first one it founds.

Parameters:
  • directed - whether to consider directed paths.
  • unconn - if True and the graph is unconnected, the longest geodesic within a component will be returned. If False and the graph is unconnected, the result is the number of vertices if there are no weights or infinity if there are weights.
  • weights - edge weights to be used. Can be a sequence or iterable or even an edge attribute name.
Returns:
the vertices in the path in order.

get_eid(v1, v2, directed=True, error=True)

source code 

Returns the edge ID of an arbitrary edge between vertices v1 and v2

Parameters:
  • v1 - the first vertex ID
  • v2 - the second vertex ID
  • directed - whether edge directions should be considered in directed graphs. The default is True. Ignored for undirected graphs.
  • error - if True, an exception will be raised when the given edge does not exist. If False, -1 will be returned in that case.
Returns:
the edge ID of an arbitrary edge between vertices v1 and v2

get_eids(pairs=None, path=None, directed=True, error=True)

source code 

Returns the edge IDs of some edges between some vertices.

This method can operate in two different modes, depending on which of the keyword arguments pairs and path are given.

The method does not consider multiple edges; if there are multiple edges between a pair of vertices, only the ID of one of the edges is returned.

Parameters:
  • pairs - a list of integer pairs. Each integer pair is considered as a source-target vertex pair; the corresponding edge is looked up in the graph and the edge ID is returned for each pair.
  • path - a list of vertex IDs. The list is considered as a continuous path from the first vertex to the last, passing through the intermediate vertices. The corresponding edge IDs between the first and the second, the second and the third and so on are looked up in the graph and the edge IDs are returned. If both path and pairs are given, the two lists are concatenated.
  • directed - whether edge directions should be considered in directed graphs. The default is True. Ignored for undirected graphs.
  • error - if True, an exception will be raised if a given edge does not exist. If False, -1 will be returned in that case.
Returns:
the edge IDs in a list

get_incidence(types)

source code 

Internal function, undocumented.

See Also: Graph.get_incidence()

get_isomorphisms_vf2(other=None, color1=None, color2=None, edge_color1=None, edge_color2=None, node_compat_fn=None, edge_compat_fn=None)

source code 

Returns all isomorphisms between the graph and another one

Vertex and edge colors may be used to restrict the isomorphisms, as only vertices and edges with the same color will be allowed to match each other.

Parameters:
  • other - the other graph. If None, the automorphisms will be returned.
  • color1 - optional vector storing the coloring of the vertices of the first graph. If None, all vertices have the same color.
  • color2 - optional vector storing the coloring of the vertices of the second graph. If None, all vertices have the same color.
  • edge_color1 - optional vector storing the coloring of the edges of the first graph. If None, all edges have the same color.
  • edge_color2 - optional vector storing the coloring of the edges of the second graph. If None, all edges have the same color.
  • node_compat_fn - a function that receives the two graphs and two node indices (one from the first graph, one from the second graph) and returns True if the nodes given by the two indices are compatible (i.e. they could be matched to each other) or False otherwise. This can be used to restrict the set of isomorphisms based on node-specific criteria that are too complicated to be represented by node color vectors (i.e. the color1 and color2 parameters). None means that every node is compatible with every other node.
  • edge_compat_fn - a function that receives the two graphs and two edge indices (one from the first graph, one from the second graph) and returns True if the edges given by the two indices are compatible (i.e. they could be matched to each other) or False otherwise. This can be used to restrict the set of isomorphisms based on edge-specific criteria that are too complicated to be represented by edge color vectors (i.e. the edge_color1 and edge_color2 parameters). None means that every edge is compatible with every other node.
Returns:
a list of lists, each item of the list containing the mapping from vertices of the second graph to the vertices of the first one

get_shortest_paths(v, to=None, weights=None, mode=OUT, output="vpath")

source code 

Calculates the shortest paths from/to a given node in a graph.

Parameters:
  • v - the source/destination for the calculated paths
  • to - a vertex selector describing the destination/source for the calculated paths. This can be a single vertex ID, a list of vertex IDs, a single vertex name, a list of vertex names or a VertexSeq object. None means all the vertices.
  • weights - edge weights in a list or the name of an edge attribute holding edge weights. If None, all edges are assumed to have equal weight.
  • mode - the directionality of the paths. IN means to calculate incoming paths, OUT means to calculate outgoing paths, ALL means to calculate both ones.
  • output - determines what should be returned. If this is "vpath", a list of vertex IDs will be returned, one path for each target vertex. For unconnected graphs, some of the list elements may be empty. Note that in case of mode=IN, the vertices in a path are returned in reversed order. If output="epath", edge IDs are returned instead of vertex IDs.
Returns:
see the documentation of the output parameter.

get_subisomorphisms_vf2(other, color1=None, color2=None, edge_color1=None, edge_color2=None, node_compat_fn=None, edge_compat_fn=None)

source code 

Returns all subisomorphisms between the graph and another one

Vertex and edge colors may be used to restrict the isomorphisms, as only vertices and edges with the same color will be allowed to match each other.

Parameters:
  • other - the other graph.
  • color1 - optional vector storing the coloring of the vertices of the first graph. If None, all vertices have the same color.
  • color2 - optional vector storing the coloring of the vertices of the second graph. If None, all vertices have the same color.
  • edge_color1 - optional vector storing the coloring of the edges of the first graph. If None, all edges have the same color.
  • edge_color2 - optional vector storing the coloring of the edges of the second graph. If None, all edges have the same color.
  • node_compat_fn - a function that receives the two graphs and two node indices (one from the first graph, one from the second graph) and returns True if the nodes given by the two indices are compatible (i.e. they could be matched to each other) or False otherwise. This can be used to restrict the set of isomorphisms based on node-specific criteria that are too complicated to be represented by node color vectors (i.e. the color1 and color2 parameters). None means that every node is compatible with every other node.
  • edge_compat_fn - a function that receives the two graphs and two edge indices (one from the first graph, one from the second graph) and returns True if the edges given by the two indices are compatible (i.e. they could be matched to each other) or False otherwise. This can be used to restrict the set of isomorphisms based on edge-specific criteria that are too complicated to be represented by edge color vectors (i.e. the edge_color1 and edge_color2 parameters). None means that every edge is compatible with every other node.
Returns:
a list of lists, each item of the list containing the mapping from vertices of the second graph to the vertices of the first one

girth(return_shortest_circle=False)

source code 

Returns the girth of the graph.

The girth of a graph is the length of the shortest circle in it.

Parameters:
  • return_shortest_circle - whether to return one of the shortest circles found in the graph.
Returns:
the length of the shortest circle or (if return_shortest_circle) is true, the shortest circle itself as a list

has_multiple()

source code 

Checks whether the graph has multiple edges.

Returns: boolean
True if the graph has at least one multiple edge, False otherwise.

hub_score(weights=None, scale=True, arpack_options=None, return_eigenvalue=False)

source code 

Calculates Kleinberg's hub score for the vertices of the graph

Parameters:
  • weights - edge weights to be used. Can be a sequence or iterable or even an edge attribute name.
  • scale - whether to normalize the scores so that the largest one is 1.
  • arpack_options - an ARPACKOptions object used to fine-tune the ARPACK eigenvector calculation. If omitted, the module-level variable called arpack_options is used.
  • return_eigenvalue - whether to return the largest eigenvalue
Returns:
the hub scores in a list and optionally the largest eigenvalue as a second member of a tuple

See Also: authority_score()

incident(vertex, mode=OUT)

source code 

Returns the edges a given vertex is incident on.

Parameters:
  • vertex - a vertex ID
  • mode - whether to return only predecessors (OUT), successors (IN) or both (ALL). Ignored for undirected graphs.

independence_number()

source code 

Returns the independence number of the graph.

The independence number of the graph is the size of the largest independent vertex set.

See Also: largest_independent_vertex_sets() for the largest independent vertex sets

independent_vertex_sets(min=0, max=0)

source code 

Returns some or all independent vertex sets of the graph as a list of tuples.

Two vertices are independent if there is no edge between them. Members of an independent vertex set are mutually independent.

Parameters:
  • min - the minimum size of sets to be returned. If zero or negative, no lower bound will be used.
  • max - the maximum size of sets to be returned. If zero or negative, no upper bound will be used.

induced_subgraph(vertices, implementation="auto")

source code 

Returns a subgraph spanned by the given vertices.

Parameters:
  • vertices - a list containing the vertex IDs which should be included in the result.
  • implementation - the implementation to use when constructing the new subgraph. igraph includes two implementations at the moment. "copy_and_delete" copies the original graph and removes those vertices that are not in the given set. This is more efficient if the size of the subgraph is comparable to the original graph. The other implementation ("create_from_scratch") constructs the result graph from scratch and then copies the attributes accordingly. This is a better solution if the subgraph is relatively small, compared to the original graph. "auto" selects between the two implementations automatically, based on the ratio of the size of the subgraph and the size of the original graph.
Returns:
the subgraph

intersection(graphs)

source code 

Creates the intersection of two (or more) graphs.

Parameters:
  • graphs - the list of graphs to be intersected with the current one.

is_bipartite(return_types=False)

source code 

Decides whether the graph is bipartite or not.

Vertices of a bipartite graph can be partitioned into two groups A and B in a way that all edges go between the two groups.

Parameters:
  • return_types - if False, the method will simply return True or False depending on whether the graph is bipartite or not. If True, the actual group assignments are also returned as a list of boolean values. (Note that the group assignment is not unique, especially if the graph consists of multiple components, since the assignments of components are independent from each other).
Returns:
True if the graph is bipartite, False if not. If return_types is True, the group assignment is also returned.

is_connected(mode=STRONG)

source code 

Decides whether the graph is connected.

Parameters:
  • mode - whether we should calculate strong or weak connectivity.
Returns:
True if the graph is connected, False otherwise.

is_dag()

source code 

Checks whether the graph is a DAG (directed acyclic graph).

A DAG is a directed graph with no directed cycles.

Returns: boolean
True if it is a DAG, False otherwise.

is_directed()

source code 

Checks whether the graph is directed.

Returns: boolean
True if it is directed, False otherwise.

is_loop(edges=None)

source code 

Checks whether a specific set of edges contain loop edges

Parameters:
  • edges - edge indices which we want to check. If None, all edges are checked.
Returns:
a list of booleans, one for every edge given

is_minimal_separator(vertices)

source code 

Decides whether the given vertex set is a minimal separator.

A minimal separator is a set of vertices whose removal disconnects the graph, while the removal of any subset of the set keeps the graph connected.

Parameters:
  • vertices - a single vertex ID or a list of vertex IDs
Returns:
True is the given vertex set is a minimal separator, False otherwise.

is_multiple(edges=None)

source code 

Checks whether an edge is a multiple edge.

Also works for a set of edges -- in this case, every edge is checked one by one. Note that if there are multiple edges going between a pair of vertices, there is always one of them that is not reported as multiple (only the others). This allows one to easily detect the edges that have to be deleted in order to make the graph free of multiple edges.

Parameters:
  • edges - edge indices which we want to check. If None, all edges are checked.
Returns:
a list of booleans, one for every edge given

is_mutual(edges=None)

source code 

Checks whether an edge has an opposite pair.

Also works for a set of edges -- in this case, every edge is checked one by one. The result will be a list of booleans (or a single boolean if only an edge index is supplied), every boolean corresponding to an edge in the edge set supplied. True is returned for a given edge a --> b if there exists another edge b --> a in the original graph (not the given edge set!). All edges in an undirected graph are mutual. In case there are multiple edges between a and b, it is enough to have at least one edge in either direction to report all edges between them as mutual, so the multiplicity of edges do not matter.

Parameters:
  • edges - edge indices which we want to check. If None, all edges are checked.
Returns:
a list of booleans, one for every edge given

is_separator(vertices)

source code 

Decides whether the removal of the given vertices disconnects the graph.

Parameters:
  • vertices - a single vertex ID or a list of vertex IDs
Returns:
True is the given vertex set is a separator, False if not.

is_simple()

source code 

Checks whether the graph is simple (no loop or multiple edges).

Returns: boolean
True if it is simple, False otherwise.

isoclass(vertices)

source code 

Returns the isomorphy class of the graph or its subgraph.

Isomorphy class calculations are implemented only for graphs with 3 or 4 vertices.

Parameters:
  • vertices - a list of vertices if we want to calculate the isomorphy class for only a subset of vertices. None means to use the full graph.
Returns:
the isomorphy class of the (sub)graph

isomorphic(other)

source code 

Checks whether the graph is isomorphic to another graph.

The algorithm being used is selected using a simple heuristic:

  • If one graph is directed and the other undirected, an exception is thrown.
  • If the two graphs does not have the same number of vertices and edges, it returns with False
  • If the graphs have three or four vertices, then an O(1) algorithm is used with precomputed data.
  • Otherwise if the graphs are directed, then the VF2 isomorphism algorithm is used (see Graph.isomorphic_vf2).
  • Otherwise the BLISS isomorphism algorithm is used, see Graph.isomorphic_bliss.
Returns:
True if the graphs are isomorphic, False otherwise.

isomorphic_bliss(other, return_mapping_12=False, return_mapping_21=False, sh1="fm", sh2="fm")

source code 

Checks whether the graph is isomorphic to another graph, using the BLISS isomorphism algorithm.

Parameters:
  • other - the other graph with which we want to compare the graph.
  • return_mapping_12 - if True, calculates the mapping which maps the vertices of the first graph to the second.
  • return_mapping_21 - if True, calculates the mapping which maps the vertices of the second graph to the first.
  • sh1 - splitting heuristics for the first graph as a case-insensitive string, with the following possible values:
    • "f": first non-singleton cell
    • "fl": first largest non-singleton cell
    • "fs": first smallest non-singleton cell
    • "fm": first maximally non-trivially connected non-singleton cell
    • "flm": largest maximally non-trivially connected non-singleton cell
    • "fsm": smallest maximally non-trivially connected non-singleton cell
  • sh2 - splitting heuristics to be used for the second graph. Accepted values are as above.
Returns:
if no mapping is calculated, the result is True if the graphs are isomorphic, False otherwise. If any or both mappings are calculated, the result is a 3-tuple, the first element being the above mentioned boolean, the second element being the 1 -> 2 mapping and the third element being the 2 -> 1 mapping. If the corresponding mapping was not calculated, None is returned in the appropriate element of the 3-tuple.

isomorphic_vf2(other=None, color1=None, color2=None, edge_color1=None, edge_color2=None, return_mapping_12=False, return_mapping_21=False, node_compat_fn=None, edge_compat_fn=None, callback=None)

source code 

Checks whether the graph is isomorphic to another graph, using the VF2 isomorphism algorithm.

Vertex and edge colors may be used to restrict the isomorphisms, as only vertices and edges with the same color will be allowed to match each other.

Parameters:
  • other - the other graph with which we want to compare the graph. If None, the automorphjisms of the graph will be tested.
  • color1 - optional vector storing the coloring of the vertices of the first graph. If None, all vertices have the same color.
  • color2 - optional vector storing the coloring of the vertices of the second graph. If None, all vertices have the same color.
  • edge_color1 - optional vector storing the coloring of the edges of the first graph. If None, all edges have the same color.
  • edge_color2 - optional vector storing the coloring of the edges of the second graph. If None, all edges have the same color.
  • return_mapping_12 - if True, calculates the mapping which maps the vertices of the first graph to the second.
  • return_mapping_21 - if True, calculates the mapping which maps the vertices of the second graph to the first.
  • callback - if not None, the isomorphism search will not stop at the first match; it will call this callback function instead for every isomorphism found. The callback function must accept four arguments: the first graph, the second graph, a mapping from the nodes of the first graph to the second, and a mapping from the nodes of the second graph to the first. The function must return True if the search should continue or False otherwise.
  • node_compat_fn - a function that receives the two graphs and two node indices (one from the first graph, one from the second graph) and returns True if the nodes given by the two indices are compatible (i.e. they could be matched to each other) or False otherwise. This can be used to restrict the set of isomorphisms based on node-specific criteria that are too complicated to be represented by node color vectors (i.e. the color1 and color2 parameters). None means that every node is compatible with every other node.
  • edge_compat_fn - a function that receives the two graphs and two edge indices (one from the first graph, one from the second graph) and returns True if the edges given by the two indices are compatible (i.e. they could be matched to each other) or False otherwise. This can be used to restrict the set of isomorphisms based on edge-specific criteria that are too complicated to be represented by edge color vectors (i.e. the edge_color1 and edge_color2 parameters). None means that every edge is compatible with every other node.
Returns:
if no mapping is calculated, the result is True if the graphs are isomorphic, False otherwise. If any or both mappings are calculated, the result is a 3-tuple, the first element being the above mentioned boolean, the second element being the 1 -> 2 mapping and the third element being the 2 -> 1 mapping. If the corresponding mapping was not calculated, None is returned in the appropriate element of the 3-tuple.

knn(vids=None, weights=None)

source code 

Calculates the average degree of the neighbors for each vertex, and the same quantity as the function of vertex degree.

Parameters:
  • vids - the vertices for which the calculation is performed. None means all vertices.
  • weights - edge weights to be used. Can be a sequence or iterable or even an edge attribute name. If this is given, the vertex strength will be used instead of the vertex degree in the calculations, but the "ordinary" vertex degree will be used for the second (degree- dependent) list in the result.
Returns:
two lists in a tuple. The first list contains the average degree of neighbors for each vertex, the second contains the average degree of neighbors as a function of vertex degree. The zeroth element of this list corresponds to vertices of degree 1.

laplacian(weights=None, normalized=False)

source code 

Returns the Laplacian matrix of a graph.

The Laplacian matrix is similar to the adjacency matrix, but the edges are denoted with -1 and the diagonal contains the node degrees.

Normalized Laplacian matrices have 1 or 0 in their diagonals (0 for vertices with no edges), edges are denoted by 1 / sqrt(d_i * d_j) where d_i is the degree of node i.

Multiple edges and self-loops are silently ignored. Although it is possible to calculate the Laplacian matrix of a directed graph, it does not make much sense.

Parameters:
  • weights - edge weights to be used. Can be a sequence or iterable or even an edge attribute name. When edge weights are used, the degree of a node is considered to be the weight of its incident edges.
  • normalized - whether to return the normalized Laplacian matrix.
Returns:
the Laplacian matrix.

largest_cliques()

source code 

Returns the largest cliques of the graph as a list of tuples.

Quite intuitively a clique is considered largest if there is no clique with more vertices in the whole graph. All largest cliques are maximal (i.e. nonextendable) but not all maximal cliques are largest.

See Also: clique_number() for the size of the largest cliques or maximal_cliques() for the maximal cliques

largest_independent_vertex_sets()

source code 

Returns the largest independent vertex sets of the graph as a list of tuples.

Quite intuitively an independent vertex set is considered largest if there is no other set with more vertices in the whole graph. All largest sets are maximal (i.e. nonextendable) but not all maximal sets are largest.

See Also: independence_number() for the size of the largest independent vertex sets or maximal_independent_vertex_sets() for the maximal (nonextendable) independent vertex sets

layout_circle(dim=2)

source code 

Places the vertices of the graph uniformly on a circle or a sphere.

Parameters:
  • dim - the desired number of dimensions for the layout. dim=2 means a 2D layout, dim=3 means a 3D layout.
Returns:
the calculated layout.

layout_drl(weights=None, fixed=None, seed=None, options=None, dim=2)

source code 

Places the vertices on a 2D plane or in the 3D space ccording to the DrL layout algorithm.

This is an algorithm suitable for quite large graphs, but it can be surprisingly slow for small ones (where the simpler force-based layouts like layout_kamada_kawai() or layout_fruchterman_reingold() are more useful.

Parameters:
  • weights - edge weights to be used. Can be a sequence or iterable or even an edge attribute name.
  • seed - if None, uses a random starting layout for the algorithm. If a matrix (list of lists), uses the given matrix as the starting position.
  • fixed - if a seed is given, you can specify some vertices to be kept fixed at their original position in the seed by passing an appropriate list here. The list must have exactly as many items as the number of vertices in the graph. Items of the list that evaluate to True denote vertices that will not be moved.
  • options - if you give a string argument here, you can select from five default preset parameterisations: default, coarsen for a coarser layout, coarsest for an even coarser layout, refine for refining an existing layout and final for finalizing a layout. If you supply an object that is not a string, the DrL layout parameters are retrieved from the respective keys of the object (so it should be a dict or something else that supports the mapping protocol). The following keys can be used:
    • edge_cut: edge cutting is done in the late stages of the algorithm in order to achieve less dense layouts. Edges are cut if there is a lot of stress on them (a large value in the objective function sum). The edge cutting parameter is a value between 0 and 1 with 0 representing no edge cutting and 1 representing maximal edge cutting.
    • init_iterations: number of iterations in the initialization phase
    • init_temperature: start temperature during initialization
    • init_attraction: attraction during initialization
    • init_damping_mult: damping multiplier during initialization
    • liquid_iterations, liquid_temperature, liquid_attraction, liquid_damping_mult: same parameters for the liquid phase
    • expansion_iterations, expansion_temperature, expansion_attraction, expansion_damping_mult: parameters for the expansion phase
    • cooldown_...: parameters for the cooldown phase
    • crunch_...: parameters for the crunch phase
    • simmer_...: parameters for the simmer phase

    Instead of a mapping, you can also use an arbitrary Python object here: if the object does not support the mapping protocol, an attribute of the object with the same name is looked up instead. If a parameter cannot be found either as a key or an attribute, the default from the default preset will be used.

  • dim - the desired number of dimensions for the layout. dim=2 means a 2D layout, dim=3 means a 3D layout.
Returns:
the calculated layout.

layout_fruchterman_reingold(weights=None, maxiter=500, maxdelta=None, area=None, coolexp=1.5, repulserad=None, seed=None, minx=None, maxx=None, miny=None, maxy=None, minz=None, maxz=None, dim=2)

source code 

Places the vertices on a 2D plane or in the 3D space according to the Fruchterman-Reingold algorithm.

This is a force directed layout, see Fruchterman, T. M. J. and Reingold, E. M.: Graph Drawing by Force-directed Placement. Software -- Practice and Experience, 21/11, 1129--1164, 1991

Parameters:
  • weights - edge weights to be used. Can be a sequence or iterable or even an edge attribute name.
  • maxiter - the number of iterations to perform. The default is 500.
  • maxdelta - the maximum distance to move a vertex in an iteration. The default is the number of vertices.
  • area - the area of the square on which the vertices will be placed. The default is the square of the number of vertices.
  • coolexp - the cooling exponent of the simulated annealing. The default is 1.5.
  • repulserad - determines the radius at which vertex-vertex repulsion cancels out attraction of adjacent vertices. The default is the number of vertices^3.
  • minx - if not None, it must be a vector with exactly as many elements as there are vertices in the graph. Each element is a minimum constraint on the X value of the vertex in the layout.
  • maxx - similar to minx, but with maximum constraints
  • miny - similar to minx, but with the Y coordinates
  • maxy - similar to maxx, but with the Y coordinates
  • minz - similar to minx, but with the Z coordinates. Use only for 3D layouts (dim=3).
  • maxz - similar to maxx, but with the Z coordinates. Use only for 3D layouts (dim=3).
  • seed - if None, uses a random starting layout for the algorithm. If a matrix (list of lists), uses the given matrix as the starting position.
  • dim - the desired number of dimensions for the layout. dim=2 means a 2D layout, dim=3 means a 3D layout.
Returns:
the calculated layout.

layout_graphopt(niter=500, node_charge=0.001, node_mass=30, spring_length=0, spring_constant=1, max_sa_movement=5, seed=None)

source code 

This is a port of the graphopt layout algorithm by Michael Schmuhl. graphopt version 0.4.1 was rewritten in C and the support for layers was removed.

graphopt uses physical analogies for defining attracting and repelling forces among the vertices and then the physical system is simulated until it reaches an equilibrium or the maximal number of iterations is reached.

See http://www.schmuhl.org/graphopt/ for the original graphopt.

Parameters:
  • niter - the number of iterations to perform. Should be a couple of hundred in general.
  • node_charge - the charge of the vertices, used to calculate electric repulsion.
  • node_mass - the mass of the vertices, used for the spring forces
  • spring_length - the length of the springs
  • spring_constant - the spring constant
  • max_sa_movement - the maximum amount of movement allowed in a single step along a single axis.
  • seed - a matrix containing a seed layout from which the algorithm will be started. If None, a random layout will be used.
Returns:
the calculated layout.

layout_grid(width=0, height=0, dim=2)

source code 

Places the vertices of a graph in a 2D or 3D grid.

Parameters:
  • width - the number of vertices in a single row of the layout. Zero or negative numbers mean that the width should be determined automatically.
  • height - the number of vertices in a single column of the layout. Zero or negative numbers mean that the height should be determined automatically. It must not be given if the number of dimensions is 2.
  • dim - the desired number of dimensions for the layout. dim=2 means a 2D layout, dim=3 means a 3D layout.
Returns:
the calculated layout.

layout_grid_fruchterman_reingold(maxiter=500, maxdelta=None, area=None, coolexp=0.99, repulserad=maxiter*maxdelta, cellsize=None, seed=None)

source code 

Places the vertices on a 2D plane according to the Fruchterman-Reingold grid algorithm.

This is a modified version of a force directed layout, see Fruchterman, T. M. J. and Reingold, E. M.: Graph Drawing by Force-directed Placement. Software -- Practice and Experience, 21/11, 1129--1164, 1991. The algorithm partitions the 2D space to a grid and vertex repulsion is then calculated only for vertices nearby.

Parameters:
  • maxiter - the number of iterations to perform.
  • maxdelta - the maximum distance to move a vertex in an iteration. None means the number of vertices.
  • area - the area of the square on which the vertices will be placed. None means the square of maxdelta.
  • coolexp - the cooling exponent of the simulated annealing.
  • repulserad - determines the radius at which vertex-vertex repulsion cancels out attraction of adjacent vertices. None means maxiter*maxdelta.
  • cellsize - the size of the grid cells. When calculating the repulsion forces, only vertices in the same or neighboring grid cells are taken into account. Defaults to the fourth root of area.
  • seed - if None, uses a random starting layout for the algorithm. If a matrix (list of lists), uses the given matrix as the starting position.
Returns:
the calculated layout.

layout_kamada_kawai(maxiter=1000, sigma=None, initemp=10, coolexp=0.99, kkconst=None, seed=None, minx=None, maxx=None, miny=None, maxy=None, minz=None, maxz=None, dim=2)

source code 

Places the vertices on a plane according to the Kamada-Kawai algorithm.

This is a force directed layout, see Kamada, T. and Kawai, S.: An Algorithm for Drawing General Undirected Graphs. Information Processing Letters, 31/1, 7--15, 1989.

Parameters:
  • maxiter - the number of iterations to perform.
  • sigma - the standard base deviation of the position change proposals. None means the number of vertices / 4
  • initemp - initial temperature of the simulated annealing.
  • coolexp - cooling exponent of the simulated annealing.
  • kkconst - the Kamada-Kawai vertex attraction constant. None means the square of the number of vertices.
  • minx - if not None, it must be a vector with exactly as many elements as there are vertices in the graph. Each element is a minimum constraint on the X value of the vertex in the layout.
  • maxx - similar to minx, but with maximum constraints
  • miny - similar to minx, but with the Y coordinates
  • maxy - similar to maxx, but with the Y coordinates
  • minz - similar to minx, but with the Z coordinates. Use only for 3D layouts (dim=3).
  • maxz - similar to maxx, but with the Z coordinates. Use only for 3D layouts (dim=3).
  • seed - if None, uses a random starting layout for the algorithm. If a matrix (list of lists), uses the given matrix as the starting position.
  • dim - the desired number of dimensions for the layout. dim=2 means a 2D layout, dim=3 means a 3D layout.
Returns:
the calculated layout.

layout_lgl(maxiter=150, maxdelta=-1, area=-1, coolexp=1.5, repulserad=-1, cellsize=-1, root=None)

source code 

Places the vertices on a 2D plane according to the Large Graph Layout.

Parameters:
  • maxiter - the number of iterations to perform.
  • maxdelta - the maximum distance to move a vertex in an iteration. If negative, defaults to the number of vertices.
  • area - the area of the square on which the vertices will be placed. If negative, defaults to the number of vertices squared.
  • coolexp - the cooling exponent of the simulated annealing.
  • repulserad - determines the radius at which vertex-vertex repulsion cancels out attraction of adjacent vertices. If negative, defaults to area times the number of vertices.
  • cellsize - the size of the grid cells. When calculating the repulsion forces, only vertices in the same or neighboring grid cells are taken into account. Defaults to the fourth root of area.
  • root - the root vertex, this is placed first, its neighbors in the first iteration, second neighbors in the second, etc. None means that a random vertex will be chosen.
Returns:
the calculated layout.

layout_mds(dist=None, dim=2, arpack_options=None)

source code 

Places the vertices in an Euclidean space with the given number of dimensions using multidimensional scaling.

This layout requires a distance matrix, where the intersection of row i and column j specifies the desired distance between vertex i and vertex j. The algorithm will try to place the vertices in a way that approximates the distance relations prescribed in the distance matrix. igraph uses the classical multidimensional scaling by Torgerson (see reference below).

For unconnected graphs, the method will decompose the graph into weakly connected components and then lay out the components individually using the appropriate parts of the distance matrix.

Parameters:
  • dist - the distance matrix. It must be symmetric and the symmetry is not checked -- results are unspecified when a non-symmetric distance matrix is used. If this parameter is None, the shortest path lengths will be used as distances. Directed graphs are treated as undirected when calculating the shortest path lengths to ensure symmetry.
  • dim - the number of dimensions. For 2D layouts, supply 2 here; for 3D layouts, supply 3.
  • arpack_options - an ARPACKOptions object used to fine-tune the ARPACK eigenvector calculation. If omitted, the module-level variable called arpack_options is used.
Returns:
the calculated layout.

Reference: Cox & Cox: Multidimensional Scaling (1994), Chapman and Hall, London.

layout_random(dim=2)

source code 

Places the vertices of the graph randomly.

Parameters:
  • dim - the desired number of dimensions for the layout. dim=2 means a 2D layout, dim=3 means a 3D layout.
Returns:
the coordinate pairs in a list.

layout_reingold_tilford(mode="out", root=None, rootlevel=None)

source code 

Places the vertices on a 2D plane according to the Reingold-Tilford layout algorithm.

This is a tree layout. If the given graph is not a tree, a breadth-first search is executed first to obtain a possible spanning tree.

Parameters:
  • mode - specifies which edges to consider when builing the tree. If it is OUT then only the outgoing, if it is IN then only the incoming edges of a parent are considered. If it is ALL then all edges are used (this was the behaviour in igraph 0.5 and before). This parameter also influences how the root vertices are calculated if they are not given. See the root parameter.
  • root - the index of the root vertex or root vertices. if this is a non-empty vector then the supplied vertex IDs are used as the roots of the trees (or a single tree if the graph is connected. If this is None or an empty list, the root vertices are automatically calculated based on topological sorting, performed with the opposite of the mode argument.
  • rootlevel - this argument is useful when drawing forests which are not trees. It specifies the level of the root vertices for every tree in the forest.
Returns:
the calculated layout.

See Also: layout_reingold_tilford_circular

Reference: EM Reingold, JS Tilford: Tidier Drawings of Trees. IEEE Transactions on Software Engineering 7:22, 223-228, 1981.

layout_reingold_tilford_circular(mode="out", root=None, rootlevel=None)

source code 

Circular Reingold-Tilford layout for trees.

This layout is similar to the Reingold-Tilford layout, but the vertices are placed in a circular way, with the root vertex in the center.

See layout_reingold_tilford for the explanation of the parameters.

Returns:
the calculated layout.

See Also: layout_reingold_tilford

Reference: EM Reingold, JS Tilford: Tidier Drawings of Trees. IEEE Transactions on Software Engineering 7:22, 223-228, 1981.

layout_star(center=0, order=None)

source code 

Calculates a star-like layout for the graph.

Parameters:
  • center - the ID of the vertex to put in the center
  • order - a numeric vector giving the order of the vertices (including the center vertex!). If it is None, the vertices will be placed in increasing vertex ID order.
Returns:
the calculated layout.

linegraph()

source code 

Returns the line graph of the graph.

The line graph L(G) of an undirected graph is defined as follows: L(G) has one vertex for each edge in G and two vertices in L(G) are connected iff their corresponding edges in the original graph share an end point.

The line graph of a directed graph is slightly different: two vertices are connected by a directed edge iff the target of the first vertex's corresponding edge is the same as the source of the second vertex's corresponding edge.

maxdegree(vertices=None, mode=ALL, loops=False)

source code 

Returns the maximum degree of a vertex set in the graph.

This method accepts a single vertex ID or a list of vertex IDs as a parameter, and returns the degree of the given vertices (in the form of a single integer or a list, depending on the input parameter).

Parameters:
  • vertices - a single vertex ID or a list of vertex IDs, or None meaning all the vertices in the graph.
  • mode - the type of degree to be returned (OUT for out-degrees, IN IN for in-degrees or ALL for the sum of them).
  • loops - whether self-loops should be counted.

maxflow(source, target, capacity=None)

source code 

Returns the maximum flow between the source and target vertices.

Parameters:
  • source - the source vertex ID
  • target - the target vertex ID
  • capacity - the capacity of the edges. It must be a list or a valid attribute name or None. In the latter case, every edge will have the same capacity.
Returns:
a tuple containing the following: the value of the maximum flow between the given vertices, the flow value on all the edges, the edge IDs that are part of the corresponding minimum cut, and the vertex IDs on one side of the cut. For directed graphs, the flow value vector gives the flow value on each edge. For undirected graphs, the flow value is positive if the flow goes from the smaller vertex ID to the bigger one and negative if the flow goes from the bigger vertex ID to the smaller.

Attention: this function has a more convenient interface in class Graph which wraps the result in a Flow object. It is advised to use that.

maxflow_value(source, target, capacity=None)

source code 

Returns the value of the maximum flow between the source and target vertices.

Parameters:
  • source - the source vertex ID
  • target - the target vertex ID
  • capacity - the capacity of the edges. It must be a list or a valid attribute name or None. In the latter case, every edge will have the same capacity.
Returns:
the value of the maximum flow between the given vertices

maximal_cliques(min=0, max=0)

source code 

Returns the maximal cliques of the graph as a list of tuples.

A maximal clique is a clique which can't be extended by adding any other vertex to it. A maximal clique is not necessarily one of the largest cliques in the graph.

Parameters:
  • min - the minimum size of maximal cliques to be returned. If zero or negative, no lower bound will be used.
  • max - the maximum size of maximal cliques to be returned. If zero or negative, no upper bound will be used. If nonzero, the size of every maximal clique found will be compared to this value and a clique will be returned only if its size is smaller than this limit.

See Also: largest_cliques() for the largest cliques.

maximal_independent_vertex_sets()

source code 

Returns the maximal independent vertex sets of the graph as a list of tuples.

A maximal independent vertex set is an independent vertex set which can't be extended by adding any other vertex to it. A maximal independent vertex set is not necessarily one of the largest independent vertex sets in the graph.

See Also: largest_independent_vertex_sets() for the largest independent vertex sets

Reference: S. Tsukiyama, M. Ide, H. Ariyoshi and I. Shirawaka: A new algorithm for generating all the maximal independent sets. SIAM J Computing, 6:505--517, 1977.

mincut(capacity=None)

source code 

Calculates the minimum cut in a graph.

The minimum cut is the minimum set of edges which needs to be removed to disconnect the graph. The minimum is calculated using the weights (capacities) of the edges, so the cut with the minimum total capacity is calculated. For undirected graphs, it uses the Stoer-Wagner algorithm as described in the reference given below.

Returns:
the value of the minimum cut, the IDs of vertices in the first and second partition, and the IDs of edges in the cut, packed in a 4-tuple

Attention: this function has a more convenient interface in class Graph which wraps the result in a Cut object. It is advised to use that.

Reference: M. Stoer, F. Wagner: A simple min-cut algorithm. Journal of the ACM 44(4):585-591, 1997.

mincut_value(source=-1, target=-1, capacity=None)

source code 

Returns the minimum cut between the source and target vertices.

Parameters:
  • source - the source vertex ID. If negative, the calculation is done for every vertex except the target and the minimum is returned.
  • target - the target vertex ID. If negative, the calculation is done for every vertex except the source and the minimum is returned.
  • capacity - the capacity of the edges. It must be a list or a valid attribute name or None. In the latter case, every edge will have the same capacity.
Returns:
the value of the minimum cut between the given vertices

minimum_size_separators()

source code 

Returns a list containing all separator vertex sets of minimum size.

A vertex set is a separator if its removal disconnects the graph. This method lists all the separators for which no smaller separator set exists in the given graph.

Returns:
a list where each item lists the vertex indices of a given separator of minimum size.

Reference: Arkady Kanevsky: Finding all minimum-size separating vertex sets in a graph. Networks 23:533--541, 1993.

modularity(membership, weights=None)

source code 

Calculates the modularity of the graph with respect to some vertex types.

The modularity of a graph w.r.t. some division measures how good the division is, or how separated are the different vertex types from each other. It is defined as Q=1/(2m) * sum(Aij-ki*kj/(2m)delta(ci,cj),i,j). m is the number of edges, Aij is the element of the A adjacency matrix in row i and column j, ki is the degree of node i, kj is the degree of node j, and Ci and cj are the types of the two vertices (i and j). delta(x,y) is one iff x=y, 0 otherwise.

If edge weights are given, the definition of modularity is modified as follows: Aij becomes the weight of the corresponding edge, ki is the total weight of edges incident on vertex i, kj is the total weight of edges incident on vertex j and m is the total edge weight in the graph.

Parameters:
  • membership - the membership vector, e.g. the vertex type index for each vertex.
  • weights - optional edge weights or None if all edges are weighed equally.
Returns:
the modularity score. Score larger than 0.3 usually indicates strong community structure.

Attention: method overridden in Graph to allow VertexClustering objects as a parameter. This method is not strictly necessary, since the VertexClustering class provides a variable called modularity.

Reference: MEJ Newman and M Girvan: Finding and evaluating community structure in networks. Phys Rev E 69 026113, 2004.

motifs_randesu(size=3, cut_prob=None, callback=None)

source code 

Counts the number of motifs in the graph

Motifs are small subgraphs of a given structure in a graph. It is argued that the motif profile (ie. the number of different motifs in the graph) is characteristic for different types of networks and network function is related to the motifs in the graph.

This function is able to find the different motifs of size three and four (ie. the number of different subgraphs with three and four vertices) in the network.

In a big network the total number of motifs can be very large, so it takes a lot of time to find all of them. In such cases, a sampling method can be used. This function is capable of doing sampling via the cut_prob argument. This argument gives the probability that a branch of the motif search tree will not be explored.

Parameters:
  • size - the size of the motifs (3 or 4).
  • cut_prob - the cut probabilities for different levels of the search tree. This must be a list of length size or None to find all motifs.
  • callback - None or a callable that will be called for every motif found in the graph. The callable must accept three parameters: the graph itself, the list of vertices in the motif and the isomorphy class of the motif (see Graph.isoclass()). The search will stop when the callback returns an object with a non-zero truth value or raises an exception.
Returns:
the list of motifs if callback is None, or None otherwise

Reference: S. Wernicke and F. Rasche: FANMOD: a tool for fast network motif detection, Bioinformatics 22(9), 1152--1153, 2006.

See Also: Graph.motifs_randesu_no()

motifs_randesu_estimate(size=3, cut_prob=None, sample)

source code 

Counts the total number of motifs in the graph

Motifs are small subgraphs of a given structure in a graph. This function estimates the total number of motifs in a graph without assigning isomorphism classes to them by extrapolating from a random sample of vertices.

Parameters:
  • size - the size of the motifs (3 or 4).
  • cut_prob - the cut probabilities for different levels of the search tree. This must be a list of length size or None to find all motifs.
  • sample - the size of the sample or the vertex IDs of the vertices to be used for sampling.

Reference: S. Wernicke and F. Rasche: FANMOD: a tool for fast network motif detection, Bioinformatics 22(9), 1152--1153, 2006.

See Also: Graph.motifs_randesu()

motifs_randesu_no(size=3, cut_prob=None)

source code 

Counts the total number of motifs in the graph

Motifs are small subgraphs of a given structure in a graph. This function counts the total number of motifs in a graph without assigning isomorphism classes to them.

Parameters:
  • size - the size of the motifs (3 or 4).
  • cut_prob - the cut probabilities for different levels of the search tree. This must be a list of length size or None to find all motifs.

Reference: S. Wernicke and F. Rasche: FANMOD: a tool for fast network motif detection, Bioinformatics 22(9), 1152--1153, 2006.

See Also: Graph.motifs_randesu()

neighborhood(vertices=None, order=1, mode=ALL)

source code 

For each vertex specified by vertices, returns the vertices reachable from that vertex in at most order steps.

Parameters:
  • vertices - a single vertex ID or a list of vertex IDs, or None meaning all the vertices in the graph.
  • mode - specifies how to take into account the direction of the edges if a directed graph is analyzed. "out" means that only the outgoing edges are followed, so all vertices reachable from the source vertex in at most order steps are counted. "in" means that only the incoming edges are followed (in reverse direction of course), so all vertices from which the source vertex is reachable in at most order steps are counted. "all" treats directed edges as undirected.
Returns:
a single list specifying the neighborhood if vertices was an integer specifying a single vertex index, or a list of lists if vertices was a list or None.

neighborhood_size(vertices=None, order=1, mode=ALL)

source code 

For each vertex specified by vertices, returns the number of vertices reachable from that vertex in at most order steps.

Parameters:
  • vertices - a single vertex ID or a list of vertex IDs, or None meaning all the vertices in the graph.
  • mode - specifies how to take into account the direction of the edges if a directed graph is analyzed. "out" means that only the outgoing edges are followed, so all vertices reachable from the source vertex in at most order steps are counted. "in" means that only the incoming edges are followed (in reverse direction of course), so all vertices from which the source vertex is reachable in at most order steps are counted. "all" treats directed edges as undirected.
Returns:
a single number specifying the neighborhood size if vertices was an integer specifying a single vertex index, or a list of sizes if vertices was a list or None.

neighbors(vertex, mode=ALL)

source code 

Returns adjacent vertices to a given vertex.

Parameters:
  • vertex - a vertex ID
  • mode - whether to return only predecessors (OUT), successors (IN) or both (ALL). Ignored for undirected graphs.

path_length_hist(directed=True)

source code 

Calculates the path length histogram of the graph

Parameters:
  • directed - whether to consider directed paths
Returns:
a tuple. The first item of the tuple is a list of path lengths, the ith element of the list contains the number of paths with length i+1. The second item contains the number of unconnected vertex pairs as a float (since it might not fit into an integer)

Attention: this function is wrapped in a more convenient syntax in the derived class Graph. It is advised to use that instead of this version.

permute_vertices(permutation)

source code 

Permutes the vertices of the graph according to the given permutation and returns the new graph.

Vertex k of the original graph will become vertex permutation[k] in the new graph. No validity checks are performed on the permutation vector.

Returns:
the new graph

personalized_pagerank(vertices=None, directed=True, damping=0.85, reset=None, reset_vertices=None, weights=None, arpack_options=None)

source code 

Calculates the personalized PageRank values of a graph.

The personalized PageRank calculation is similar to the PageRank calculation, but the random walk is reset to a non-uniform distribution over the vertices in every step with probability 1-damping instead of a uniform distribution.

Parameters:
  • vertices - the indices of the vertices being queried. None means all of the vertices.
  • directed - whether to consider directed paths.
  • damping - the damping factor. 1-damping is the PageRank value for vertices with no incoming links.
  • reset - the distribution over the vertices to be used when resetting the random walk. Can be a sequence, an iterable or a vertex attribute name as long as they return a list of floats whose length is equal to the number of vertices. If None, a uniform distribution is assumed, which makes the method equivalent to the original PageRank algorithm.
  • reset_vertices - an alternative way to specify the distribution over the vertices to be used when resetting the random walk. Simply supply a list of vertex IDs here, or a VertexSeq or a Vertex. Resetting will take place using a uniform distribution over the specified vertices.
  • weights - edge weights to be used. Can be a sequence or iterable or even an edge attribute name.
  • arpack_options - an ARPACKOptions object used to fine-tune the ARPACK eigenvector calculation. If omitted, the module-level variable called arpack_options is used.
Returns:
a list with the personalized PageRank values of the specified vertices.

predecessors(vertex)

source code 

Returns the predecessors of a given vertex.

Equivalent to calling the Graph.neighbors method with type=IN.

radius(mode=OUT)

source code 

Calculates the radius of the graph.

The radius of a graph is defined as the minimum eccentricity of its vertices (see eccentricity()).

Parameters:
  • mode - what kind of paths to consider for the calculation in case of directed graphs. OUT considers paths that follow edge directions, IN considers paths that follow the opposite edge directions, ALL ignores edge directions. The argument is ignored for undirected graphs.
Returns:
the radius

reciprocity(ignore_loops=True, mode="default")

source code 

Reciprocity defines the proportion of mutual connections in a directed graph. It is most commonly defined as the probability that the opposite counterpart of a directed edge is also included in the graph. This measure is calculated if mode is "default".

Prior to igraph 0.6, another measure was implemented, defined as the probability of mutual connection between a vertex pair if we know that there is a (possibly non-mutual) connection between them. In other words, (unordered) vertex pairs are classified into three groups: (1) disconnected, (2) non-reciprocally connected and (3) reciprocally connected. The result is the size of group (3), divided by the sum of sizes of groups (2) and (3). This measure is calculated if mode is "ratio".

Parameters:
  • ignore_loops - whether loop edges should be ignored.
  • mode - the algorithm to use to calculate the reciprocity; see above for more details.
Returns:
the reciprocity of the graph

rewire(n=1000, mode="simple")

source code 

Randomly rewires the graph while preserving the degree distribution.

Please note that the rewiring is done "in-place", so the original graph will be modified. If you want to preserve the original graph, use the copy method before.

Parameters:
  • n - the number of rewiring trials.
  • mode - the rewiring algorithm to use. It can either be "simple" or "loops"; the former does not create or destroy loop edges while the latter does.

rewire_edges(prob, loops=False, multiple=False)

source code 

Rewires the edges of a graph with constant probability.

Each endpoint of each edge of the graph will be rewired with a constant probability, given in the first argument.

Please note that the rewiring is done "in-place", so the original graph will be modified. If you want to preserve the original graph, use the copy method before.

Parameters:
  • prob - rewiring probability
  • loops - whether the algorithm is allowed to create loop edges
  • multiple - whether the algorithm is allowed to create multiple edges.

shortest_paths(source=None, target=None, weights=None, mode=OUT)

source code 

Calculates shortest path lengths for given vertices in a graph.

The algorithm used for the calculations is selected automatically: a simple BFS is used for unweighted graphs, Dijkstra's algorithm is used when all the weights are positive. Otherwise, the Bellman-Ford algorithm is used if the number of requested source vertices is larger than 100 and Johnson's algorithm is used otherwise.

Parameters:
  • source - a list containing the source vertex IDs which should be included in the result. If None, all vertices will be considered.
  • target - a list containing the target vertex IDs which should be included in the result. If None, all vertices will be considered.
  • weights - a list containing the edge weights. It can also be an attribute name (edge weights are retrieved from the given attribute) or None (all edges have equal weight).
  • mode - the type of shortest paths to be used for the calculation in directed graphs. OUT means only outgoing, IN means only incoming paths. ALL means to consider the directed graph as an undirected one.
Returns:
the shortest path lengths for given vertices in a matrix

similarity_dice(vertices=None, pairs=None, mode=IGRAPH_ALL, loops=True)

source code 

Dice similarity coefficient of vertices.

The Dice similarity coefficient of two vertices is twice the number of their common neighbors divided by the sum of their degrees. This coefficient is very similar to the Jaccard coefficient, but usually gives higher similarities than its counterpart.

Parameters:
  • vertices - the vertices to be analysed. If None and pairs is also None, all vertices will be considered.
  • pairs - the vertex pairs to be analysed. If this is given, vertices must be None, and the similarity values will be calculated only for the given pairs. Vertex pairs must be specified as tuples of vertex IDs.
  • mode - which neighbors should be considered for directed graphs. Can be ALL, IN or OUT, ignored for undirected graphs.
  • loops - whether vertices should be considered adjacent to themselves. Setting this to True assumes a loop edge for all vertices even if none is present in the graph. Setting this to False may result in strange results: nonadjacent vertices may have larger similarities compared to the case when an edge is added between them -- however, this might be exactly the result you want to get.
Returns:
the pairwise similarity coefficients for the vertices specified, in the form of a matrix if pairs is None or in the form of a list if pairs is not None.

similarity_inverse_log_weighted(vertices=None, mode=IGRAPH_ALL)

source code 

Inverse log-weighted similarity coefficient of vertices.

Each vertex is assigned a weight which is 1 / log(degree). The log-weighted similarity of two vertices is the sum of the weights of their common neighbors.

Parameters:
  • vertices - the vertices to be analysed. If None, all vertices will be considered.
  • mode - which neighbors should be considered for directed graphs. Can be ALL, IN or OUT, ignored for undirected graphs. IN means that the weights are determined by the out-degrees, OUT means that the weights are determined by the in-degrees.
Returns:
the pairwise similarity coefficients for the vertices specified, in the form of a matrix (list of lists).

similarity_jaccard(vertices=None, pairs=None, mode=IGRAPH_ALL, loops=True)

source code 

Jaccard similarity coefficient of vertices.

The Jaccard similarity coefficient of two vertices is the number of their common neighbors divided by the number of vertices that are adjacent to at least one of them.

Parameters:
  • vertices - the vertices to be analysed. If None and pairs is also None, all vertices will be considered.
  • pairs - the vertex pairs to be analysed. If this is given, vertices must be None, and the similarity values will be calculated only for the given pairs. Vertex pairs must be specified as tuples of vertex IDs.
  • mode - which neighbors should be considered for directed graphs. Can be ALL, IN or OUT, ignored for undirected graphs.
  • loops - whether vertices should be considered adjacent to themselves. Setting this to True assumes a loop edge for all vertices even if none is present in the graph. Setting this to False may result in strange results: nonadjacent vertices may have larger similarities compared to the case when an edge is added between them -- however, this might be exactly the result you want to get.
Returns:
the pairwise similarity coefficients for the vertices specified, in the form of a matrix if pairs is None or in the form of a list if pairs is not None.

simplify(multiple=True, loops=True, combine_edges=None)

source code 

Simplifies a graph by removing self-loops and/or multiple edges.

For example, suppose you have a graph with an edge attribute named weight. graph.simplify(combine_edges=max) will take the maximum of the weights of multiple edges and assign that weight to the collapsed edge. graph.simplify(combine_edges=sum) will take the sum of the weights. You can also write graph.simplify(combine_edges=dict(weight="sum")) or graph.simplify(combine_edges=dict(weight=sum)), since sum is recognised both as a Python built-in function and as a string constant.

Parameters:
  • multiple - whether to remove multiple edges.
  • loops - whether to remove loops.
  • combine_edges - specifies how to combine the attributes of multiple edges between the same pair of vertices into a single attribute. If it is None, only one of the edges will be kept and all the attributes will be lost. If it is a function, the attributes of multiple edges will be collected and passed on to that function which will return the new attribute value that has to be assigned to the single collapsed edge. It can also be one of the following string constants:
    • "ignore": all the edge attributes will be ignored.
    • "sum": the sum of the edge attribute values will be used for the new edge.
    • "product": the product of the edge attribute values will be used for the new edge.
    • "mean": the mean of the edge attribute values will be used for the new edge.
    • "median": the median of the edge attribute values will be used for the new edge.
    • "min": the minimum of the edge attribute values will be used for the new edge.
    • "max": the maximum of the edge attribute values will be used for the new edge.
    • "first": the attribute value of the first edge in the collapsed set will be used for the new edge.
    • "last": the attribute value of the last edge in the collapsed set will be used for the new edge.
    • "random": a randomly selected value will be used for the new edge
    • "concat": the attribute values will be concatenated for the new edge.

    You can also use a dict mapping edge attribute names to functions or the above string constants if you want to make the behaviour of the simplification process depend on the name of the attribute. None is a special key in this dict, its value will be used for all the attributes not specified explicitly in the dictionary.

strength(vertices, mode=ALL, loops=True, weights=None)

source code 

Returns the strength (weighted degree) of some vertices from the graph

This method accepts a single vertex ID or a list of vertex IDs as a parameter, and returns the strength (that is, the sum of the weights of all incident edges) of the given vertices (in the form of a single integer or a list, depending on the input parameter).

Parameters:
  • vertices - a single vertex ID or a list of vertex IDs
  • mode - the type of degree to be returned (OUT for out-degrees, IN IN for in-degrees or ALL for the sum of them).
  • loops - whether self-loops should be counted.
  • weights - edge weights to be used. Can be a sequence or iterable or even an edge attribute name.

subcomponent(v, mode=ALL)

source code 

Determines the indices of vertices which are in the same component as a given vertex.

Parameters:
  • v - the index of the vertex used as the source/destination
  • mode - if equals to IN, returns the vertex IDs from where the given vertex can be reached. If equals to OUT, returns the vertex IDs which are reachable from the given vertex. If equals to ALL, returns all vertices within the same component as the given vertex, ignoring edge directions. Note that this is not equal to calculating the union of the results of IN and OUT.
Returns:
the indices of vertices which are in the same component as a given vertex.

subgraph_edges(edges, delete_vertices=True)

source code 

Returns a subgraph spanned by the given edges.

Parameters:
  • edges - a list containing the edge IDs which should be included in the result.
  • delete_vertices - if True, vertices not incident on any of the specified edges will be deleted from the result. If False, all vertices will be kept.
Returns:
the subgraph

subisomorphic_vf2(other, color1=None, color2=None, edge_color1=None, edge_color2=None, return_mapping_12=False, return_mapping_21=False, callback=None, node_compat_fn=None, edge_compat_fn=None)

source code 

Checks whether a subgraph of the graph is isomorphic to another graph.

Vertex and edge colors may be used to restrict the isomorphisms, as only vertices and edges with the same color will be allowed to match each other.

Parameters:
  • other - the other graph with which we want to compare the graph.
  • color1 - optional vector storing the coloring of the vertices of the first graph. If None, all vertices have the same color.
  • color2 - optional vector storing the coloring of the vertices of the second graph. If None, all vertices have the same color.
  • edge_color1 - optional vector storing the coloring of the edges of the first graph. If None, all edges have the same color.
  • edge_color2 - optional vector storing the coloring of the edges of the second graph. If None, all edges have the same color.
  • return_mapping_12 - if True, calculates the mapping which maps the vertices of the first graph to the second. The mapping can contain -1 if a given node is not mapped.
  • return_mapping_21 - if True, calculates the mapping which maps the vertices of the second graph to the first. The mapping can contain -1 if a given node is not mapped.
  • callback - if not None, the subisomorphism search will not stop at the first match; it will call this callback function instead for every subisomorphism found. The callback function must accept four arguments: the first graph, the second graph, a mapping from the nodes of the first graph to the second, and a mapping from the nodes of the second graph to the first. The function must return True if the search should continue or False otherwise.
  • node_compat_fn - a function that receives the two graphs and two node indices (one from the first graph, one from the second graph) and returns True if the nodes given by the two indices are compatible (i.e. they could be matched to each other) or False otherwise. This can be used to restrict the set of isomorphisms based on node-specific criteria that are too complicated to be represented by node color vectors (i.e. the color1 and color2 parameters). None means that every node is compatible with every other node.
  • edge_compat_fn - a function that receives the two graphs and two edge indices (one from the first graph, one from the second graph) and returns True if the edges given by the two indices are compatible (i.e. they could be matched to each other) or False otherwise. This can be used to restrict the set of isomorphisms based on edge-specific criteria that are too complicated to be represented by edge color vectors (i.e. the edge_color1 and edge_color2 parameters). None means that every edge is compatible with every other node.
Returns:
if no mapping is calculated, the result is True if the graph contains a subgraph that's isomorphic to the given one, False otherwise. If any or both mappings are calculated, the result is a 3-tuple, the first element being the above mentioned boolean, the second element being the 1 -> 2 mapping and the third element being the 2 -> 1 mapping. If the corresponding mapping was not calculated, None is returned in the appropriate element of the 3-tuple.

successors(vertex)

source code 

Returns the successors of a given vertex.

Equivalent to calling the Graph.neighbors method with type=OUT.

to_directed(mutual=True)

source code 

Converts an undirected graph to directed.

Parameters:
  • mutual - True if mutual directed edges should be created for every undirected edge. If False, a directed edge with arbitrary direction is created.

to_undirected(mode="collapse", combine_edges=None)

source code 

Converts a directed graph to undirected.

Parameters:
  • mode - specifies what to do with multiple directed edges going between the same vertex pair. True or "collapse" means that only a single edge should be created from multiple directed edges. False or "each" means that every edge will be kept (with the arrowheads removed). "mutual" creates one undirected edge for each mutual directed edge pair.
  • combine_edges - specifies how to combine the attributes of multiple edges between the same pair of vertices into a single attribute. See Graph.simplify() for more details.

topological_sorting(mode=OUT)

source code 

Calculates a possible topological sorting of the graph.

Returns a partial sorting and issues a warning if the graph is not a directed acyclic graph.

Parameters:
  • mode - if OUT, vertices are returned according to the forward topological order -- all vertices come before their successors. If IN, all vertices come before their ancestors.
Returns:
a possible topological ordering as a list

transitivity_avglocal_undirected(mode="nan")

source code 

Calculates the average of the vertex transitivities of the graph.

The transitivity measures the probability that two neighbors of a vertex are connected. In case of the average local transitivity, this probability is calculated for each vertex and then the average is taken. Vertices with less than two neighbors require special treatment, they will either be left out from the calculation or they will be considered as having zero transitivity, depending on the mode parameter.

Note that this measure is different from the global transitivity measure (see transitivity_undirected()) as it simply takes the average local transitivity across the whole network.

Parameters:
  • mode - defines how to treat vertices with degree less than two. If TRANSITIVITT_ZERO or "zero", these vertices will have zero transitivity. If TRANSITIVITY_NAN or "nan", these vertices will be excluded from the average.

See Also: transitivity_undirected(), transitivity_local_undirected()

Reference: D. J. Watts and S. Strogatz: Collective dynamics of small-world networks. Nature 393(6884):440-442, 1998.

transitivity_local_undirected(vertices=None, mode="nan", weights=None)

source code 

Calculates the local transitivity (clustering coefficient) of the given vertices in the graph.

The transitivity measures the probability that two neighbors of a vertex are connected. In case of the local transitivity, this probability is calculated separately for each vertex.

Note that this measure is different from the global transitivity measure (see transitivity_undirected()) as it calculates a transitivity value for each vertex individually.

The traditional local transitivity measure applies for unweighted graphs only. When the weights argument is given, this function calculates the weighted local transitivity proposed by Barrat et al (see references).

Parameters:
  • vertices - a list containing the vertex IDs which should be included in the result. None means all of the vertices.
  • mode - defines how to treat vertices with degree less than two. If TRANSITIVITT_ZERO or "zero", these vertices will have zero transitivity. If TRANSITIVITY_NAN or "nan", these vertices will have NaN (not a number) as their transitivity.
  • weights - edge weights to be used. Can be a sequence or iterable or even an edge attribute name.
Returns:
the transitivities for the given vertices in a list

See Also: transitivity_undirected(), transitivity_avglocal_undirected()

Reference:
  • Watts DJ and Strogatz S: Collective dynamics of small-world networks. Nature 393(6884):440-442, 1998.
  • Barrat A, Barthelemy M, Pastor-Satorras R and Vespignani A: The architecture of complex weighted networks. PNAS 101, 3747 (2004). http://arxiv.org/abs/cond-mat/0311416.

transitivity_undirected(mode="nan")

source code 

Calculates the global transitivity (clustering coefficient) of the graph.

The transitivity measures the probability that two neighbors of a vertex are connected. More precisely, this is the ratio of the triangles and connected triplets in the graph. The result is a single real number. Directed graphs are considered as undirected ones.

Note that this measure is different from the local transitivity measure (see transitivity_local_undirected()) as it calculates a single value for the whole graph.

Parameters:
  • mode - if TRANSITIVITY_ZERO or "zero", the result will be zero if the graph does not have any triplets. If "nan" or TRANSITIVITY_NAN, the result will be NaN (not a number).
Returns:
the transitivity

See Also: transitivity_local_undirected(), transitivity_avglocal_undirected()

Reference: S. Wasserman and K. Faust: Social Network Analysis: Methods and Applications. Cambridge: Cambridge University Press, 1994.

triad_census()

source code 

Triad census, as defined by Davis and Leinhardt

Calculating the triad census means classifying every triplets of vertices in a directed graph. A triplet can be in one of 16 states, these are listed in the documentation of the C interface of igraph.

Attention: this function has a more convenient interface in class Graph which wraps the result in a TriadCensus object. It is advised to use that. The name of the triplet classes are also documented there.

unfold_tree(sources=None, mode=OUT)

source code 

Unfolds the graph using a BFS to a tree by duplicating vertices as necessary.

Parameters:
  • sources - the source vertices to start the unfolding from. It should be a list of vertex indices, preferably one vertex from each connected component. You can use Graph.topological_sorting() to determine a suitable set. A single vertex index is also accepted.
  • mode - which edges to follow during the BFS. OUT follows outgoing edges, IN follows incoming edges, ALL follows both. Ignored for undirected graphs.
Returns:
the unfolded tree graph and a mapping from the new vertex indices to the old ones.

union(graphs)

source code 

Creates the union of two (or more) graphs.

Parameters:
  • graphs - the list of graphs to be united with the current one.

vcount()

source code 

Counts the number of vertices.

Returns: integer
the number of vertices in the graph.

vertex_attributes()

source code 
Returns:
the attribute name list of the graph's vertices

vertex_connectivity(source=-1, target=-1, checks=True, neighbors="error")

source code 

Calculates the vertex connectivity of the graph or between some vertices.

The vertex connectivity between two given vertices is the number of vertices that have to be removed in order to disconnect the two vertices into two separate components. This is also the number of vertex disjoint directed paths between the vertices (apart from the source and target vertices of course). The vertex connectivity of the graph is the minimal vertex connectivity over all vertex pairs.

This method calculates the vertex connectivity of a given vertex pair if both the source and target vertices are given. If none of them is given (or they are both negative), the overall vertex connectivity is returned.

Parameters:
  • source - the source vertex involved in the calculation.
  • target - the target vertex involved in the calculation.
  • checks - if the whole graph connectivity is calculated and this is True, igraph performs some basic checks before calculation. If the graph is not strongly connected, then the connectivity is obviously zero. If the minimum degree is one, then the connectivity is also one. These simple checks are much faster than checking the entire graph, therefore it is advised to set this to True. The parameter is ignored if the connectivity between two given vertices is computed.
  • neighbors - tells igraph what to do when the two vertices are connected. "error" raises an exception, "infinity" returns infinity, "ignore" ignores the edge.
Returns:
the vertex connectivity

write_dimacs(f, source, target, capacity=None)

source code 

Writes the graph in DIMACS format to the given file.

Parameters:
  • f - the name of the file to be written or a Python file handle
  • source - the source vertex ID
  • target - the target vertex ID
  • capacity - the capacities of the edges in a list. If it is not a list, the corresponding edge attribute will be used to retrieve capacities.

write_dot(f)

source code 

Writes the graph in DOT format to the given file.

DOT is the format used by the GraphViz software package.

Parameters:
  • f - the name of the file to be written or a Python file handle

write_edgelist(f)

source code 

Writes the edge list of a graph to a file.

Directed edges are written in (from, to) order.

Parameters:
  • f - the name of the file to be written or a Python file handle

write_gml(f, creator=None, ids=None)

source code 

Writes the graph in GML format to the given file.

Parameters:
  • f - the name of the file to be written or a Python file handle
  • creator - optional creator information to be written to the file. If None, the current date and time is added.
  • ids - optional numeric vertex IDs to use in the file. This must be a list of integers or None. If None, the id attribute of the vertices are used, or if they don't exist, numeric vertex IDs will be generated automatically.

write_graphml(f)

source code 

Writes the graph to a GraphML file.

Parameters:
  • f - the name of the file to be written or a Python file handle

write_leda(f, names="name", weights="weights")

source code 

Writes the graph to a file in LEDA native format.

The LEDA format supports at most one attribute per vertex and edge. You can specify which vertex and edge attribute you want to use. Note that the name of the attribute is not saved in the LEDA file.

Parameters:
  • f - the name of the file to be written or a Python file handle
  • names - the name of the vertex attribute to be stored along with the vertices. It is usually used to store the vertex names (hence the name of the keyword argument), but you may also use a numeric attribute. If you don't want to store any vertex attributes, supply None here.
  • weights - the name of the edge attribute to be stored along with the edges. It is usually used to store the edge weights (hence the name of the keyword argument), but you may also use a string attribute. If you don't want to store any edge attributes, supply None here.

write_lgl(f, names="name", weights="weights", isolates=True)

source code 

Writes the edge list of a graph to a file in .lgl format.

Note that multiple edges and/or loops break the LGL software, but igraph does not check for this condition. Unless you know that the graph does not have multiple edges and/or loops, it is wise to call simplify() before saving.

Parameters:
  • f - the name of the file to be written or a Python file handle
  • names - the name of the vertex attribute containing the name of the vertices. If you don't want to store vertex names, supply None here.
  • weights - the name of the edge attribute containing the weight of the vertices. If you don't want to store weights, supply None here.
  • isolates - whether to include isolated vertices in the output.

write_ncol(f, names="name", weights="weights")

source code 

Writes the edge list of a graph to a file in .ncol format.

Note that multiple edges and/or loops break the LGL software, but igraph does not check for this condition. Unless you know that the graph does not have multiple edges and/or loops, it is wise to call simplify() before saving.

Parameters:
  • f - the name of the file to be written or a Python file handle
  • names - the name of the vertex attribute containing the name of the vertices. If you don't want to store vertex names, supply None here.
  • weights - the name of the edge attribute containing the weight of the vertices. If you don't want to store weights, supply None here.

write_pajek(f)

source code 

Writes the graph in Pajek format to the given file.

Parameters:
  • f - the name of the file to be written or a Python file handle