Nie jesteś zalogowany | zaloguj się

Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego

  • Skala szarości
  • Wysoki kontrast
  • Negatyw
  • Podkreślenie linków
  • Reset

Praca przyjęta na konferencję IEEE

Praca pt. Attacking Similarity-Based Sign Prediction, której autorami są między innymi Michał Godziszewski (doktorant w Instytucie Informatyki MIM UW), Marcin Waniek (absolwent MIM UW, obecnie pracownik naukowy New York University Abu Dhabi), dr Tomasz Michalak (pracownik MIM UW) została przyjęta na konferencję IEEE International Conference on Data Mining (ICDM) 2021 (CORE A*, 200 punktów MNiSW, acceptance rate 20%).

W pracy pt. Attacking Similarity-Based Sign Prediction przedstawiono analizę obliczeniową problemu atakowania algorytmów przewidywania znaków (sign prediction) w sieciach. W problemie tym celem atakującego jest ukrycie przed obrońcą (analitykiem) znaków pewnego docelowego zbioru krawędzi. Atakujący stara się tego dokonać poprzez usunięcie znaków wybranych krawędzi w sieci tak, by obrońcy trudno było przewidzieć znaki połączeń ze zbioru docelowego na podstawie pewnej uprzednio zdefiniowanej miary podobieństwa wierzchołków. W artykule dowiedziono między innymi, że problem ataku jest NP-trudny, bez względu na to, czy do przewidywania znaków stosuje się lokalne, czy globalne miary podobieństwa. W pracy konstrowany jest algorytm heurystyczny dla tego problemu oraz bada się jego skuteczność na kilku rzeczywistych i generowanych sztucznie zestawach danych.