Abstract
Service discovery in the Social Internet of Things (SIoT) must be both efficient and trustworthy. Dense device graphs and heterogeneous link reliability make naïve traversal ineffective and risk-prone. We address this by constructing an Individual's Small-World SIoT (ISWSIoT) search space via a trust threshold α and proposing a class- and trust-based informed search algorithm that combines deterministic neighbor ranking, class-aware (friendship) selection, Top-K exploration, a hop bound H, and a selective fallback mechanism. This dual control (α and K) is designed to balance reliability and exploration while bounding search depth. We posit and evaluate four hypotheses: (H1) setting [Formula: see text] improves discovery relative to permissive thresholds; (H2) α-filtering with Top-K reduces exploration cost (visited nodes) while preserving short paths and low latency; (H3) increasing K and H boosts success with only moderate latency overhead; and (H4) fallback restores progress under strict trust filtering with limited cost. Experiments on five real-world graphs perform an SIoT-style α-profiling of success, hops, latency, visited nodes, and LCC ratio. The results show that discovery improves from permissive to moderate α and stabilizes near [Formula: see text]; visited nodes decrease as α rises, while hops remain modest and latency low; larger K and H increase success with moderate latency increases; and fallback recovers discovery when strict α yields few eligible neighbors. Runtime measurements indicate that the proposed method is competitive-often fastest on larger graphs-relative to standard graph searches. Overall, the findings validate the hypotheses and demonstrate that a trust- and class-aware, dual-controlled discovery algorithm provides effective, efficient, and robust service discovery in SIoT.