Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
88 lines (81 sloc) 3.17 KB
use greedy::*;
use ris::*;
use objective::*;
use petgraph::prelude::*;
use proper_im::*;
use slog::Logger;
use std::f64::consts::E;
use std::collections::BTreeSet;
use std::iter::FromIterator;
use num_traits::Float;
use imm::logbinom;
fn estimate_inf<'b, 'a: 'b, M>(g: &'a Graph<(), f32>,
seeds: &Vec<NodeIndex>,
eps2: f64,
delta2: f64,
tmax: usize)
-> Option<f64>
where M: TriggeringModel<'b, (), f32, Item = NodeIndex>
{
let c = 2.0 * (E - 2.0);
let lam2 = 1.0 + 2.0 * c * (1.0 + eps2) * (1.0 / delta2 * 1.0 / eps2.powi(2)).ln();
let mut cov = 0.0;
let seed_set = BTreeSet::from_iter(seeds.iter().cloned());
for t in 1..tmax + 1 {
let sample = M::new_uniform(g).collect::<BTreeSet<_>>();
cov += 1.0.min(sample.intersection(&seed_set).count() as f64);
if cov >= lam2 {
return Some(g.node_count() as f64 * cov / t as f64);
}
}
None
}
#[allow(non_snake_case)]
pub fn ssa_unweighted<'b, 'a: 'b, M>(g: &'a Graph<(), f32>,
eps: f64,
delta: f64,
budget: usize,
log: Logger)
-> Result<(f64, InfMax), CurvError<InfMax>>
where M: TriggeringModel<'b, (), f32, Item = NodeIndex>
{
let n = g.node_count();
let (eps1, eps2, eps3) = (eps / 6.0, eps / 2.0, eps / 4.0 * (1.0 - 1.0 / E));
let c = 2.0 * (E - 2.0);
let lam1 = (1.0 + eps1) * (1.0 + eps2) * 2.0 * c * (3.0 / delta * 1.0 / eps3.powi(2)).ln();
let mut R = lam1;
let mut im = InfMax::new::<M>(&g, lam1 as usize, log.new(o!("section" => "ssa infmax")));
loop {
// the formula for estimated influence in SSA is cov * n / |R|, where n is number of nodes and
// |R| is number of RR sets
let (inf, seeds, _) = greedy(&im, budget, &log)?;
let inf = inf as f64;
if inf * R / n as f64 >= lam1 {
let maybe_inf =
estimate_inf::<M>(g,
&seeds,
eps2,
delta / 3.0,
(R * (1.0 + eps2) / (1.0 - eps2) * eps3.powi(2) /
eps2.powi(2)) as usize);
if let Some(inf_c) = maybe_inf {
if inf <= (1.0 + eps1) * inf_c {
// gotten enough samples, return
return Ok((inf, im));
} else {
info!(log, "insufficient samples, continuing"; "inf_c" => inf_c, "inf" => inf);
}
} else {
info!(log, "insufficient samples to compute inf_c, continuing");
}
} else if R >=
(8.0 + 2.0 * eps) * n as f64 * ((2.0 / delta).ln() + logbinom(n, budget)) /
eps.powi(2) {
// im.finalize();
return Ok((inf, im));
}
im.augment::<M>(R as usize);
R += R;
info!(log, "augmented samples"; "|R|" => R);
}
}