Seeding Networks Built from Biased Friendship Reports

Programs that spread health information through a community, such as HIV prevention among homeless youth, choose a few "seed" people to train, hoping they pass the message on. The map of who knows whom is usually built by asking people to name their friends. Current planning algorithms treat that map as either correct or randomly noisy, as if each reported friendship were independently right or wrong. Survey research says otherwise. People forget friends in consistent ways, over-name popular peers, and hide stigmatized ties. These errors are correlated: when one person inflates their popularity, all of their edges are wrong in the same direction.

We argue that correlated errors damage one specific quantity that seed selection depends on, which is how much two candidate seeds' audiences overlap. If people over-name the popular kids, those popular kids look like they share everyone, so the planner either piles seeds onto them or wrongly rules them out as redundant. If people hide stigmatized ties, the network loses the bridges between groups, and seeds that actually reach the same people look separate. We propose to model the reporting process explicitly and to fit it from information every friend-naming survey already contains, namely the pattern of one-sided reports where A names B but B does not name A. We add a small set of verified ties. The planner then selects seeds and spends a limited verification budget on the ties that most change which seeds overlap.

Core Claim

Planning under edge uncertainty already exists. PSINET models unknown friendships in homeless-youth networks as a planning problem with hidden state and samples possible graphs. It gives each uncertain edge its own existence probability, even though its authors trace the uncertainty to youth being "vague about their friendships during interviews." ARISEN explores an unmapped network by querying people. It down-weights clusters it has already found so that seeds do not pile into one community, but it assumes every answer is truthful.

Our claim is that when reporting bias is organized around people rather than around individual edges, three things follow. First, sampling edges independently underestimates how wrong the estimated overlap between seeds can be, because errors on a person's edges move together instead of averaging out. Second, a reporting model with a reporter effect (how much this person recalls), a target effect (how often this person is over-named), and a tie-type effect (how often this kind of tie is withheld) can be partly identified from one-sided reports and anchored by a few verified ties. Third, choosing seeds by expected spread under that correlated model, and verifying the ties that most affect overlap, recovers spread that independent-noise planners lose. The size of that gain should grow with bias strength and vanish when bias is absent.

The missing-heritability literature supplies the reason to calibrate noisy reports rather than discard them. Howard et al. found 14 genome-wide loci for self-reported "broad depression" but only 1 for hospital-coded depression. The noisy measure won because of sample size. Ge et al. showed the other side: traits measured only by self-report, such as walking pace, have near-zero SNP-heritability, meaning common genetic variants explain almost none of their variation because measurement error buries the signal. Chen et al. and Yuan et al. recovered signal by anchoring subjective measures to objective ones: image-derived traits in Chen et al., and a panel of blood metabolic markers in Yuan et al. The network analogue is direct. Throwing away unverified ties is the hospital-code strategy, and trusting every tie is the raw self-report strategy. We propose the third option: keep all reports and correct them against a small objective anchor. Genetics serves here as motivating evidence and as a source of design lessons, not as an application.

Research Program

The reporting model treats the true graph $A$ as hidden. Person $i$ reports a tie to $j$ with probability

$$P(R_{ij}=1 \mid A_{ij}=a) = \mathrm{logistic}(\alpha_i + \beta_j + \gamma\, t_{ij} + \delta\, a).$$

The terms are defined as follows. $R_{ij}$ indicates that $i$ named $j$. $\alpha_i$ is $i$'s general tendency to name people, which captures recall. $\beta_j$ is how readily others name $j$, which captures prestige inflation. $t_{ij}$ marks tie types known to be under-reported, which captures stigma withholding. $\delta$ separates true from false ties. Classic social-desirability findings, such as the measurement non-invariance of self-report scales across groups shown by Yue et al., and recall degradation, as in Vernon et al., motivate separate person-level terms rather than one global noise rate.

Identification comes from two sources. The first is the directed survey, which contains up to two reports per pair. The second is a verified subset, such as PSINET's solid edges. Without that subset, forgetting by $i$ and inflation of $i$ by others cannot be fully told apart. We will measure how large the verified subset must be before the parameters are recovered.

Seed selection maximizes expected cascade spread averaged over graphs sampled from the posterior, where the posterior is the fitted model's updated belief about the true graph. That objective remains submodular, meaning each added seed contributes less than the one before. Greedy selection therefore keeps the $(1-1/e)$ guarantee of Kempe et al., in expectation over the model. Because posterior samples share person-level parameters, the implied overlap between two seeds carries realistic, correlated uncertainty.

On top of this sits a verification policy. Given a budget of $k$ ties to check, each step picks the pair whose resolution most changes the expected value of the currently chosen seed set. This is a value-of-information criterion aimed at redundancy between seeds, not at discovering the whole graph. It is a probabilistic cousin of the neighbor discounting of Wang et al. and the reverse message passing of Maharana et al., which lower a node's priority once a neighbor is chosen. In our version the discount itself is uncertain and can be bought down. The idea that errors are organized around people, not scattered independently, is the ingredient we isolate in ablations.

Baselines

The naive reference is degree centrality on the reported graph, which picks the most-named people. PSINET reports roughly 60% more indirect influence spread than degree centrality on the homeless-youth networks, so degree centrality is a floor, not a competitor.

The strongest existing method for our question is an independent-edge planner in the PSINET style. It gives each uncertain edge its own probability and runs expected-spread greedy selection over sampled graphs. We use the greedy-over-samples form rather than the full hidden-state planner, which isolates the noise model from the planner. It receives the same reports, the same verified subset, the same number of graph samples, and the same seed budget. Its edge probabilities are tuned on the verified subset with a search budget equal to the one we spend fitting our model.

The second strong competitor is ARISEN-style community-level seeding with its query budget set equal to our verification budget. ARISEN reports 20 to 50% more spread than baseline heuristics and reports matching full-graph performance after surveying 20 to 35% of the network, but only under truthful answers. We found no reported result on Lacuna for any influence-maximization method under systematic, person-organized reporting bias, so all comparisons in that setting are new.

The ceiling is greedy selection on the true graph. Two ablations test the key ingredients. The first keeps our reporting model but spends the verification budget on randomly chosen ties. The second keeps overlap-targeted verification but replaces our model with independent edge noise. Beating the independent-edge planner means a statistically reliable gain in true spread, as a fraction of the ceiling, at matched budgets once bias is moderate or strong. It also requires no loss when bias is zero.

Why not just…?

Why not just model uncertainty with independent edge probabilities, as PSINET does? This is the real threat. If reporting bias is weak or mostly edge-level, our model reduces to that baseline and adds only fitting cost. The bias-strength sweep settles it. We predict equality at zero bias. As prestige inflation grows, we predict the independent planner will over-select heavily named people, and that the true overlap among its seeds will exceed its own estimate. We will measure both quantities directly.

Why not just symmetrize the reports, keeping a tie if either person names it (union) or only if both do (intersection)? Both are free and common. The union rule adopts every inflated tie, and the intersection rule deletes every tie one side withholds. Neither can shift the balance between the two errors across different people. We include both rules as baselines. We expect the union rule to fail under inflation and the intersection rule to fail under withholding, while our model tracks the better of the two in each regime.

Why not just use coarse structure, since Brown et al. show macro-level targeting is near-optimal? Brown et al. prove that knowledge of the degree distribution and communities suffices on large random graphs when people's actions reinforce each other. Our networks have 150 to 350 nodes and spread by independent cascades, one of the social-contagion models defined by Kempe et al., so their concentration argument may not apply. Community-level seeding is our ARISEN-style baseline. If it matches our method, we will report that fine-grained bias modeling is unnecessary at this scale.

Why not just verify more ties, or survey everyone? Wilder et al. argue that complete mapping of hidden populations is impractical, and PSINET notes that interviews stay vague even when conducted. We plot spread against verification budget for random and targeted verification. This shows how many random checks it takes to match targeted verification.

Proposed Experiments

Ground truth is the central difficulty, so the main study is semi-synthetic. We take the My Friend's Place homeless-youth networks (about 150 to 160 nodes), the Indian village household networks (250 to 350 nodes), Netscience (1,461 nodes), and synthetic community-structured graphs, both Stochastic Block Models and Block Two-Level Erdős–Rényi graphs with heavy-tailed degrees. We treat each observed graph as the truth and generate directed reports from it under three bias families, alone and combined, at graded strengths: person-level recall loss, prestige inflation proportional to degree, and withholding of a designated tie class that preferentially removes between-community bridges.

Outcomes are measured on the true graph. The primary metric is expected independent-cascade spread as a fraction of the full-knowledge greedy ceiling. Diagnostics are the gap between each method's estimated and true overlap among its chosen seeds, the share of the seed budget spent on top-decile-degree people, and the calibration of posterior edge probabilities on held-out true ties.

Four decisive checks follow. First, at zero bias our method must match the independent-edge planner. Second, under prestige inflation the independent planner's underestimate of overlap among its own seeds should grow with bias strength, and our method should close most of that gap. Third, the two ablations should show which ingredient matters. If the independent-noise model with targeted verification does as well as the full method, the reporting model is not earning its keep. If our model with random verification does as well, the targeted verification policy is not. Fourth, we will vary the verified-subset size to find the point at which recall and inflation become separable.

On the real My Friend's Place data, we hold out a fraction of the verified solid edges as a partial check. Methods are compared by likelihood of the held-out ties and by how their seed choices shift. Because the true graph is unknown there, we treat this as evidence of plausibility, not as ground truth.