Efficient Flooding Search: Utilizing K-Scaffold Subgraph
Kun Zhao, Xiaomin Ma, Jun Yang · 2011
Topology structure plays a key role in transmitting information in complex network. Hub-hub structure acts as main communication backbone, which affords fundamental communication service for the connectors around it. In this paper, first, we decompose the random graph into three-tier: hubs layer C, connectors layer N1 and layer N2. C and N1 compose the K-scaffold sub graph. Second, we propose a K-scaffold sub graph based flooding search strategy. Third, we evaluate KBS strategy in simulator based experiment and compare it with BS strategy. The experiment results shows KBS can improve the search success rate by several ten times and decrease workloads by several times.