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 and 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.

[2]

Y. Bar-Yam, Dynamics of Complex Systems, $1^{st}$ Edition, Addison-Wesley, Boston, 1997.

[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.

[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.

[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.

[6]

V. Chapela, Tips for Managing Intentional Risk, ISACA, 2011. Available from: http://www.isaca.org/About-ISACA/-ISACA-Newsletter/.

[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.

[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.

[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.

[10]

M. E. J. Newman, The structure and function of complex networks, SIAM Review, 45 (2003), 167-256. doi: 10.1137/S003614450342480.

[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.

[12]

S. H. Strogatz, Exploring complex networks, Nature, 410 (2001), 268-276.

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.

[2]

Y. Bar-Yam, Dynamics of Complex Systems, $1^{st}$ Edition, Addison-Wesley, Boston, 1997.

[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.

[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.

[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.

[6]

V. Chapela, Tips for Managing Intentional Risk, ISACA, 2011. Available from: http://www.isaca.org/About-ISACA/-ISACA-Newsletter/.

[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.

[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.

[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.

[10]

M. E. J. Newman, The structure and function of complex networks, SIAM Review, 45 (2003), 167-256. doi: 10.1137/S003614450342480.

[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.

[12]

S. H. Strogatz, Exploring complex networks, Nature, 410 (2001), 268-276.

[1]

Guillaume Cantin, Alexandre Thorel. On a generalized diffusion problem: A complex network approach. Discrete and Continuous Dynamical Systems - B, 2022, 27 (4) : 2345-2365. 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 and 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 and 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 and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1385-1398. doi: 10.3934/dcdss.2019095

[6]

François Monard, Guillaume Bal. Inverse diffusion problems with redundant internal information. Inverse Problems and Imaging, 2012, 6 (2) : 289-313. doi: 10.3934/ipi.2012.6.289

[7]

Lidong Liu, Fajie Wei, Shenghan Zhou. Major project risk assessment method based on BP neural network. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1053-1064. doi: 10.3934/dcdss.2019072

[8]

Philippe Michel, Suman Kumar Tumuluri. A note on a neuron network model with diffusion. Discrete and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 795-809. doi: 10.3934/dcdss.2019053

2020 Impact Factor: 1.213

Metrics

  • PDF downloads (81)
  • HTML views (0)
  • Cited by (3)

[Back to Top]