Attacking Similarity-Based Sign Prediction

Michal Tomasz Godziszewski; Tomasz P. Michalak; Marcin Waniek; Talal Rahwan; Kai Zhou; Yulin Zhu

doi:10.1109/ICDM51629.2021.00173

Attacking Similarity-Based Sign Prediction

Michal Tomasz Godziszewski, Tomasz P. Michalak, Marcin Waniek, Talal Rahwan, Kai Zhou, Yulin Zhu

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

Abstract

In this paper, we present a computational analysis of the problem of attacking sign prediction, whereby the aim of the attacker (a network member) is to hide from the defender (an analyst) the signs of a target set of links by removing the signs of some other, non-target, links. The problem turns out to be NP-hard if either local or global similarity measures are used for sign prediction. We propose a heuristic algorithm and test its effectiveness on several real-life and synthetic datasets.

Original language	English
Title of host publication	Proceedings - 21st IEEE International Conference on Data Mining, ICDM 2021
Editors	James Bailey, Pauli Miettinen, Yun Sing Koh, Dacheng Tao, Xindong Wu
Publisher	IEEE
Pages	1072-1077
Number of pages	6
ISBN (Electronic)	9781665423984
ISBN (Print)	978-1-6654-2398-4
DOIs	https://doi.org/10.1109/ICDM51629.2021.00173
Publication status	Published - Dec 2021

Publication series

Name	Proceedings - IEEE International Conference on Data Mining, ICDM
Volume	2021-December
ISSN (Print)	1550-4786

Keywords

complexity
link prediction
networks
np-hardness
sign prediction
similarity measures

ASJC Scopus subject areas

Engineering(all)

More information

10.1109/ICDM51629.2021.00173

Cite this

Godziszewski, M. T., Michalak, T. P., Waniek, M., Rahwan, T., Zhou, K., & Zhu, Y. (2021). Attacking Similarity-Based Sign Prediction. In J. Bailey, P. Miettinen, Y. S. Koh, D. Tao, & X. Wu (Eds.), Proceedings - 21st IEEE International Conference on Data Mining, ICDM 2021 (pp. 1072-1077). (Proceedings - IEEE International Conference on Data Mining, ICDM; Vol. 2021-December). IEEE. https://doi.org/10.1109/ICDM51629.2021.00173

Godziszewski, Michal Tomasz ; Michalak, Tomasz P. ; Waniek, Marcin et al. / Attacking Similarity-Based Sign Prediction. Proceedings - 21st IEEE International Conference on Data Mining, ICDM 2021. editor / James Bailey ; Pauli Miettinen ; Yun Sing Koh ; Dacheng Tao ; Xindong Wu. IEEE, 2021. pp. 1072-1077 (Proceedings - IEEE International Conference on Data Mining, ICDM).

@inproceedings{4a2c6638e610472f933902d06fc92122,

title = "Attacking Similarity-Based Sign Prediction",

abstract = "In this paper, we present a computational analysis of the problem of attacking sign prediction, whereby the aim of the attacker (a network member) is to hide from the defender (an analyst) the signs of a target set of links by removing the signs of some other, non-target, links. The problem turns out to be NP-hard if either local or global similarity measures are used for sign prediction. We propose a heuristic algorithm and test its effectiveness on several real-life and synthetic datasets.",

keywords = "complexity, link prediction, networks, np-hardness, sign prediction, similarity measures",

author = "Godziszewski, {Michal Tomasz} and Michalak, {Tomasz P.} and Marcin Waniek and Talal Rahwan and Kai Zhou and Yulin Zhu",

note = "Funding Information: ACKNOWLEDGEMENTS Micha{\l} Tomasz Godziszewski and Tomasz Michalak were supported by the Polish National Science Centre grant 2016/23/B/ST6/03599. K. Zhou and Y. Zhu were supported by the PolyU Internal Fund (No. BE3U). Publisher Copyright: {\textcopyright} 2021 IEEE.",

year = "2021",

month = dec,

doi = "10.1109/ICDM51629.2021.00173",

language = "English",

isbn = "978-1-6654-2398-4",

series = "Proceedings - IEEE International Conference on Data Mining, ICDM",

publisher = "IEEE",

pages = "1072--1077",

editor = "James Bailey and Pauli Miettinen and Koh, {Yun Sing} and Dacheng Tao and Xindong Wu",

booktitle = "Proceedings - 21st IEEE International Conference on Data Mining, ICDM 2021",

address = "United States",

}

Godziszewski, MT, Michalak, TP, Waniek, M, Rahwan, T, Zhou, K & Zhu, Y 2021, Attacking Similarity-Based Sign Prediction. in J Bailey, P Miettinen, YS Koh, D Tao & X Wu (eds), Proceedings - 21st IEEE International Conference on Data Mining, ICDM 2021. Proceedings - IEEE International Conference on Data Mining, ICDM, vol. 2021-December, IEEE, pp. 1072-1077. https://doi.org/10.1109/ICDM51629.2021.00173

Attacking Similarity-Based Sign Prediction. / Godziszewski, Michal Tomasz; Michalak, Tomasz P.; Waniek, Marcin et al.

Proceedings - 21st IEEE International Conference on Data Mining, ICDM 2021. ed. / James Bailey; Pauli Miettinen; Yun Sing Koh; Dacheng Tao; Xindong Wu. IEEE, 2021. p. 1072-1077 (Proceedings - IEEE International Conference on Data Mining, ICDM; Vol. 2021-December).

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

TY - GEN

T1 - Attacking Similarity-Based Sign Prediction

AU - Godziszewski, Michal Tomasz

AU - Michalak, Tomasz P.

AU - Waniek, Marcin

AU - Rahwan, Talal

AU - Zhou, Kai

AU - Zhu, Yulin

N1 - Funding Information: ACKNOWLEDGEMENTS Michał Tomasz Godziszewski and Tomasz Michalak were supported by the Polish National Science Centre grant 2016/23/B/ST6/03599. K. Zhou and Y. Zhu were supported by the PolyU Internal Fund (No. BE3U). Publisher Copyright: © 2021 IEEE.

PY - 2021/12

Y1 - 2021/12

N2 - In this paper, we present a computational analysis of the problem of attacking sign prediction, whereby the aim of the attacker (a network member) is to hide from the defender (an analyst) the signs of a target set of links by removing the signs of some other, non-target, links. The problem turns out to be NP-hard if either local or global similarity measures are used for sign prediction. We propose a heuristic algorithm and test its effectiveness on several real-life and synthetic datasets.

AB - In this paper, we present a computational analysis of the problem of attacking sign prediction, whereby the aim of the attacker (a network member) is to hide from the defender (an analyst) the signs of a target set of links by removing the signs of some other, non-target, links. The problem turns out to be NP-hard if either local or global similarity measures are used for sign prediction. We propose a heuristic algorithm and test its effectiveness on several real-life and synthetic datasets.

KW - complexity

KW - link prediction

KW - networks

KW - np-hardness

KW - sign prediction

KW - similarity measures

UR - http://www.scopus.com/inward/record.url?scp=85125187585&partnerID=8YFLogxK

U2 - 10.1109/ICDM51629.2021.00173

DO - 10.1109/ICDM51629.2021.00173

M3 - Conference article published in proceeding or book

SN - 978-1-6654-2398-4

T3 - Proceedings - IEEE International Conference on Data Mining, ICDM

SP - 1072

EP - 1077

BT - Proceedings - 21st IEEE International Conference on Data Mining, ICDM 2021

A2 - Bailey, James

A2 - Miettinen, Pauli

A2 - Koh, Yun Sing

A2 - Tao, Dacheng

A2 - Wu, Xindong

PB - IEEE

ER -

Godziszewski MT, Michalak TP, Waniek M, Rahwan T, Zhou K, Zhu Y. Attacking Similarity-Based Sign Prediction. In Bailey J, Miettinen P, Koh YS, Tao D, Wu X, editors, Proceedings - 21st IEEE International Conference on Data Mining, ICDM 2021. IEEE. 2021. p. 1072-1077. (Proceedings - IEEE International Conference on Data Mining, ICDM). https://doi.org/10.1109/ICDM51629.2021.00173

Attacking Similarity-Based Sign Prediction

Abstract

Publication series

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this