Package igraph :: Class Graph

Class Graph

object --+    
         |    
 GraphBase --+
             |
            Graph

Generic graph.

This class is built on top of GraphBase, so the order of the methods in the Epydoc documentation is a little bit obscure: inherited methods come after the ones implemented directly in the subclass. Graph provides many functions that GraphBase does not, mostly because these functions are not speed critical and they were easier to implement in Python than in pure C. An example is the attribute handling in the constructor: the constructor of Graph accepts three dictionaries corresponding to the graph, vertex and edge attributes while the constructor of GraphBase does not. This extension was needed to make Graph serializable through the pickle module.

Instance Methods

[hide private]

__add__(self, other)
Copies the graph and extends the copy depending on the type of the other object given.

__coerce__(self, other)
Coercion rules.

__iadd__(self, other)
In-place addition (disjoint union).

__init__(n=None, edges=None, directed=None, graph_attrs=None, vertex_attrs=None, edge_attrs=None)
Constructs a graph from scratch.

__isub__(self, other)
In-place subtraction (difference).

__mul__(self, other)
Copies exact replicas of the original graph an arbitrary number of times.

__plot__(self, context, bbox, palette, *args, **kwds)
Plots the graph to the given Cairo context in the given bounding box

__reduce__(self)
Support for pickling.

__sub__(self, other)
Removes the given object(s) from the graph

_get_es(self)

_get_vs(self)

adhesion(source=-1, target=-1, checks=True)
Calculates the edge connectivity of the graph or between some vertices.

alpha()
Returns the independence number of the graph.

biconnected_components(return_articulation_points=False)
Calculates the biconnected components of the graph.

blocks(return_articulation_points=False)
Calculates the biconnected components of the graph.

clusters(mode=STRONG)
Calculates the (strong or weak) clusters (connected components) for a given graph.

cohesion(source=-1, target=-1, checks=True, neighbors="error")
Calculates the vertex connectivity of the graph or between some vertices.

community_edge_betweenness(self, clusters=None, directed=True)
Community structure based on the betweenness of the edges in the network.

community_fastgreedy(self, weights=None)
Community structure based on the greedy optimization of modularity.

community_leading_eigenvector(clusters=None, return_merges=False)
Newman's leading eigenvector method for detecting community structure.

community_leading_eigenvector_naive(clusters=None, return_merges=False)
A naive implementation of Newman's eigenvector community structure detection.

community_walktrap(self, weights=None, steps=4)
Community detection algorithm of Latapy & Pons, based on random walks.

components(mode=STRONG)
Calculates the (strong or weak) clusters (connected components) for a given graph.

count_automorphisms_vf2(self)
Returns the number of automorphisms of the graph

cut_vertices()
Returns the list of articulation points in the graph.

degree_distribution(bin_width=1, ...)
Calculates the degree distribution of the graph.

delete_edges(self, *args, **kwds)
Deletes some edges from the graph.

dyad_census()
Calculates the dyad census of the graph.

eccentricity(self, vertices=None)
Calculates eccentricities for vertices with the given indices.

edge_disjoint_paths(source=-1, target=-1, checks=True)
Calculates the edge connectivity of the graph or between some vertices.

evcent(scale=True, weights=None, return_eigenvalue=False, arpack_options=None)
Calculates the eigenvector centralities of the vertices in a graph.

get_adjacency(self, type=2, attribute=None, default=None)
Returns the adjacency matrix of a graph.

get_adjedgelist(type=OUT)
Returns the adjacency edge list representation of the graph.

get_adjlist(type=OUT)
Returns the adjacency list representation of the graph.

get_automorphisms_vf2(self)
Returns all automorphisms of the graph

indegree(self, *args, **kwds)
Returns the in-degrees in a list.

k_core(self, *args)
Returns some k-cores of the graph.

layout(self, layout=None, *args, **kwds)
Returns the layout of the graph according to a layout algorithm.

mincut(capacity=None)
Returns a minimum cut in an undirected graph.

modularity(membership, weights=None)
Calculates the modularity score of the graph with respect to a given clustering.

omega()
Returns the clique number of the graph.

outdegree(self, *args, **kwds)
Returns the out-degrees in a list.

path_length_hist(directed=True)
Returns the path length histogram of the graph

save(self, f, format=None, *args, **kwds)
Unified writing function for graphs.

shell_index(mode=ALL)
Finds the coreness (shell index) of the vertices of the network.

shortest_paths_dijkstra(vertices, weights=None, mode=OUT)
Calculates shortest path lengths for given nodes in a graph.

summary(self, verbosity=0)
Returns basic statistics about the graph in a string

triad_census()
Calculates the triad census of the graph.

vertex_disjoint_paths(source=-1, target=-1, checks=True, neighbors="error")
Calculates the vertex connectivity of the graph or between some vertices.

write(self, f, format=None, *args, **kwds)
Unified writing function for graphs.

write_adjacency(self, f, sep=' ', eol='\n', *args, **kwds)
Writes the adjacency matrix of the graph to the given file

write_graphmlz(self, f, compresslevel=9)
Writes the graph to a zipped GraphML file.

write_pickle(self, fname=None, version=-1)
Saves the graph in Python pickled format

write_svg(self, fname, layout, width=None, height=None, labels='label', colors='color', shapes='shape', vertex_size=10, edge_colors='color', font_size=16, *args, **kwds)
Saves the graph as an SVG (Scalable Vector Graphics) file

Inherited from GraphBase: Adjacency, Asymmetric_Preference, Atlas, Barabasi, De_Bruijn, Degree_Sequence, Erdos_Renyi, Establishment, Famous, Forest_Fire, Full, Full_Citation, GRG, Growing_Random, Isoclass, Kautz, LCF, Lattice, Preference, Read_DIMACS, Read_Edgelist, Read_GML, Read_GraphML, Read_Lgl, Read_Ncol, Read_Pajek, Recent_Degree, Ring, Star, Tree, Watts_Strogatz, Weighted_Adjacency, __and__, __delitem__, __getitem__, __invert__, __len__, __new__, __or__, __rand__, __ror__, __setitem__, __str__, add_edges, add_vertices, adjacent, are_connected, articulation_points, attributes, authority_score, average_path_length, betweenness, bfs, bfsiter, bibcoupling, clique_number, cliques, closeness, cocitation, complementer, compose, constraint, convergence_degree, convergence_field_size, copy, coreness, count_isomorphisms_vf2, count_multiple, count_subisomorphisms_vf2, decompose, degree, delete_vertices, density, diameter, difference, disjoint_union, ecount, edge_attributes, edge_betweenness, edge_connectivity, eigenvector_centrality, farthest_points, get_all_shortest_paths, get_diameter, get_edgelist, get_eid, get_isomorphisms_vf2, get_shortest_paths, get_subisomorphisms_vf2, girth, hub_score, independence_number, independent_vertex_sets, intersection, is_connected, is_directed, is_loop, is_multiple, is_mutual, is_simple, isoclass, isomorphic, isomorphic_bliss, isomorphic_vf2, laplacian, largest_cliques, largest_independent_vertex_sets, layout_circle, layout_drl, layout_fruchterman_reingold, layout_fruchterman_reingold_3d, layout_graphopt, layout_grid_fruchterman_reingold, layout_kamada_kawai, layout_kamada_kawai_3d, layout_lgl, layout_random, layout_random_3d, layout_reingold_tilford, layout_reingold_tilford_circular, layout_sphere, linegraph, maxdegree, maxflow_value, maximal_cliques, maximal_independent_vertex_sets, mincut_value, motifs_randesu, motifs_randesu_estimate, motifs_randesu_no, neighbors, pagerank, pagerank_old, permute_vertices, predecessors, reciprocity, rewire, shortest_paths, similarity_dice, similarity_inverse_log_weighted, similarity_jaccard, simplify, spanning_tree, subcomponent, subgraph, subisomorphic_vf2, successors, to_directed, to_undirected, topological_sorting, transitivity_local_undirected, transitivity_undirected, union, vcount, vertex_attributes, vertex_connectivity, write_dimacs, write_dot, write_edgelist, write_gml, write_graphml, write_lgl, write_ncol, write_pajek

Inherited from object: __delattr__, __getattribute__, __hash__, __reduce_ex__, __repr__, __setattr__

Class Methods

[hide private]

Load(klass, f, format=None, *args, **kwds)
Unified reading function for graphs.

Read(klass, f, format=None, *args, **kwds)
Unified reading function for graphs.

Read_Adjacency(klass, f, sep=None, comment_char='#', attribute=None, *args, **kwds)
Constructs a graph based on an adjacency matrix from the given file

Read_GraphMLz(f, directed=True, index=0)
Reads a graph from a zipped GraphML file.

Read_Pickle(klass, fname=None)
Reads a graph from Python pickled format

_identify_format(filename)
Tries to identify the format of the graph stored in the file with the given filename.

Class Variables

[hide private]

_format_mapping = {'adj': ('Read_Adjacency', 'write_adjacency'...

_layout_mapping = {'circle': 'layout_circle', 'circle_3d': 'la...

Properties

[hide private]

es
The edge sequence of the graph

vs
The vertex sequence of the graph

Inherited from object: __class__

Method Details

[hide private]

Load(klass, f, format=None, *args, **kwds)
Class Method

Unified reading function for graphs.

This method tries to identify the format of the graph given in the first parameter and calls the corresponding reader method.

The remaining arguments are passed to the reader method without any changes.

Parameters:

f - the file containing the graph to be loaded
format - the format of the file (if known in advance). None means auto-detection. Possible values are: "ncol" (NCOL format), "lgl" (LGL format), "graphml", "graphmlz" (GraphML and gzipped GraphML format), "gml" (GML format), "net", "pajek" (Pajek format), "dimacs" (DIMACS format), "edgelist", "edges" or "edge" (edge list), "adjacency" (adjacency matrix), "pickle" (Python pickled format).

Raises:

IOError - if the file format can't be identified and none was given.

Read(klass, f, format=None, *args, **kwds)
Class Method

Unified reading function for graphs.

This method tries to identify the format of the graph given in the first parameter and calls the corresponding reader method.

The remaining arguments are passed to the reader method without any changes.

Parameters:

f - the file containing the graph to be loaded
format - the format of the file (if known in advance). None means auto-detection. Possible values are: "ncol" (NCOL format), "lgl" (LGL format), "graphml", "graphmlz" (GraphML and gzipped GraphML format), "gml" (GML format), "net", "pajek" (Pajek format), "dimacs" (DIMACS format), "edgelist", "edges" or "edge" (edge list), "adjacency" (adjacency matrix), "pickle" (Python pickled format).

Raises:

IOError - if the file format can't be identified and none was given.

Read_Adjacency(klass, f, sep=None, comment_char=`'#'`, attribute=None, *args, **kwds)
Class Method

Constructs a graph based on an adjacency matrix from the given file

Additional positional and keyword arguments not mentioned here are passed intact to Graph.Adjacency.

Parameters:

f - the name of the file to be read or a file object
sep - the string that separates the matrix elements in a row. None means an arbitrary sequence of whitespace characters.
comment_char - lines starting with this string are treated as comments.
attribute - an edge attribute name where the edge weights are stored in the case of a weighted adjacency matrix. If None, no weights are stored, values larger than 1 are considered as edge multiplicities.

Returns:

the created graph

Read_GraphMLz(f, directed=True, index=0)
Class Method

Reads a graph from a zipped GraphML file.

Parameters:

f - the name of the file
index - if the GraphML file contains multiple graphs, specified the one that should be loaded. Graph indices start from zero, so if you want to load the first graph, specify 0 here.

Returns:

the loaded graph object

Read_Pickle(klass, fname=None)
Class Method

Reads a graph from Python pickled format

Parameters:

fname - the name of the file, a stream to read from, or a string containing the pickled data. The string is assumed to hold pickled data if it is longer than 40 characters and contains a substring that's peculiar to pickled versions of an igraph Graph object.

Returns:

the created graph object.

add(self, other)
(Addition operator)

Copies the graph and extends the copy depending on the type of the other object given.

Parameters:

other - if it is an integer, the copy is extended by the given number of vertices. If it is a tuple with two elements, the copy is extended by a single edge. If it is a list of tuples, the copy is extended by multiple edges. If it is a Graph, a disjoint union is performed.

coerce(self, other)

Coercion rules.

This method is needed to allow the graph to react to additions with lists, tuples, integers, vertices, edges and so on.

iadd(self, other)

In-place addition (disjoint union).

See Also: __add__

init(n=None, edges=None, directed=None, graph_attrs=None, vertex_attrs=None, edge_attrs=None)
(Constructor)

Constructs a graph from scratch.

Parameters:

n - the number of vertices. Can be omitted.
edges - the edge list where every list item is a pair of integers. If any of the integers is larger than n-1, the number of vertices is adjusted accordingly.
directed - whether the graph should be directed
graph_attrs - the attributes of the graph as a dictionary.
vertex_attrs - the attributes of the vertices as a dictionary. Every dictionary value must be an iterable with exactly n items.
edge_attrs - the attributes of the edges as a dictionary. Every dictionary value must be an iterable with exactly m items where m is the number of edges.

Overrides: object.__init__

isub(self, other)

In-place subtraction (difference).

See Also: __sub__

mul(self, other)

Copies exact replicas of the original graph an arbitrary number of times.

Parameters:

other - if it is an integer, multiplies the graph by creating the given number of identical copies and taking the disjoint union of them.

plot(self, context, bbox, palette, *args, **kwds)

Plots the graph to the given Cairo context in the given bounding box

The visual style of vertices and edges can be modified at three places in the following order of precedence (lower indices override higher indices):

Keyword arguments of this function (or of plot() which is passed intact to Graph.__plot__().
Vertex or edge attributes, specified later in the list of keyword arguments.
igraph-wide plotting defaults (see igraph.config.Configuration)
Built-in defaults.

E.g., if the vertex_size keyword attribute is not present, but there exists a vertex attribute named size, the sizes of the vertices will be specified by that attribute.

Besides the usual self-explanatory plotting parameters (context, bbox, palette), it accepts the following keyword arguments:

layout: the layout to be used. If not an instance of Layout, it will be passed to Graph.layout to calculate the layout. Note that if you want a deterministic layout that does not change with every plot, you must either use a deterministic layout function (like Graph.layout_circle) or calculate the layout in advance and pass a Layout object here.
margin: the top, right, bottom, left margins as a 4-tuple. If it has less than 4 elements or is a single float, the elements will be re-used until the length is at least 4.
vertex_size: size of the vertices. The corresponding vertex attribute is called size. The default is 10. Vertex sizes are measured in the unit of the Cairo context on which igraph is drawing.
vertex_color: color of the vertices. The corresponding vertex attribute is color, the default is red. Colors can be specified either by common X11 color names (see the source code of igraph.colors for a list of known colors), by 3-tuples of floats (ranging between 0 and 1 for the R, G and B components), by CSS-style string specifications (#rrggbb) or by integer color indices of the specified palette.
vertex_shape: shape of the vertices. Alternatively it can be specified by the shape vertex attribute. Possibilities are: square, {circle}, {triangle}, {triangle-down} or hidden. See the source code of igraph.drawing for a list of alternative shape names that are also accepted and mapped to these.
vertex_label: labels drawn next to the vertices. The corresponding vertex attribute is label.
vertex_label_dist: distance of the midpoint of the vertex label from the center of the corresponding vertex. The corresponding vertex attribute is label_dist.
vertex_label_color: color of the label. Corresponding vertex attribute: label_color. See vertex_color for color specification syntax.
vertex_label_size: font size of the label, specified in the unit of the Cairo context on which we are drawing. Corresponding vertex attribute: label_size.
vertex_label_angle: the direction of the line connecting the midpoint of the vertex with the midpoint of the label. This can be used to position the labels relative to the vertices themselves in conjunction with vertex_label_dist. Corresponding vertex attribute: label_angle. The default is -math.pi/4.
edge_color: color of the edges. The corresponding edge attribute is color, the default is red. See vertex_color for color specification syntax.
edge_width: width of the edges in the default unit of the Cairo context on which we are drawing. The corresponding edge attribute is width, the default is 1.

reduce(self)

Support for pickling.

Overrides: object.__reduce__

sub(self, other)
(Subtraction operator)

Removes the given object(s) from the graph

Parameters:

other - if it is an integer, removes the vertex with the given ID from the graph (note that the remaining vertices will get re-indexed!). If it is a tuple, removes the given edge. If it is a graph, takes the difference of the two graphs. Accepts lists of integers or lists of tuples as well, but they can't be mixed! Also accepts Edge and EdgeSeq objects.

_identify_format(filename)
Class Method

Tries to identify the format of the graph stored in the file with the given filename. It identifies most file formats based on the extension of the file (and not on syntactic evaluation). The only exception is the adjacency matrix format and the edge list format: the first few lines of the file are evaluated to decide between the two.

Parameters:

filename - the name of the file or a file object whose name attribute is set.

Returns:

the format of the file as a string.

Note: Internal function, should not be called directly.

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

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

alpha()

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

biconnected_components(return_articulation_points=False)

Calculates the biconnected components of the graph.

Parameters:

return_articulation_points - whether to return the articulation points as well

Returns:

an OverlappingVertexClustering object describing the biconnected components and optionally the list of articulation points

Overrides: GraphBase.biconnected_components

blocks(return_articulation_points=False)

Calculates the biconnected components of the graph.

Parameters:

return_articulation_points - whether to return the articulation points as well

Returns:

an OverlappingVertexClustering object describing the biconnected components and optionally the list of articulation points

clusters(mode=STRONG)

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

Parameters:

mode - must be either STRONG or WEAK, depending on the clusters being sought. Optional, defaults to STRONG.

Returns:

a VertexClustering object

Overrides: GraphBase.clusters

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

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

community_edge_betweenness(self, clusters=None, directed=True)

Community structure based on the betweenness of the edges in the network.

The idea is that the betweenness of the edges connecting two communities is typically high, as many of the shortest paths between nodes in separate communities go through them. So we gradually remove the edge with the highest betweenness and recalculate the betweennesses after every removal. This way sooner or later the network falls of to separate components. The result of the clustering will be represented by a dendrogram.

Parameters:

clusters - the number of clusters we would like to see. This practically defines the "level" where we "cut" the dendrogram to get the membership vector of the vertices. If None, the dendrogram is cut at the level which maximizes the modularity.
directed - whether the directionality of the edges should be taken into account or not.

Returns:

a VertexClustering object. Besides the usual methods and members, this object will have a member called merges which records information used to produce the dendrogram. It is practically a list of tuples where each tuple defines two nodes which will be joined in a step. Node IDs from 0 to n-1 (where n is the number of vertices) correspond to the individual vertices, while node IDs up from n correspond to merged communities. n means the community created after the first merge, n+1 means the community created after the second merge and so on...

Overrides: GraphBase.community_edge_betweenness

community_fastgreedy(self, weights=None)

Community structure based on the greedy optimization of modularity.

This algorithm merges individual nodes into communities in a way that greedily maximizes the modularity score of the graph. It can be proven that if no merge can increase the current modularity score, the algorithm can be stopped since no further increase can be achieved.

This algorithm is said to run almost in linear time on sparse graphs.

Parameters:

weights - edge attribute name or a list containing edge weights

Returns:

an appropriate VertexClustering object.

Overrides: GraphBase.community_fastgreedy

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

community_leading_eigenvector(clusters=None, return_merges=False)

Newman's leading eigenvector method for detecting community structure. This is the proper implementation of the recursive, divisive algorithm: each split is done by maximizing the modularity regarding the original network.

Parameters:

clusters - the desired number of communities. If None, 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, so the actual number of discovered communities can be less than the desired one.
return_merges - whether the returned VertexClustering object should contain information about the merges performed on the graph.
return_merges - whether

Returns:

an appropriate VertexClustering object.

Overrides: GraphBase.community_leading_eigenvector

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

community_leading_eigenvector_naive(clusters=None, return_merges=False)

A naive implementation of Newman's eigenvector community structure detection. This function splits the network into two components according to the leading eigenvector of the modularity matrix and then recursively takes the given number of steps by splitting the communities as individual networks. This is not the correct way, however, see the reference for explanation. Consider using the correct community_leading_eigenvector method instead.

Parameters:

clusters - the desired number of communities. If None, 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, so the actual number of discovered communities can be less than the desired one.
return_merges - whether the returned VertexClustering object should contain information about the merges performed on the graph.
return_merges - whether

Returns:

an appropriate VertexClustering object.

Overrides: GraphBase.community_leading_eigenvector_naive

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

community_walktrap(self, weights=None, steps=4)

Community detection algorithm of Latapy & Pons, based on random walks.

The basic idea of the algorithm is that short random walks tend to stay in the same community. The result of the clustering will be represented as a dendrogram.

Parameters:

weights - name of an edge attribute or a list containing edge weights
steps - length of random walks to perform

Returns:

a VertexDendrogram object, initially cut at the maximum modularity.

Overrides: GraphBase.community_walktrap

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

components(mode=STRONG)

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

Parameters:

mode - must be either STRONG or WEAK, depending on the clusters being sought. Optional, defaults to STRONG.

Returns:

a VertexClustering object

cut_vertices()

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.

degree_distribution(bin_width=1, ...)

Calculates the degree distribution of the graph.

Unknown keyword arguments are directly passed to degree().

Parameters:

bin_width - the bin width of the histogram

Returns:

a histogram representing the degree distribution of the graph.

delete_edges(self, *args, **kwds)

Deletes some edges from the graph.

The set of edges to be deleted is determined by the positional and keyword arguments. If any keyword argument is present, or the first positional argument is callable, an edge sequence is derived by calling EdgeSeq.select with the same positional and keyword arguments. Edges in the derived edge sequence will be removed. Otherwise the first positional argument is considered as follows:

None - deletes all edges
a single integer - deletes the edge with the given ID
a list of integers - deletes the edges denoted by the given IDs
a list of 2-tuples - deletes the edges denoted by the given source-target vertex pairs. When multiple edges are present between a given source-target vertex pair, only one is removed.

Parameters:

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

Returns:

the same graph object

Overrides: GraphBase.delete_edges

dyad_census()

Calculates the dyad census of the graph.

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 from a to b or from b to a but not the other way round) and null (there is no connection between a and b).

Returns:: a DyadCensus object.
Overrides: GraphBase.dyad_census

Reference: Holland, P.W. and Leinhardt, S. (1970). A Method for Detecting Structure in Sociometric Data. American Journal of Sociology, 70, 492-513.

eccentricity(self, vertices=None)

Calculates eccentricities for vertices with the given indices.

Eccentricity is given as the reciprocal of the greatest distance between the vertex being considered and any other vertex in the graph.

Please note that for any unconnected graph, eccentricities will all be equal to 1 over the number of vertices, since for all vertices the greatest distance will be equal to the number of vertices (this is how shortest_paths denotes vertex pairs where it is impossible to reach one from the other).

Parameters:

vertices - the vertices to consider. If None, all vertices are considered.

Returns:

the eccentricities in a list

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

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

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

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

Calculates the eigenvector centralities of the vertices in a graph.

Parameters:

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)

get_adjacency(self, type=2, attribute=None, default=None)

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.
attribute - if None, returns the ordinary adjacency matrix. When the name of a valid edge attribute is given here, the matrix returned will contain the default value at the places where there is no edge or the value of the given attribute where there is an edge. Multiple edges are not supported, the value written in the matrix in this case will be unpredictable.
default - the default value written to the cells in the case of adjacency matrices with attributes.

Returns:

the adjacency matrix as a Matrix.

Overrides: GraphBase.get_adjacency

get_adjedgelist(type=OUT)

Returns the adjacency edge list representation of the graph.

The adjacency edge list representation is a list of lists. Each item of the outer list belongs to a single vertex of the graph. The inner list contains the IDs of the adjacent edges of the given vertex.

Parameters:

type - if OUT, returns the successors of the vertex. If IN, returns the predecessors of the vertex. If ALL, both the predecessors and the successors will be returned. Ignored for undirected graphs.

get_adjlist(type=OUT)

Returns the adjacency list representation of the graph.

The adjacency list representation is a list of lists. Each item of the outer list belongs to a single vertex of the graph. The inner list contains the neighbors of the given vertex.

Parameters:

type - if OUT, returns the successors of the vertex. If IN, returns the predecessors of the vertex. If ALL, both the predecessors and the successors will be returned. Ignored for undirected graphs.

get_automorphisms_vf2(self)

Returns all automorphisms of the graph

Returns:: a list of lists, each item containing a possible mapping of the graph vertices to itself according to the automorphism

indegree(self, *args, **kwds)

Returns the in-degrees in a list.

See degree for possible arguments.

k_core(self, *args)

Returns some k-cores of the graph.

The method accepts an arbitrary number of arguments representing the desired indices of the k-cores to be returned. The arguments can also be lists or tuples. The result is a single Graph object if an only integer argument was given, otherwise the result is a list of Graph objects representing the desired k-cores in the order the arguments were specified. If no argument is given, returns all k-cores in increasing order of k.

layout(self, layout=None, *args, **kwds)

Returns the layout of the graph according to a layout algorithm.

Parameters and keyword arguments not specified here are passed to the layout algorithm directly. See the documentation of the layout algorithms for the explanation of these parameters.

Registered layout names understood by this method are:

circle, circular: circular layout (see Graph.layout_circle)
drl: DrL layout for large graphs (see Graph.layout_drl)
fr, fruchterman_reingold: Fruchterman-Reingold layout (see Graph.layout_fruchterman_reingold).
fr_3d, fr3d, fruchterman_reingold_3d: 3D Fruchterman-Reingold layout (see Graph.layout_fruchterman_reingold_3d).
graphopt: the graphopt algorithm (see Graph.layout_graphopt)
gfr, grid_fr, grid_fruchterman_reingold: grid-based Fruchterman-Reingold layout (see Graph.layout_grid_fruchterman_reingold)
kk, kamada_kawai: Kamada-Kawai layout (see Graph.layout_kamada_kawai)
kk_3d, kk3d, kamada_kawai_3d: 3D Kamada-Kawai layout (see Graph.layout_kamada_kawai_3d)
lgl, large, large_graph: Large Graph Layout (see Graph.layout_lgl)
random: random layout (see Graph.layout_random)
random_3d: random 3D layout (see Graph.layout_random_3d)
rt, tree, reingold_tilford: Reingold-Tilford tree layout (see Graph.layout_reingold_tilford)
sphere, spherical, circle_3d, circular_3d: spherical layout (see Graph.layout_sphere)

Parameters:

layout - the layout to use. This can be one of the registered layout names or a callable which returns either a Layout object or a list of lists containing the coordinates. If None, uses the value of the plotting.layout configuration key.

Returns:

a Layout object.

mincut(capacity=None)

Returns a minimum cut in an undirected graph.

Parameters:

capacity - the edge capacities (weights). If None, all edges have equal weight.

Returns:

a Cut object describing the minimum cut

Overrides: GraphBase.mincut

modularity(membership, weights=None)

Calculates the modularity score of the graph with respect to a given clustering.

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 adjacent to vertex i, kj is the total weight of edges adjacent to vertex j and m is the total edge weight in the graph.

Parameters:

membership - a membership list or a VertexClustering object
weights - optional edge weights or None if all edges are weighed equally. Attribute names are also allowed.

Returns:

the modularity score

Overrides: GraphBase.modularity

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

omega()

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.

outdegree(self, *args, **kwds)

Returns the out-degrees in a list.

See degree for possible arguments.

path_length_hist(directed=True)

Returns the path length histogram of the graph

Parameters:

directed - whether to consider directed paths. Ignored for undirected graphs.

Returns:

a Histogram object. The object will also have an unconnected attribute that stores the number of unconnected vertex pairs (where the second vertex can not be reached from the first one). The latter one will be of type long (and not a simple integer), since this can be very large.

Overrides: GraphBase.path_length_hist

save(self, f, format=None, *args, **kwds)

Unified writing function for graphs.

This method tries to identify the format of the graph given in the first parameter (based on extension) and calls the corresponding writer method.

The remaining arguments are passed to the writer method without any changes.

Parameters:

f - the file containing the graph to be saved
format - the format of the file (if one wants to override the format determined from the filename extension, or the filename itself is a stream). None means auto-detection. Possible values are: "ncol" (NCOL format), "lgl" (LGL format), "graphml", "graphmlz" (GraphML and gzipped GraphML format), "gml" (GML format), "dot", "graphviz" (DOT format, used by GraphViz), "net", "pajek" (Pajek format), "dimacs" (DIMACS format), "edgelist", "edges" or "edge" (edge list), "adjacency" (adjacency matrix), "pickle" (Python pickled format), "svg" (Scalable Vector Graphics).

Raises:

IOError - if the file format can't be identified and none was given.

shell_index(mode=ALL)

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.

shortest_paths_dijkstra(vertices, weights=None, mode=OUT)

Calculates shortest path lengths for given nodes in a graph.

Parameters:

vertices - a list containing the vertex IDs which should be included in the result.
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). Edge weights must be non-negative for the algorithm to work (since weighted shortest path calculation is based on Dijkstra's algorithm)
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 nodes in a matrix

summary(self, verbosity=0)

Returns basic statistics about the graph in a string

Parameters:

verbosity - the amount of statistics to be returned. 0 returns the usual statistics (node, edge count, directedness, number of strong components, density, reciprocity, average path length, diameter). 1 also returns the detailed degree distributions.

triad_census()

Calculates the triad census of the graph.

Returns:: a TriadCensus object.
Overrides: GraphBase.triad_census

Reference: Davis, J.A. and Leinhardt, S. (1972). The Structure of Positive Interpersonal Relations in Small Groups. In: J. Berger (Ed.), Sociological Theories in Progress, Volume 2, 218-251. Boston: Houghton Mifflin.

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

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

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(self, f, format=None, *args, **kwds)

Unified writing function for graphs.

This method tries to identify the format of the graph given in the first parameter (based on extension) and calls the corresponding writer method.

The remaining arguments are passed to the writer method without any changes.

Parameters:

f - the file containing the graph to be saved
format - the format of the file (if one wants to override the format determined from the filename extension, or the filename itself is a stream). None means auto-detection. Possible values are: "ncol" (NCOL format), "lgl" (LGL format), "graphml", "graphmlz" (GraphML and gzipped GraphML format), "gml" (GML format), "dot", "graphviz" (DOT format, used by GraphViz), "net", "pajek" (Pajek format), "dimacs" (DIMACS format), "edgelist", "edges" or "edge" (edge list), "adjacency" (adjacency matrix), "pickle" (Python pickled format), "svg" (Scalable Vector Graphics).

Raises:

IOError - if the file format can't be identified and none was given.

write_adjacency(self, f, sep=`'` `'`, eol=`'\n'`, *args, **kwds)

Writes the adjacency matrix of the graph to the given file

All the remaining arguments not mentioned here are passed intact to Graph.get_adjacency.

Parameters:

f - the name of the file to be written.
sep - the string that separates the matrix elements in a row
eol - the string that separates the rows of the matrix. Please note that igraph is able to read back the written adjacency matrix if and only if this is a single newline character

write_graphmlz(self, f, compresslevel=9)

Writes the graph to a zipped GraphML file.

The library uses the gzip compression algorithm, so the resulting file can be unzipped with regular gzip uncompression (like gunzip or zcat from Unix command line) or the Python gzip module.

Uses a temporary file to store intermediate GraphML data, so make sure you have enough free space to store the unzipped GraphML file as well.

Parameters:

f - the name of the file to be written.
compresslevel - the level of compression. 1 is fastest and produces the least compression, and 9 is slowest and produces the most compression.

write_pickle(self, fname=None, version=-1)

Saves the graph in Python pickled format

Parameters:

fname - the name of the file or a stream to save to. If None, saves the graph to a string and returns the string.
version - pickle protocol version to be used. If -1, uses the highest protocol available

Returns:

None if the graph was saved successfully to the file given, or a string if fname was None.

write_svg(self, fname, layout, width=None, height=None, labels=`'label'`, colors=`'color'`, shapes=`'shape'`, vertex_size=10, edge_colors=`'color'`, font_size=16, *args, **kwds)

Saves the graph as an SVG (Scalable Vector Graphics) file

Parameters:

fname - the name of the file
layout - the layout of the graph. Can be either an explicitly specified layout (using a list of coordinate pairs) or the name of a layout algorithm (which should refer to a method in the Graph object, but without the layout_ prefix.
width - the preferred width in pixels (default: 400)
height - the preferred height in pixels (default: 400)
labels - the vertex labels. Either it is the name of a vertex attribute to use, or a list explicitly specifying the labels. It can also be None.
colors - the vertex colors. Either it is the name of a vertex attribute to use, or a list explicitly specifying the colors. A color can be anything acceptable in an SVG file.
shapes - the vertex shapes. Either it is the name of a vertex attribute to use, or a list explicitly specifying the shapes as integers. Shape 0 means hidden (nothing is drawn), shape 1 is a circle, shape 2 is a rectangle.
vertex_size - vertex size in pixels
edge_colors - the edge colors. Either it is the name of an edge attribute to use, or a list explicitly specifying the colors. A color can be anything acceptable in an SVG file.
font_size - font size. If it is a string, it is written into the SVG file as-is (so you can specify anything which is valid as the value of the font-size style). If it is a number, it is interpreted as pixel size and converted to the proper attribute value accordingly.

Class Variable Details

[hide private]

_format_mapping

Value:

{'adj': ('Read_Adjacency', 'write_adjacency'),
 'adjacency': ('Read_Adjacency', 'write_adjacency'),
 'dimacs': ('Read_DIMACS', 'write_dimacs'),
 'dot': (None, 'write_dot'),
 'edge': ('Read_Edgelist', 'write_edgelist'),
 'edgelist': ('Read_Edgelist', 'write_edgelist'),
 'edges': ('Read_Edgelist', 'write_edgelist'),
 'gml': ('Read_GML', 'write_gml'),
...

_layout_mapping

Value:

{'circle': 'layout_circle',
 'circle_3d': 'layout_sphere',
 'circular': 'layout_circle',
 'circular_3d': 'layout_sphere',
 'drl': 'layout_drl',
 'fr': 'layout_fruchterman_reingold',
 'fr3d': 'layout_fruchterman_reingold_3d',
 'fr_3d': 'layout_fruchterman_reingold_3d',
...

Property Details

[hide private]

es

The edge sequence of the graph

Get Method:: _get_es(self)

vs

The vertex sequence of the graph

Get Method:: _get_vs(self)

Class Graph

Load(klass, f, format=None, *args, **kwds) Class Method

Read(klass, f, format=None, *args, **kwds) Class Method

Read_Adjacency(klass, f, sep=None, comment_char='#', attribute=None, *args, **kwds) Class Method

Read_GraphMLz(f, directed=True, index=0) Class Method

Read_Pickle(klass, fname=None) Class Method

__add__(self, other) (Addition operator)

__coerce__(self, other)

__iadd__(self, other)

__init__(n=None, edges=None, directed=None, graph_attrs=None, vertex_attrs=None, edge_attrs=None) (Constructor)

__isub__(self, other)

__mul__(self, other)

__plot__(self, context, bbox, palette, *args, **kwds)

__reduce__(self)

__sub__(self, other) (Subtraction operator)

_identify_format(filename) Class Method

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

alpha()

biconnected_components(return_articulation_points=False)

blocks(return_articulation_points=False)

clusters(mode=STRONG)

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

community_edge_betweenness(self, clusters=None, directed=True)

community_fastgreedy(self, weights=None)

community_leading_eigenvector(clusters=None, return_merges=False)

community_leading_eigenvector_naive(clusters=None, return_merges=False)

community_walktrap(self, weights=None, steps=4)

components(mode=STRONG)

cut_vertices()

degree_distribution(bin_width=1, ...)

delete_edges(self, *args, **kwds)

dyad_census()

eccentricity(self, vertices=None)

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

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

get_adjacency(self, type=2, attribute=None, default=None)

get_adjedgelist(type=OUT)

get_adjlist(type=OUT)

get_automorphisms_vf2(self)

indegree(self, *args, **kwds)

k_core(self, *args)

layout(self, layout=None, *args, **kwds)

mincut(capacity=None)

modularity(membership, weights=None)

omega()

outdegree(self, *args, **kwds)

path_length_hist(directed=True)

save(self, f, format=None, *args, **kwds)

shell_index(mode=ALL)

shortest_paths_dijkstra(vertices, weights=None, mode=OUT)

summary(self, verbosity=0)

triad_census()

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

write(self, f, format=None, *args, **kwds)

write_adjacency(self, f, sep=' ', eol='\n', *args, **kwds)

write_graphmlz(self, f, compresslevel=9)

write_pickle(self, fname=None, version=-1)

write_svg(self, fname, layout, width=None, height=None, labels='label', colors='color', shapes='shape', vertex_size=10, edge_colors='color', font_size=16, *args, **kwds)

_format_mapping

_layout_mapping

es

vs

Load(klass, f, format=None, *args, **kwds)
Class Method

Read(klass, f, format=None, *args, **kwds)
Class Method

Read_Adjacency(klass, f, sep=None, comment_char=`'#'`, attribute=None, *args, **kwds)
Class Method

Read_GraphMLz(f, directed=True, index=0)
Class Method

Read_Pickle(klass, fname=None)
Class Method

add(self, other)
(Addition operator)

coerce(self, other)

iadd(self, other)

init(n=None, edges=None, directed=None, graph_attrs=None, vertex_attrs=None, edge_attrs=None)
(Constructor)

isub(self, other)

mul(self, other)

plot(self, context, bbox, palette, *args, **kwds)

reduce(self)

sub(self, other)
(Subtraction operator)

_identify_format(filename)
Class Method

write_adjacency(self, f, sep=`'` `'`, eol=`'\n'`, *args, **kwds)

write_svg(self, fname, layout, width=None, height=None, labels=`'label'`, colors=`'color'`, shapes=`'shape'`, vertex_size=10, edge_colors=`'color'`, font_size=16, *args, **kwds)