
Contributions
- A moth-flame optimization algorithm to strategically deploy sparse observers across networks, balancing coverage and redundancy without requiring prior knowledge of propagation models or user attributes.
- Belief functions (from Dempster-Shafer theory) used instead of conventional probabilities to explicitly represent uncertainty and indistinguishability among candidate sources.
- Generalized Bayesian inference to integrate multi-observer evidence with credibility weighting based on observer structural characteristics, mitigating noise and incomplete data.
- Reformulation of source localization as a multi-criteria decision problem, enabling extensible frameworks for incorporating additional information sources and reasoning mechanisms.
Method
EAGLE integrates two main processes: strategic observer deployment and source inference.
Observer Deployment: A moth-flame optimization (MFO) algorithm determines optimal observer placement. The fitness function balances two goals: maximizing coverage (fraction of candidate users with at least one nearby observer) and maintaining redundancy (cross-observability across candidate users). The algorithm is discrete, working directly in the space of user IDs. Population initialization uses degree-based heuristics to seed high-degree nodes, and genetic operators (crossover, mutation) explore the solution space. Saturation constraints prevent local convergence.
Information Collection: Observers deployed in the network record the timing and direction of received information. From these observations, candidate sources (narrowed to users near exposed observers via shortest-path distance) are ranked using pairwise and group likelihood assessments. Pairwise likelihood compares time and path-distance differences between two observers; group likelihood aggregates consensus from multiple observers. Both are weighted by observer credibility: degree-based for pairwise (higher-degree observers more reliable), and adjusted for missing authoritative observers in group assessments.
Source Inference: Observations yield likelihood scores for candidates, cast as belief functions over subsets of candidates. The belief function allows explicit modeling of global ignorance (belief in all candidates) and local ignorance (belief within candidate clusters). A generalized Bayesian inference model recursively combines belief functions from multiple likelihood information sources, weighted by credibility, then extracts the candidate with highest combined belief. Belief degenerates to classical probability when all observers are equally reliable and all candidates distinguishable.
Results
Synthetic network experiments (Barabási-Albert, Erdős-Rényi, Watts-Strogatz, random walk propagation) show EAGLE achieves the lowest error distance across nearly all settings, with stable performance as network density increases. Competing methods (SNF, GE, ESL, DISCE) performance degrades sharply with network size. With 0.5% observer coverage, EAGLE achieves error distance < 1 in small networks and maintains competitive accuracy even in networks of 10,000+ users where competitors' F-scores drop below 0.1.
Real Twitter network results (MoskowAthletics, ~66K users; NYClimateMatch, ~92K users): EAGLE identifies sources even with only 20–120 exposed observers. On reconstructed propagation trees from Twitter data, EAGLE achieves error distances below 2 and identifies potential sources in smaller sets than SNF, GE, or OLS. Against four representative propagation models (heterogeneous SI epidemic, heterogeneous diffusion process, random walk propagation, time-varying network diffusion), EAGLE shows robust performance across varied dynamics, consistently outperforming SOTA baselines.
Notes
Strengths: Clear problem formulation with explicit treatment of real-world constraints (limited observers, heterogeneous reliability, unknown propagation models). Moth-flame optimization and belief functions are well-motivated choices for discrete optimization and uncertainty representation. Comprehensive experiments across synthetic topologies and real Twitter data. Scalable inference reported to work with 100,000+ users and 20–120 observers.
Limitations: Requires observers to report exact timing and direction of received information; deployment cost not modeled, only assumed to scale with observer count. Credibility weighting relies on structural properties (degree, connectivity); observers' actual reliability may vary due to unmodeled factors (temporal heterogeneity in network activity, observer-specific blindspots). Experiments focus on Twitter; applicability to other platforms or offline networks unclear. No discussion of adversarial observers or cost-benefit trade-offs in deployment strategy.
Open questions: Can credibility assessments be learned from data rather than fixed structurally? How sensitive is performance to errors in observer timing reports? Multi-source localization mentioned as future work—how would belief functions scale to competing or correlated sources?