Skip to contents

Graphs, SAT and CRFs: degree centrality, diameter, betweenness, CDCL, linear-chain CRF

Source: R/GraphLogic.R
GraphDegreeCentrality.Rd

GraphDegreeCentrality: Freeman deg(v) / (n - 1) (mode "out", "in" or "all"). GraphDiameter: largest finite shortest-path distance (BFS hop counts, or Dijkstra with weighted), eccentricities and a farthest pair (1-based). GraphBetweenness: Brandes accumulation of pair dependencies, halved for undirected graphs, optionally normalised as igraph. CdclSolve: conflict-driven clause learning with scanning unit propagation, VSIDS decisions (false first, ties to the lowest index), first-UIP learning and non-chronological backjumping. CrfMarginals, CrfViterbi and CrfFit: linear-chain CRF with parameter vector packing emission weights (row-major K x d), label biases and transitions (row-major K x K); forward-backward marginals, Viterbi decoding (0-based labels) and L2-penalised maximum likelihood by L-BFGS.

Usage

GraphDegreeCentrality(A, mode = "all")

GraphDiameter(A, weighted = FALSE)

GraphBetweenness(A, weighted = FALSE, normalized = FALSE)

CdclSolve(cnf, n_vars = NULL, max_conflicts = 1e+05)

CrfMarginals(theta, X, n_labels)

CrfViterbi(theta, X, n_labels)

CrfFit(sequences, labels, n_labels, l2 = 1, max_iter = 500)

Arguments

A

Adjacency (or edge-length) matrix; nonzero means an edge.

mode

"all", "out" or "in".

weighted

Use edge lengths (Dijkstra) instead of hop counts.

normalized

Normalise betweenness.

cnf

List of clauses (integer vectors of literals).

n_vars

Number of variables, or NULL for the largest index used.

max_conflicts

Conflict budget.

theta

CRF parameter vector.

X

Feature matrix of one sequence (rows are positions).

n_labels

Number of labels.

sequences

List of feature matrices.

labels

List of 0-based label vectors.

l2

Ridge penalty.

max_iter

L-BFGS iterations.

Value

A vector or list.

References

Freeman, L. C. (1979). Social Networks 1, 215-239. Newman, M. E. J. (2010). Networks: An Introduction. Brandes, U. (2001). J. Math. Sociology 25, 163-177. Marques-Silva, J. P. and Sakallah, K. A. (1999). IEEE Trans. Computers 48, 506-521. Lafferty, J., McCallum, A. and Pereira, F. (2001). ICML 2001, 282-289.

Examples

GraphDegreeCentrality(rbind(c(0, 1, 1), c(1, 0, 0), c(1, 0, 0)))
#> [1] 1.0 0.5 0.5
CdclSolve(list(c(1, 2), c(-1, 2), c(1, -2), c(-1, -2, 3)))$model
#> [1] 1 2 3