# American Institute of Mathematical Sciences

March  2015, 10(1): 195-208. doi: 10.3934/nhm.2015.10.195

## Efficient algorithms for estimating loss of information in a complex network: Applications to intentional risk analysis

 1 IT Risk, Fraud and Security, Research and Innovation for IT Risk, Fraud and Security, BBVA, Madrid, Spain 2 Suggestic Inc, Palo Alto, San Francisco Bay Area, California, United States 3 Departamento de Matemática Aplicada, Ciencia e Ingeniería de los Materiales y Tecnología Electrónica, Universidad Rey Juan Carlos, 28933 Móstoles (Madrid), Spain

Received  July 2014 Revised  December 2014 Published  February 2015

In this work we propose a model for the diffusion of information in a complex network. The main assumption of the model is that the information is initially located at certain nodes and then is disseminated, with occasional losses when traversing the edges, to the rest of the network. We present two efficient algorithms, which we called max-path and sum-path, to compute, respectively, lower and upper bounds for the amount of information received at each node. Finally we provide an application of these algorithms to intentional risk analysis.
Citation: Santiago Moral, Victor Chapela, Regino Criado, Ángel Pérez, Miguel Romance. Efficient algorithms for estimating loss of information in a complex network: Applications to intentional risk analysis. Networks & Heterogeneous Media, 2015, 10 (1) : 195-208. doi: 10.3934/nhm.2015.10.195
##### References:
 [1] A. Barrat, M. Barthélemy and A. Vespignani, Dynamical Processes on Complex Networks, $1^{st}$ Edition, Cambridge University Press, New York, 2008. doi: 10.1017/CBO9780511791383.  Google Scholar [2] Y. Bar-Yam, Dynamics of Complex Systems, $1^{st}$ Edition, Addison-Wesley, Boston, 1997.  Google Scholar [3] S. Boccaletti, G. Bianconi , R. Criado, C. I. del Genio, J. Gómez-Gardeñes, M. Romance, I. Sendiña-Nadal, Z. Wang and M. Zanin, The structure and dynamics of multilayer networks, Physics Reports, 544 (2014), 1-122. doi: 10.1016/j.physrep.2014.07.001.  Google Scholar [4] S. Boccaletti, V. Latora, Y. Moreno, M. Chavez and D.-U. Hwang, Complex networks: Structure and dynamics, Physics Reports, 424 (2006), 175-308. doi: 10.1016/j.physrep.2005.10.009.  Google Scholar [5] J. Borondo, F. Borondo, C. Rodriguez-Sickert and C. A. Hidalgo, To each according to its degree: The meritocracy and topocracy of embedded markets, Scientific Reports, 4 (2014), 1-7. doi: 10.1038/srep03784.  Google Scholar [6] V. Chapela, Tips for Managing Intentional Risk, ISACA, 2011. Available from: http://www.isaca.org/About-ISACA/-ISACA-Newsletter/. Google Scholar [7] L. R. Ford and D. R. Fulkerson, Maximal flow through a network, Canadian Journal of Mathematics, 8 (1956), 399-404. doi: 10.4153/CJM-1956-045-5.  Google Scholar [8] Y. Lin, J. C. S. Lui, K. Jung and S. Lim, Modelling multi-state diffusion process in complex networks: Theory and applications, 2013 International Conference on Signal-Image Technology & Internet-Based Systems (SITIS), 2013, 506-513. doi: 10.1109/SITIS.2013.86.  Google Scholar [9] D. López-Pintado, Diffusion in complex social networks, Games and Economic Behavior, 62 (2008), 573-590. doi: 10.1016/j.geb.2007.08.001.  Google Scholar [10] M. E. J. Newman, The structure and function of complex networks, SIAM Review, 45 (2003), 167-256. doi: 10.1137/S003614450342480.  Google Scholar [11] M. Safar, K. Mahdi and S. Torabi, Network robustness and irreversibility of information diffusion in Complex networks, Journal of Computational Science, 2 (2011), 198-206. doi: 10.1016/j.jocs.2011.05.005.  Google Scholar [12] S. H. Strogatz, Exploring complex networks, Nature, 410 (2001), 268-276. Google Scholar

show all references

##### References:
 [1] A. Barrat, M. Barthélemy and A. Vespignani, Dynamical Processes on Complex Networks, $1^{st}$ Edition, Cambridge University Press, New York, 2008. doi: 10.1017/CBO9780511791383.  Google Scholar [2] Y. Bar-Yam, Dynamics of Complex Systems, $1^{st}$ Edition, Addison-Wesley, Boston, 1997.  Google Scholar [3] S. Boccaletti, G. Bianconi , R. Criado, C. I. del Genio, J. Gómez-Gardeñes, M. Romance, I. Sendiña-Nadal, Z. Wang and M. Zanin, The structure and dynamics of multilayer networks, Physics Reports, 544 (2014), 1-122. doi: 10.1016/j.physrep.2014.07.001.  Google Scholar [4] S. Boccaletti, V. Latora, Y. Moreno, M. Chavez and D.-U. Hwang, Complex networks: Structure and dynamics, Physics Reports, 424 (2006), 175-308. doi: 10.1016/j.physrep.2005.10.009.  Google Scholar [5] J. Borondo, F. Borondo, C. Rodriguez-Sickert and C. A. Hidalgo, To each according to its degree: The meritocracy and topocracy of embedded markets, Scientific Reports, 4 (2014), 1-7. doi: 10.1038/srep03784.  Google Scholar [6] V. Chapela, Tips for Managing Intentional Risk, ISACA, 2011. Available from: http://www.isaca.org/About-ISACA/-ISACA-Newsletter/. Google Scholar [7] L. R. Ford and D. R. Fulkerson, Maximal flow through a network, Canadian Journal of Mathematics, 8 (1956), 399-404. doi: 10.4153/CJM-1956-045-5.  Google Scholar [8] Y. Lin, J. C. S. Lui, K. Jung and S. Lim, Modelling multi-state diffusion process in complex networks: Theory and applications, 2013 International Conference on Signal-Image Technology & Internet-Based Systems (SITIS), 2013, 506-513. doi: 10.1109/SITIS.2013.86.  Google Scholar [9] D. López-Pintado, Diffusion in complex social networks, Games and Economic Behavior, 62 (2008), 573-590. doi: 10.1016/j.geb.2007.08.001.  Google Scholar [10] M. E. J. Newman, The structure and function of complex networks, SIAM Review, 45 (2003), 167-256. doi: 10.1137/S003614450342480.  Google Scholar [11] M. Safar, K. Mahdi and S. Torabi, Network robustness and irreversibility of information diffusion in Complex networks, Journal of Computational Science, 2 (2011), 198-206. doi: 10.1016/j.jocs.2011.05.005.  Google Scholar [12] S. H. Strogatz, Exploring complex networks, Nature, 410 (2001), 268-276. Google Scholar
 [1] Guillaume Cantin, Alexandre Thorel. On a generalized diffusion problem: A complex network approach. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021135 [2] David J. Aldous. A stochastic complex network model. Electronic Research Announcements, 2003, 9: 152-161. [3] Vikram Krishnamurthy, William Hoiles. Information diffusion in social sensing. Numerical Algebra, Control & Optimization, 2016, 6 (3) : 365-411. doi: 10.3934/naco.2016017 [4] Mahendra Piraveenan, Mikhail Prokopenko, Albert Y. Zomaya. On congruity of nodes and assortative information content in complex networks. Networks & Heterogeneous Media, 2012, 7 (3) : 441-461. doi: 10.3934/nhm.2012.7.441 [5] Weiping Li, Haiyan Wu, Jie Yang. Intelligent recognition algorithm for social network sensitive information based on classification technology. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1385-1398. doi: 10.3934/dcdss.2019095 [6] Lidong Liu, Fajie Wei, Shenghan Zhou. Major project risk assessment method based on BP neural network. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1053-1064. doi: 10.3934/dcdss.2019072 [7] François Monard, Guillaume Bal. Inverse diffusion problems with redundant internal information. Inverse Problems & Imaging, 2012, 6 (2) : 289-313. doi: 10.3934/ipi.2012.6.289 [8] Philippe Michel, Suman Kumar Tumuluri. A note on a neuron network model with diffusion. Discrete & Continuous Dynamical Systems - B, 2020, 25 (9) : 3659-3676. doi: 10.3934/dcdsb.2020085 [9] Li Gang. An optimization detection algorithm for complex intrusion interference signal in mobile wireless network. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1371-1384. doi: 10.3934/dcdss.2019094 [10] Xianmin Geng, Shengli Zhou, Jiashan Tang, Cong Yang. A sufficient condition for classified networks to possess complex network features. Networks & Heterogeneous Media, 2012, 7 (1) : 59-69. doi: 10.3934/nhm.2012.7.59 [11] Jianfeng Jia, Xuewei Liu, Yixin Zhang, Zhe Li, Yanjie Xu, Jiaqi Yan. Rumor propagation controlling based on finding important nodes in complex network. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2521-2529. doi: 10.3934/jimo.2019067 [12] Jingli Ren, Dandan Zhu, Haiyan Wang. Spreading-vanishing dichotomy in information diffusion in online social networks with intervention. Discrete & Continuous Dynamical Systems - B, 2019, 24 (4) : 1843-1865. doi: 10.3934/dcdsb.2018240 [13] Jan Lorenz, Stefano Battiston. Systemic risk in a network fragility model analyzed with probability density evolution of persistent random walks. Networks & Heterogeneous Media, 2008, 3 (2) : 185-200. doi: 10.3934/nhm.2008.3.185 [14] Reza Lotfi, Yahia Zare Mehrjerdi, Mir Saman Pishvaee, Ahmad Sadeghieh, Gerhard-Wilhelm Weber. A robust optimization model for sustainable and resilient closed-loop supply chain network design considering conditional value at risk. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 221-253. doi: 10.3934/naco.2020023 [15] M. Núñez-López, J. X. Velasco-Hernández, P. A. Marquet. The dynamics of technological change under constraints: Adopters and resources. Discrete & Continuous Dynamical Systems - B, 2014, 19 (10) : 3299-3317. doi: 10.3934/dcdsb.2014.19.3299 [16] Yu-Hao Liang, Wan-Rou Wu, Jonq Juang. Fastest synchronized network and synchrony on the Julia set of complex-valued coupled map lattices. Discrete & Continuous Dynamical Systems - B, 2016, 21 (1) : 173-184. doi: 10.3934/dcdsb.2016.21.173 [17] Hongming Yang, C. Y. Chung, Xiaojiao Tong, Pingping Bing. Research on dynamic equilibrium of power market with complex network constraints based on nonlinear complementarity function. Journal of Industrial & Management Optimization, 2008, 4 (3) : 617-630. doi: 10.3934/jimo.2008.4.617 [18] Rui Hu, Yuan Yuan. Stability, bifurcation analysis in a neural network model with delay and diffusion. Conference Publications, 2009, 2009 (Special) : 367-376. doi: 10.3934/proc.2009.2009.367 [19] Roberta Sirovich, Laura Sacerdote, Alessandro E. P. Villa. Cooperative behavior in a jump diffusion model for a simple network of spiking neurons. Mathematical Biosciences & Engineering, 2014, 11 (2) : 385-401. doi: 10.3934/mbe.2014.11.385 [20] Xuchen Lin, Ting-Jie Lu, Xia Chen. Total factor productivity growth and technological change in the telecommunications industry. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 795-809. doi: 10.3934/dcdss.2019053

2020 Impact Factor: 1.213