Title:	Network Analysis and Visualization
Version:	2.1.4
Description:	Routines for simple graphs and network analysis. It can handle large graphs very well and provides functions for generating random and regular graphs, graph visualization, centrality methods and much more.
License:	GPL-2 | GPL-3 [expanded from: GPL (≥ 2)]
URL:	https://r.igraph.org/, https://igraph.org/, https://igraph.discourse.group/
BugReports:	https://github.com/igraph/rigraph/issues
Depends:	methods, R (≥ 3.5.0)
Imports:	cli, graphics, grDevices, lifecycle, magrittr, Matrix, pkgconfig (≥ 2.0.0), rlang, stats, utils, vctrs
Suggests:	ape (≥ 5.7-0.1), callr, decor, digest, igraphdata, knitr, rgl (≥ 1.3.14), rmarkdown, scales, stats4, tcltk, testthat, vdiffr, withr
Enhances:	graph
LinkingTo:	cpp11 (≥ 0.5.0)
VignetteBuilder:	knitr
Config/Needs/build:	roxygen2, devtools, irlba, pkgconfig, igraph/igraph.r2cdocs, moodymudskipper/devtag
Config/Needs/coverage:	covr
Config/Needs/website:	readr
Config/testthat/edition:	3
Config/testthat/parallel:	true
Config/testthat/start-first:	vs-es, scan, vs-operators, weakref, watts.strogatz.game
Encoding:	UTF-8
RoxygenNote:	7.3.2.9000
SystemRequirements:	libxml2 (optional), glpk (>= 4.57, optional)
NeedsCompilation:	yes
Packaged:	2025-01-22 19:28:33 UTC; kirill
Author:	Gábor Csárdi [aut], Tamás Nepusz [aut], Vincent Traag [aut], Szabolcs Horvát [aut], Fabio Zanini [aut], Daniel Noom [aut], Kirill Müller [aut, cre], Maëlle Salmon [ctb], Michael Antonov [ctb], Chan Zuckerberg Initiative [fnd]
Maintainer:	Kirill Müller <kirill@cynkra.com>
Repository:	CRAN
Date/Publication:	2025-01-23 10:20:02 UTC

The igraph package

Description

igraph is a library and R package for network analysis.

Introduction

The main goals of the igraph library is to provide a set of data types and functions for 1) pain-free implementation of graph algorithms, 2) fast handling of large graphs, with millions of vertices and edges, 3) allowing rapid prototyping via high level languages like R.

igraph graphs

igraph graphs have a class ‘igraph’. They are printed to the screen in a special format, here is an example, a ring graph created using make_ring():

    IGRAPH U--- 10 10 -- Ring graph
    + attr: name (g/c), mutual (g/x), circular (g/x)  

‘IGRAPH’ denotes that this is an igraph graph. Then come four bits that denote the kind of the graph: the first is ‘U’ for undirected and ‘D’ for directed graphs. The second is ‘N’ for named graph (i.e. if the graph has the ‘name’ vertex attribute set). The third is ‘W’ for weighted graphs (i.e. if the ‘weight’ edge attribute is set). The fourth is ‘B’ for bipartite graphs (i.e. if the ‘type’ vertex attribute is set).

Then come two numbers, the number of vertices and the number of edges in the graph, and after a double dash, the name of the graph (the ‘name’ graph attribute) is printed if present. The second line is optional and it contains all the attributes of the graph. This graph has a ‘name’ graph attribute, of type character, and two other graph attributes called ‘mutual’ and ‘circular’, of a complex type. A complex type is simply anything that is not numeric or character. See the documentation of print.igraph() for details.

If you want to see the edges of the graph as well, then use the print_all() function:

    > print_all(g)
    IGRAPH badcafe U--- 10 10 -- Ring graph
    + attr: name (g/c), mutual (g/x), circular (g/x)
    + edges:
     [1] 1-- 2 2-- 3 3-- 4 4-- 5 5-- 6 6-- 7 7-- 8 8-- 9 9--10 1--10 

Creating graphs

There are many functions in igraph for creating graphs, both deterministic and stochastic; stochastic graph constructors are called ‘games’.

To create small graphs with a given structure probably the graph_from_literal() function is easiest. It uses R's formula interface, its manual page contains many examples. Another option is make_graph(), which takes numeric vertex ids directly. graph_from_atlas() creates graph from the Graph Atlas, make_graph() can create some special graphs.

To create graphs from field data, graph_from_edgelist(), graph_from_data_frame() and graph_from_adjacency_matrix() are probably the best choices.

The igraph package includes some classic random graphs like the Erdős-Rényi GNP and GNM graphs (sample_gnp(), sample_gnm()) and some recent popular models, like preferential attachment (sample_pa()) and the small-world model (sample_smallworld()).

Vertex and edge IDs

Vertices and edges have numerical vertex ids in igraph. Vertex ids are always consecutive and they start with one. I.e. for a graph with n vertices the vertex ids are between 1 and n. If some operation changes the number of vertices in the graphs, e.g. a subgraph is created via induced_subgraph(), then the vertices are renumbered to satisfy this criteria.

The same is true for the edges as well, edge ids are always between one and m, the total number of edges in the graph.

It is often desirable to follow vertices along a number of graph operations, and vertex ids don't allow this because of the renumbering. The solution is to assign attributes to the vertices. These are kept by all operations, if possible. See more about attributes in the next section.

Attributes

In igraph it is possible to assign attributes to the vertices or edges of a graph, or to the graph itself. igraph provides flexible constructs for selecting a set of vertices or edges based on their attribute values, see vertex_attr(), V() and E() for details.

Some vertex/edge/graph attributes are treated specially. One of them is the ‘name’ attribute. This is used for printing the graph instead of the numerical ids, if it exists. Vertex names can also be used to specify a vector or set of vertices, in all igraph functions. E.g. degree() has a v argument that gives the vertices for which the degree is calculated. This argument can be given as a character vector of vertex names.

Edges can also have a ‘name’ attribute, and this is treated specially as well. Just like for vertices, edges can also be selected based on their names, e.g. in the delete_edges() and other functions.

We note here, that vertex names can also be used to select edges. The form ‘from|to’, where ‘from’ and ‘to’ are vertex names, select a single, possibly directed, edge going from ‘from’ to ‘to’. The two forms can also be mixed in the same edge selector.

Other attributes define visualization parameters, see igraph.plotting for details.

Attribute values can be set to any R object, but note that storing the graph in some file formats might result the loss of complex attribute values. All attribute values are preserved if you use base::save() and base::load() to store/retrieve your graphs.

Visualization

igraph provides three different ways for visualization. The first is the plot.igraph() function. (Actually you don't need to write plot.igraph(), plot() is enough. This function uses regular R graphics and can be used with any R device.

The second function is tkplot(), which uses a Tk GUI for basic interactive graph manipulation. (Tk is quite resource hungry, so don't try this for very large graphs.)

The third way requires the rgl package and uses OpenGL. See the rglplot() function for the details.

Make sure you read igraph.plotting before you start plotting your graphs.

File formats

igraph can handle various graph file formats, usually both for reading and writing. We suggest that you use the GraphML file format for your graphs, except if the graphs are too big. For big graphs a simpler format is recommended. See read_graph() and write_graph() for details.

Further information

The igraph homepage is at https://igraph.org. See especially the documentation section. Join the discussion forum at https://igraph.discourse.group if you have questions or comments.

Author(s)

Maintainer: Kirill Müller kirill@cynkra.com (ORCID)

Authors:

• Gábor Csárdi csardi.gabor@gmail.com (ORCID)

• Tamás Nepusz ntamas@gmail.com (ORCID)

• Vincent Traag (ORCID)

• Szabolcs Horvát szhorvat@gmail.com (ORCID)

• Fabio Zanini fabio.zanini@unsw.edu.au (ORCID)

• Daniel Noom

Other contributors:

• Maëlle Salmon [contributor]

• Michael Antonov [contributor]

• Chan Zuckerberg Initiative [funder]

See Also

Useful links:

• https://r.igraph.org/

• https://igraph.org/

• https://igraph.discourse.group/

• Report bugs at https://github.com/igraph/rigraph/issues

Helpers within vertex/index sequences

Description

Functions to be used only with ⁠[.igraph.es⁠ and ⁠[.igraph.vs⁠

Usage

.nei(...)

.innei(...)

.outnei(...)

.inc(...)

.from(...)

.to(...)

Arguments

Details

See [.igraph.vs and [.igraph.es.

Value

An error

Query and manipulate a graph as it were an adjacency matrix

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

Query and manipulate a graph as it were an adjacency list

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

Magrittr's pipes

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

Add vertices, edges or another graph to a graph

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)

Add edges to a graph

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)

Add layout to graph

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

Add vertices to a graph

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)

Add edges to a graph

Description

add.edges() was renamed to add_edges() to create a more consistent API.

Usage

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

Arguments

Various vertex shapes when plotting igraph graphs

Description

add.vertex.shape() was renamed to add_shape() to create a more consistent API.

Usage

add.vertex.shape(
  shape,
  clip = shape_noclip,
  plot = shape_noplot,
  parameters = list()
)

Arguments

Add vertices to a graph

Description

add.vertices() was renamed to add_vertices() to create a more consistent API.

Usage

add.vertices(graph, nv, ..., attr = list())

Arguments

Adjacent vertices of multiple vertices in a graph

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

Find triangles in graphs

Description

adjacent.triangles() was renamed to count_triangles() to create a more consistent API.

Usage

adjacent.triangles(graph, vids = V(graph))

Arguments

Generate an evolving random graph with preferential attachment and aging

Description

aging.ba.game() was renamed to sample_pa_age() to create a more consistent API.

Usage

aging.ba.game(
  n,
  pa.exp,
  aging.exp,
  m = NULL,
  aging.bin = 300,
  out.dist = NULL,
  out.seq = NULL,
  out.pref = FALSE,
  directed = TRUE,
  zero.deg.appeal = 1,
  zero.age.appeal = 0,
  deg.coef = 1,
  age.coef = 1,
  time.window = NULL
)

Arguments

Generate an evolving random graph with preferential attachment and aging

Description

aging.barabasi.game() was renamed to sample_pa_age() to create a more consistent API.

Usage

aging.barabasi.game(
  n,
  pa.exp,
  aging.exp,
  m = NULL,
  aging.bin = 300,
  out.dist = NULL,
  out.seq = NULL,
  out.pref = FALSE,
  directed = TRUE,
  zero.deg.appeal = 1,
  zero.age.appeal = 0,
  deg.coef = 1,
  age.coef = 1,
  time.window = NULL
)

Arguments

Generate an evolving random graph with preferential attachment and aging

Description

aging.prefatt.game() was renamed to sample_pa_age() to create a more consistent API.

Usage

aging.prefatt.game(
  n,
  pa.exp,
  aging.exp,
  m = NULL,
  aging.bin = 300,
  out.dist = NULL,
  out.seq = NULL,
  out.pref = FALSE,
  directed = TRUE,
  zero.deg.appeal = 1,
  zero.age.appeal = 0,
  deg.coef = 1,
  age.coef = 1,
  time.window = NULL
)

Arguments

List all simple paths from one source

Description

This function lists all simple paths from one source vertex to another vertex or vertices. A path is simple if contains no repeated vertices.

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

Find Bonacich alpha centrality scores of network positions

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)

Find Bonacich alpha centrality scores of network positions

Description

alpha.centrality() was renamed to alpha_centrality() to create a more consistent API.

Usage

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

Arguments

Are two vertices adjacent?

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)

Are two vertices adjacent?

Description

are.connected() was renamed to are_adjacent() to create a more consistent API.

Usage

are.connected(graph, v1, v2)

Arguments

ARPACK eigenvector calculation

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

Articulation points and bridges of a graph

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)

Articulation points and bridges of a graph

Description

articulation.points() was renamed to articulation_points() to create a more consistent API.

Usage

articulation.points(graph)

Arguments

Convert a graph to an adjacency matrix

Description

We plan to remove as_adj() in favor of the more explicitly named as_adjacency_matrix() so please use as_adjacency_matrix() instead.

Usage

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

Arguments

Adjacency lists

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)

Convert a graph to an adjacency matrix

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

Bipartite adjacency matrix of a bipartite graph

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)

Creating igraph graphs from data frames or vice-versa

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

Convert between directed and undirected graphs

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)

Convert a graph to an edge list

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)

Convert igraph graphs to graphNEL objects from the graph package

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

Convert a vertex or edge sequence to an ordinary vector

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

As incidence matrix

Description

as_incidence_matrix() was renamed to as_biadjacency_matrix() to create a more consistent API.

Usage

as_incidence_matrix(...)

Details

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.

Convert a graph to a long data frame

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)

Declare a numeric vector as a membership vector

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

as_phylo

Description

as_phylo methods were renamed as.phylo for more consistency with other R methods.

Usage

as_phylo(x, ...)

Arguments

Convert between directed and undirected graphs

Description

as.directed() was renamed to as_directed() to create a more consistent API.

Usage

as.directed(graph, mode = c("mutual", "arbitrary", "random", "acyclic"))

Arguments

Conversion to igraph

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)

Convert igraph objects to adjacency or edge list matrices

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

Convert between undirected and unundirected graphs

Description

as.undirected() was renamed to as_undirected() to create a more consistent API.

Usage

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

Arguments

Assortativity coefficient

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

Assortativity coefficient

Description

assortativity.degree() was renamed to assortativity_degree() to create a more consistent API.

Usage

assortativity.degree(graph, directed = TRUE)

Arguments

Assortativity coefficient

Description

assortativity.nominal() was renamed to assortativity_nominal() to create a more consistent API.

Usage

assortativity.nominal(graph, types, directed = TRUE, normalized = TRUE)

Arguments

Trait-based random generation

Description

asymmetric.preference.game() was renamed to sample_asym_pref() to create a more consistent API.

Usage

asymmetric.preference.game(
  nodes,
  types,
  type.dist.matrix = matrix(1, types, types),
  pref.matrix = matrix(1, types, types),
  loops = FALSE
)

Arguments

Kleinberg's authority centrality scores.

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

Kleinberg's hub and authority centrality scores.

Description

authority.score() was renamed to authority_score() to create a more consistent API.

Usage

authority.score(
  graph,
  scale = TRUE,
  weights = NULL,
  options = arpack_defaults()
)

Arguments

Optimal edge curvature when plotting graphs

Description

autocurve.edges() was renamed to curve_multiple() to create a more consistent API.

Usage

autocurve.edges(graph, start = 0.5)

Arguments

Generating set of the automorphism group of a graph

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)

Number of automorphisms

Description

automorphisms() was renamed to count_automorphisms() to create a more consistent API.

Usage

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

Arguments

Shortest (directed or undirected) paths between vertices

Description

average.path.length() was renamed to mean_distance() to create a more consistent API.

Usage

average.path.length(
  graph,
  weights = NULL,
  directed = TRUE,
  unconnected = TRUE,
  details = FALSE
)

Arguments

Generate random graphs using preferential attachment

Description

ba.game() was renamed to sample_pa() to create a more consistent API.

Usage

ba.game(
  n,
  power = 1,
  m = NULL,
  out.dist = NULL,
  out.seq = NULL,
  out.pref = FALSE,
  zero.appeal = 1,
  directed = TRUE,
  algorithm = c("psumtree", "psumtree-multiple", "bag"),
  start.graph = NULL
)

Arguments

Generate random graphs using preferential attachment

Description

barabasi.game() was renamed to sample_pa() to create a more consistent API.

Usage

barabasi.game(
  n,
  power = 1,
  m = NULL,
  out.dist = NULL,
  out.seq = NULL,
  out.pref = FALSE,
  zero.appeal = 1,
  directed = TRUE,
  algorithm = c("psumtree", "psumtree-multiple", "bag"),
  start.graph = NULL
)

Arguments

Vertex and edge betweenness centrality

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)

Breadth-first search

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)

Biconnected components

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)

Biconnected components

Description

biconnected.components() was renamed to biconnected_components() to create a more consistent API.

Usage

biconnected.components(graph)

Arguments

Decide whether a graph is bipartite

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)

Project a bipartite graph

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)
isomorphic(proj[[1]], make_full_graph(10))
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)

Decide whether a graph is bipartite

Description

bipartite.mapping() was renamed to bipartite_mapping() to create a more consistent API.

Usage

bipartite.mapping(graph)

Arguments

Project a bipartite graph

Description

bipartite.projection() was renamed to bipartite_projection() to create a more consistent API.

Usage

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

Arguments

Project a bipartite graph

Description

bipartite.projection.size() was renamed to bipartite_projection_size() to create a more consistent API.

Usage

bipartite.projection.size(graph, types = NULL)

Arguments

Bipartite random graphs

Description

bipartite.random.game() was renamed to sample_bipartite() to create a more consistent API.

Usage

bipartite.random.game(
  n1,
  n2,
  type = c("gnp", "gnm"),
  p,
  m,
  directed = FALSE,
  mode = c("out", "in", "all")
)

Arguments

Calculate Cohesive Blocks

Description

blockGraphs() was renamed to graphs_from_cohesive_blocks() to create a more consistent API.

Usage

blockGraphs(blocks, graph)

Arguments

Find Bonacich Power Centrality Scores of Network Positions

Description

bonpow() was renamed to power_centrality() to create a more consistent API.

Usage

bonpow(
  graph,
  nodes = V(graph),
  loops = FALSE,
  exponent = 1,
  rescale = FALSE,
  tol = 1e-07,
  sparse = TRUE
)

Arguments

Concatenate edge sequences

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

Concatenate vertex sequences

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

Graph generation based on different vertex types

Description

callaway.traits.game() was renamed to sample_traits_callaway() to create a more consistent API.

Usage

callaway.traits.game(
  nodes,
  types,
  edge.per.step = 1,
  type.dist = rep(1, types),
  pref.matrix = matrix(1, types, types),
  directed = FALSE
)

Arguments

Canonical permutation of a graph

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

Canonical permutation of a graph

Description

canonical.permutation() was renamed to canonical_permutation() to create a more consistent API.

Usage

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

Arguments

Palette for categories

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

Centralize a graph according to the betweenness of vertices

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

Theoretical maximum for betweenness 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

Centralize a graph according to the closeness of vertices

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

Theoretical maximum for closeness 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

Centralize a graph according to the degrees of vertices

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

Theoretical maximum for degree 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

Centralize a graph according to the eigenvector centrality of vertices

Description

See centralize() for a summary of graph centralization.

Usage

centr_eigen(
  graph,
  directed = FALSE,
  scale = TRUE,
  options = arpack_defaults(),
  normalized = TRUE
)

Arguments

Value

A named list with the following components:

Related documentation in the C library

igraph_centralization_eigenvector_centrality().

See Also

Other centralization related: centr_betw(), centr_betw_tmax(), centr_clo(), centr_clo_tmax(), centr_degree(), centr_degree_tmax(), 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

# The most centralized graph according to eigenvector centrality
g0 <- make_graph(c(2, 1), n = 10, dir = FALSE)
g1 <- make_star(10, mode = "undirected")
centr_eigen(g0)$centralization
centr_eigen(g1)$centralization

Theoretical maximum for eigenvector centralization

Description

See centralize() for a summary of graph centralization.

Usage

centr_eigen_tmax(graph = NULL, nodes = 0, directed = FALSE, scale = TRUE)

Arguments

Value

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

Related documentation in the C library

igraph_centralization_eigenvector_centrality_tmax().

See Also

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

Examples

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

Centralize a graph according to the betweenness of vertices

Description

centralization.betweenness() was renamed to centr_betw() to create a more consistent API.

Usage

centralization.betweenness(graph, directed = TRUE, normalized = TRUE)

Arguments

Theoretical maximum for betweenness centralization

Description

centralization.betweenness.tmax() was renamed to centr_betw_tmax() to create a more consistent API.

Usage

centralization.betweenness.tmax(graph = NULL, nodes = 0, directed = TRUE)

Arguments

Centralize a graph according to the closeness of vertices

Description

centralization.closeness() was renamed to centr_clo() to create a more consistent API.

Usage

centralization.closeness(
  graph,
  mode = c("out", "in", "all", "total"),
  normalized = TRUE
)

Arguments

Theoretical maximum for closeness centralization

Description

centralization.closeness.tmax() was renamed to centr_clo_tmax() to create a more consistent API.

Usage

centralization.closeness.tmax(
  graph = NULL,
  nodes = 0,
  mode = c("out", "in", "all", "total")
)

Arguments

Centralize a graph according to the degrees of vertices

Description

centralization.degree() was renamed to centr_degree() to create a more consistent API.

Usage

centralization.degree(
  graph,
  mode = c("all", "out", "in", "total"),
  loops = TRUE,
  normalized = TRUE
)

Arguments

Theoretical maximum for degree centralization

Description

centralization.degree.tmax() was renamed to centr_degree_tmax() to create a more consistent API.

Usage

centralization.degree.tmax(
  graph = NULL,
  nodes = 0,
  mode = c("all", "out", "in", "total"),
  loops = FALSE
)

Arguments

Centralize a graph according to the eigenvector centrality of vertices

Description

centralization.evcent() was renamed to centr_eigen() to create a more consistent API.

Usage

centralization.evcent(
  graph,
  directed = FALSE,
  scale = TRUE,
  options = arpack_defaults(),
  normalized = TRUE
)

Arguments

Theoretical maximum for betweenness centralization

Description

centralization.evcent.tmax() was renamed to centr_eigen_tmax() to create a more consistent API.

Usage

centralization.evcent.tmax(
  graph = NULL,
  nodes = 0,
  directed = FALSE,
  scale = TRUE
)

Arguments

Centralization of a graph

Description

Centralization is a method for creating a graph level centralization measure from the centrality scores of the vertices.

Usage

centralize(scores, theoretical.max = 0, normalized = TRUE)

Arguments

Details

Centralization is a general method for calculating a graph-level centrality score based on node-level centrality measure. The formula for this is

C(G)=\sum_v (\max_w c_w - c_v),

where c_v is the centrality of vertex v.

The graph-level centralization measure can be normalized by dividing by the maximum theoretical score for a graph with the same number of vertices, using the same parameters, e.g. directedness, whether we consider loop edges, etc.

For degree, closeness and betweenness the most centralized structure is some version of the star graph, in-star, out-star or undirected star.

For eigenvector centrality the most centralized structure is the graph with a single edge (and potentially many isolates).

centralize() implements general centralization formula to calculate a graph-level score from vertex-level scores.

Value

A real scalar, the centralization of the graph from which scores were derived.

Related documentation in the C library

igraph_centralization().

References

Freeman, L.C. (1979). Centrality in Social Networks I: Conceptual Clarification. Social Networks 1, 215–239.

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

See Also

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

Examples

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

# Calculate centralization from pre-computed scores
deg <- degree(g)
tmax <- centr_degree_tmax(g, loops = FALSE)
centralize(deg, tmax)

# The most centralized graph according to eigenvector centrality
g0 <- make_graph(c(2, 1), n = 10, dir = FALSE)
g1 <- make_star(10, mode = "undirected")
centr_eigen(g0)$centralization
centr_eigen(g1)$centralization

Centralization of a graph

Description

centralize.scores() was renamed to centralize() to create a more consistent API.

Usage

centralize.scores(scores, theoretical.max = 0, normalized = TRUE)

Arguments

Random citation graphs

Description

cited.type.game() was renamed to sample_cit_types() to create a more consistent API.

Usage

cited.type.game(
  n,
  edges = 1,
  types = rep(0, n),
  pref = rep(1, length(types)),
  directed = TRUE,
  attr = TRUE
)

Arguments

Random citation graphs

Description

citing.cited.type.game() was renamed to sample_cit_cit_types() to create a more consistent API.

Usage

citing.cited.type.game(
  n,
  edges = 1,
  types = rep(0, n),
  pref = matrix(1, nrow = length(types), ncol = length(types)),
  directed = TRUE,
  attr = TRUE
)

Arguments

Functions to find cliques, i.e. complete subgraphs in a graph

Description

clique.number() was renamed to clique_num() to create a more consistent API.

Usage

clique.number(graph)

Arguments

Functions to find cliques, i.e. complete subgraphs in a graph

Description

These functions find all, the largest or all the maximal cliques in an undirected graph. The size of the largest clique can also be calculated.

Usage

cliques(graph, min = 0, max = 0)

largest_cliques(graph)

max_cliques(graph, min = NULL, max = NULL, subset = NULL, file = NULL)

count_max_cliques(graph, min = NULL, max = NULL, subset = NULL)

clique_num(graph)

largest_weighted_cliques(graph, vertex.weights = NULL)

weighted_clique_num(graph, vertex.weights = NULL)

clique_size_counts(graph, min = 0, max = 0, maximal = FALSE)

Arguments

Details

cliques() find all complete subgraphs in the input graph, obeying the size limitations given in the min and max arguments.

largest_cliques() finds all largest cliques in the input graph. A clique is largest if there is no other clique including more vertices.

max_cliques() finds all maximal cliques in the input graph. A clique is maximal if it cannot be extended to a larger clique. The largest cliques are always maximal, but a maximal clique is not necessarily the largest.

count_max_cliques() counts the maximal cliques.

clique_num() calculates the size of the largest clique(s).

clique_size_counts() returns a numeric vector representing a histogram of clique sizes, between the given minimum and maximum clique size.

Value

cliques(), largest_cliques() and clique_num() return a list containing numeric vectors of vertex ids. Each list element is a clique, i.e. a vertex sequence of class igraph.vs().

max_cliques() returns NULL, invisibly, if its file argument is not NULL. The output is written to the specified file in this case.

clique_num() and count_max_cliques() return an integer scalar.

clique_size_counts() returns a numeric vector with the clique sizes such that the i-th item belongs to cliques of size i. Trailing zeros are currently truncated, but this might change in future versions.

Related documentation in the C library

igraph_cliques(), igraph_largest_cliques(), igraph_clique_number(), igraph_largest_weighted_cliques(), igraph_weighted_clique_number(), igraph_maximal_cliques_hist(), igraph_clique_size_hist().

Author(s)

Tamas Nepusz ntamas@gmail.com and Gabor Csardi csardi.gabor@gmail.com

References

For maximal cliques the following algorithm is implemented: David Eppstein, Maarten Loffler, Darren Strash: Listing All Maximal Cliques in Sparse Graphs in Near-optimal Time. https://arxiv.org/abs/1006.5440

See Also

Other cliques: ivs(), weighted_cliques()

Examples

# this usually contains cliques of size six
g <- sample_gnp(100, 0.3)
clique_num(g)
cliques(g, min = 6)
largest_cliques(g)

# To have a bit less maximal cliques, about 100-200 usually
g <- sample_gnp(100, 0.03)
max_cliques(g)

Closeness centrality of vertices

Description

Closeness centrality measures how many steps are required to access every other vertex from a given vertex.

Usage

closeness(
  graph,
  vids = V(graph),
  mode = c("out", "in", "all", "total"),
  weights = NULL,
  normalized = FALSE,
  cutoff = -1
)

Arguments

Details

The closeness centrality of a vertex is defined as the inverse of the sum of distances to all the other vertices in the graph:

\frac{1}{\sum_{i\ne v} d_{vi}}

If there is no (directed) path between vertex v and i, then i is omitted from the calculation. If no other vertices are reachable from v, then its closeness is returned as NaN.

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 (which is the default), then the function calculates the exact closeness scores. Since igraph 1.6.0, a cutoff value of zero is treated literally, i.e. path with a length greater than zero are ignored.

Closeness centrality is meaningful only for connected graphs. In disconnected graphs, consider using the harmonic centrality with harmonic_centrality()

Value

Numeric vector with the closeness values of all the vertices in v.

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.

See Also

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

Examples

g <- make_ring(10)
g2 <- make_star(10)
closeness(g)
closeness(g2, mode = "in")
closeness(g2, mode = "out")
closeness(g2, mode = "all")

Community structure detection based on edge betweenness

Description

Community structure detection based on the betweenness of the edges in the network. This method is also known as the Girvan-Newman algorithm.

Usage

cluster_edge_betweenness(
  graph,
  weights = NULL,
  directed = TRUE,
  edge.betweenness = TRUE,
  merges = TRUE,
  bridges = TRUE,
  modularity = TRUE,
  membership = TRUE
)

Arguments

Details

The idea behind this method is that the betweenness of the edges connecting two communities is typically high, as many of the shortest paths between vertices in separate communities pass through them. The algorithm successively removes edges with the highest betweenness, recalculating betweenness values after each removal. This way eventually the network splits into two components, then one of these components splits again, and so on, until all edges are removed. The resulting hierarhical partitioning of the vertices can be encoded as a dendrogram.

cluster_edge_betweenness() returns various information collected through the run of the algorithm. Specifically, removed.edges contains the edge IDs in order of the edges' removal; edge.betweenness contains the betweenness of each of these at the time of their removal; and bridges contains the IDs of edges whose removal caused a split.

Value

cluster_edge_betweenness() returns a communities() object, please see the communities() manual page for details.

Author(s)

Gabor Csardi csardi.gabor@gmail.com

References

M Newman and M Girvan: Finding and evaluating community structure in networks, Physical Review E 69, 026113 (2004)

See Also

edge_betweenness() for the definition and calculation of the edge betweenness, cluster_walktrap(), cluster_fast_greedy(), cluster_leading_eigen() for other community detection methods.

See communities() for extracting the results of the community detection.

Community detection as_membership(), 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

g <- sample_pa(100, m = 2, directed = FALSE)
eb <- cluster_edge_betweenness(g)

g <- make_full_graph(10) %du% make_full_graph(10)
g <- add_edges(g, c(1, 11))
eb <- cluster_edge_betweenness(g)
eb

Community structure via greedy optimization of modularity

Description

This function tries to find dense subgraph, also called communities in graphs via directly optimizing a modularity score.

Usage

cluster_fast_greedy(
  graph,
  merges = TRUE,
  modularity = TRUE,
  membership = TRUE,
  weights = NULL
)

Arguments

Details

This function implements the fast greedy modularity optimization algorithm for finding community structure, see A Clauset, MEJ Newman, C Moore: Finding community structure in very large networks, http://www.arxiv.org/abs/cond-mat/0408187 for the details.

Value

cluster_fast_greedy() returns a communities() object, please see the communities() manual page for details.

Author(s)

Tamas Nepusz ntamas@gmail.com and Gabor Csardi csardi.gabor@gmail.com for the R interface.

References

A Clauset, MEJ Newman, C Moore: Finding community structure in very large networks, http://www.arxiv.org/abs/cond-mat/0408187

See Also

communities() for extracting the results.

See also cluster_walktrap(), cluster_spinglass(), cluster_leading_eigen() and cluster_edge_betweenness(), cluster_louvain() cluster_leiden() for other methods.

Community detection as_membership(), cluster_edge_betweenness(), 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

g <- make_full_graph(5) %du% make_full_graph(5) %du% make_full_graph(5)
g <- add_edges(g, c(1, 6, 1, 11, 6, 11))
fc <- cluster_fast_greedy(g)
membership(fc)
sizes(fc)

Community detection algorithm based on interacting fluids

Description

The algorithm detects communities based on the simple idea of several fluids interacting in a non-homogeneous environment (the graph topology), expanding and contracting based on their interaction and density.

Usage

cluster_fluid_communities(graph, no.of.communities)

Arguments

Value

cluster_fluid_communities() returns a communities() object, please see the communities() manual page for details.

Author(s)

Ferran Parés

References

Parés F, Gasulla DG, et. al. (2018) Fluid Communities: A Competitive, Scalable and Diverse Community Detection Algorithm. In: Complex Networks & Their Applications VI: Proceedings of Complex Networks 2017 (The Sixth International Conference on Complex Networks and Their Applications), Springer, vol 689, p 229, doi: 10.1007/978-3-319-72150-7_19

See Also

See communities() for extracting the membership, modularity scores, etc. from the results.

Other community detection algorithms: cluster_walktrap(), cluster_spinglass(), cluster_leading_eigen(), cluster_edge_betweenness(), cluster_fast_greedy(), cluster_label_prop() cluster_louvain(), cluster_leiden()

Community detection as_membership(), cluster_edge_betweenness(), cluster_fast_greedy(), 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

g <- make_graph("Zachary")
comms <- cluster_fluid_communities(g, 2)

Infomap community finding

Description

Find community structure that minimizes the expected description length of a random walker trajectory. If the graph is directed, edge directions will be taken into account.

Usage

cluster_infomap(
  graph,
  e.weights = NULL,
  v.weights = NULL,
  nb.trials = 10,
  modularity = TRUE
)

Arguments

Details

Please see the details of this method in the references given below.

Value

cluster_infomap() returns a communities() object, please see the communities() manual page for details.

Author(s)

Martin Rosvall wrote the original C++ code. This was ported to be more igraph-like by Emmanuel Navarro. The R interface and some cosmetics was done by Gabor Csardi csardi.gabor@gmail.com.

References

The original paper: M. Rosvall and C. T. Bergstrom, Maps of information flow reveal community structure in complex networks, PNAS 105, 1118 (2008) doi:10.1073/pnas.0706851105, https://arxiv.org/abs/0707.0609

A more detailed paper: M. Rosvall, D. Axelsson, and C. T. Bergstrom, The map equation, Eur. Phys. J. Special Topics 178, 13 (2009). doi:10.1140/epjst/e2010-01179-1, https://arxiv.org/abs/0906.1405.

See Also

Other community finding methods and communities().

Community detection as_membership(), cluster_edge_betweenness(), cluster_fast_greedy(), cluster_fluid_communities(), 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

## Zachary's karate club
g <- make_graph("Zachary")

imc <- cluster_infomap(g)
membership(imc)
communities(imc)

Finding communities based on propagating labels

Description

This is a fast, nearly linear time algorithm for detecting community structure in networks. In works by labeling the vertices with unique labels and then updating the labels by majority voting in the neighborhood of the vertex.

Usage

cluster_label_prop(
  graph,
  weights = NULL,
  ...,
  mode = c("out", "in", "all"),
  initial = NULL,
  fixed = NULL
)

Arguments

Details

This function implements the community detection method described in: Raghavan, U.N. and Albert, R. and Kumara, S.: Near linear time algorithm to detect community structures in large-scale networks. Phys Rev E 76, 036106. (2007). This version extends the original method by the ability to take edge weights into consideration and also by allowing some labels to be fixed.

From the abstract of the paper: “In our algorithm every node is initialized with a unique label and at every step each node adopts the label that most of its neighbors currently have. In this iterative process densely connected groups of nodes form a consensus on a unique label to form communities.”

Value

cluster_label_prop() returns a communities() object, please see the communities() manual page for details.

Author(s)

Tamas Nepusz ntamas@gmail.com for the C implementation, Gabor Csardi csardi.gabor@gmail.com for this manual page.

References

Raghavan, U.N. and Albert, R. and Kumara, S.: Near linear time algorithm to detect community structures in large-scale networks. Phys Rev E 76, 036106. (2007)

See Also

communities() for extracting the actual results.

cluster_fast_greedy(), cluster_walktrap(), cluster_spinglass(), cluster_louvain() and cluster_leiden() for other community detection methods.

Community detection as_membership(), cluster_edge_betweenness(), cluster_fast_greedy(), cluster_fluid_communities(), cluster_infomap(), 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

g <- sample_gnp(10, 5 / 10) %du% sample_gnp(9, 5 / 9)
g <- add_edges(g, c(1, 12))
cluster_label_prop(g)

Community structure detecting based on the leading eigenvector of the community matrix

Description

This function tries to find densely connected subgraphs in a graph by calculating the leading non-negative eigenvector of the modularity matrix of the graph.

Usage

cluster_leading_eigen(
  graph,
  steps = -1,
  weights = NULL,
  start = NULL,
  options = arpack_defaults(),
  callback = NULL,
  extra = NULL,
  env = parent.frame()
)

Arguments

Details

The function documented in these section implements the ‘leading eigenvector’ method developed by Mark Newman, see the reference below.

The heart of the method is the definition of the modularity matrix, B, which is B=A-P, A being the adjacency matrix of the (undirected) network, and P contains the probability that certain edges are present according to the ‘configuration model’. In other words, a P[i,j] element of P is the probability that there is an edge between vertices i and j in a random network in which the degrees of all vertices are the same as in the input graph.

The leading eigenvector method works by calculating the eigenvector of the modularity matrix for the largest positive eigenvalue and then separating vertices into two community based on the sign of the corresponding element in the eigenvector. If all elements in the eigenvector are of the same sign that means that the network has no underlying comuunity structure. Check Newman's paper to understand why this is a good method for detecting community structure.

Value

cluster_leading_eigen() returns a named list with the following members:

Callback functions

The callback argument can be used to supply a function that is called after each eigenvector calculation. The following arguments are supplied to this function:

membership

The actual membership vector, with zero-based indexing.

community

The community that the algorithm just tried to split, community numbering starts with zero here.

value

The eigenvalue belonging to the leading eigenvector the algorithm just found.

vector

The leading eigenvector the algorithm just found.

multiplier

An R function that can be used to multiple the actual modularity matrix with an arbitrary vector. Supply the vector as an argument to perform this multiplication. This function can be used with ARPACK.

extra

The extra argument that was passed to cluster_leading_eigen().

The callback function should return a scalar number. If this number is non-zero, then the clustering is terminated.

Author(s)

Gabor Csardi csardi.gabor@gmail.com

References

MEJ Newman: Finding community structure using the eigenvectors of matrices, Physical Review E 74 036104, 2006.

See Also

modularity(), cluster_walktrap(), cluster_edge_betweenness(), cluster_fast_greedy(), as.dendrogram()

Community detection as_membership(), cluster_edge_betweenness(), cluster_fast_greedy(), cluster_fluid_communities(), cluster_infomap(), cluster_label_prop(), 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

g <- make_full_graph(5) %du% make_full_graph(5) %du% make_full_graph(5)
g <- add_edges(g, c(1, 6, 1, 11, 6, 11))
lec <- cluster_leading_eigen(g)
lec

cluster_leading_eigen(g, start = membership(lec))

Finding community structure of a graph using the Leiden algorithm of Traag, van Eck & Waltman.

Description

The Leiden algorithm is similar to the Louvain algorithm, cluster_louvain(), but it is faster and yields higher quality solutions. It can optimize both modularity and the Constant Potts Model, which does not suffer from the resolution-limit (see preprint http://arxiv.org/abs/1104.3083).

Usage

cluster_leiden(
  graph,
  objective_function = c("CPM", "modularity"),
  ...,
  weights = NULL,
  resolution = 1,
  resolution_parameter = deprecated(),
  beta = 0.01,
  initial_membership = NULL,
  n_iterations = 2,
  vertex_weights = NULL
)

Arguments

Details

The Leiden algorithm consists of three phases: (1) local moving of nodes, (2) refinement of the partition and (3) aggregation of the network based on the refined partition, using the non-refined partition to create an initial partition for the aggregate network. In the local move procedure in the Leiden algorithm, only nodes whose neighborhood has changed are visited. The refinement is done by restarting from a singleton partition within each cluster and gradually merging the subclusters. When aggregating, a single cluster may then be represented by several nodes (which are the subclusters identified in the refinement).

The Leiden algorithm provides several guarantees. The Leiden algorithm is typically iterated: the output of one iteration is used as the input for the next iteration. At each iteration all clusters are guaranteed to be connected and well-separated. After an iteration in which nothing has changed, all nodes and some parts are guaranteed to be locally optimally assigned. Finally, asymptotically, all subsets of all clusters are guaranteed to be locally optimally assigned. For more details, please see Traag, Waltman & van Eck (2019).

The objective function being optimized is

\frac{1}{2m} \sum_{ij} (A_{ij} - \gamma n_i n_j)\delta(\sigma_i, \sigma_j)

where m is the total edge weight, A_{ij} is the weight of edge (i, j), \gamma is the so-called resolution parameter, n_i is the node weight of node i, \sigma_i is the cluster of node i and \delta(x, y) = 1 if and only if x = y and 0 otherwise. By setting n_i = k_i, the degree of node i, and dividing \gamma by 2m, you effectively obtain an expression for modularity.

Hence, the standard modularity will be optimized when you supply the degrees as vertex_weights and by supplying as a resolution parameter \frac{1}{2m}, with m the number of edges. If you do not specify any vertex_weights, the correct vertex weights and scaling of \gamma is determined automatically by the objective_function argument.

Value

cluster_leiden() returns a communities() object, please see the communities() manual page for details.

Author(s)

Vincent Traag

References

Traag, V. A., Waltman, L., & van Eck, N. J. (2019). From Louvain to Leiden: guaranteeing well-connected communities. Scientific reports, 9(1), 5233. doi: 10.1038/s41598-019-41695-z, arXiv:1810.08473v3 [cs.SI]

See Also

See communities() for extracting the membership, modularity scores, etc. from the results.

Other community detection algorithms: cluster_walktrap(), cluster_spinglass(), cluster_leading_eigen(), cluster_edge_betweenness(), cluster_fast_greedy(), cluster_label_prop() cluster_louvain() cluster_fluid_communities() cluster_infomap() cluster_optimal() cluster_walktrap()

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

Examples

g <- make_graph("Zachary")
# By default CPM is used
r <- quantile(strength(g))[2] / (gorder(g) - 1)
# Set seed for sake of reproducibility
set.seed(1)
ldc <- cluster_leiden(g, resolution = r)
print(ldc)
plot(ldc, g)

Finding community structure by multi-level optimization of modularity

Description

This function implements the multi-level modularity optimization algorithm for finding community structure, see references below. It is based on the modularity measure and a hierarchical approach.

Usage

cluster_louvain(graph, weights = NULL, resolution = 1)

Arguments

Details

This function implements the multi-level modularity optimization algorithm for finding community structure, see VD Blondel, J-L Guillaume, R Lambiotte and E Lefebvre: Fast unfolding of community hierarchies in large networks, https://arxiv.org/abs/0803.0476 for the details.

It is based on the modularity measure and a hierarchical approach. Initially, each vertex is assigned to a community on its own. In every step, vertices are re-assigned to communities in a local, greedy way: each vertex is moved to the community with which it achieves the highest contribution to modularity. When no vertices can be reassigned, each community is considered a vertex on its own, and the process starts again with the merged communities. The process stops when there is only a single vertex left or when the modularity cannot be increased any more in a step. Since igraph 1.3, vertices are processed in a random order.

This function was contributed by Tom Gregorovic.

Value

cluster_louvain() returns a communities() object, please see the communities() manual page for details.

Author(s)

Tom Gregorovic, Tamas Nepusz ntamas@gmail.com

References

Vincent D. Blondel, Jean-Loup Guillaume, Renaud Lambiotte, Etienne Lefebvre: Fast unfolding of communities in large networks. J. Stat. Mech. (2008) P10008

See Also

See communities() for extracting the membership, modularity scores, etc. from the results.

Other community detection algorithms: cluster_walktrap(), cluster_spinglass(), cluster_leading_eigen(), cluster_edge_betweenness(), cluster_fast_greedy(), cluster_label_prop() cluster_leiden()

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

Examples

# This is so simple that we will have only one level
g <- make_full_graph(5) %du% make_full_graph(5) %du% make_full_graph(5)
g <- add_edges(g, c(1, 6, 1, 11, 6, 11))
cluster_louvain(g)

Optimal community structure

Description

This function calculates the optimal community structure of a graph, by maximizing the modularity measure over all possible partitions.

Usage

cluster_optimal(graph, weights = NULL)

Arguments

Details

This function calculates the optimal community structure for a graph, in terms of maximal modularity score.

The calculation is done by transforming the modularity maximization into an integer programming problem, and then calling the GLPK library to solve that. Please the reference below for details.

Note that modularity optimization is an NP-complete problem, and all known algorithms for it have exponential time complexity. This means that you probably don't want to run this function on larger graphs. Graphs with up to fifty vertices should be fine, graphs with a couple of hundred vertices might be possible.

Value

cluster_optimal() returns a communities() object, please see the communities() manual page for details.

Examples

## Zachary's karate club
g <- make_graph("Zachary")

## We put everything into a big 'try' block, in case
## igraph was compiled without GLPK support

## The calculation only takes a couple of seconds
oc <- cluster_optimal(g)

## Double check the result
print(modularity(oc))
print(modularity(g, membership(oc)))

## Compare to the greedy optimizer
fc <- cluster_fast_greedy(g)
print(modularity(fc))

Author(s)

Gabor Csardi csardi.gabor@gmail.com

References

Ulrik Brandes, Daniel Delling, Marco Gaertler, Robert Gorke, Martin Hoefer, Zoran Nikoloski, Dorothea Wagner: On Modularity Clustering, IEEE Transactions on Knowledge and Data Engineering 20(2):172-188, 2008.

See Also

communities() for the documentation of the result, modularity(). See also cluster_fast_greedy() for a fast greedy optimizer.

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

Finding communities in graphs based on statistical meachanics

Description

This function tries to find communities in graphs via a spin-glass model and simulated annealing.

Usage

cluster_spinglass(
  graph,
  weights = NULL,
  vertex = NULL,
  spins = 25,
  parupdate = FALSE,
  start.temp = 1,
  stop.temp = 0.01,
  cool.fact = 0.99,
  update.rule = c("config", "random", "simple"),
  gamma = 1,
  implementation = c("orig", "neg"),
  gamma.minus = 1
)

Arguments

Details

This function tries to find communities in a graph. A community is a set of nodes with many edges inside the community and few edges between outside it (i.e. between the community itself and the rest of the graph.)

This idea is reversed for edges having a negative weight, i.e. few negative edges inside a community and many negative edges between communities. Note that only the ‘neg’ implementation supports negative edge weights.

The spinglass.cummunity function can solve two problems related to community detection. If the vertex argument is not given (or it is NULL), then the regular community detection problem is solved (approximately), i.e. partitioning the vertices into communities, by optimizing the an energy function.

If the vertex argument is given and it is not NULL, then it must be a vertex id, and the same energy function is used to find the community of the the given vertex. See also the examples below.

Value

If the vertex argument is not given, i.e. the first form is used then a cluster_spinglass() returns a communities() object.

If the vertex argument is present, i.e. the second form is used then a named list is returned with the following components:

Author(s)

Jorg Reichardt for the original code and Gabor Csardi csardi.gabor@gmail.com for the igraph glue code.

Changes to the original function for including the possibility of negative ties were implemented by Vincent Traag (https://www.traag.net/).

References

J. Reichardt and S. Bornholdt: Statistical Mechanics of Community Detection, Phys. Rev. E, 74, 016110 (2006), https://arxiv.org/abs/cond-mat/0603718

M. E. J. Newman and M. Girvan: Finding and evaluating community structure in networks, Phys. Rev. E 69, 026113 (2004)

V.A. Traag and Jeroen Bruggeman: Community detection in networks with positive and negative links, https://arxiv.org/abs/0811.2329 (2008).

See Also

communities(), components()

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

Examples

g <- sample_gnp(10, 5 / 10) %du% sample_gnp(9, 5 / 9)
g <- add_edges(g, c(1, 12))
g <- induced_subgraph(g, subcomponent(g, 1))
cluster_spinglass(g, spins = 2)
cluster_spinglass(g, vertex = 1)

Community structure via short random walks

Description

This function tries to find densely connected subgraphs, also called communities in a graph via random walks. The idea is that short random walks tend to stay in the same community.

Usage

cluster_walktrap(
  graph,
  weights = NULL,
  steps = 4,
  merges = TRUE,
  modularity = TRUE,
  membership = TRUE
)

Arguments

Details

This function is the implementation of the Walktrap community finding algorithm, see Pascal Pons, Matthieu Latapy: Computing communities in large networks using random walks, https://arxiv.org/abs/physics/0512106

Value

cluster_walktrap() returns a communities() object, please see the communities() manual page for details.

Author(s)

Pascal Pons (http://psl.pons.free.fr/) and Gabor Csardi csardi.gabor@gmail.com for the R and igraph interface

References

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

See Also

See communities() on getting the actual membership vector, merge matrix, modularity score, etc.

modularity() and cluster_fast_greedy(), cluster_spinglass(), cluster_leading_eigen(), cluster_edge_betweenness(), cluster_louvain(), and cluster_leiden() for other community detection methods.

Community detection as_membership(), 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(), compare(), groups(), make_clusters(), membership(), modularity.igraph(), plot_dendrogram(), split_join_distance(), voronoi_cells()

Examples

g <- make_full_graph(5) %du% make_full_graph(5) %du% make_full_graph(5)
g <- add_edges(g, c(1, 6, 1, 11, 6, 11))
cluster_walktrap(g)

Connected components of a graph

Description

cluster.distribution() was renamed to component_distribution() to create a more consistent API.

Usage

cluster.distribution(graph, cumulative = FALSE, mul.size = FALSE, ...)

Arguments

Connected components of a graph

Description

clusters() was renamed to components() to create a more consistent API.

Usage

clusters(graph, mode = c("weak", "strong"))