contract_vertices: Contract multiple vertices into 1 new vertex

In SNAnalyst/DF21: SNA functions and dataset for Data Forensics 2021-2022

Contract multiple vertices into 1 new vertex

Description

contract_vertices combines a set of vertices into one pseudo-vertex and returns the reduced network.

Usage

contract_vertices(
  g,
  vertices,
  method = c("min", "max", "union", "add"),
  attr = NULL,
  new_name = "set",
  out_as_igraph = TRUE
)

Arguments

g	network as an igraph object or an adjacency matrix.
vertices	Numeric vertor indicating the indeces of the vertices are to be contracted.
method	Indication of which grouping criterion should be used. method="min" indicates the "minimum" criterion (edge values as distances). method="max" indicates the "maximum" criterion (edge values as non-cummulative strengths). method="add" indicates the "addition" criterion (edge values as cummulative strengths). method="union" indicates the "union" criterion (edge values as probability). The default is "min". See details for examples.
attr	Either NULL or a character string giving an edge attribute name to be used as weights. If NULL, the unweighted network is used to calculate the values of the resulting contracted network. If not NULL then the values of the given edge attribute are included in the adjacency matrix. If the graph has multiple edges, the edge attribute of an arbitrarily chosen edge (for the multiple edges) is included.
new_name	character, name of the new pseudovertex. If not specified, it will be called "set".
out_as_igraph	logical. If TRUE the resulting network is returned as an igraph object. If FALSE, the output is returned as an adjacency matrix.

Details

This function contracts a set of vertices into a pseudo-vertex and returns the network with that new vertex included (and the contracted vertices excluded).

Weighted ties can be used. This requires to either provide a weighted adjacency matrix OR an igraph object with an attribute that is used for weights. Make sure that this attribute is numeric. By default, if the igraph object contains an edge attribute called weight, this attribute will be used as a weight by default, unless a different edge attribute is explicitly specified as attr.

The method specifies how the (possibly weighted) edges between the selected vertices and the other vertices are combined into edges between the new pseudovertex and the other vertices. The default is to use the min procedure.

NOTE: if g is an igraph object without vertex names, the names will be added automatically (as integeres, numbered from 1). This is useful, so it is clear who-is-who after the vertex contraction.

Minimum Criterion: the edge value between a group and an outside vertex is measured as the minimal value among all the (nonzero) edge values between any vertex in the group and the outside vertex. Suggested if edge values are interpreted as distances.
Example: suppose vertex A to C has distance 2 and B to C has distance 1, then according to the minimum criterion, the distance between C and the merged set AB is 1. Note that if B and C are not connected, the algorithm takes the distance between A and C to describe the distance between AB and C.

Maximun Criterion: the edge value between a group and an outside vertex is measured as the maximal value among all the (nonzero) edge values between any vertex in the group and the outside vertex. Suggested if edge values are interpreted as non-cummulative strengths.
Example: we keep using the above example, but the figure now indicates the strength of tie. According to the maximum criterion, the strength of tie between AB and C is 2.

Addition Criterion: the edge value between a group and an outside vertex is measured as the sum of all the edge values between any vertex in the group and the outside vertex. Suggested if edge values are as cummulative strengths.
Example: according to the addition criterion, the strength of tie between AB and C is 3

Union Criterion: the edge value between a group and an outside vertex is measured as the probability that there is at least one path connecting the group with the outside vertex. Suggested if edge values are as probability.
Example: suppose A has probability 0.2 to reach C and B has probability 0.5 to reach C, then C can be reached from merged AB with probability 1 - (1 - 0.2) * (1 - 0.5) = 0.6 according to the union criterion.

Value

An igraph object or an adjacency matrix of the contracted network.

Note

Based on the contract function from the keyplayer package. The implementation in our package is more general.

Examples

# Create a 5x5 weighted and directed adjacency matrix, where edge values
# represent the strength of tie
W <- matrix(
  c(0, 1, 3, 0, 0,
    0, 0, 0, 4, 0,
    1, 1, 0, 2, 0,
    0, 0, 0, 0, 3,
    0, 2, 0, 0, 0),
    nrow = 5, ncol = 5, byrow = TRUE)

# If the strength is believed to be non-accumulative for a group of vertices,
# it is proper to use the "maximum" criterion to contract vertex 2 and 3
contract_vertices(W, c(2, 3), "max")

# Transform the edge value to probability interpretaion
P <- W * 0.2

# Contract vertex 2 and 3 using the "union" criterion as it is proper for
# probability matrix input
contract_vertices(P, c(2, 3), "union")

SNAnalyst/DF21 documentation built on March 21, 2022, 12:02 a.m.