Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
352 lines (316 sloc) 12 KB
use objective::*;
use cover::{MaxCover, MaxCoverState};
use petgraph::prelude::*;
use petgraph::graph::node_index;
use ris::*;
use bit_set::BitSet;
use std::collections::{BTreeMap, BTreeSet};
use std::f32;
use slog::Logger;
use itertools::EitherOrBoth::*;
use itertools::Itertools;
/// Influence Maximization via RIS (see Borg et al. 2014).
/// The sampling step is done upon creation with `new`.
pub struct InfMax<'a> {
/// The internal representation of the problem; used to solve it.
internal: MaxCover,
/// The graph being acted on
graph: &'a Graph<(), f32>,
/// The hypergraph representation of the influence graph. Each node `u` maps to a set of nodes
/// `v` which it influences in one or more RIS samples.
hypergraph: BTreeMap<NodeIndex, BTreeSet<NodeIndex>>,
/// The mapping from set indices to node indices; used in translating from `internal` to back
/// to the original domain.
mapping: Vec<NodeIndex>,
/// The mapping from node indices to set indices; used in translating from external input to
/// the representation of `internal`.
inverse_mapping: BTreeMap<NodeIndex, usize>,
/// The number of RR sets covered by each element that covers any.
rr_counts: BTreeMap<NodeIndex, usize>,
rr_total: usize,
log: Logger,
}
#[derive(Default, Clone)]
pub struct State {
internal: MaxCoverState,
}
impl<'b, 'a: 'b> InfMax<'a> {
/// Create a new instance of the influence maximization problem that uses RIS sampling
/// internally. The triggering model `M` is used to construct `k` RIS samples, which are then
/// used to build the problem instance.
///
/// Internally, the problem is represented by a `MaxCover` instance.
pub fn new<M>(g: &'a Graph<(), f32>, k: usize, log: Logger) -> Self
where M: TriggeringModel<'b, (), f32, Item = NodeIndex>
{
let (hg, counts) = sample::<_, _, M>(&g, k);
let mapping = hg.keys().cloned().collect::<Vec<_>>();
let inv = mapping.iter().enumerate().map(|(i, &x)| (x, i)).collect();
let mc = MaxCover::new(hg.values().cloned().collect(), false, &log);
InfMax {
hypergraph: hg,
graph: g,
internal: mc,
mapping: mapping,
inverse_mapping: inv,
rr_counts: counts,
rr_total: k,
log: log,
}
}
/// Add `k` more RIS samples to the problem instance.
///
/// *Note*: This invalidates all current states and results; any that linger on will *not*
/// match the new instance. At this time, this is not checked.
pub fn augment<M>(&mut self, k: usize)
where M: TriggeringModel<'b, (), f32, Item = NodeIndex>
{
let (hg, counts) = sample::<_, _, M>(self.graph, k);
for (el, mut set) in hg.into_iter() {
self.hypergraph.entry(el).or_insert_with(|| BTreeSet::new()).append(&mut set);
}
for (el, count) in counts.into_iter() {
*self.rr_counts.entry(el).or_insert(0) += count;
}
self.mapping = self.hypergraph.keys().cloned().collect::<Vec<_>>();
self.inverse_mapping = self.mapping.iter().enumerate().map(|(i, &x)| (x, i)).collect();
self.internal = MaxCover::new(self.hypergraph.values().cloned().collect(),
false,
&self.log);
self.rr_total += k;
}
/// The number of RR sets covered by the given seed set. This method is available primarily to
/// support IMM.
pub fn sets_covered(&self, seeds: &Vec<NodeIndex>) -> usize {
seeds.iter().map(|seed| self.rr_counts[seed]).sum()
}
/// Finalize the internal problem, precomputing the dependent sets. Not recommended for any
/// non-trivial graph due to the number of dependencies -- an efficient memoized cache is now
/// in use instead.
#[deprecated(note="An efficient memoized cache is now in use; finalizing is no longer necessary.")]
pub fn finalize(&mut self) {
self.internal = MaxCover::new(self.hypergraph.values().cloned().collect(), true, &self.log);
}
fn convert_err(&self, err: CurvError<MaxCover>) -> CurvError<Self> {
use objective::CurvError::*;
match err {
NoCandidates(el) => NoCandidates(self.mapping[el]),
SampleTooSmall(s, k) => SampleTooSmall(s, k),
Other(s) => Other(s),
}
}
fn convert_set(&self, s: &BitSet) -> BitSet {
s.iter()
.filter_map(|x| if self.inverse_mapping.contains_key(&node_index(x)) {
Some(self.inverse_mapping[&node_index(x)])
} else {
None
})
.collect()
}
}
impl<'a> Objective for InfMax<'a> {
type Element = NodeIndex;
type State = State;
fn max_gamma(&self) -> Option<f32> {
Some(1.0)
}
fn elements(&self) -> Vec<Self::Element> {
self.graph.node_indices().collect()
}
fn depends(&self,
u: Self::Element,
state: &Self::State)
-> Result<BTreeSet<Self::Element>, CurvError<Self>> {
if self.inverse_mapping.contains_key(&u) {
self.internal
.depends(self.inverse_mapping[&u], &state.internal)
.map(|set| set.into_iter().map(|i| self.mapping[i]).collect())
.map_err(|e| self.convert_err(e))
} else {
Ok(BTreeSet::new())
}
}
fn benefit(&self, s: &BitSet, state: &Self::State) -> Result<f32, CurvError<Self>> {
Ok(self.internal
.benefit(&self.convert_set(s), &state.internal)
.map_err(|e| self.convert_err(e))? * self.graph.node_count() as f32 /
self.rr_total as f32)
}
fn delta(&self,
u: Self::Element,
s: &BitSet,
state: &Self::State)
-> Result<f32, CurvError<Self>> {
if self.inverse_mapping.contains_key(&u) {
Ok(self.internal
.delta(self.inverse_mapping[&u],
&self.convert_set(s),
&state.internal)
.map_err(|e| self.convert_err(e))? *
self.graph.node_count() as f32 / self.rr_total as f32)
} else {
Ok(0.0)
}
}
fn nabla(&self,
u: Self::Element,
v: Self::Element,
s: &BitSet,
state: &Self::State)
-> Result<f32, CurvError<Self>> {
if self.inverse_mapping.contains_key(&u) && self.inverse_mapping.contains_key(&v) {
self.internal
.nabla(self.inverse_mapping[&u],
self.inverse_mapping[&v],
&self.convert_set(s),
&state.internal)
.map_err(|e| self.convert_err(e))
// the n / |R| scaling cancels out
} else {
Ok(1.0) // in this case, either being absent simply implies no change
}
}
fn insert_mut(&self, u: Self::Element, state: &mut Self::State) -> Result<(), CurvError<Self>> {
if self.inverse_mapping.contains_key(&u) {
self.internal
.insert_mut(self.inverse_mapping[&u], &mut state.internal)
.map_err(|e| self.convert_err(e))
} else {
// Err(CurvError::Other(format!("attempt to add unmapped element {:?}", u)))
// adding an un-mapped element is a no-op
Ok(())
}
}
}
pub struct RobustIM<'a> {
graph: &'a Graph<(), f32>,
internal: Vec<InfMax<'a>>,
opt_ests: Vec<f32>,
log: Logger,
}
#[derive(Default, Clone)]
pub struct RobustIMState {
internal: Vec<State>,
}
impl<'a> RobustIM<'a> {
pub fn new(g: &'a Graph<(), f32>,
models: Vec<InfMax<'a>>,
opt_ests: Vec<f32>,
log: Logger)
-> RobustIM<'a> {
RobustIM {
graph: g,
internal: models,
opt_ests: opt_ests,
log: log,
}
}
}
impl<'a> Objective for RobustIM<'a> {
type Element = NodeIndex;
type State = RobustIMState;
fn max_gamma(&self) -> Option<f32> {
None
}
fn elements(&self) -> Vec<Self::Element> {
self.graph.node_indices().collect()
}
fn depends(&self,
u: Self::Element,
state: &Self::State)
-> Result<BTreeSet<Self::Element>, CurvError<Self>> {
self.internal
.iter()
.zip_longest(&state.internal)
.map(|pair| match pair {
Both(int, state) => int.depends(u, &state),
Left(int) => int.depends(u, &State::default()),
Right(_) => panic!("more states than models; cannot handle this"),
})
.fold(Ok(BTreeSet::new()), |set, deps| {
let mut set = set?;
set.append(&mut deps?);
Ok(set)
})
}
fn benefit(&self, s: &BitSet, state: &Self::State) -> Result<f32, CurvError<Self>> {
let bens = self.internal
.iter()
.zip(&self.opt_ests)
.zip_longest(&state.internal)
.map(|pair| match pair {
Both((int, opt), state) => Ok(int.benefit(s, &state)? / opt),
Left((int, opt)) => Ok(int.benefit(s, &State::default())? / opt),
Right(_) => panic!("more states than models; cannot handles this"),
})
.collect::<Result<Vec<f32>, CurvError<Self>>>()?;
bens.iter()
.fold(None,
|prev: Option<f32>, &cur: &f32| if let Some(prev) = prev {
Some(prev.min(cur))
} else {
Some(cur)
})
.ok_or(CurvError::Other(format!("no models to take min of")))
}
fn delta(&self,
u: Self::Element,
s: &BitSet,
state: &Self::State)
-> Result<f32, CurvError<Self>> {
let ustate = self.insert(u, state)?;
let mut us = s.clone();
us.insert(u.into());
Ok(self.benefit(&us, &ustate)? - self.benefit(s, state)?)
}
fn nabla(&self,
u: Self::Element,
v: Self::Element,
s: &BitSet,
state: &Self::State)
-> Result<f32, CurvError<Self>> {
let vstate = self.insert(v, state)?;
let mut vs = s.clone();
vs.insert(u.into());
let lower = self.delta(u, s, state)? + EPSILON;
let upper = self.delta(u, &vs, &vstate)? + EPSILON;
if lower == 0.0 && upper == 0.0 {
Ok(1.0)
} else if lower == 0.0 && upper != 0.0 {
Err(CurvError::Other(format!("would produce NaN (upper = {}, lower = {})",
upper,
lower)))
} else {
Ok(upper / lower)
}
}
fn insert_mut(&self, u: Self::Element, state: &mut Self::State) -> Result<(), CurvError<Self>> {
if state.internal.is_empty() {
state.internal = self.internal
.iter()
.map(|int| int.insert(u, &State::default()).unwrap_or_else(|err| {
// warn!(self.log, "error encountered inserting element"; "el" => format!("{:?}", u), "err" => String::from(err));
State::default()
}))
.collect::<Vec<_>>();
} else {
for (int, state) in self.internal.iter().zip(&mut state.internal) {
int.insert_mut(u, state).unwrap_or_else(|err| {
// warn!(self.log, "error encountered inserting element"; "el" => format!("{:?}", u), "err" => String::from(err))
});
}
}
Ok(())
}
}
impl<'a> From<CurvError<InfMax<'a>>> for CurvError<RobustIM<'a>> {
fn from(err: CurvError<InfMax<'a>>) -> Self {
use self::CurvError::*;
match err {
NoCandidates(el) => NoCandidates(el),
SampleTooSmall(s, k) => SampleTooSmall(s, k),
Other(s) => Other(s),
}
}
}