Home  Trees  Indices  Help 



object +  GraphBase
Lowlevel representation of a graph.
Don't use it directly, use igraph.Graph instead.






















































































a new object with type S, a subtype of T 
































































































































integer 




































boolean 


















boolean 


boolean 












boolean 


































































































































integer 
























Inherited from 


Inherited from 

Generates a graph from its adjacency matrix.

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.

Generates a graph from the Graph Atlas.
Reference: An Atlas of Graphs by Ronald C. Read and Robin J. Wilson, Oxford University Press, 1998. 
Generates a graph based on the BarabasiAlbert model.
Reference: Barabasi, AL and Albert, R. 1999. Emergence of scaling in random networks. Science, 286 509512. 
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.

Generates a graph with a given degree sequence.

Generates a graph based on the ErdosRenyi model.

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.

Generates a famous graph based on its name. Several famous graphs are known to

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.

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

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

Generates a growing random graph.

Generates a graph with a given isomorphy class.

Generates a kregular random graph A kregular random graph is a random graph where each vertex has degree k. If the graph is directed, both the indegree and the outdegree of each vertex will be k.

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.

Generates a graph from LCF notation. LCF is short for LederbergCoxeterFrucht, it is a concise notation for 3regular 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.

Generates a regular lattice.

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.

Reads a graph from a file conforming to the DIMACS minimumcost 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:

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

Reads an edge list from a file and creates a graph based on it. Please note that the vertex indices are zerobased.

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

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/).

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

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.

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.

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

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.

Generates a ring graph.

Generates a star graph.

Generates a nongrowing 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 outfitness and as a target proportional to its infitness.

Generates a nongrowing graph with prescribed powerlaw degree distributions.
Reference:

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

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, 440442, 1998 
Generates a graph from its adjacency matrix.

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. 
x.__init__(...) initializes x; see help(type(x)) for signature


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)

Adds edges to the graph.

Adds vertices to the graph.

Returns a list containing all the minimal st 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.
Reference: Anne Berry, JeanPaul Bordat and Olivier Cogis: Generating all the minimal separators of a graph. In: Peter Widmayer, Gabriele Neyer and Stephan Eidenbenz (eds.): Graphtheoretic concepts in computer science, 1665, 167172, 1999. Springer. 
Returns all the cuts between the source and target vertices in a directed graph. This function lists all edgecuts between a source and a target vertex. Every cut is listed exactly once.

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

Decides whether two given vertices are directly connected.

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. 
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.
Reference:
See Also: assortativity_degree() when the types are the vertex degrees 
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.
See Also: assortativity() 
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.
Reference: Newman MEJ: Mixing patterns in networks, Phys Rev E 67:026126, 2003. 

Calculates Kleinberg's authority score for the vertices of the graph
See Also: hub_score() 
Calculates the average path length in a graph.

Calculates or estimates the betweenness of vertices in a graph. Keyword arguments:

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

Calculates bibliographic coupling scores for given vertices in a graph.

Calculates the biconnected components of the graph.

Internal function, undocumented. See Also: Graph.bipartite_projection() 
Internal function, undocumented. See Also: Graph.bipartite_projection_size() 
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. 
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)

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.

Calculates the (strong or weak) clusters for a given 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. 
Calculates cocitation scores for given vertices in a graph.

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 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, 78217826 (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.
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. 
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 bottomup 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.
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() 
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.
Reference:

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.
Reference: Raghavan, U.N. and Albert, R. and Kumara, S. Near linear time algorithm to detect community structures in largescale networks. Phys Rev E 76:036106, 2007. http://arxiv.org/abs/0709.2938. 
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.
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 
Finds the community structure of the graph according to the multilevel algorithm of Blondel et al. This is a bottomup 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.
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, JL 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() 
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.

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

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.
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() 
Returns the complementer of the graph

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.

Contracts some vertices in the graph, i.e. replaces groups of vertices with single vertices. Edges are not affected.
See Also: Graph.simplify() 
Finds the coreness (shell index) of the vertices of the network. The kcore 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 kcore but not a member of the k+1core.
Reference: Vladimir Batagelj, Matjaz Zaversnik: An O(m) Algorithm for Core Decomposition of Networks. 
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.

Counts the multiplicities of the given edges.

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.

Decomposes the graph into subgraphs.

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). 
Removes edges from the graph. All vertices will be kept, even if they lose all their edges. Nonexistent edges will be silently ignored.

Deletes vertices and all its edges from the graph.

Calculates the density of the graph.

Calculates the diameter of the graph.

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

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.
Reference: Eagle N, Macy M and Claxton R: Network diversity and economic development, Science 328, 10291031, 2010. 
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.
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. 
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.

Counts the number of edges.


Calculates or estimates the edge betweennesses in a graph.

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.

Calculates the eigenvector centralities of the vertices in a graph.

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.

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.
Reference: Eades P, Lin X and Smyth WF: A fast and effective heuristic for the feedback arc set problem. In: Proc Inf Process Lett 319323, 1993. 
Returns the adjacency matrix of a graph.

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

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.

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

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 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.

Internal function, undocumented. See Also: Graph.get_incidence() 
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.

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

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.

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

Checks whether the graph has multiple edges.

Calculates Kleinberg's hub score for the vertices of the graph
See Also: authority_score() 
Returns the edges a given vertex is incident on. 
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 
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.

Returns a subgraph spanned by the given vertices.

Creates the intersection of two (or more) graphs.

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.

Decides whether the graph is connected.

Checks whether the graph is a DAG (directed acyclic graph). A DAG is a directed graph with no directed cycles.

Checks whether the graph is directed.

Checks whether a specific set of edges contain loop edges

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.

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.

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.

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

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

Returns the isomorphy class of the graph or its subgraph. Isomorphy class calculations are implemented only for graphs with 3 or 4 vertices.

Checks whether the graph is isomorphic to another graph. The algorithm being used is selected using a simple heuristic:

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

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.

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

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 selfloops are silently ignored. Although it is possible to calculate the Laplacian matrix of a directed graph, it does not make much sense.

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 
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 
Places the vertices of the graph uniformly on a circle or a sphere.

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 forcebased layouts
like

Places the vertices on a 2D plane or in the 3D space according to the FruchtermanReingold algorithm. This is a force directed layout, see Fruchterman, T. M. J. and Reingold, E. M.: Graph Drawing by Forcedirected Placement. Software  Practice and Experience, 21/11, 11291164, 1991

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.

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

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

Places the vertices on a plane according to the KamadaKawai 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, 715, 1989.

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

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.
Reference: Cox & Cox: Multidimensional Scaling (1994), Chapman and Hall, London. 
Places the vertices of the graph randomly.

Places the vertices on a 2D plane according to the ReingoldTilford layout algorithm. This is a tree layout. If the given graph is not a tree, a breadthfirst search is executed first to obtain a possible spanning tree.
See Also: layout_reingold_tilford_circular Reference: EM Reingold, JS Tilford: Tidier Drawings of Trees. IEEE Transactions on Software Engineering 7:22, 223228, 1981. 
Circular ReingoldTilford layout for trees. This layout is similar to the ReingoldTilford 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.
See Also: layout_reingold_tilford Reference: EM Reingold, JS Tilford: Tidier Drawings of Trees. IEEE Transactions on Software Engineering 7:22, 223228, 1981. 
Calculates a starlike layout for the graph.

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. 
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). 
Returns the maximum flow between the source and target vertices.

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

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.
See Also: largest_cliques() for the largest cliques. 
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:505517, 1977. 
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 StoerWagner algorithm as described in the reference given below.

Returns the minimum cut between the source and target vertices.

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.
Reference: Arkady Kanevsky: Finding all minimumsize separating vertex sets in a graph. Networks 23:533541, 1993. 
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(Aijki*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 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.
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
Reference: MEJ Newman and M Girvan: Finding and evaluating community structure in networks. Phys Rev E 69 026113, 2004. 
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.
Reference: S. Wernicke and F. Rasche: FANMOD: a tool for fast network motif detection, Bioinformatics 22(9), 11521153, 2006. See Also: Graph.motifs_randesu_no() 
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.
Reference: S. Wernicke and F. Rasche: FANMOD: a tool for fast network motif detection, Bioinformatics 22(9), 11521153, 2006. See Also: Graph.motifs_randesu() 
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.
Reference: S. Wernicke and F. Rasche: FANMOD: a tool for fast network motif detection, Bioinformatics 22(9), 11521153, 2006. See Also: Graph.motifs_randesu() 
For each vertex specified by vertices, returns the vertices reachable from that vertex in at most order steps.

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

Returns adjacent vertices to a given vertex. 
Calculates the path length histogram of the graph
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. 
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.

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 nonuniform distribution over the vertices in every step with probability 1damping instead of a uniform distribution.

Returns the predecessors of a given vertex. Equivalent to calling the Graph.neighbors method with type=IN. 
Calculates the radius of the graph. The radius of a graph is defined as the minimum eccentricity of its vertices (see eccentricity()).
See Also: Graph.eccentricity() 
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 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 nonmutual) connection between them. In other words,
(unordered) vertex pairs are classified into three groups: (1)
disconnected, (2) nonreciprocally 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

Randomly rewires the graph while preserving the degree distribution. Please note that the rewiring is done "inplace", so the original graph will be modified. If you want to preserve the original graph, use the copy method before.

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 "inplace", so the original graph will be modified. If you want to preserve the original graph, use the copy method before.

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 BellmanFord algorithm is used if the number of requested source vertices is larger than 100 and Johnson's algorithm is used otherwise.

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.

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

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.

Simplifies a graph by removing selfloops and/or multiple edges. For example, suppose you have a graph with an edge attribute named

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

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

Returns a subgraph spanned by the given edges.

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.

Returns the successors of a given vertex. Equivalent to calling the Graph.neighbors method with type=OUT. 
Converts an undirected graph to directed.

Converts a directed graph to undirected.

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. 
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.
See Also: transitivity_undirected(), transitivity_local_undirected() Reference: D. J. Watts and S. Strogatz: Collective dynamics of smallworld networks. Nature 393(6884):440442, 1998. 
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
See Also: transitivity_undirected(), transitivity_avglocal_undirected() Reference:

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.
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, 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. 
Unfolds the graph using a BFS to a tree by duplicating vertices as necessary.

Creates the union of two (or more) graphs.

Counts the number of vertices.


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.

Writes the graph in DIMACS format to the given file.

Writes the graph in DOT format to the given file. DOT is the format used by the GraphViz software package.

Writes the edge list of a graph to a file. Directed edges are written in (from, to) order.

Writes the graph in GML format to the given file.

Writes the graph to a GraphML file.

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.

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.

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.

Writes the graph in Pajek format to the given file.

Home  Trees  Indices  Help 


Generated by Epydoc 3.0.1 on Fri Mar 1 23:27:15 2013  http://epydoc.sourceforge.net 