Package 'igraph'

Description

Query and manipulate a graph as it were an adjacency matrix

Usage

## S3 method for class 'igraph'

  x[
  i,
  j,
  ...,
  from,
  to,
  sparse = igraph_opt("sparsematrices"),
  edges = FALSE,
  drop = TRUE,
  attr = if (is_weighted(x)) "weight" else NULL
]

Arguments

Details

The single bracket indexes the (possibly weighted) adjacency matrix of the graph. Here is what you can do with it:

1. Check whether there is an edge between two vertices ($v$ and $w$) in the graph:

     graph[v, w]

   A numeric scalar is returned, one if the edge exists, zero otherwise.

2. Extract the (sparse) adjacency matrix of the graph, or part of it:

     graph[]
   graph[1:3,5:6]
   graph[c(1,3,5),]

   The first variants returns the full adjacency matrix, the other two return part of it.

3. The from and to arguments can be used to check the existence of many edges. In this case, both from and to must be present and they must have the same length. They must contain vertex ids or names. A numeric vector is returned, of the same length as from and to, it contains ones for existing edges edges and zeros for non-existing ones. Example:

     graph[from=1:3, to=c(2,3,5)]

   .

4. For weighted graphs, the [ operator returns the edge weights. For non-esistent edges zero weights are returned. Other edge attributes can be queried as well, by giving the attr argument.

5. Querying edge ids instead of the existance of edges or edge attributes. E.g.

     graph[1, 2, edges=TRUE]

   returns the id of the edge between vertices 1 and 2, or zero if there is no such edge.

6. Adding one or more edges to a graph. For this the element(s) of the imaginary adjacency matrix must be set to a non-zero numeric value (or TRUE):

     graph[1, 2] <- 1
   graph[1:3,1] <- 1
   graph[from=1:3, to=c(2,3,5)] <- TRUE

   This does not affect edges that are already present in the graph, i.e. no multiple edges are created.

7. Adding weighted edges to a graph. The attr argument contains the name of the edge attribute to set, so it does not have to be ‘weight’:

     graph[1, 2, attr="weight"]<- 5
   graph[from=1:3, to=c(2,3,5)] <- c(1,-1,4)

   If an edge is already present in the network, then only its weights or other attribute are updated. If the graph is already weighted, then the attr="weight" setting is implicit, and one does not need to give it explicitly.

8. Deleting edges. The replacement syntax allow the deletion of edges, by specifying FALSE or NULL as the replacement value:

     graph[v, w] <- FALSE

   removes the edge from vertex $v$ to vertex $w$. As this can be used to delete edges between two sets of vertices, either pairwise:

     graph[from=v, to=w] <- FALSE

   or not:

     graph[v, w] <- FALSE 

   if $v$ and $w$ are vectors of edge ids or names.

‘[’ allows logical indices and negative indices as well, with the usual R semantics. E.g.

  graph[degree(graph)==0, 1] <- 1

adds an edge from every isolate vertex to vertex one, and

  G <- make_empty_graph(10)
G[-1,1] <- TRUE

creates a star graph.

Of course, the indexing operators support vertex names, so instead of a numeric vertex id a vertex can also be given to ‘[’ and ‘[[’.

Value

A scalar or matrix. See details below.

See Also

Other structural queries: [[.igraph(), adjacent_vertices(), are_adjacent(), ends(), get_edge_ids(), gorder(), gsize(), head_of(), incident(), incident_edges(), is_directed(), neighbors(), tail_of()

Description

Query and manipulate a graph as it were an adjacency list

Usage

## S3 method for class 'igraph'
x[[i, j, from, to, ..., directed = TRUE, edges = FALSE, exact = TRUE]]

Arguments

Details

The double bracket operator indexes the (imaginary) adjacency list of the graph. This can used for the following operations:

1. Querying the adjacent vertices for one or more vertices:

     graph[[1:3,]]
   graph[[,1:3]]

   The first form gives the successors, the second the predecessors or the 1:3 vertices. (For undirected graphs they are equivalent.)

2. Querying the incident edges for one or more vertices, if the edges argument is set to TRUE:

     graph[[1:3, , edges=TRUE]]
   graph[[, 1:3, edges=TRUE]]

3. Querying the edge ids between two sets or vertices, if both indices are used. E.g.

     graph[[v, w, edges=TRUE]]

   gives the edge ids of all the edges that exist from vertices $v$ to vertices $w$.

The alternative argument names from and to can be used instead of the usual i and j, to make the code more readable:

 graph[[from = 1:3]]
graph[[from = v, to = w, edges = TRUE]]

‘[[’ operators allows logical indices and negative indices as well, with the usual R semantics.

Vertex names are also supported, so instead of a numeric vertex id a vertex can also be given to ‘[’ and ‘[[’.

See Also

Other structural queries: [.igraph(), adjacent_vertices(), are_adjacent(), ends(), get_edge_ids(), gorder(), gsize(), head_of(), incident(), incident_edges(), is_directed(), neighbors(), tail_of()

Description

igraph re-exports the ⁠%>%⁠ operator of magrittr, because we find it very useful. Please see the documentation in the magrittr package.

Arguments

Value

Result of applying the right hand side to the result of the left hand side.

Examples

make_ring(10) %>%
  add_edges(c(1, 6)) %>%
  plot()

Description

Add vertices, edges or another graph to a graph

Usage

## S3 method for class 'igraph'
e1 + e2

Arguments

Details

The plus operator can be used to add vertices or edges to graph. The actual operation that is performed depends on the type of the right hand side argument.

• If is is another igraph graph object and they are both named graphs, then the union of the two graphs are calculated, see union().

• If it is another igraph graph object, but either of the two are not named, then the disjoint union of the two graphs is calculated, see disjoint_union().

• If it is a numeric scalar, then the specified number of vertices are added to the graph.

• If it is a character scalar or vector, then it is interpreted as the names of the vertices to add to the graph.

• If it is an object created with the vertex() or vertices() function, then new vertices are added to the graph. This form is appropriate when one wants to add some vertex attributes as well. The operands of the vertices() function specifies the number of vertices to add and their attributes as well.

  The unnamed arguments of vertices() are concatenated and used as the ‘name’ vertex attribute (i.e. vertex names), the named arguments will be added as additional vertex attributes. Examples:

    g <- g +
          vertex(shape="circle", color= "red")
    g <- g + vertex("foo", color="blue")
    g <- g + vertex("bar", "foobar")
    g <- g + vertices("bar2", "foobar2", color=1:2, shape="rectangle")

  vertex() is just an alias to vertices(), and it is provided for readability. The user should use it if a single vertex is added to the graph.

• If it is an object created with the edge() or edges() function, then new edges will be added to the graph. The new edges and possibly their attributes can be specified as the arguments of the edges() function.

  The unnamed arguments of edges() are concatenated and used as vertex ids of the end points of the new edges. The named arguments will be added as edge attributes.

  Examples:

    g <- make_empty_graph() +
           vertices(letters[1:10]) +
           vertices("foo", "bar", "bar2", "foobar2")
    g <- g + edge("a", "b")
    g <- g + edges("foo", "bar", "bar2", "foobar2")
    g <- g + edges(c("bar", "foo", "foobar2", "bar2"), color="red", weight=1:2)

  See more examples below.

  edge() is just an alias to edges() and it is provided for readability. The user should use it if a single edge is added to the graph.

• If it is an object created with the path() function, then new edges that form a path are added. The edges and possibly their attributes are specified as the arguments to the path() function. The non-named arguments are concatenated and interpreted as the vertex ids along the path. The remaining arguments are added as edge attributes.

  Examples:

    g <- make_empty_graph() + vertices(letters[1:10])
    g <- g + path("a", "b", "c", "d")
    g <- g + path("e", "f", "g", weight=1:2, color="red")
    g <- g + path(c("f", "c", "j", "d"), width=1:3, color="green")

It is important to note that, although the plus operator is commutative, i.e. is possible to write

  graph <- "foo" + make_empty_graph()

it is not associative, e.g.

  graph <- "foo" + "bar" + make_empty_graph()

results a syntax error, unless parentheses are used:

  graph <- "foo" + ( "bar" + make_empty_graph() )

For clarity, we suggest to always put the graph object on the left hand side of the operator:

  graph <- make_empty_graph() + "foo" + "bar"

See Also

Other functions for manipulating graph structure: add_edges(), add_vertices(), complementer(), compose(), connect(), contract(), delete_edges(), delete_vertices(), difference(), difference.igraph(), disjoint_union(), edge(), igraph-minus, intersection(), intersection.igraph(), path(), permute(), rep.igraph(), reverse_edges(), simplify(), union(), union.igraph(), vertex()

Examples

# 10 vertices named a,b,c,... and no edges
g <- make_empty_graph() + vertices(letters[1:10])

# Add edges to make it a ring
g <- g + path(letters[1:10], letters[1], color = "grey")

# Add some extra random edges
g <- g + edges(sample(V(g), 10, replace = TRUE), color = "red")
g$layout <- layout_in_circle
plot(g)

Description

The new edges are given as a vertex sequence, e.g. internal numeric vertex ids, or vertex names. The first edge points from edges[1] to edges[2], the second from edges[3] to edges[4], etc.

Usage

add_edges(graph, edges, ..., attr = list())

Arguments

Details

If attributes are supplied, and they are not present in the graph, their values for the original edges of the graph are set to NA.

Value

The graph, with the edges (and attributes) added.

See Also

Other functions for manipulating graph structure: +.igraph(), add_vertices(), complementer(), compose(), connect(), contract(), delete_edges(), delete_vertices(), difference(), difference.igraph(), disjoint_union(), edge(), igraph-minus, intersection(), intersection.igraph(), path(), permute(), rep.igraph(), reverse_edges(), simplify(), union(), union.igraph(), vertex()

Examples

g <- make_empty_graph(n = 5) %>%
  add_edges(c(
    1, 2,
    2, 3,
    3, 4,
    4, 5
  )) %>%
  set_edge_attr("color", value = "red") %>%
  add_edges(c(5, 1), color = "green")
E(g)[[]]
plot(g)

Description

Add layout to graph

Usage

add_layout_(graph, ..., overwrite = TRUE)

Arguments

Value

The input graph, with the layout added.

See Also

layout_() for a description of the layout API.

Other graph layouts: component_wise(), layout_(), layout_as_bipartite(), layout_as_star(), layout_as_tree(), layout_in_circle(), layout_nicely(), layout_on_grid(), layout_on_sphere(), layout_randomly(), layout_with_dh(), layout_with_fr(), layout_with_gem(), layout_with_graphopt(), layout_with_kk(), layout_with_lgl(), layout_with_mds(), layout_with_sugiyama(), merge_coords(), norm_coords(), normalize()

Examples

(make_star(11) + make_star(11)) %>%
  add_layout_(as_star(), component_wise()) %>%
  plot()

Description

If attributes are supplied, and they are not present in the graph, their values for the original vertices of the graph are set to NA.

Usage

add_vertices(graph, nv, ..., attr = list())

Arguments

Value

The graph, with the vertices (and attributes) added.

See Also

Other functions for manipulating graph structure: +.igraph(), add_edges(), complementer(), compose(), connect(), contract(), delete_edges(), delete_vertices(), difference(), difference.igraph(), disjoint_union(), edge(), igraph-minus, intersection(), intersection.igraph(), path(), permute(), rep.igraph(), reverse_edges(), simplify(), union(), union.igraph(), vertex()

Examples

g <- make_empty_graph() %>%
  add_vertices(3, color = "red") %>%
  add_vertices(2, color = "green") %>%
  add_edges(c(
    1, 2,
    2, 3,
    3, 4,
    4, 5
  ))
g
V(g)[[]]
plot(g)

Description

This function is similar to neighbors(), but it queries the adjacent vertices for multiple vertices at once.

Usage

adjacent_vertices(graph, v, mode = c("out", "in", "all", "total"))

Arguments

Value

A list of vertex sequences.

See Also

Other structural queries: [.igraph(), [[.igraph(), are_adjacent(), ends(), get_edge_ids(), gorder(), gsize(), head_of(), incident(), incident_edges(), is_directed(), neighbors(), tail_of()

Examples

g <- make_graph("Zachary")
adjacent_vertices(g, c(1, 34))

Description

This function lists are simple paths from one source vertex to another vertex or vertices. A path is simple if the vertices it visits are not visited more than once.

Usage

all_simple_paths(
  graph,
  from,
  to = V(graph),
  mode = c("out", "in", "all", "total"),
  cutoff = -1
)

Arguments

Details

Note that potentially there are exponentially many paths between two vertices of a graph, and you may run out of memory when using this function, if your graph is lattice-like.

This function currently ignored multiple and loop edges.

Value

A list of integer vectors, each integer vector is a path from the source vertex to one of the target vertices. A path is given by its vertex ids.

See Also

Other paths: diameter(), distance_table(), eccentricity(), graph_center(), radius()

Examples

g <- make_ring(10)
all_simple_paths(g, 1, 5)
all_simple_paths(g, 1, c(3, 5))

Description

alpha_centrality() calculates the alpha centrality of some (or all) vertices in a graph.

Usage

alpha_centrality(
  graph,
  nodes = V(graph),
  alpha = 1,
  loops = FALSE,
  exo = 1,
  weights = NULL,
  tol = 1e-07,
  sparse = TRUE
)

Arguments

Details

The alpha centrality measure can be considered as a generalization of eigenvector centrality to directed graphs. It was proposed by Bonacich in 2001 (see reference below).

The alpha centrality of the vertices in a graph is defined as the solution of the following matrix equation:

$x=\alpha A^T x+e,$

where $A$ is the (not necessarily symmetric) adjacency matrix of the graph, $e$ is the vector of exogenous sources of status of the vertices and $\alpha$ is the relative importance of the endogenous versus exogenous factors.

Value

A numeric vector contaning the centrality scores for the selected vertices.

Warning

Singular adjacency matrices cause problems for this algorithm, the routine may fail is certain cases.

Author(s)

Gabor Csardi csardi.gabor@gmail.com

References

Bonacich, P. and Lloyd, P. (2001). “Eigenvector-like measures of centrality for asymmetric relations” Social Networks, 23, 191-201.

See Also

eigen_centrality() and power_centrality()

Centrality measures authority_score(), betweenness(), closeness(), diversity(), eigen_centrality(), harmonic_centrality(), hits_scores(), page_rank(), power_centrality(), spectrum(), strength(), subgraph_centrality()

Examples

# The examples from Bonacich's paper
g.1 <- make_graph(c(1, 3, 2, 3, 3, 4, 4, 5))
g.2 <- make_graph(c(2, 1, 3, 1, 4, 1, 5, 1))
g.3 <- make_graph(c(1, 2, 2, 3, 3, 4, 4, 1, 5, 1))
alpha_centrality(g.1)
alpha_centrality(g.2)
alpha_centrality(g.3, alpha = 0.5)

Description

The order of the vertices only matters in directed graphs, where the existence of a directed ⁠(v1, v2)⁠ edge is queried.

Usage

are_adjacent(graph, v1, v2)

Arguments

Value

A logical scalar, TRUE if edge ⁠(v1, v2)⁠ exists in the graph.

Related documentation in the C library

igraph_are_adjacent().

See Also

Other structural queries: [.igraph(), [[.igraph(), adjacent_vertices(), ends(), get_edge_ids(), gorder(), gsize(), head_of(), incident(), incident_edges(), is_directed(), neighbors(), tail_of()

Examples

ug <- make_ring(10)
ug
are_adjacent(ug, 1, 2)
are_adjacent(ug, 2, 1)

dg <- make_ring(10, directed = TRUE)
dg
are_adjacent(ug, 1, 2)
are_adjacent(ug, 2, 1)

Description

Interface to the ARPACK library for calculating eigenvectors of sparse matrices

Usage

arpack_defaults()

arpack(
  func,
  extra = NULL,
  sym = FALSE,
  options = arpack_defaults(),
  env = parent.frame(),
  complex = !sym
)

Arguments

Details

ARPACK is a library for solving large scale eigenvalue problems. The package is designed to compute a few eigenvalues and corresponding eigenvectors of a general $n$ by $n$ matrix $A$. It is most appropriate for large sparse or structured matrices $A$ where structured means that a matrix-vector product w <- Av requires order $n$ rather than the usual order $n^2$ floating point operations.

This function is an interface to ARPACK. igraph does not contain all ARPACK routines, only the ones dealing with symmetric and non-symmetric eigenvalue problems using double precision real numbers.

The eigenvalue calculation in ARPACK (in the simplest case) involves the calculation of the $Av$ product where $A$ is the matrix we work with and $v$ is an arbitrary vector. The function supplied in the fun argument is expected to perform this product. If the product can be done efficiently, e.g. if the matrix is sparse, then arpack() is usually able to calculate the eigenvalues very quickly.

The options argument specifies what kind of calculation to perform. It is a list with the following members, they correspond directly to ARPACK parameters. On input it has the following fields:

bmat

Character constant, possible values: ‘I’, standard eigenvalue problem, $Ax=\lambda x$; and ‘G’, generalized eigenvalue problem, $Ax=\lambda B x$. Currently only ‘I’ is supported.

n

Numeric scalar. The dimension of the eigenproblem. You only need to set this if you call arpack() directly. (I.e. not needed for eigen_centrality(), page_rank(), etc.)

which

Specify which eigenvalues/vectors to compute, character constant with exactly two characters.

Possible values for symmetric input matrices:

"LA"

Compute nev largest (algebraic) eigenvalues.

"SA"

Compute nev smallest (algebraic) eigenvalues.

"LM"

Compute nev largest (in magnitude) eigenvalues.

"SM"

Compute nev smallest (in magnitude) eigenvalues.

"BE"

Compute nev eigenvalues, half from each end of the spectrum. When nev is odd, compute one more from the high end than from the low end.

Possible values for non-symmetric input matrices:

"LM"

Compute nev eigenvalues of largest magnitude.

"SM"

Compute nev eigenvalues of smallest magnitude.

"LR"

Compute nev eigenvalues of largest real part.

"SR"

Compute nev eigenvalues of smallest real part.

"LI"

Compute nev eigenvalues of largest imaginary part.

"SI"

Compute nev eigenvalues of smallest imaginary part.

This parameter is sometimes overwritten by the various functions, e.g. page_rank() always sets ‘LM’.

nev

Numeric scalar. The number of eigenvalues to be computed.

tol

Numeric scalar. Stopping criterion: the relative accuracy of the Ritz value is considered acceptable if its error is less than tol times its estimated value. If this is set to zero then machine precision is used.

ncv

Number of Lanczos vectors to be generated.

ldv

Numberic scalar. It should be set to zero in the current implementation.

ishift

Either zero or one. If zero then the shifts are provided by the user via reverse communication. If one then exact shifts with respect to the reduced tridiagonal matrix $T$. Please always set this to one.

maxiter

Maximum number of Arnoldi update iterations allowed.

nb

Blocksize to be used in the recurrence. Please always leave this on the default value, one.

mode

The type of the eigenproblem to be solved. Possible values if the input matrix is symmetric:

1

$Ax=\lambda x$, $A$ is symmetric.

2

$Ax=\lambda Mx$, $A$ is symmetric, $M$ is symmetric positive definite.

3

$Kx=\lambda Mx$, $K$ is symmetric, $M$ is symmetric positive semi-definite.

4

$Kx=\lambda KGx$, $K$ is symmetric positive semi-definite, $KG$ is symmetric indefinite.

5

$Ax=\lambda Mx$, $A$ is symmetric, $M$ is symmetric positive semi-definite. (Cayley transformed mode.)

Please note that only mode==1 was tested and other values might not work properly.

Possible values if the input matrix is not symmetric:

1

$Ax=\lambda x$.

2

$Ax=\lambda Mx$, $M$ is symmetric positive definite.

3

$Ax=\lambda Mx$, $M$ is symmetric semi-definite.

4

$Ax=\lambda Mx$, $M$ is symmetric semi-definite.

Please note that only mode==1 was tested and other values might not work properly.

start

Not used currently. Later it be used to set a starting vector.

sigma

Not used currently.

sigmai

Not use currently.

On output the following additional fields are added:

info

Error flag of ARPACK. Possible values:

0

Normal exit.

1

Maximum number of iterations taken.

3

No shifts could be applied during a cycle of the Implicitly restarted Arnoldi iteration. One possibility is to increase the size of ncv relative to nev.

ARPACK can return more error conditions than these, but they are converted to regular igraph errors.

iter

Number of Arnoldi iterations taken.

nconv

Number of “converged” Ritz values. This represents the number of Ritz values that satisfy the convergence critetion.

numop

Total number of matrix-vector multiplications.

numopb

Not used currently.

numreo

Total number of steps of re-orthogonalization.

Please see the ARPACK documentation for additional details.

Value

A named list with the following members:

Author(s)

Rich Lehoucq, Kristi Maschhoff, Danny Sorensen, Chao Yang for ARPACK, Gabor Csardi csardi.gabor@gmail.com for the R interface.

References

D.C. Sorensen, Implicit Application of Polynomial Filters in a k-Step Arnoldi Method. SIAM J. Matr. Anal. Apps., 13 (1992), pp 357-385.

R.B. Lehoucq, Analysis and Implementation of an Implicitly Restarted Arnoldi Iteration. Rice University Technical Report TR95-13, Department of Computational and Applied Mathematics.

B.N. Parlett & Y. Saad, Complex Shift and Invert Strategies for Real Matrices. Linear Algebra and its Applications, vol 88/89, pp 575-595, (1987).

See Also

eigen_centrality(), page_rank(), hub_score(), cluster_leading_eigen() are some of the functions in igraph that use ARPACK.

Examples

# Identity matrix
f <- function(x, extra = NULL) x
arpack(f, options = list(n = 10, nev = 2, ncv = 4), sym = TRUE)

# Graph laplacian of a star graph (undirected), n>=2
# Note that this is a linear operation
f <- function(x, extra = NULL) {
  y <- x
  y[1] <- (length(x) - 1) * x[1] - sum(x[-1])
  for (i in 2:length(x)) {
    y[i] <- x[i] - x[1]
  }
  y
}

arpack(f, options = list(n = 10, nev = 1, ncv = 3), sym = TRUE)

# double check
eigen(laplacian_matrix(make_star(10, mode = "undirected")))

## First three eigenvalues of the adjacency matrix of a graph
## We need the 'Matrix' package for this
if (require(Matrix)) {
  set.seed(42)
  g <- sample_gnp(1000, 5 / 1000)
  M <- as_adjacency_matrix(g, sparse = TRUE)
  f2 <- function(x, extra = NULL) {
    cat(".")
    as.vector(M %*% x)
  }
  baev <- arpack(f2, sym = TRUE, options = list(
    n = vcount(g), nev = 3, ncv = 8,
    which = "LM", maxiter = 2000
  ))
}

Description

articulation_points() finds the articulation points (or cut vertices)

Usage

articulation_points(graph)

bridges(graph)

Arguments

Details

Articulation points or cut vertices are vertices whose removal increases the number of connected components in a graph. Similarly, bridges or cut-edges are edges whose removal increases the number of connected components in a graph. If the original graph was connected, then the removal of a single articulation point or a single bridge makes it disconnected. If a graph contains no articulation points, then its vertex connectivity is at least two.

Value

For articulation_points(), a numeric vector giving the vertex IDs of the articulation points of the input graph. For bridges(), a numeric vector giving the edge IDs of the bridges of the input graph.

Related documentation in the C library

igraph_articulation_points(), igraph_bridges().

Author(s)

Gabor Csardi csardi.gabor@gmail.com

See Also

biconnected_components(), components(), is_connected(), vertex_connectivity(), edge_connectivity()

Connected components biconnected_components(), component_distribution(), decompose(), is_biconnected()

Examples

g <- disjoint_union(make_full_graph(5), make_full_graph(5))
clu <- components(g)$membership
g <- add_edges(g, c(match(1, clu), match(2, clu)))
articulation_points(g)

g <- make_graph("krackhardt_kite")
bridges(g)

Description

Create adjacency lists from a graph, either for adjacent edges or for neighboring vertices

Usage

as_adj_list(
  graph,
  mode = c("all", "out", "in", "total"),
  loops = c("twice", "once", "ignore"),
  multiple = TRUE
)

as_adj_edge_list(
  graph,
  mode = c("all", "out", "in", "total"),
  loops = c("twice", "once", "ignore")
)

Arguments

Details

as_adj_list() returns a list of numeric vectors, which include the ids of neighbor vertices (according to the mode argument) of all vertices.

as_adj_edge_list() returns a list of numeric vectors, which include the ids of adjacent edges (according to the mode argument) of all vertices.

If igraph_opt("return.vs.es") is true (default), the numeric vectors of the adjacency lists are coerced to igraph.vs, this can be a very expensive operation on large graphs.

Value

A list of igraph.vs or a list of numeric vectors depending on the value of igraph_opt("return.vs.es"), see details for performance characteristics.

Author(s)

Gabor Csardi csardi.gabor@gmail.com

See Also

as_edgelist(), as_adjacency_matrix()

Other conversion: as.matrix.igraph(), as_adjacency_matrix(), as_biadjacency_matrix(), as_data_frame(), as_directed(), as_edgelist(), as_graphnel(), as_long_data_frame(), graph_from_adj_list(), graph_from_graphnel()

Examples

g <- make_ring(10)
as_adj_list(g)
as_adj_edge_list(g)

Description

Sometimes it is useful to work with a standard representation of a graph, like an adjacency matrix.

Usage

as_adjacency_matrix(
  graph,
  type = c("both", "upper", "lower"),
  attr = NULL,
  edges = deprecated(),
  names = TRUE,
  sparse = igraph_opt("sparsematrices")
)

Arguments

Details

as_adjacency_matrix() returns the adjacency matrix of a graph, a regular matrix if sparse is FALSE, or a sparse matrix, as defined in the ‘Matrix’ package, if sparse if TRUE.

Value

A vcount(graph) by vcount(graph) (usually) numeric matrix.

See Also

graph_from_adjacency_matrix(), read_graph()

Other conversion: as.matrix.igraph(), as_adj_list(), as_biadjacency_matrix(), as_data_frame(), as_directed(), as_edgelist(), as_graphnel(), as_long_data_frame(), graph_from_adj_list(), graph_from_graphnel()

Examples

g <- sample_gnp(10, 2 / 10)
as_adjacency_matrix(g)
V(g)$name <- letters[1:vcount(g)]
as_adjacency_matrix(g)
E(g)$weight <- runif(ecount(g))
as_adjacency_matrix(g, attr = "weight")

Description

This function can return a sparse or dense bipartite adjacency matrix of a bipartite network. The bipartite adjacency matrix is an $n$ times $m$ matrix, $n$ and $m$ are the number of vertices of the two kinds.

Usage

as_biadjacency_matrix(
  graph,
  types = NULL,
  attr = NULL,
  names = TRUE,
  sparse = FALSE
)

Arguments

Details

Bipartite graphs have a type vertex attribute in igraph, this is boolean and FALSE for the vertices of the first kind and TRUE for vertices of the second kind.

Some authors refer to the bipartite adjacency matrix as the "bipartite incidence matrix". igraph 1.6.0 and later does not use this naming to avoid confusion with the edge-vertex incidence matrix.

Value

A sparse or dense matrix.

Author(s)

Gabor Csardi csardi.gabor@gmail.com

See Also

graph_from_biadjacency_matrix() for the opposite operation.

Other conversion: as.matrix.igraph(), as_adj_list(), as_adjacency_matrix(), as_data_frame(), as_directed(), as_edgelist(), as_graphnel(), as_long_data_frame(), graph_from_adj_list(), graph_from_graphnel()

Examples

g <- make_bipartite_graph(c(0, 1, 0, 1, 0, 0), c(1, 2, 2, 3, 3, 4))
as_biadjacency_matrix(g)

Description

This function creates an igraph graph from one or two data frames containing the (symbolic) edge list and edge/vertex attributes.

Usage

as_data_frame(x, what = c("edges", "vertices", "both"))

graph_from_data_frame(d, directed = TRUE, vertices = NULL)

from_data_frame(...)

Arguments

Details

graph_from_data_frame() creates igraph graphs from one or two data frames. It has two modes of operation, depending whether the vertices argument is NULL or not.

If vertices is NULL, then the first two columns of d are used as a symbolic edge list and additional columns as edge attributes. The names of the attributes are taken from the names of the columns.

If vertices is not NULL, then it must be a data frame giving vertex metadata. The first column of vertices is assumed to contain symbolic vertex names, this will be added to the graphs as the ‘name’ vertex attribute. Other columns will be added as additional vertex attributes. If vertices is not NULL then the symbolic edge list given in d is checked to contain only vertex names listed in vertices.

Typically, the data frames are exported from some spreadsheet software like Excel and are imported into R via read.table(), read.delim() or read.csv().

All edges in the data frame are included in the graph, which may include multiple parallel edges and loops.

as_data_frame() converts the igraph graph into one or more data frames, depending on the what argument.

If the what argument is edges (the default), then the edges of the graph and also the edge attributes are returned. The edges will be in the first two columns, named from and to. (This also denotes edge direction for directed graphs.) For named graphs, the vertex names will be included in these columns, for other graphs, the numeric vertex ids. The edge attributes will be in the other columns. It is not a good idea to have an edge attribute named from or to, because then the column named in the data frame will not be unique. The edges are listed in the order of their numeric ids.

If the what argument is vertices, then vertex attributes are returned. Vertices are listed in the order of their numeric vertex ids.

If the what argument is both, then both vertex and edge data is returned, in a list with named entries vertices and edges.

Value

An igraph graph object for graph_from_data_frame(), and either a data frame or a list of two data frames named edges and vertices for as.data.frame.

Note

For graph_from_data_frame() NA elements in the first two columns ‘d’ are replaced by the string “NA” before creating the graph. This means that all NAs will correspond to a single vertex.

NA elements in the first column of ‘vertices’ are also replaced by the string “NA”, but the rest of ‘vertices’ is not touched. In other words, vertex names (=the first column) cannot be NA, but other vertex attributes can.

Author(s)

Gabor Csardi csardi.gabor@gmail.com

See Also

graph_from_literal() for another way to create graphs, read.table() to read in tables from files.

Other conversion: as.matrix.igraph(), as_adj_list(), as_adjacency_matrix(), as_biadjacency_matrix(), as_directed(), as_edgelist(), as_graphnel(), as_long_data_frame(), graph_from_adj_list(), graph_from_graphnel()

Other biadjacency: graph_from_biadjacency_matrix()

Examples

## A simple example with a couple of actors
## The typical case is that these tables are read in from files....
actors <- data.frame(
  name = c(
    "Alice", "Bob", "Cecil", "David",
    "Esmeralda"
  ),
  age = c(48, 33, 45, 34, 21),
  gender = c("F", "M", "F", "M", "F")
)
relations <- data.frame(
  from = c(
    "Bob", "Cecil", "Cecil", "David",
    "David", "Esmeralda"
  ),
  to = c("Alice", "Bob", "Alice", "Alice", "Bob", "Alice"),
  same.dept = c(FALSE, FALSE, TRUE, FALSE, FALSE, TRUE),
  friendship = c(4, 5, 5, 2, 1, 1), advice = c(4, 5, 5, 4, 2, 3)
)
g <- graph_from_data_frame(relations, directed = TRUE, vertices = actors)
print(g, e = TRUE, v = TRUE)

## The opposite operation
as_data_frame(g, what = "vertices")
as_data_frame(g, what = "edges")

Description

as_directed() converts an undirected graph to directed, as_undirected() does the opposite, it converts a directed graph to undirected.

Usage

as_directed(graph, mode = c("mutual", "arbitrary", "random", "acyclic"))

as_undirected(
  graph,
  mode = c("collapse", "each", "mutual"),
  edge.attr.comb = igraph_opt("edge.attr.comb")
)

Arguments

Details

Conversion algorithms for as_directed():

"arbitrary"

The number of edges in the graph stays the same, an arbitrarily directed edge is created for each undirected edge, but the direction of the edge is deterministic (i.e. it always points the same way if you call the function multiple times).

"mutual"

Two directed edges are created for each undirected edge, one in each direction.

"random"

The number of edges in the graph stays the same, and a randomly directed edge is created for each undirected edge. You will get different results if you call the function multiple times with the same graph.

"acyclic"

The number of edges in the graph stays the same, and a directed edge is created for each undirected edge such that the resulting graph is guaranteed to be acyclic. This is achieved by ensuring that edges always point from a lower index vertex to a higher index. Note that the graph may include cycles of length 1 if the original graph contained loop edges.

Conversion algorithms for as_undirected():

"each"

The number of edges remains constant, an undirected edge is created for each directed one, this version might create graphs with multiple edges.

"collapse"

One undirected edge will be created for each pair of vertices which are connected with at least one directed edge, no multiple edges will be created.

"mutual"

One undirected edge will be created for each pair of mutual edges. Non-mutual edges are ignored. This mode might create multiple edges if there are more than one mutual edge pairs between the same pair of vertices.

Value

A new graph object.

Related documentation in the C library

igraph_to_directed().

Author(s)

Gabor Csardi csardi.gabor@gmail.com

See Also

simplify() for removing multiple and/or loop edges from a graph.

Other conversion: as.matrix.igraph(), as_adj_list(), as_adjacency_matrix(), as_biadjacency_matrix(), as_data_frame(), as_edgelist(), as_graphnel(), as_long_data_frame(), graph_from_adj_list(), graph_from_graphnel()

Examples

g <- make_ring(10)
as_directed(g, "mutual")
g2 <- make_star(10)
as_undirected(g)

# Combining edge attributes
g3 <- make_ring(10, directed = TRUE, mutual = TRUE)
E(g3)$weight <- seq_len(ecount(g3))
ug3 <- as_undirected(g3)
print(ug3, e = TRUE)

x11(width = 10, height = 5)
layout(rbind(1:2))
plot(g3, layout = layout_in_circle, edge.label = E(g3)$weight)
plot(ug3, layout = layout_in_circle, edge.label = E(ug3)$weight)


g4 <- make_graph(c(
  1, 2, 3, 2, 3, 4, 3, 4, 5, 4, 5, 4,
  6, 7, 7, 6, 7, 8, 7, 8, 8, 7, 8, 9, 8, 9,
  9, 8, 9, 8, 9, 9, 10, 10, 10, 10
))
E(g4)$weight <- seq_len(ecount(g4))
ug4 <- as_undirected(g4,
  mode = "mutual",
  edge.attr.comb = list(weight = length)
)
print(ug4, e = TRUE)

Description

Sometimes it is useful to work with a standard representation of a graph, like an edge list.

Usage

as_edgelist(graph, names = TRUE)

Arguments

Details

as_edgelist() returns the list of edges in a graph.

Value

A ecount(graph) by 2 numeric matrix.

See Also

graph_from_adjacency_matrix(), read_graph()

Other conversion: as.matrix.igraph(), as_adj_list(), as_adjacency_matrix(), as_biadjacency_matrix(), as_data_frame(), as_directed(), as_graphnel(), as_long_data_frame(), graph_from_adj_list(), graph_from_graphnel()

Examples

g <- sample_gnp(10, 2 / 10)
as_edgelist(g)

V(g)$name <- LETTERS[seq_len(gorder(g))]
as_edgelist(g)

Description

The graphNEL class is defined in the graph package, it is another way to represent graphs. These functions are provided to convert between the igraph and the graphNEL objects.

Usage

as_graphnel(graph)

Arguments

Details

as_graphnel() converts an igraph graph to a graphNEL graph. It converts all graph/vertex/edge attributes. If the igraph graph has a vertex attribute ‘name’, then it will be used to assign vertex names in the graphNEL graph. Otherwise numeric igraph vertex ids will be used for this purpose.

Value

as_graphnel() returns a graphNEL graph object.

See Also

graph_from_graphnel() for the other direction, as_adjacency_matrix(), graph_from_adjacency_matrix(), as_adj_list() and graph_from_adj_list() for other graph representations.

Other conversion: as.matrix.igraph(), as_adj_list(), as_adjacency_matrix(), as_biadjacency_matrix(), as_data_frame(), as_directed(), as_edgelist(), as_long_data_frame(), graph_from_adj_list(), graph_from_graphnel()

Examples

## Undirected
g <- make_ring(10)
V(g)$name <- letters[1:10]
GNEL <- as_graphnel(g)
g2 <- graph_from_graphnel(GNEL)
g2

## Directed
g3 <- make_star(10, mode = "in")
V(g3)$name <- letters[1:10]
GNEL2 <- as_graphnel(g3)
g4 <- graph_from_graphnel(GNEL2)
g4

Description

Convert a vertex or edge sequence to an ordinary vector

Usage

as_ids(seq)

## S3 method for class 'igraph.vs'
as_ids(seq)

## S3 method for class 'igraph.es'
as_ids(seq)

Arguments

Details

For graphs without names, a numeric vector is returned, containing the internal numeric vertex or edge ids.

For graphs with names, and vertex sequences, the vertex names are returned in a character vector.

For graphs with names and edge sequences, a character vector is returned, with the ‘bar’ notation: a|b means an edge from vertex a to vertex b.

Value

A character or numeric vector, see details below.

See Also

Other vertex and edge sequences: E(), V(), igraph-es-attributes, igraph-es-indexing, igraph-es-indexing2, igraph-vs-attributes, igraph-vs-indexing, igraph-vs-indexing2, print.igraph.es(), print.igraph.vs()

Examples

g <- make_ring(10)
as_ids(V(g))
as_ids(E(g))

V(g)$name <- letters[1:10]
as_ids(V(g))
as_ids(E(g))

Description

A long data frame contains all metadata about both the vertices and edges of the graph. It contains one row for each edge, and all metadata about that edge and its incident vertices are included in that row. The names of the columns that contain the metadata of the incident vertices are prefixed with from_ and to_. The first two columns are always named from and to and they contain the numeric ids of the incident vertices. The rows are listed in the order of numeric vertex ids.

Usage

as_long_data_frame(graph)

Arguments

Value

A long data frame.

See Also

Other conversion: as.matrix.igraph(), as_adj_list(), as_adjacency_matrix(), as_biadjacency_matrix(), as_data_frame(), as_directed(), as_edgelist(), as_graphnel(), graph_from_adj_list(), graph_from_graphnel()

Examples

g <- make_(
  ring(10),
  with_vertex_(name = letters[1:10], color = "red"),
  with_edge_(weight = 1:10, color = "green")
)
as_long_data_frame(g)

Description

This is useful if you want to use functions defined on membership vectors, but your membership vector does not come from an igraph clustering method.

Usage

as_membership(x)

Arguments

Value

The input vector, with the membership class added.

See Also

Community detection cluster_edge_betweenness(), cluster_fast_greedy(), cluster_fluid_communities(), cluster_infomap(), cluster_label_prop(), cluster_leading_eigen(), cluster_leiden(), cluster_louvain(), cluster_optimal(), cluster_spinglass(), cluster_walktrap(), compare(), groups(), make_clusters(), membership(), modularity.igraph(), plot_dendrogram(), split_join_distance(), voronoi_cells()

Examples

## Compare to the correct clustering
g <- (make_full_graph(10) + make_full_graph(10)) %>%
  rewire(each_edge(p = 0.2))
correct <- rep(1:2, each = 10) %>% as_membership()
fc <- cluster_fast_greedy(g)
compare(correct, fc)
compare(correct, membership(fc))

Description

These functions convert various objects to igraph graphs.

Usage

as.igraph(x, ...)

Arguments

Details

You can use as.igraph() to convert various objects to igraph graphs. Right now the following objects are supported:

• codeigraphHRG These objects are created by the fit_hrg() and consensus_tree() functions.

Value

All these functions return an igraph graph.

Author(s)

Gabor Csardi csardi.gabor@gmail.com.

Examples

g <- make_full_graph(5) + make_full_graph(5)
hrg <- fit_hrg(g)
as.igraph(hrg)

Description

Get adjacency or edgelist representation of the network stored as an igraph object.

Usage

## S3 method for class 'igraph'
as.matrix(x, matrix.type = c("adjacency", "edgelist"), ...)

Arguments

Details

If matrix.type is "edgelist", then a two-column numeric edge list matrix is returned. The value of attrname is ignored.

If matrix.type is "adjacency", then a square adjacency matrix is returned. For adjacency matrices, you can use the attr keyword argument to use the values of an edge attribute in the matrix cells. See the documentation of as_adjacency_matrix for more details.

Other arguments passed through ... are passed to either as_adjacency_matrix() or as_edgelist() depending on the value of matrix.type.

Value

Depending on the value of matrix.type either a square adjacency matrix or a two-column numeric matrix representing the edgelist.

Author(s)

Michal Bojanowski, originally from the intergraph package

See Also

Other conversion: as_adj_list(), as_adjacency_matrix(), as_biadjacency_matrix(), as_data_frame(), as_directed(), as_edgelist(), as_graphnel(), as_long_data_frame(), graph_from_adj_list(), graph_from_graphnel()

Examples

g <- make_graph("zachary")
as.matrix(g, "adjacency")
as.matrix(g, "edgelist")
# use edge attribute "weight"
E(g)$weight <- rep(1:10, length.out = ecount(g))
as.matrix(g, "adjacency", sparse = FALSE, attr = "weight")

Description

The assortativity coefficient is positive if similar vertices (based on some external property) tend to connect to each, and negative otherwise.

Usage

assortativity(
  graph,
  values,
  ...,
  values.in = NULL,
  directed = TRUE,
  normalized = TRUE,
  types1 = NULL,
  types2 = NULL
)

assortativity_nominal(graph, types, directed = TRUE, normalized = TRUE)

assortativity_degree(graph, directed = TRUE)

Arguments

Details

The assortativity coefficient measures the level of homophyly of the graph, based on some vertex labeling or values assigned to vertices. If the coefficient is high, that means that connected vertices tend to have the same labels or similar assigned values.

M.E.J. Newman defined two kinds of assortativity coefficients, the first one is for categorical labels of vertices. assortativity_nominal() calculates this measure. It is defined as

$r=\frac{\sum_i e_{ii}-\sum_i a_i b_i}{1-\sum_i a_i b_i}$

where $e_{ij}$ is the fraction of edges connecting vertices of type $i$ and $j$, $a_i=\sum_j e_{ij}$ and $b_j=\sum_i e_{ij}$.

The second assortativity variant is based on values assigned to the vertices. assortativity() calculates this measure. It is defined as

$r=\frac1{\sigma_q^2}\sum_{jk} jk(e_{jk}-q_j q_k)$

for undirected graphs ($q_i=\sum_j e_{ij}$) and as

$r=\frac1{\sigma_o\sigma_i}\sum_{jk}jk(e_{jk}-q_j^o q_k^i)$

for directed ones. Here $q_i^o=\sum_j e_{ij}$, $q_i^i=\sum_j e_{ji}$, moreover, $\sigma_q$, $\sigma_o$ and $\sigma_i$ are the standard deviations of $q$, $q^o$ and $q^i$, respectively.

The reason of the difference is that in directed networks the relationship is not symmetric, so it is possible to assign different values to the outgoing and the incoming end of the edges.

assortativity_degree() uses vertex degree as vertex values and calls assortativity().

Undirected graphs are effectively treated as directed ones with all-reciprocal edges. Thus, self-loops are taken into account twice in undirected graphs.

Value

A single real number.

Related documentation in the C library

igraph_assortativity(), igraph_assortativity_nominal(), igraph_assortativity_degree().

Author(s)

Gabor Csardi csardi.gabor@gmail.com

References

M. E. J. Newman: Mixing patterns in networks, Phys. Rev. E 67, 026126 (2003) https://arxiv.org/abs/cond-mat/0209450

M. E. J. Newman: Assortative mixing in networks, Phys. Rev. Lett. 89, 208701 (2002) https://arxiv.org/abs/cond-mat/0205405

Examples

# random network, close to zero
assortativity_degree(sample_gnp(10000, 3 / 10000))

# BA model, tends to be dissortative
assortativity_degree(sample_pa(10000, m = 4))

Description

Kleinberg's authority centrality scores.

Kleinberg's hub centrality scores.

Usage

authority_score(
  graph,
  scale = TRUE,
  weights = NULL,
  options = arpack_defaults()
)

hub_score(graph, scale = TRUE, weights = NULL, options = arpack_defaults())

Arguments

See Also

Centrality measures alpha_centrality(), betweenness(), closeness(), diversity(), eigen_centrality(), harmonic_centrality(), hits_scores(), page_rank(), power_centrality(), spectrum(), strength(), subgraph_centrality()

Description

Compute the generating set of the automorphism group of a graph.

Usage

automorphism_group(
  graph,
  colors = NULL,
  sh = c("fm", "f", "fs", "fl", "flm", "fsm"),
  details = FALSE
)

Arguments

Details

An automorphism of a graph is a permutation of its vertices which brings the graph into itself. The automorphisms of a graph form a group and there exists a subset of this group (i.e. a set of permutations) such that every other permutation can be expressed as a combination of these permutations. These permutations are called the generating set of the automorphism group.

This function calculates a possible generating set of the automorphism of a graph using the BLISS algorithm. See also the BLISS homepage at http://www.tcs.hut.fi/Software/bliss/index.html. The calculated generating set is not necessarily minimal, and it may depend on the splitting heuristics used by BLISS.

Value

When details is FALSE, a list of vertex permutations that form a generating set of the automorphism group of the input graph. When details is TRUE, a named list with two members:

Related documentation in the C library

igraph_automorphism_group().

Author(s)

Tommi Junttila (http://users.ics.aalto.fi/tjunttil/) for BLISS, Gabor Csardi csardi.gabor@gmail.com for the igraph glue code and Tamas Nepusz ntamas@gmail.com for this manual page.

References

Tommi Junttila and Petteri Kaski: Engineering an Efficient Canonical Labeling Tool for Large and Sparse Graphs, Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments and the Fourth Workshop on Analytic Algorithms and Combinatorics. 2007.

See Also

canonical_permutation(), permute(), count_automorphisms()

Other graph automorphism: count_automorphisms()

Examples

## A ring has n*2 automorphisms, and a possible generating set is one that
## "turns" the ring by one vertex to the left or right
g <- make_ring(10)
automorphism_group(g)

Description

The vertex and edge betweenness are (roughly) defined by the number of geodesics (shortest paths) going through a vertex or an edge.

Usage

betweenness(
  graph,
  v = V(graph),
  directed = TRUE,
  weights = NULL,
  normalized = FALSE,
  cutoff = -1
)

edge_betweenness(
  graph,
  e = E(graph),
  directed = TRUE,
  weights = NULL,
  cutoff = -1
)

Arguments

Details

The vertex betweenness of vertex v is defined by

$\sum_{i\ne j, i\ne v, j\ne v} g_{ivj}/g_{ij}$

The edge betweenness of edge e is defined by

$\sum_{i\ne j} g_{iej}/g_{ij}.$

betweenness() calculates vertex betweenness, edge_betweenness() calculates edge betweenness.

Here $g_{ij}$ is the total number of shortest paths between vertices $i$ and $j$ while $g_{ivj}$ is the number of those shortest paths which pass though vertex $v$.

Both functions allow you to consider only paths of length cutoff or smaller; this can be run for larger graphs, as the running time is not quadratic (if cutoff is small). If cutoff is negative (the default), then the function calculates the exact betweenness scores. Since igraph 1.6.0, a cutoff value of zero is treated literally, i.e. paths of length larger than zero are ignored.

For calculating the betweenness a similar algorithm to the one proposed by Brandes (see References) is used.

Value

A numeric vector with the betweenness score for each vertex in v for betweenness().

A numeric vector with the edge betweenness score for each edge in e for edge_betweenness().

Note

edge_betweenness() might give false values for graphs with multiple edges.

Author(s)

Gabor Csardi csardi.gabor@gmail.com

References

Freeman, L.C. (1979). Centrality in Social Networks I: Conceptual Clarification. Social Networks, 1, 215-239. doi:10.1016/0378-8733(78)90021-7

Ulrik Brandes, A Faster Algorithm for Betweenness Centrality. Journal of Mathematical Sociology 25(2):163-177, 2001. doi:10.1080/0022250X.2001.9990249

See Also

closeness(), degree(), harmonic_centrality()

Centrality measures alpha_centrality(), authority_score(), closeness(), diversity(), eigen_centrality(), harmonic_centrality(), hits_scores(), page_rank(), power_centrality(), spectrum(), strength(), subgraph_centrality()

Examples

g <- sample_gnp(10, 3 / 10)
betweenness(g)
edge_betweenness(g)

Description

Breadth-first search is an algorithm to traverse a graph. We start from a root vertex and spread along every edge “simultaneously”.

Usage

bfs(
  graph,
  root,
  mode = c("out", "in", "all", "total"),
  unreachable = TRUE,
  restricted = NULL,
  order = TRUE,
  rank = FALSE,
  father = FALSE,
  pred = FALSE,
  succ = FALSE,
  dist = FALSE,
  callback = NULL,
  extra = NULL,
  rho = parent.frame(),
  neimode = deprecated()
)

Arguments

Details

The callback function must have the following arguments:

graph

The input graph is passed to the callback function here.

data

A named numeric vector, with the following entries: ‘vid’, the vertex that was just visited, ‘pred’, its predecessor (zero if this is the first vertex), ‘succ’, its successor (zero if this is the last vertex), ‘rank’, the rank of the current vertex, ‘dist’, its distance from the root of the search tree.

extra

The extra argument.

The callback must return FALSE to continue the search or TRUE to terminate it. See examples below on how to use the callback function.

Value

A named list with the following entries:

Note that order, rank, father, pred, succ and dist might be NULL if their corresponding argument is FALSE, i.e. if their calculation is not requested.

Author(s)

Gabor Csardi csardi.gabor@gmail.com

See Also

dfs() for depth-first search.

Other structural.properties: component_distribution(), connect(), constraint(), coreness(), degree(), dfs(), distance_table(), edge_density(), feedback_arc_set(), girth(), is_acyclic(), is_dag(), is_matching(), k_shortest_paths(), knn(), reciprocity(), subcomponent(), subgraph(), topo_sort(), transitivity(), unfold_tree(), which_multiple(), which_mutual()

Examples

## Two rings
bfs(make_ring(10) %du% make_ring(10),
  root = 1, "out",
  order = TRUE, rank = TRUE, father = TRUE, pred = TRUE,
  succ = TRUE, dist = TRUE
)

## How to use a callback
f <- function(graph, data, extra) {
  print(data)
  FALSE
}
tmp <- bfs(make_ring(10) %du% make_ring(10),
  root = 1, "out",
  callback = f
)

## How to use a callback to stop the search
## We stop after visiting all vertices in the initial component
f <- function(graph, data, extra) {
  data["succ"] == -1
}
bfs(make_ring(10) %du% make_ring(10), root = 1, callback = f)

Description

Finding the biconnected components of a graph

Usage

biconnected_components(graph)

Arguments

Details

A graph is biconnected if the removal of any single vertex (and its adjacent edges) does not disconnect it.

A biconnected component of a graph is a maximal biconnected subgraph of it. The biconnected components of a graph can be given by the partition of its edges: every edge is a member of exactly one biconnected component. Note that this is not true for vertices: the same vertex can be part of many biconnected components.

Value

A named list with three components:

Related documentation in the C library

igraph_biconnected_components().

Author(s)

Gabor Csardi csardi.gabor@gmail.com

See Also

articulation_points(), components(), is_connected(), vertex_connectivity()

Connected components articulation_points(), component_distribution(), decompose(), is_biconnected()

Examples

g <- disjoint_union(make_full_graph(5), make_full_graph(5))
clu <- components(g)$membership
g <- add_edges(g, c(which(clu == 1), which(clu == 2)))
bc <- biconnected_components(g)

Description

This function decides whether the vertices of a network can be mapped to two vertex types in a way that no vertices of the same type are connected.

Usage

bipartite_mapping(graph)

Arguments

Details

A bipartite graph in igraph has a ‘type’ vertex attribute giving the two vertex types.

This function simply checks whether a graph could be bipartite. It tries to find a mapping that gives a possible division of the vertices into two classes, such that no two vertices of the same class are connected by an edge.

The existence of such a mapping is equivalent of having no circuits of odd length in the graph. A graph with loop edges cannot bipartite.

Note that the mapping is not necessarily unique, e.g. if the graph has at least two components, then the vertices in the separate components can be mapped independently.

Value

A named list with two elements:

Related documentation in the C library

igraph_is_bipartite().

Author(s)

Gabor Csardi csardi.gabor@gmail.com

See Also

Bipartite graphs bipartite_projection(), is_bipartite(), make_bipartite_graph()

Examples

## Rings with an even number of vertices are bipartite
g <- make_ring(10)
bipartite_mapping(g)

## All star graphs are bipartite
g2 <- make_star(10)
bipartite_mapping(g2)

## A graph containing a triangle is not bipartite
g3 <- make_ring(10)
g3 <- add_edges(g3, c(1, 3))
bipartite_mapping(g3)

Description

A bipartite graph is projected into two one-mode networks

Usage

bipartite_projection(
  graph,
  types = NULL,
  multiplicity = TRUE,
  probe1 = NULL,
  which = c("both", "true", "false"),
  remove.type = TRUE
)

bipartite_projection_size(graph, types = NULL)

Arguments

Details

Bipartite graphs have a type vertex attribute in igraph, this is boolean and FALSE for the vertices of the first kind and TRUE for vertices of the second kind.

bipartite_projection_size() calculates the number of vertices and edges in the two projections of the bipartite graphs, without calculating the projections themselves. This is useful to check how much memory the projections would need if you have a large bipartite graph.

bipartite_projection() calculates the actual projections. You can use the probe1 argument to specify the order of the projections in the result. By default vertex type FALSE is the first and TRUE is the second.

bipartite_projection() keeps vertex attributes.

Value

A list of two undirected graphs. See details above.

Related documentation in the C library

igraph_bipartite_projection_size().

Author(s)

Gabor Csardi csardi.gabor@gmail.com

See Also

Bipartite graphs bipartite_mapping(), is_bipartite(), make_bipartite_graph()

Examples

## Projection of a full bipartite graph is a full graph
g <- make_full_bipartite_graph(10, 5)
proj <- bipartite_projection(g)
graph.isomorphic(proj[[1]], make_full_graph(10))
graph.isomorphic(proj[[2]], make_full_graph(5))

## The projection keeps the vertex attributes
M <- matrix(0, nrow = 5, ncol = 3)
rownames(M) <- c("Alice", "Bob", "Cecil", "Dan", "Ethel")
colnames(M) <- c("Party", "Skiing", "Badminton")
M[] <- sample(0:1, length(M), replace = TRUE)
M
g2 <- graph_from_biadjacency_matrix(M)
g2$name <- "Event network"
proj2 <- bipartite_projection(g2)
print(proj2[[1]], g = TRUE, e = TRUE)
print(proj2[[2]], g = TRUE, e = TRUE)

Description

Concatenate edge sequences

Usage

## S3 method for class 'igraph.es'
c(..., recursive = FALSE)

Arguments

Value

An edge sequence, the input sequences concatenated.

See Also

Other vertex and edge sequence operations: c.igraph.vs(), difference.igraph.es(), difference.igraph.vs(), igraph-es-indexing, igraph-es-indexing2, igraph-vs-indexing, igraph-vs-indexing2, intersection.igraph.es(), intersection.igraph.vs(), rev.igraph.es(), rev.igraph.vs(), union.igraph.es(), union.igraph.vs(), unique.igraph.es(), unique.igraph.vs()

Examples

g <- make_(ring(10), with_vertex_(name = LETTERS[1:10]))
c(E(g)[1], E(g)["A|B"], E(g)[1:4])

Description

Concatenate vertex sequences

Usage

## S3 method for class 'igraph.vs'
c(..., recursive = FALSE)

Arguments

Value

A vertex sequence, the input sequences concatenated.

See Also

Other vertex and edge sequence operations: c.igraph.es(), difference.igraph.es(), difference.igraph.vs(), igraph-es-indexing, igraph-es-indexing2, igraph-vs-indexing, igraph-vs-indexing2, intersection.igraph.es(), intersection.igraph.vs(), rev.igraph.es(), rev.igraph.vs(), union.igraph.es(), union.igraph.vs(), unique.igraph.es(), unique.igraph.vs()

Examples

g <- make_(ring(10), with_vertex_(name = LETTERS[1:10]))
c(V(g)[1], V(g)["A"], V(g)[1:4])

Description

The canonical permutation brings every isomorphic graphs into the same (labeled) graph.

Usage

canonical_permutation(
  graph,
  colors = NULL,
  sh = c("fm", "f", "fs", "fl", "flm", "fsm")
)

Arguments

Details

canonical_permutation() computes a permutation which brings the graph into canonical form, as defined by the BLISS algorithm. All isomorphic graphs have the same canonical form.

See the paper below for the details about BLISS. This and more information is available at http://www.tcs.hut.fi/Software/bliss/index.html.

The possible values for the sh argument are:

"f"

First non-singleton cell.

"fl"

First largest non-singleton cell.

"fs"

First smallest non-singleton cell.

"fm"

First maximally non-trivially connectec non-singleton cell.

"flm"

Largest maximally non-trivially connected non-singleton cell.

"fsm"

Smallest maximally non-trivially connected non-singleton cell.

See the paper in references for details about these.

Value

A list with the following members:

Related documentation in the C library

igraph_canonical_permutation().

Author(s)

Tommi Junttila for BLISS, Gabor Csardi csardi.gabor@gmail.com for the igraph and R interfaces.

References

Tommi Junttila and Petteri Kaski: Engineering an Efficient Canonical Labeling Tool for Large and Sparse Graphs, Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments and the Fourth Workshop on Analytic Algorithms and Combinatorics. 2007.

See Also

permute() to apply a permutation to a graph, graph.isomorphic() for deciding graph isomorphism, possibly based on canonical labels.

Other graph isomorphism: count_isomorphisms(), count_subgraph_isomorphisms(), graph_from_isomorphism_class(), isomorphic(), isomorphism_class(), isomorphisms(), subgraph_isomorphic(), subgraph_isomorphisms()

Examples

## Calculate the canonical form of a random graph
g1 <- sample_gnm(10, 20)
cp1 <- canonical_permutation(g1)
cf1 <- permute(g1, cp1$labeling)

## Do the same with a random permutation of it
g2 <- permute(g1, sample(vcount(g1)))
cp2 <- canonical_permutation(g2)
cf2 <- permute(g2, cp2$labeling)

## Check that they are the same
el1 <- as_edgelist(cf1)
el2 <- as_edgelist(cf2)
el1 <- el1[order(el1[, 1], el1[, 2]), ]
el2 <- el2[order(el2[, 1], el2[, 2]), ]
all(el1 == el2)

Description

This is a color blind friendly palette from https://jfly.uni-koeln.de/color/. It has 8 colors.

Usage

categorical_pal(n)

Arguments

Details

This is the suggested palette for visualizations where vertex colors mark categories, e.g. community membership.

Value

A character vector of RGB color codes.

Examples

library(igraphdata)
data(karate)
karate <- karate 
  add_layout_(with_fr()) 
  set_vertex_attr("size", value = 10)

cl_k <- cluster_optimal(karate)

V(karate)$color <- membership(cl_k)
karate$palette <- categorical_pal(length(cl_k))
plot(karate)

See Also

Other palettes: diverging_pal(), r_pal(), sequential_pal()

Description

See centralize() for a summary of graph centralization.

Usage

centr_betw(graph, directed = TRUE, normalized = TRUE)

Arguments

Value

A named list with the following components:

See Also

Other centralization related: centr_betw_tmax(), centr_clo(), centr_clo_tmax(), centr_degree(), centr_degree_tmax(), centr_eigen(), centr_eigen_tmax(), centralize()

Examples

# A BA graph is quite centralized
g <- sample_pa(1000, m = 4)
centr_degree(g)$centralization
centr_clo(g, mode = "all")$centralization
centr_betw(g, directed = FALSE)$centralization
centr_eigen(g, directed = FALSE)$centralization

Description

See centralize() for a summary of graph centralization.

Usage

centr_betw_tmax(graph = NULL, nodes = 0, directed = TRUE)

Arguments

Value

Real scalar, the theoretical maximum (unnormalized) graph betweenness centrality score for graphs with given order and other parameters.

Related documentation in the C library

igraph_centralization_betweenness_tmax().

See Also

Other centralization related: centr_betw(), centr_clo(), centr_clo_tmax(), centr_degree(), centr_degree_tmax(), centr_eigen(), centr_eigen_tmax(), centralize()

Examples

# A BA graph is quite centralized
g <- sample_pa(1000, m = 4)
centr_betw(g, normalized = FALSE)$centralization %>%
  `/`(centr_betw_tmax(g))
centr_betw(g, normalized = TRUE)$centralization

Description

See centralize() for a summary of graph centralization.

Usage

centr_clo(graph, mode = c("out", "in", "all", "total"), normalized = TRUE)

Arguments

Value

A named list with the following components:

Related documentation in the C library

igraph_centralization_closeness().

See Also

Other centralization related: centr_betw(), centr_betw_tmax(), centr_clo_tmax(), centr_degree(), centr_degree_tmax(), centr_eigen(), centr_eigen_tmax(), centralize()

Examples

# A BA graph is quite centralized
g <- sample_pa(1000, m = 4)
centr_degree(g)$centralization
centr_clo(g, mode = "all")$centralization
centr_betw(g, directed = FALSE)$centralization
centr_eigen(g, directed = FALSE)$centralization

Description

See centralize() for a summary of graph centralization.

Usage

centr_clo_tmax(graph = NULL, nodes = 0, mode = c("out", "in", "all", "total"))

Arguments

Value

Real scalar, the theoretical maximum (unnormalized) graph closeness centrality score for graphs with given order and other parameters.

Related documentation in the C library

igraph_centralization_closeness_tmax().

See Also

Other centralization related: centr_betw(), centr_betw_tmax(), centr_clo(), centr_degree(), centr_degree_tmax(), centr_eigen(), centr_eigen_tmax(), centralize()

Examples

# A BA graph is quite centralized
g <- sample_pa(1000, m = 4)
centr_clo(g, normalized = FALSE)$centralization %>%
  `/`(centr_clo_tmax(g))
centr_clo(g, normalized = TRUE)$centralization

Description

See centralize() for a summary of graph centralization.

Usage

centr_degree(
  graph,
  mode = c("all", "out", "in", "total"),
  loops = TRUE,
  normalized = TRUE
)

Arguments

Value

A named list with the following components:

Related documentation in the C library

igraph_centralization_degree().

See Also

Other centralization related: centr_betw(), centr_betw_tmax(), centr_clo(), centr_clo_tmax(), centr_degree_tmax(), centr_eigen(), centr_eigen_tmax(), centralize()

Examples

# A BA graph is quite centralized
g <- sample_pa(1000, m = 4)
centr_degree(g)$centralization
centr_clo(g, mode = "all")$centralization
centr_betw(g, directed = FALSE)$centralization
centr_eigen(g, directed = FALSE)$centralization

Description

See centralize() for a summary of graph centralization.

Usage

centr_degree_tmax(
  graph = NULL,
  nodes = 0,
  mode = c("all", "out", "in", "total"),
  loops
)

Arguments

Value

Real scalar, the theoretical maximum (unnormalized) graph degree centrality score for graphs with given order and other parameters.

See Also

Other centralization related: centr_betw(), centr_betw_tmax(), centr_clo(), centr_clo_tmax(), centr_degree(), centr_eigen(), centr_eigen_tmax(), centralize()

Examples

# A BA graph is quite centralized
g <- sample_pa(1000, m = 4)
centr_degree(g, normalized = FALSE)$centralization %>%
  `/`(centr_degree_tmax(g, loops = FALSE))
centr_degree(g, normalized = TRUE)$centralization