firstImprovement: Graph Rewiring First Improvement Optimization Algorithm

In MiloMonnier/supplynet: Supply network design and robustness assessment tools

Description

Minimize a given graph metric (function) by iterative rewiring process. At each time step, a candidate is generated by rewiring

Usage

firstImprovement(
  g,
  rewiring.FUN = NULL,
  fun2min = NULL,
  niter = Inf,
  score.tolerance = 0.01,
  max.succ.reject = 100,
  verbose = TRUE,
  ...
)

Arguments

g	an igraph object
rewiring.FUN	function of rewiring to apply to the graph at each time step
fun2min	function, metric to minimize
niter	maximal number of iterations. Default is Infinite
score.tolerance	a numeric threshold of fun2min under which graph is accepted as result. Default is 0.01 (1% of a normalized metric)
max.succ.reject	maximal number of successive rejects of candidates, beyond which we consider that the graph cannot be improved anymore, and is returned. Default is 100
verbose	Wether or not displaying fun2min evolution. Default is TRUE
...	additionnal arguments passed to rewiring.FUN

Value

a list of 5 elements:

g

the optimized graph

value

the fun2min value obtained at the end of the process

g_list

list of igraphs object. History of successive improvements

iter

number of iterations elapsed

acceptation_rate

Acceptation rate during the process

Examples

library(igraph)
g = sample_pa(n=100, power=1, m=1,  directed=FALSE)
is_dag(g)
res = firstImprovement(g, rewiring.FUN=rewire, with=each_edge(prob=1),
fun2min=transitivity, niter=10)

MiloMonnier/supplynet documentation built on Feb. 16, 2021, 8:03 p.m.