An approach to finding the cost-effective immunization targets for information assurance

Information assurance is increasing in importance as threats abound in the highly connected world of e-business. For enterprises, the goal is to achieve a secure information environment in a cost-effective manner. This paper focuses on the issue of how to cost-effectively immunize an enterprise's network to prevent threats (e.g., virus, rumor) from invading and spreading. An approach, namely Cost-Effective Immunization Targets (CEIT) is proposed as a means to identify the cost-effective immunization targets and provide direct cost/benefit trade-off solutions for practitioners. In the approach, a novel concept, savability, is introduced as an extension of return on security investment (ROSI), with the reduced expected infection probability as mitigated risks through immunization. Meanwhile, a bond percolation process, which can be done in just a single graph traversal, is incorporated to simplify the estimation of expected infection probability in place of repeated diffusion simulations. Theoretical analysis proves that the proposed approach can approximate the optimal solutions within a definite lower bound. Finally, experiments on real-world information network datasets reveal that the algorithm CEIT outperforms other immunization strategies in both homogeneous and heterogeneous cost cases. Further, a case study indicates that the CEIT-identified immunization targets are more likely to 'save' the important nodes with high potential infection loss, avoiding redundant immunization.