Discovery of black holes in complex networks

1.820 381


Abstract. Networks are vital in today's world. Design and configuration of networks have made the special considerations necessary for its various aspects such as security, integrity, scalability and cost. Malicious nodes on the network must be identified to enhance the resistance of network. Thus, detection of malicious nodes is critical in the networks .The concepts are presented in this article such as cross talking and black holes and studied networks are under the influence of random and targeted attacks. Also some algorithms have been developed to assess the vulnerability value and networks analysis against random and targeted failures in terms of establishment and detection of black holes and measurement of cross talking value in order to analyze the complex networks by help of above mentioned   implications. The proposed strategies will allow us to design the networks and to reduce the threshold to secure them for all modes of problems (targeted and random).


computer networks, complex networks, cross talking, black hole, failure rate

Full Text:



C. Cooper, R. Klasing, and T. Radzik, "Locating and Repairing Faults in a Network with Mobile Agents," Theoretical Computer Science, vol. 411, no. 14, pp. 1638-1647, 2010.

J. Chalopin, S. Das, A. Labourel, and E. Markou, "Black Hole Search with Finite Automata Scattered in a Synchronous Tours," In Distributed Computing, Springer Berlin Heidelberg, pp. 432-446, 2011.

J. Chalopin, S. Das, A. Labourel, and E. Markou, "Tight Bounds for Scattered Black Hole Search in a Ring," Structural Information and Communication Complexity. Springer Berlin Heidelberg, pp. 186-197, 2011.

S. Dobrev, P. Flocchini, G. Prencipe, and N. Santoro, "Searching For a Black Hole in Arbitrary Networks: Optimal Mobile Agent Protocols," in: Proceedings of the twenty-first annual symposium on Principles of distributed computing. ACM, 2002.

W. Shi, "Black Hole Search with Tokens in Interconnected Networks," Stabilization, Safety, and Security of Distributed Systems. Springer Berlin Heidelberg, pp. 670-682, 2009.

C. Y. Chong, and S. P. Kumar, "Sensor Networks: Evolution, Opportunities, and Challenges," in: proceedings of IEEE, vol. 91, no. 8, pp. 1247-1256, 2003.

A. Cerpa, and D. Estrin, "ASCENT: Adaptive Self-configuring Sensor Networks Topologies," mobile computing, IEEE transactions on, vol.3, no. 3, pp.272-285, 2004.

J. Kleinberg, "Detecting a Network Failure," Internet Mathematics, vol. 1, no. 1, pp. 37-55, 2004.

N. Shrivastava, S. Suri, and C. D. Tpth, "Detecting Cuts in Sensor Networks," ACM Transactions on Sensor Networks, vol. 4, no. 2, pp. 1-25, 2008.

H. Ritter, R. Winter, and J. Schiller, "A Partition Detection System for Mobile Ad-hoc Networks," in: Proceedings of IEEE Conference on Sensor and Ad-hoc Communications and Networks (SECON), pp. 489-497, 2004.

P. Barooah, "Distributed Cut Detection in Sensor Networks," Decision and Control, 2008. CDC 2008. 47th IEEE Conference on. IEEE, pp. 1097-1102, 2008.

M. Won, S. M.George, and R. Stoleru, "Towards Robustness and Energy Efficiency of Cut Detection in Wireless Sensor Networks," Ad Hoc Networks, vol. 9, no. 3, pp. 249-264, 2010.

L. Chun-Ping, L. Yu-Rong, H. Da-Ren, and Z. Lu-Jin," A Formula of Average Path Length for Unweighted Networks," Communications in Theoretical Physics, vol. 50, no. 4, 1017, 2008. [14] A. Perisic, and C. T. Bauch, "Social Contact Networks and Disease Eradicability Under Voluntary Vaccination," PLOS Computational Biology, vol. 5, no. 2, e. 1000280, 2009.

P. Crucitti, V. Latora, M. Marchiori, and A. Rapisarda, "Efficiency of Scale-Free Networks: Error and Attack Tolerance," Phys. A, Statistical Mechanics and its Applications, vol. 320, pp.622-642, 2008.

I. Simonsen, L. Buzna, K. Peters, S. Bornholdt, and D. Helbing, "Dynamic Effects Increasing Network Vulnerability to Cascading Failures," Phys. Rev. Lett, vol. 63, no. 3, pp. 283-420, 2008.

D. Centola, "Failure in Complex Social Networks," Journal of Mathematical Sociology, vol. 33, no. 1, pp. 64-68, 2008.

S. Dobrev, N. Santoro, and W. Shi, "Scattered Mobile Agents Searchin for a Black Hole in an Unoriented Ring Using Tokens," International Journal of Foundations of Computer Science, vol. 19, no. 6, pp. 1355-1372, 2008.

P. Flocchini, D. Ilcinkas, and N. Santoro, "Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pure Tokens," In Distributed Computing. Springer Berlin Heidelberg, pp. 227-241, 2008.

D. Centola, "Failure In Complex Social Networks," Journal of mathematical sociology, vol. 33, no.1, pp. 64-68, 2008.

J. Wu, H. Z. Deng, Y. J. Tan, and D. Z. Zhu, "Vulnrability of Complex Networks Under Intentional Attack With Incomplete Information," Phys. A, vol. 40, no. 11, pp. 2665-2671, 2007.