Artykuł w czasopiśmie
Brak miniatury
Licencja
ClosedAccessDostęp zamknięty
 

Attacking Similarity-Based Link Prediction in Social Networks

Uproszczony widok
dc.abstract.enLink prediction is one of the fundamental problems in computational social science. A particularly common means to predict existence of unobserved links is via structural similarity metrics, such as the number of common neighbors; node pairs with higher similarity are thus deemed more likely to be linked. However, a number of applications of link prediction, such as predicting links in gang or terrorist networks, are adversarial, with another party incentivized to minimize its effectiveness by manipulating observed information about the network. We offer a comprehensive algorithmic investigation of the problem of attacking similarity-based link prediction through link deletion, focusing on two broad classes of such approaches, one which uses only local information about target links, and another which uses global network information. While we show several variations of the general problem to be NP-Hard for both local and global metrics, we exhibit a number of well-motivated special cases which are tractable. Additionally, we provide principled and empirically effective algorithms for the intractable cases, in some cases proving worst-case approximation guarantees.
dc.affiliationUniwersytet Warszawski
dc.conference.countryKanada
dc.conference.datefinish2019-05-17
dc.conference.datestart2019-05-13
dc.conference.placeMontreal
dc.conference.seriesInternational Joint Conference on Autonomous Agents and Multiagent Systems (previously the International Conference on Multiagent Systems, ICMAS, changed in 2000)
dc.conference.seriesInternational Joint Conference on Autonomous Agents and Multiagent Systems (previously the International Conference on Multiagent Systems, ICMAS, changed in 2000)
dc.conference.shortcutAAMAS 2019
dc.conference.weblinkhttp://aamas2019.encs.concordia.ca/
dc.contributor.authorVorobeychik, Yevgeniy
dc.contributor.authorZhou, Kai
dc.contributor.authorMichalak, Tomasz
dc.contributor.authorWaniek, Marcin
dc.contributor.authorRahwan, Talal
dc.date.accessioned2024-01-24T16:58:12Z
dc.date.available2024-01-24T16:58:12Z
dc.date.issued2019
dc.description.financeNie dotyczy
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/101283
dc.identifier.weblinkhttps://dl.acm.org/doi/10.5555/3306127.3331707
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.pages305–313
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.titleAttacking Similarity-Based Link Prediction in Social Networks
dc.typeJournalArticle
dspace.entity.typePublication