Abstract
This paper introduces a new optimization problem which aims to develop a distribution plan of vaccines which will be supplied over time such that an epidemic can be best suppressed until a complete cure for it is invented. We first exploit the concept of temporal graph to capture the projected images of the evolving social relations over time and formally define the social-relation-based vaccine distribution planning problem (SVDP\(^2\)) on the temporal graph. Then, we introduce a graph induction technique to merge the subgraphs in the temporal graph into a single directed acyclic graph. Next, we introduce a max-flow algorithm based technique to evaluate the quality of any feasible solution of the problem. Most importantly, we introduce a polynomial time enumeration technique which will be used along with the evaluation technique to produce a best possible solution within polynomial time.
This work was supported in part by US National Science Foundation (NSF) CREST No. HRD-1345219. This research was jointly supported by National Natural Science Foundation of China under grants 11471005.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Zhang, Y., Prakash, B.A.: DAVA: distributing vaccines over networks under prior information. In: SIAM International Conference on Data Mining (SDM 2014), pp. 46–54 (2014)
Hayrapetyan, A., Kempe, D., Pál, M., Svitkina, Z.: Unbalanced graph cuts. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol. 3669, pp. 191–202. Springer, Heidelberg (2005)
Engelberg, R., Könemann, J., Naor, J.: Cut problems in Graphs with a Budget Constraint. Journal of Discrete Algorithms 5(2), 262–279 (2007)
Finbow, S., MacGillivray, G.: The Firefighter Problem: A Survey of Results, Directions and Questions. Australasian Journal of Combinatorics 43, 57–77 (2009)
Anshelevich, E., Chakrabarty, D., Hate, A., Swamy, C.: Approximation algorithms for the firefighter problem: cuts over time and submodularity. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol. 5878, pp. 974–983. Springer, Heidelberg (2009)
Anshelevich, E., Chakrabarty, D., Hate, A., Swamy, C.: Approximability of the Firefighter Problem Computing Cuts over Time. Algorithmica 62, 520–536 (2012)
Wang, N.: Modeling and Analysis of Massive Social Networks, Ph.D. Dissertation (2005)
Bringmann, B., Berlingerio, M., Bonchi, F., Gionis, A.: Learning and Predicting the Evolution of Social Networks. IEEE Intelligent Systems 25(4), 26–35 (2010)
Vinterbo, S.A.: Privacy: A Machine Learning View. IEEE Transactions on Knowledge and Data Engineering 16(8), 939–948 (2004)
Kostakos, V.: Temporal graphs. Physica A: Statistical Mechanics and its Applications 388(6), 1007–1023 (2009)
Anifantis, E., Stai, E., Karyotis, V., Papavassiliou, S.: Exploiting Social Features for Improving Cognitive Radio Infrastructures and Social Services via Combined MRF and Back Pressure Cross-layer Resource Allocation. Computational Social Networks 1(4) (2014)
Lu, Z., Fan, L., Wu, W., Thuraisingham, B., Yang, K.: Efficient Influence Spread Estimation for Influence Maximization under the Linear Threshold Model. Computational Social Networks 1(2) (2014)
Kim, H., Beznosov, K., Yoneki, E.: A Study on the Influential Neighbors to Maximize Information Diffusion in Online Social Networks. Computational Social Network 2(3) (2015)
Ai, C., Zhong, W., Yan, M., Gu, F.: A Partner-matching Framework for Social Activity Communities. Computational Social Networks 1(5) (2014)
Ventresca, M., Aleman, D.: Efficiently Identifying Critical Nodes in Large Complex Networks. Computational Social Networks 2(6) (2015)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Kim, D., Guo, H., Li, Y., Wang, W., Kwon, SS., Tokuta, A.O. (2015). Social Relation Based Long-Term Vaccine Distribution Planning to Suppress Pandemic. In: Thai, M., Nguyen, N., Shen, H. (eds) Computational Social Networks. CSoNet 2015. Lecture Notes in Computer Science(), vol 9197. Springer, Cham. https://doi.org/10.1007/978-3-319-21786-4_3
Download citation
DOI: https://doi.org/10.1007/978-3-319-21786-4_3
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-21785-7
Online ISBN: 978-3-319-21786-4
eBook Packages: Computer ScienceComputer Science (R0)