#[cfg(feature = "numkong")]
use numkong::SparseIntersect;
use rand::{Rng, SeedableRng};
use rand_xoshiro::Xoshiro256PlusPlus;
use rayon::prelude::*;
use rustc_hash::{FxHashMap, FxHashSet};
use std::cmp::Reverse;
use std::collections::BinaryHeap;
use std::sync::mpsc;
use std::thread;
use std::time::Instant;
fn profile(stage: &str, start: Instant, edges: usize) {
if std::env::var_os("FASTMOB_RECAST_PROFILE").is_some() {
eprintln!(
"recast {stage} seconds={:.6} edges={edges}",
start.elapsed().as_secs_f64()
);
}
}
type Edge = (u32, u32);
const DAY_MS: i64 = 86_400_000;
pub struct ContactGraphMetrics {
pub clustering_coefficient: Vec<f64>,
pub topological_overlap: Vec<f64>,
}
pub fn contact_graph_metrics(node_count: usize, from: &[u32], to: &[u32]) -> ContactGraphMetrics {
ContactGraphMetrics {
clustering_coefficient: local_clustering_coefficients(node_count, from, to),
topological_overlap: topological_overlaps(node_count, from, to)
.into_iter()
.map(f64::from)
.collect(),
}
}
fn edge(a: u32, b: u32) -> Edge {
if a < b { (a, b) } else { (b, a) }
}
fn stream_seed(seed: u64, replica: usize, window: usize) -> u64 {
seed ^ (replica as u64).wrapping_mul(0x9E37_79B9_7F4A_7C15)
^ (window as u64).wrapping_mul(0xD1B5_4A32_D192_ED03)
}
#[derive(Clone)]
struct Interval {
user: u32,
start: i64,
end: i64,
}
#[derive(Clone)]
pub struct TemporalEvents {
pub events: Vec<FxHashSet<Edge>>,
pub window_starts_ms: Vec<i64>,
}
pub fn event_graphs(
users: &[u32],
locations: &[u32],
starts: &[i64],
ends: &[i64],
min_contact_ms: i64,
) -> TemporalEvents {
if users.is_empty() {
return TemporalEvents {
events: Vec::new(),
window_starts_ms: Vec::new(),
};
}
let min_window = starts.iter().copied().min().unwrap().div_euclid(DAY_MS);
let max_window = ends
.iter()
.copied()
.filter(|&x| x > i64::MIN)
.map(|x| (x - 1).div_euclid(DAY_MS))
.max()
.unwrap_or(min_window);
let steps = (max_window - min_window + 1).max(0) as usize;
let mut groups: FxHashMap<(i64, u32), Vec<Interval>> = FxHashMap::default();
for i in 0..users.len() {
if ends[i] <= starts[i] {
continue;
}
for window in starts[i].div_euclid(DAY_MS)..=(ends[i] - 1).div_euclid(DAY_MS) {
let lo = starts[i].max(window * DAY_MS);
let hi = ends[i].min((window + 1) * DAY_MS);
if hi - lo >= min_contact_ms {
groups
.entry((window, locations[i]))
.or_default()
.push(Interval {
user: users[i],
start: lo,
end: hi,
});
}
}
}
let mut buckets: Vec<_> = groups.into_iter().collect();
buckets.sort_unstable_by_key(|((window, location), _)| (*window, *location));
let bucket_edges: Vec<(usize, Vec<Edge>)> = buckets
.into_par_iter()
.map(|((window, _), mut intervals)| {
intervals.sort_unstable_by_key(|x| (x.start, x.end, x.user));
let mut expiry = BinaryHeap::new();
let mut active: FxHashMap<u32, usize> = FxHashMap::default();
let mut edges = FxHashSet::default();
for current in intervals {
let required_end = current.start + min_contact_ms;
while let Some(&Reverse((end, user))) = expiry.peek() {
if end >= required_end {
break;
}
expiry.pop();
let count = active.get_mut(&user).unwrap();
*count -= 1;
if *count == 0 {
active.remove(&user);
}
}
for &user in active.keys() {
if user != current.user {
edges.insert(edge(user, current.user));
}
}
*active.entry(current.user).or_insert(0) += 1;
expiry.push(Reverse((current.end, current.user)));
}
let mut edges: Vec<_> = edges.into_iter().collect();
edges.sort_unstable();
((window - min_window) as usize, edges)
})
.collect();
let mut events: Vec<FxHashSet<Edge>> = (0..steps).map(|_| FxHashSet::default()).collect();
for (window, edges) in bucket_edges {
events[window].extend(edges);
}
TemporalEvents {
events,
window_starts_ms: (0..steps)
.map(|i| (min_window + i as i64) * DAY_MS)
.collect(),
}
}
pub struct TemporalGraphOutput {
pub window_starts_ms: Vec<i64>,
pub edge_offsets: Vec<u64>,
pub edge_from: Vec<u32>,
pub edge_to: Vec<u32>,
}
pub fn flatten_events(temporal: &TemporalEvents) -> TemporalGraphOutput {
let mut offsets = Vec::with_capacity(temporal.events.len() + 1);
let mut from = Vec::new();
let mut to = Vec::new();
offsets.push(0);
for event in &temporal.events {
let mut edges: Vec<_> = event.iter().copied().collect();
edges.sort_unstable();
for (u, v) in edges {
from.push(u);
to.push(v);
}
offsets.push(from.len() as u64);
}
TemporalGraphOutput {
window_starts_ms: temporal.window_starts_ms.clone(),
edge_offsets: offsets,
edge_from: from,
edge_to: to,
}
}
pub fn aggregate_flat_events(
edge_offsets: &[u64],
edge_from: &[u32],
edge_to: &[u32],
) -> (Vec<u32>, Vec<u32>, Vec<f64>) {
let steps = edge_offsets.len().saturating_sub(1);
let counts = (0..steps)
.into_par_iter()
.fold(FxHashMap::default, |mut counts, window| {
let start = edge_offsets[window] as usize;
let end = edge_offsets[window + 1] as usize;
for i in start..end {
*counts
.entry(edge(edge_from[i], edge_to[i]))
.or_insert(0usize) += 1;
}
counts
})
.reduce(FxHashMap::default, |mut left, right| {
for (pair, count) in right {
*left.entry(pair).or_insert(0) += count;
}
left
});
let mut values: Vec<_> = counts.into_iter().collect();
values.sort_unstable_by_key(|(pair, _)| *pair);
let denominator = steps.max(1) as f64;
let mut from = Vec::with_capacity(values.len());
let mut to = Vec::with_capacity(values.len());
let mut persistence = Vec::with_capacity(values.len());
for ((u, v), count) in values {
from.push(u);
to.push(v);
persistence.push(count as f64 / denominator);
}
(from, to, persistence)
}
fn aggregate_from_counts(
counts: FxHashMap<Edge, usize>,
steps: usize,
) -> (Vec<u32>, Vec<u32>, Vec<f32>) {
let mut values: Vec<_> = counts.into_iter().collect();
values.sort_unstable_by_key(|(e, _)| *e);
let denom = steps.max(1) as f64;
let mut from = Vec::with_capacity(values.len());
let mut to = Vec::with_capacity(values.len());
let mut persistence = Vec::with_capacity(values.len());
for ((u, v), n) in values {
from.push(u);
to.push(v);
persistence.push((n as f64 / denom) as f32);
}
(from, to, persistence)
}
fn aggregate_serial(events: &[FxHashSet<Edge>]) -> (Vec<u32>, Vec<u32>, Vec<f32>) {
let mut counts: FxHashMap<Edge, usize> = FxHashMap::default();
for event in events {
for &e in event {
*counts.entry(e).or_insert(0) += 1;
}
}
aggregate_from_counts(counts, events.len())
}
fn aggregate(events: &[FxHashSet<Edge>]) -> (Vec<u32>, Vec<u32>, Vec<f32>) {
let counts = events
.par_iter()
.fold(FxHashMap::default, |mut counts, event| {
for &e in event {
*counts.entry(e).or_insert(0) += 1;
}
counts
})
.reduce(FxHashMap::default, |mut left, right| {
for (edge, count) in right {
*left.entry(edge).or_insert(0) += count;
}
left
});
aggregate_from_counts(counts, events.len())
}
#[inline(always)]
fn count_common(a: &[u32], b: &[u32]) -> usize {
#[cfg(feature = "numkong")]
{
u32::sparse_intersection_size(a, b)
}
#[cfg(not(feature = "numkong"))]
{
let (mut i, mut j, mut n) = (0, 0, 0);
while i < a.len() && j < b.len() {
let x = a[i];
let y = b[j];
n += (x == y) as usize;
i += (x <= y) as usize;
j += (x >= y) as usize;
}
n
}
}
fn build_adjacency_csr(node_count: usize, from: &[u32], to: &[u32]) -> (Vec<usize>, Vec<u32>) {
let mut degree = vec![0usize; node_count];
for i in 0..from.len() {
degree[from[i] as usize] += 1;
degree[to[i] as usize] += 1;
}
let mut offsets = vec![0usize; node_count + 1];
for i in 0..node_count {
offsets[i + 1] = offsets[i] + degree[i];
}
let mut flat = vec![0u32; offsets[node_count] as usize];
let mut cursor = offsets.clone();
for i in 0..from.len() {
let (u, v) = (from[i], to[i]);
flat[cursor[u as usize] as usize] = v;
cursor[u as usize] += 1;
flat[cursor[v as usize] as usize] = u;
cursor[v as usize] += 1;
}
for i in 0..node_count {
let s = offsets[i] as usize;
let e = offsets[i + 1] as usize;
flat[s..e].sort_unstable();
}
(offsets, flat)
}
fn overlaps(node_count: usize, from: &[u32], to: &[u32]) -> Vec<f32> {
let (offsets, flat) = build_adjacency_csr(node_count, from, to);
let words = node_count.div_ceil(64);
let mut bit_offsets = vec![usize::MAX; node_count];
let mut bit_words = 0usize;
for u in 0..node_count {
if offsets[u + 1] - offsets[u] >= words.saturating_mul(2).max(64)
&& bit_words.saturating_add(words) <= 512 * 1024 * 1024
{
bit_offsets[u] = bit_words;
bit_words += words;
}
}
let mut bits = vec![0u64; bit_words];
for u in 0..node_count {
if bit_offsets[u] != usize::MAX {
for &v in &flat[offsets[u]..offsets[u + 1]] {
bits[bit_offsets[u] + v as usize / 64] |= 1u64 << (v % 64);
}
}
}
(0..from.len())
.into_par_iter()
.map(|i| {
let a = &flat[offsets[from[i] as usize]..offsets[from[i] as usize + 1]];
let b = &flat[offsets[to[i] as usize]..offsets[to[i] as usize + 1]];
let (ao, bo) = (bit_offsets[from[i] as usize], bit_offsets[to[i] as usize]);
let inter = match (ao != usize::MAX, bo != usize::MAX) {
(true, true) => bits[ao..ao + words]
.iter()
.zip(&bits[bo..bo + words])
.map(|(&x, &y)| (x & y).count_ones() as usize)
.sum(),
(true, false) => b
.iter()
.filter(|&&v| bits[ao + v as usize / 64] & (1u64 << (v % 64)) != 0)
.count(),
(false, true) => a
.iter()
.filter(|&&v| bits[bo + v as usize / 64] & (1u64 << (v % 64)) != 0)
.count(),
(false, false) => count_common(a, b),
};
let union = a.len() + b.len() - inter;
if union == 0 {
0.0
} else {
inter as f32 / union as f32
}
})
.collect()
}
pub fn topological_overlaps(node_count: usize, from: &[u32], to: &[u32]) -> Vec<f32> {
overlaps(node_count, from, to)
}
fn overlaps_serial(node_count: usize, from: &[u32], to: &[u32]) -> Vec<f32> {
let (offsets, flat) = build_adjacency_csr(node_count, from, to);
(0..from.len())
.map(|i| {
let a = &flat[offsets[from[i] as usize]..offsets[from[i] as usize + 1]];
let b = &flat[offsets[to[i] as usize]..offsets[to[i] as usize + 1]];
let inter = count_common(a, b);
let union = a.len() + b.len() - inter;
if union == 0 {
0.0
} else {
inter as f32 / union as f32
}
})
.collect()
}
fn count_common_after(a: &[u32], b: &[u32], threshold: u32) -> usize {
count_common(
&a[a.partition_point(|&node| node <= threshold)..],
&b[b.partition_point(|&node| node <= threshold)..],
)
}
pub fn local_clustering_coefficients(node_count: usize, from: &[u32], to: &[u32]) -> Vec<f64> {
let (offsets, flat) = build_adjacency_csr(node_count, from, to);
(0..node_count)
.into_par_iter()
.map(|node| {
let neighbors = &flat[offsets[node]..offsets[node + 1]];
let degree = neighbors.len();
if degree < 2 {
return 0.0;
}
let links: usize = neighbors
.iter()
.map(|&neighbor| {
let other = &flat[offsets[neighbor as usize]..offsets[neighbor as usize + 1]];
count_common_after(neighbors, other, neighbor)
})
.sum();
2.0 * links as f64 / (degree * (degree - 1)) as f64
})
.collect()
}
fn local_clustering_coefficients_serial(node_count: usize, from: &[u32], to: &[u32]) -> Vec<f64> {
let (offsets, flat) = build_adjacency_csr(node_count, from, to);
(0..node_count)
.map(|node| {
let neighbors = &flat[offsets[node]..offsets[node + 1]];
let degree = neighbors.len();
if degree < 2 {
return 0.0;
}
let links: usize = neighbors
.iter()
.map(|&neighbor| {
let other = &flat[offsets[neighbor as usize]..offsets[neighbor as usize + 1]];
count_common_after(neighbors, other, neighbor)
})
.sum();
2.0 * links as f64 / (degree * (degree - 1)) as f64
})
.collect()
}
fn sort_nodes_by_degree_desc(degree: &[usize]) -> Vec<u32> {
let n = degree.len();
let max_degree = degree.iter().copied().max().unwrap_or(0);
let mut starts = vec![0u32; max_degree + 1];
for &d in degree {
starts[d] += 1;
}
let mut cumulative = 0u32;
for d in (0..=max_degree).rev() {
let count = starts[d];
starts[d] = cumulative;
cumulative += count;
}
let mut order = vec![0u32; n];
for (i, &d) in degree.iter().enumerate() {
order[starts[d] as usize] = i as u32;
starts[d] += 1;
}
order
}
fn sample_expected_degree_edges(
node_count: usize,
degree: &[usize],
sum: usize,
rng: &mut Xoshiro256PlusPlus,
emit: impl FnMut(u32, u32),
) {
if sum == 0 || node_count < 2 {
return;
}
let order = sort_nodes_by_degree_desc(degree);
let seq: Vec<f64> = order.iter().map(|&i| degree[i as usize] as f64).collect();
sample_ordered_edges(&order, &seq, sum, rng, emit);
}
pub fn expected_degree_graph(degree: &[usize], seed: u64) -> (Vec<u32>, Vec<u32>) {
let mut rng = Xoshiro256PlusPlus::seed_from_u64(seed);
let sum: usize = degree.iter().sum();
let mut values = Vec::new();
sample_expected_degree_edges(degree.len(), degree, sum, &mut rng, |u, v| {
values.push(edge(u, v));
});
values.sort_unstable();
values.into_iter().unzip()
}
fn sample_ordered_edges(
order: &[u32],
seq: &[f64],
sum: usize,
rng: &mut Xoshiro256PlusPlus,
mut emit: impl FnMut(u32, u32),
) {
if sum == 0 {
return;
}
let rho = 1.0 / sum as f64;
let n = order.len();
for u in 0..n {
let mut v = u + 1;
if v >= n {
continue;
}
let factor = seq[u] * rho;
let mut p = (seq[v] * factor).min(1.0);
while v < n && p > 0.0 {
if p != 1.0 {
let r: f64 = rng.r#gen();
let jump = r.ln() / (1.0 - p).ln();
if !jump.is_finite() {
break;
}
v += jump.floor() as usize;
}
if v < n {
let q = (seq[v] * factor).min(1.0);
if rng.r#gen::<f64>() < q / p {
emit(order[u], order[v]);
}
v += 1;
p = q;
}
}
}
}
pub fn rnd(
node_count: usize,
event: &FxHashSet<Edge>,
rng: &mut Xoshiro256PlusPlus,
) -> FxHashSet<Edge> {
let mut degree = vec![0usize; node_count];
for &(u, v) in event {
degree[u as usize] += 1;
degree[v as usize] += 1;
}
let sum: usize = degree.iter().sum();
let mut result = FxHashSet::default();
sample_expected_degree_edges(node_count, °ree, sum, rng, |a, b| {
result.insert(edge(a, b));
});
result
}
pub fn t_rnd(
node_count: usize,
temporal: &TemporalEvents,
replica: usize,
seed: u64,
) -> TemporalEvents {
let events = temporal
.events
.par_iter()
.enumerate()
.map(|(window, event)| {
let mut rng = Xoshiro256PlusPlus::seed_from_u64(stream_seed(seed, replica, window));
rnd(node_count, event, &mut rng)
})
.collect();
TemporalEvents {
events,
window_starts_ms: temporal.window_starts_ms.clone(),
}
}
pub fn rnd_graph(
node_count: usize,
edge_from: &[u32],
edge_to: &[u32],
seed: u64,
) -> (Vec<u32>, Vec<u32>) {
let event: FxHashSet<Edge> = edge_from
.iter()
.zip(edge_to)
.filter_map(|(&u, &v)| (u != v).then_some(edge(u, v)))
.collect();
let mut rng = Xoshiro256PlusPlus::seed_from_u64(seed);
let mut values: Vec<_> = rnd(node_count, &event, &mut rng).into_iter().collect();
values.sort_unstable();
values.into_iter().unzip()
}
pub fn t_rnd_graph(
node_count: usize,
window_starts_ms: &[i64],
edge_offsets: &[u64],
edge_from: &[u32],
edge_to: &[u32],
replica: usize,
seed: u64,
) -> TemporalGraphOutput {
let events = (0..window_starts_ms.len())
.map(|i| {
let lo = edge_offsets[i] as usize;
let hi = edge_offsets[i + 1] as usize;
edge_from[lo..hi]
.iter()
.zip(&edge_to[lo..hi])
.filter_map(|(&u, &v)| (u != v).then_some(edge(u, v)))
.collect()
})
.collect();
flatten_events(&t_rnd(
node_count,
&TemporalEvents {
events,
window_starts_ms: window_starts_ms.to_vec(),
},
replica,
seed,
))
}
fn threshold(values: &mut [f32], p_rnd: f64) -> f64 {
if values.is_empty() {
return 1.0;
}
values.sort_by(|a, b| a.total_cmp(b));
values[(((values.len() as f64) * (1.0 - p_rnd)).ceil() as usize)
.saturating_sub(1)
.min(values.len() - 1)] as f64
}
fn relationship_class(p: f32, o: f32, pt: f64, ot: f64) -> u8 {
match (p as f64 > pt, o as f64 > ot) {
(true, true) => 0,
(true, false) => 1,
(false, true) => 2,
(false, false) => 3,
}
}
pub struct RecastOutput {
pub edge_from: Vec<u32>,
pub edge_to: Vec<u32>,
pub persistence: Vec<f32>,
pub topological_overlap: Vec<f32>,
pub classes: Vec<u8>,
pub persistence_threshold: f64,
pub overlap_threshold: f64,
pub time_steps: usize,
}
fn random_replicas(
node_count: usize,
temporal: &TemporalEvents,
replicas: usize,
seed: u64,
) -> Vec<TemporalEvents> {
let replicas = replicas.max(1);
let windows = temporal.events.len();
if windows == 0 {
return (0..replicas)
.map(|_| TemporalEvents {
events: Vec::new(),
window_starts_ms: Vec::new(),
})
.collect();
}
let generated: Vec<FxHashSet<Edge>> = (0..replicas * windows)
.into_par_iter()
.map(|index| {
let replica = index / windows;
let window = index % windows;
let mut rng = Xoshiro256PlusPlus::seed_from_u64(stream_seed(seed, replica, window));
rnd(node_count, &temporal.events[window], &mut rng)
})
.collect();
generated
.chunks(windows)
.map(|events| TemporalEvents {
events: events.to_vec(),
window_starts_ms: temporal.window_starts_ms.clone(),
})
.collect()
}
fn classify_events_with_randoms(
node_count: usize,
temporal: &TemporalEvents,
p_rnd: f64,
randoms: &[TemporalEvents],
) -> (RecastOutput, Vec<f32>, Vec<f32>) {
let (edge_from, edge_to, persistence) = aggregate(&temporal.events);
let time_steps = temporal.events.len();
if edge_from.is_empty() {
return (
RecastOutput {
edge_from,
edge_to,
persistence,
topological_overlap: Vec::new(),
classes: Vec::new(),
persistence_threshold: 1.0,
overlap_threshold: 1.0,
time_steps,
},
Vec::new(),
Vec::new(),
);
}
let topological_overlap = overlaps(node_count, &edge_from, &edge_to);
let null_metrics: Vec<_> = randoms
.par_iter()
.map(|random| {
let (rf, rt, rp) = aggregate_serial(&random.events);
let overlap = overlaps_serial(node_count, &rf, &rt);
(rp, overlap)
})
.collect();
let mut null_persistence = Vec::new();
let mut null_overlap = Vec::new();
for (persistence, overlap) in null_metrics {
null_persistence.extend(persistence);
null_overlap.extend(overlap);
}
let persistence_threshold = threshold(&mut null_persistence, p_rnd);
let overlap_threshold = threshold(&mut null_overlap, p_rnd);
let classes = persistence
.iter()
.zip(&topological_overlap)
.map(|(&p, &o)| relationship_class(p, o, persistence_threshold, overlap_threshold))
.collect();
(
RecastOutput {
edge_from,
edge_to,
persistence,
topological_overlap,
classes,
persistence_threshold,
overlap_threshold,
time_steps,
},
null_persistence,
null_overlap,
)
}
struct NullTail {
values: Vec<f32>,
total: usize,
keep: usize,
upper: bool,
}
impl NullTail {
fn new(max_values: usize, p: f64) -> Self {
let upper = p <= 0.5;
let fraction = if upper { p } else { 1.0 - p };
let keep = ((max_values as f64 * fraction).ceil() as usize).saturating_add(2);
Self {
values: Vec::new(),
total: 0,
keep,
upper,
}
}
fn extend(&mut self, values: &[f32]) {
self.total += values.len();
for chunk in values.chunks(65_536) {
self.values.extend_from_slice(chunk);
if self.values.len() > self.keep.saturating_mul(2).max(65_536) {
self.trim();
}
}
}
fn trim(&mut self) {
if self.values.len() > self.keep {
let upper = self.upper;
self.values.select_nth_unstable_by(self.keep, |a, b| {
if upper {
b.total_cmp(a)
} else {
a.total_cmp(b)
}
});
self.values.truncate(self.keep);
}
}
fn threshold(&mut self, p: f64) -> f64 {
if self.total == 0 {
return 1.0;
}
self.trim();
let rank = ((self.total as f64 * (1.0 - p)).ceil() as usize)
.saturating_sub(1)
.min(self.total - 1);
let index = if self.upper {
self.total - 1 - rank
} else {
rank
};
let upper = self.upper;
*self
.values
.select_nth_unstable_by(index, |a, b| {
if upper {
b.total_cmp(a)
} else {
a.total_cmp(b)
}
})
.1 as f64
}
fn merge(&mut self, partial: NullTail) {
self.total += partial.total;
self.values.extend(partial.values);
if self.values.len() > self.keep.saturating_mul(2).max(65_536) {
self.trim();
}
}
}
fn histogram_threshold(histogram: &FxHashMap<u32, usize>, p: f64) -> f64 {
let total: usize = histogram.values().sum();
if total == 0 {
return 1.0;
}
let rank = ((total as f64 * (1.0 - p)).ceil() as usize)
.saturating_sub(1)
.min(total - 1);
let mut bins: Vec<_> = histogram
.iter()
.map(|(&bits, &count)| (f32::from_bits(bits), count))
.collect();
bins.sort_unstable_by(|a, b| a.0.total_cmp(&b.0));
let mut cumulative = 0;
for (value, count) in bins {
cumulative += count;
if cumulative > rank {
return value as f64;
}
}
unreachable!()
}
fn classify_events_streaming(
node_count: usize,
temporal: TemporalEvents,
p_rnd: f64,
replicas: usize,
seed: u64,
) -> RecastOutput {
let started = Instant::now();
let (edge_from, edge_to, persistence) = aggregate(&temporal.events);
profile("observed_aggregate", started, edge_from.len());
let time_steps = temporal.events.len();
if edge_from.is_empty() {
return RecastOutput {
edge_from,
edge_to,
persistence,
topological_overlap: Vec::new(),
classes: Vec::new(),
persistence_threshold: 1.0,
overlap_threshold: 1.0,
time_steps,
};
}
let started = Instant::now();
let sampling: Vec<_> = temporal
.events
.par_iter()
.map(|event| {
let mut degree = vec![0usize; node_count];
for &(a, b) in event {
degree[a as usize] += 1;
degree[b as usize] += 1;
}
let sum = degree.iter().sum::<usize>();
let order = sort_nodes_by_degree_desc(°ree);
let seq: Vec<f64> = order.iter().map(|&u| degree[u as usize] as f64).collect();
(order, seq, sum)
})
.collect();
drop(temporal);
profile("sampling_metadata", started, edge_from.len());
let started = Instant::now();
let topological_overlap = overlaps(node_count, &edge_from, &edge_to);
profile("observed_overlap", started, edge_from.len());
let replicas = replicas.max(1);
let max_values = node_count.saturating_mul(node_count.saturating_sub(1)) / 2;
let mut null_overlap = NullTail::new(max_values.saturating_mul(replicas), p_rnd);
let mut persistence_histogram = FxHashMap::default();
let workers_per_replica = rayon::current_num_threads().div_ceil(replicas).max(1);
thread::scope(|scope| {
let (sender, receiver) = mpsc::channel();
for replica in 0..replicas {
let sender = sender.clone();
let sampling = &sampling;
scope.spawn(move || {
let pool = rayon::ThreadPoolBuilder::new()
.num_threads(workers_per_replica)
.build()
.unwrap();
let started = Instant::now();
let counts = pool.install(|| {
sampling
.par_iter()
.enumerate()
.fold(
FxHashMap::default,
|mut counts, (window, (order, seq, sum))| {
let mut rng = Xoshiro256PlusPlus::seed_from_u64(stream_seed(
seed, replica, window,
));
sample_ordered_edges(order, seq, *sum, &mut rng, |a, b| {
*counts.entry(edge(a, b)).or_insert(0usize) += 1;
});
counts
},
)
.reduce(FxHashMap::default, |mut left, right| {
for (edge, count) in right {
*left.entry(edge).or_insert(0) += count;
}
left
})
});
profile("null_sample_aggregate", started, counts.len());
let started = Instant::now();
let (from, to, persistence) = aggregate_from_counts(counts, time_steps);
profile("null_order", started, from.len());
let started = Instant::now();
let overlap = pool.install(|| overlaps(node_count, &from, &to));
profile("null_overlap", started, from.len());
let started = Instant::now();
let mut histogram = FxHashMap::default();
for value in persistence {
*histogram.entry(value.to_bits()).or_insert(0usize) += 1;
}
let mut tail = NullTail::new(max_values.saturating_mul(replicas), p_rnd);
tail.extend(&overlap);
profile("null_tail", started, from.len());
sender.send((histogram, tail)).unwrap();
});
}
drop(sender);
for (histogram, tail) in receiver {
for (value, count) in histogram {
*persistence_histogram.entry(value).or_insert(0usize) += count;
}
null_overlap.merge(tail);
}
});
let started = Instant::now();
let persistence_threshold = histogram_threshold(&persistence_histogram, p_rnd);
let overlap_threshold = null_overlap.threshold(p_rnd);
let classes = persistence
.iter()
.zip(&topological_overlap)
.map(|(&p, &o)| relationship_class(p, o, persistence_threshold, overlap_threshold))
.collect();
profile("thresholds_and_classes", started, edge_from.len());
RecastOutput {
edge_from,
edge_to,
persistence,
topological_overlap,
classes,
persistence_threshold,
overlap_threshold,
time_steps,
}
}
#[allow(clippy::too_many_arguments)]
pub fn recast_classify(
node_count: usize,
users: &[u32],
locations: &[u32],
starts: &[i64],
ends: &[i64],
min_contact_ms: i64,
p_rnd: f64,
replicas: usize,
seed: u64,
) -> RecastOutput {
let started = Instant::now();
let temporal = event_graphs(users, locations, starts, ends, min_contact_ms);
profile(
"events",
started,
temporal.events.iter().map(|x| x.len()).sum(),
);
classify_events_streaming(node_count, temporal, p_rnd, replicas, seed)
}
fn average_clustering(node_count: usize, event: &FxHashSet<Edge>) -> f64 {
if node_count == 0 {
return 0.0;
}
let (from, to): (Vec<_>, Vec<_>) = event.iter().copied().unzip();
local_clustering_coefficients(node_count, &from, &to)
.into_iter()
.sum::<f64>()
/ node_count as f64
}
fn cumulative_clustering(node_count: usize, temporal: &TemporalEvents) -> Vec<f64> {
let mut aggregate = FxHashSet::default();
temporal
.events
.iter()
.map(|event| {
aggregate.extend(event.iter().copied());
average_clustering(node_count, &aggregate)
})
.collect()
}
fn average_clustering_serial(node_count: usize, event: &FxHashSet<Edge>) -> f64 {
if node_count == 0 {
return 0.0;
}
let (from, to): (Vec<_>, Vec<_>) = event.iter().copied().unzip();
let total: f64 = local_clustering_coefficients_serial(node_count, &from, &to)
.into_iter()
.sum();
total / node_count as f64
}
fn cumulative_clustering_serial(node_count: usize, temporal: &TemporalEvents) -> Vec<f64> {
let mut aggregate = FxHashSet::default();
temporal
.events
.iter()
.map(|event| {
aggregate.extend(event.iter().copied());
average_clustering_serial(node_count, &aggregate)
})
.collect()
}
fn mean_std(series: &[Vec<f64>]) -> (Vec<f64>, Vec<f64>) {
if series.is_empty() {
return (Vec::new(), Vec::new());
}
let n = series.len() as f64;
let means: Vec<_> = (0..series[0].len())
.map(|i| series.iter().map(|x| x[i]).sum::<f64>() / n)
.collect();
let std = (0..means.len())
.map(|i| {
(series
.iter()
.map(|x| (x[i] - means[i]).powi(2))
.sum::<f64>()
/ n)
.sqrt()
})
.collect();
(means, std)
}
fn random_only_events(temporal: &TemporalEvents, output: &RecastOutput) -> TemporalEvents {
let random: FxHashSet<Edge> = output
.edge_from
.iter()
.zip(&output.edge_to)
.zip(&output.classes)
.filter_map(|((&u, &v), &class)| (class == 3).then_some((u, v)))
.collect();
TemporalEvents {
events: temporal
.events
.iter()
.map(|event| {
event
.iter()
.filter(|e| random.contains(e))
.copied()
.collect()
})
.collect(),
window_starts_ms: temporal.window_starts_ms.clone(),
}
}
pub struct RecastValidationOutput {
pub classification: RecastOutput,
pub observed_persistence: Vec<f32>,
pub observed_overlap: Vec<f32>,
pub random_persistence: Vec<f32>,
pub random_overlap: Vec<f32>,
pub full_observed_clustering: Vec<f64>,
pub full_random_mean: Vec<f64>,
pub full_random_std: Vec<f64>,
pub random_only_observed_clustering: Vec<f64>,
pub random_only_random_mean: Vec<f64>,
pub random_only_random_std: Vec<f64>,
pub graph: TemporalGraphOutput,
}
#[allow(clippy::too_many_arguments)]
pub fn validate_recast(
node_count: usize,
users: &[u32],
locations: &[u32],
starts: &[i64],
ends: &[i64],
min_contact_ms: i64,
p_rnd: f64,
replicas: usize,
seed: u64,
) -> RecastValidationOutput {
let temporal = event_graphs(users, locations, starts, ends, min_contact_ms);
let randoms = random_replicas(node_count, &temporal, replicas, seed);
let (classification, random_persistence, random_overlap) =
classify_events_with_randoms(node_count, &temporal, p_rnd, &randoms);
let full_observed_clustering = cumulative_clustering(node_count, &temporal);
let full_series: Vec<_> = randoms
.par_iter()
.map(|x| cumulative_clustering_serial(node_count, x))
.collect();
let (full_random_mean, full_random_std) = mean_std(&full_series);
let observed_random = random_only_events(&temporal, &classification);
let random_only_observed_clustering = cumulative_clustering(node_count, &observed_random);
let random_only_series: Vec<_> = randoms
.par_iter()
.map(|x| cumulative_clustering_serial(node_count, &random_only_events(x, &classification)))
.collect();
let (random_only_random_mean, random_only_random_std) = mean_std(&random_only_series);
RecastValidationOutput {
observed_persistence: classification.persistence.clone(),
observed_overlap: classification.topological_overlap.clone(),
classification,
random_persistence,
random_overlap,
full_observed_clustering,
full_random_mean,
full_random_std,
random_only_observed_clustering,
random_only_random_mean,
random_only_random_std,
graph: flatten_events(&temporal),
}
}
#[cfg(test)]
mod tests {
use super::*;
use rayon::ThreadPoolBuilder;
#[test]
fn aggregate_raw_graph_from_temporal_events() {
let (from, to, persistence) = aggregate_flat_events(&[0, 2, 3], &[0, 1, 1], &[1, 2, 2]);
assert_eq!((from, to), (vec![0, 1], vec![1, 2]));
assert_eq!(persistence, vec![0.5, 1.0]);
}
#[test]
fn raw_contact_metrics_match_triangle_fixture() {
let metrics = contact_graph_metrics(4, &[0, 0, 1, 2], &[1, 2, 2, 3]);
assert_eq!(
metrics.clustering_coefficient,
vec![1.0, 1.0, 1.0 / 3.0, 0.0]
);
assert!((metrics.topological_overlap[0] - 1.0 / 3.0).abs() < 1e-6);
assert_eq!(metrics.topological_overlap[1..], [0.25, 0.25, 0.0]);
}
#[test]
fn adaptive_overlap_matches_sparse_reference() {
let mut from = Vec::new();
let mut to = Vec::new();
for u in 0..250u32 {
for v in u + 1..300u32 {
if v < 180 || (u * 17 + v * 13) % 41 == 0 {
from.push(u);
to.push(v);
}
}
}
assert_eq!(overlaps(310, &from, &to), overlaps_serial(310, &from, &to));
}
#[test]
fn exact_tail_and_histogram_match_sorted_quantiles() {
let original: Vec<f32> = (0..200_123)
.map(|i| ((i * 7919) % 107) as f32 / 107.0)
.collect();
for p in [0.0, 0.00001, 0.001, 0.1, 0.5, 0.9, 0.99999, 1.0] {
let mut tail = NullTail::new(original.len() + 199, p);
let mut histogram = FxHashMap::default();
for chunk in original.chunks(1337) {
tail.extend(chunk);
}
for &v in &original {
*histogram.entry(v.to_bits()).or_insert(0) += 1;
}
let expected = threshold(&mut original.clone(), p);
assert_eq!(tail.threshold(p), expected);
assert_eq!(histogram_threshold(&histogram, p), expected);
assert_eq!(NullTail::new(10, p).threshold(p), 1.0);
}
}
#[test]
fn streaming_matches_materialized_reference() {
let (users, locations, starts, ends) = parallel_fixture();
let temporal = event_graphs(&users, &locations, &starts, &ends, 60_000);
for seed in [0, 9, 42] {
for p in [0.0, 0.001, 0.5, 1.0] {
let randoms = random_replicas(4, &temporal, 5, seed);
let expected = classify_events_with_randoms(4, &temporal, p, &randoms).0;
let actual = classify_events_streaming(4, temporal.clone(), p, 5, seed);
assert_eq!(actual.edge_from, expected.edge_from);
assert_eq!(actual.edge_to, expected.edge_to);
assert_eq!(actual.persistence, expected.persistence);
assert_eq!(actual.topological_overlap, expected.topological_overlap);
assert_eq!(actual.classes, expected.classes);
assert_eq!(actual.persistence_threshold, expected.persistence_threshold);
assert_eq!(actual.overlap_threshold, expected.overlap_threshold);
}
}
}
fn parallel_fixture() -> (Vec<u32>, Vec<u32>, Vec<i64>, Vec<i64>) {
(
vec![0, 1, 2, 0, 1, 3, 2, 3],
vec![0, 0, 0, 1, 1, 1, 0, 1],
vec![
0,
60_000,
120_000,
DAY_MS,
DAY_MS + 60_000,
DAY_MS + 120_000,
2 * DAY_MS,
2 * DAY_MS + 60_000,
],
vec![
300_000,
360_000,
420_000,
DAY_MS + 300_000,
DAY_MS + 360_000,
DAY_MS + 420_000,
2 * DAY_MS + 300_000,
2 * DAY_MS + 360_000,
],
)
}
#[test]
fn interval_contacts_require_overlap() {
let t = event_graphs(&[0, 1, 2], &[0, 0, 0], &[0, 5, 20], &[10, 15, 30], 1);
assert_eq!(t.events.len(), 1);
assert!(t.events[0].contains(&(0, 1)));
assert_eq!(t.events[0].len(), 1);
}
#[test]
fn interval_contacts_require_minimum_duration() {
let t = event_graphs(&[0, 1], &[0, 0], &[0, 60_000], &[360_000, 300_000], 300_000);
assert!(t.events[0].is_empty());
let t = event_graphs(&[0, 1], &[0, 0], &[0, 60_000], &[360_000, 300_000], 240_000);
assert!(t.events[0].contains(&(0, 1)));
}
#[test]
fn event_graphs_matches_naive_o_n_squared_reference_on_dense_overlaps() {
let n = 400usize;
let mut state = 0x2545_F491_4F6C_DD1Du64;
let mut next = move || {
state ^= state << 13;
state ^= state >> 7;
state ^= state << 17;
state
};
let mut users = Vec::new();
let mut locations = Vec::new();
let mut starts = Vec::new();
let mut ends = Vec::new();
for u in 0..n {
let start = (next() % 500_000) as i64;
let duration = 60_000 + (next() % 400_000) as i64;
users.push(u as u32);
locations.push(0u32);
starts.push(start);
ends.push(start + duration);
}
let min_contact_ms = 120_000;
let observed = event_graphs(&users, &locations, &starts, &ends, min_contact_ms);
assert_eq!(observed.events.len(), 1);
let mut expected = FxHashSet::default();
for i in 0..n {
for j in (i + 1)..n {
let overlap = starts[i].max(starts[j])..ends[i].min(ends[j]);
if overlap.end - overlap.start >= min_contact_ms {
expected.insert(edge(users[i], users[j]));
}
}
}
assert_eq!(observed.events[0], expected);
assert!(
!expected.is_empty(),
"test fixture produced no overlaps to check"
);
}
#[test]
fn rnd_is_seeded_simple_graph() {
let event: FxHashSet<Edge> = [(0, 1), (0, 2), (1, 3)].into_iter().collect();
let mut a = Xoshiro256PlusPlus::seed_from_u64(4);
let mut b = Xoshiro256PlusPlus::seed_from_u64(4);
assert_eq!(rnd(4, &event, &mut a), rnd(4, &event, &mut b));
}
#[test]
fn rnd_edge_cases_emit_nothing() {
let empty: FxHashSet<Edge> = FxHashSet::default();
let mut rng = Xoshiro256PlusPlus::seed_from_u64(1);
assert!(rnd(0, &empty, &mut rng).is_empty());
assert!(rnd(1, &empty, &mut rng).is_empty());
assert!(rnd(5, &empty, &mut rng).is_empty());
}
#[test]
fn sample_expected_degree_edges_matches_theoretical_probabilities() {
let node_count = 12;
let degree = [8usize, 6, 6, 5, 4, 3, 3, 2, 2, 1, 1, 1];
let sum: usize = degree.iter().sum();
let trials = 40_000u64;
let mut observed = vec![0u64; node_count * node_count];
for seed in 0..trials {
let mut rng = Xoshiro256PlusPlus::seed_from_u64(seed);
sample_expected_degree_edges(node_count, °ree, sum, &mut rng, |a, b| {
let (lo, hi) = if a < b { (a, b) } else { (b, a) };
observed[lo as usize * node_count + hi as usize] += 1;
});
}
for u in 0..node_count {
for v in (u + 1)..node_count {
let expected_p = ((degree[u] * degree[v]) as f64 / sum as f64).min(1.0);
let observed_p = observed[u * node_count + v] as f64 / trials as f64;
assert!(
(observed_p - expected_p).abs() < 0.02,
"pair ({u},{v}): expected {expected_p:.4}, observed {observed_p:.4}"
);
}
}
}
#[test]
fn sort_nodes_by_degree_desc_matches_comparison_sort() {
let degree = [3usize, 0, 3, 7, 1, 0, 5, 1, 7, 2];
let mut expected: Vec<u32> = (0..degree.len() as u32).collect();
expected.sort_by(|&a, &b| degree[b as usize].cmp(°ree[a as usize]));
let actual = sort_nodes_by_degree_desc(°ree);
assert_eq!(actual.len(), expected.len());
let actual_degrees: Vec<usize> = actual.iter().map(|&i| degree[i as usize]).collect();
let expected_degrees: Vec<usize> = expected.iter().map(|&i| degree[i as usize]).collect();
assert_eq!(actual_degrees, expected_degrees);
let mut actual_sorted = actual.clone();
actual_sorted.sort_unstable();
assert_eq!(actual_sorted, (0..degree.len() as u32).collect::<Vec<_>>());
}
#[test]
fn sort_nodes_by_degree_desc_handles_empty_and_all_zero() {
assert!(sort_nodes_by_degree_desc(&[]).is_empty());
let all_zero = sort_nodes_by_degree_desc(&[0, 0, 0]);
let mut sorted = all_zero.clone();
sorted.sort_unstable();
assert_eq!(sorted, vec![0, 1, 2]);
}
#[test]
fn recast_emits_all_four_relationship_classes() {
assert_eq!(relationship_class(2.0, 2.0, 1.0, 1.0), 0);
assert_eq!(relationship_class(2.0, 1.0, 1.0, 1.0), 1);
assert_eq!(relationship_class(1.0, 2.0, 1.0, 1.0), 2);
assert_eq!(relationship_class(1.0, 1.0, 1.0, 1.0), 3);
}
#[test]
fn classifier_is_stable_across_rayon_thread_counts() {
let (users, locations, starts, ends) = parallel_fixture();
let single = ThreadPoolBuilder::new().num_threads(1).build().unwrap();
let many = ThreadPoolBuilder::new().num_threads(4).build().unwrap();
let one = single
.install(|| recast_classify(4, &users, &locations, &starts, &ends, 60_000, 0.5, 3, 9));
let four = many
.install(|| recast_classify(4, &users, &locations, &starts, &ends, 60_000, 0.5, 3, 9));
assert_eq!(one.edge_from, four.edge_from);
assert_eq!(one.edge_to, four.edge_to);
assert_eq!(one.persistence, four.persistence);
assert_eq!(one.topological_overlap, four.topological_overlap);
assert_eq!(one.classes, four.classes);
assert_eq!(one.persistence_threshold, four.persistence_threshold);
assert_eq!(one.overlap_threshold, four.overlap_threshold);
}
#[test]
fn temporal_randomization_is_stable_across_rayon_thread_counts() {
let (users, locations, starts, ends) = parallel_fixture();
let temporal = event_graphs(&users, &locations, &starts, &ends, 60_000);
let single = ThreadPoolBuilder::new().num_threads(1).build().unwrap();
let many = ThreadPoolBuilder::new().num_threads(4).build().unwrap();
let one = single.install(|| flatten_events(&t_rnd(4, &temporal, 2, 17)));
let four = many.install(|| flatten_events(&t_rnd(4, &temporal, 2, 17)));
assert_eq!(one.edge_offsets, four.edge_offsets);
assert_eq!(one.edge_from, four.edge_from);
assert_eq!(one.edge_to, four.edge_to);
}
#[test]
fn validation_keeps_classification_stable_across_rayon_thread_counts() {
let (users, locations, starts, ends) = parallel_fixture();
let single = ThreadPoolBuilder::new().num_threads(1).build().unwrap();
let many = ThreadPoolBuilder::new().num_threads(4).build().unwrap();
let one = single
.install(|| validate_recast(4, &users, &locations, &starts, &ends, 60_000, 0.5, 3, 23));
let four = many
.install(|| validate_recast(4, &users, &locations, &starts, &ends, 60_000, 0.5, 3, 23));
assert_eq!(one.classification.edge_from, four.classification.edge_from);
assert_eq!(one.classification.edge_to, four.classification.edge_to);
assert_eq!(one.classification.classes, four.classification.classes);
assert_eq!(
one.classification.persistence_threshold,
four.classification.persistence_threshold
);
assert_eq!(
one.classification.overlap_threshold,
four.classification.overlap_threshold
);
for (left, right) in one.full_random_mean.iter().zip(&four.full_random_mean) {
assert!((left - right).abs() < 1e-12);
}
for (left, right) in one
.random_only_random_std
.iter()
.zip(&four.random_only_random_std)
{
assert!((left - right).abs() < 1e-12);
}
}
}