CoVerD: Community-Based Vertex Defense Against Crawling Adversaries

Pegah Hozhabrierdi, Sucheta Soundarajan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The problem of hiding a node inside of a network in the presence of an unauthorized crawler has been shown to be NP-complete. The available heuristics tackle this problem from mainly two perspectives: (1) the local immediate neighborhood of the target node (local perturbation models) and (2) the global structure of the graph (global perturbation models). While the objective of both is similar (i.e., decreasing the centrality of the target node), they vary substantially in their performance and efficiency; the global measures are computationally inefficient in the real-world scenarios, while the local perturbation methods deal with the problem of constrained performance. In this study, we propose a community-based heuristic, CoVerD, that retains both the computational efficiency of local methods and the superior performance of global methods in minimizing the target’s closeness centrality. Our experiments on five real-world networks show a significant increase in performance by using CoVerD against both BFS and DFS crawling attacks. In some instances, our algorithm successfully increased the crawler’s budget by 3 and 10 times compared to the next best-performing benchmark. The results of this study show the importance of the local community structure in preserving the privacy of the nodes in a network, and pave a promising path for designing scalable and effective network protection models.

Original languageEnglish (US)
Title of host publicationComplex Networks and Their Applications X - Proceedings of the 10th International Conference on Complex Networks and Their Applications COMPLEX NETWORKS 2021
EditorsRosa Maria Benito, Chantal Cherifi, Hocine Cherifi, Esteban Moro, Luis M. Rocha, Marta Sales-Pardo
PublisherSpringer Science and Business Media Deutschland GmbH
Pages354-366
Number of pages13
ISBN (Print)9783030934088
DOIs
StatePublished - 2022
Event10th International Conference on Complex Networks and Their Applications, COMPLEX NETWORKS 2021 - Madrid, Spain
Duration: Nov 30 2021Dec 2 2021

Publication series

NameStudies in Computational Intelligence
Volume1015
ISSN (Print)1860-949X
ISSN (Electronic)1860-9503

Conference

Conference10th International Conference on Complex Networks and Their Applications, COMPLEX NETWORKS 2021
Country/TerritorySpain
CityMadrid
Period11/30/2112/2/21

Keywords

  • Closeness centrality
  • Community
  • Crawling
  • Protection

ASJC Scopus subject areas

  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'CoVerD: Community-Based Vertex Defense Against Crawling Adversaries'. Together they form a unique fingerprint.

Cite this