Burning some myths on privacy properties of social networks against active attacks

Serafino Cicerone, Gabriele Di Stefano, Sandi Klavžar, Ismael G. Yero · 2025

Read Burning some myths on privacy properties of social networks against active attacks by Serafino Cicerone, Gabriele Di Stefano, Sandi Klavžar, Ismael G. Yero (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-16944.txt.

Introduction

Serafino Cicerone, Gabriele Di Stefano, Sandi Klavžar, and Ismael Yero push back on the claim that social networks have no privacy, in a 2025 paper. They study active attacks, where an intruder plants accounts to fingerprint a network's users. A formal anonymity measure scores how well a network resists such attacks. The worst possible privacy corresponds to a special family of graphs the authors know well.

Large computational experiments on random graphs show those worst-case graphs are rare. Most networks, the results suggest, resist active fingerprinting better than folklore claims. The paper reframes a debate usually settled by anecdote: privacy in social graphs is a spectrum, and much of it sits far from the worst end.

Catalog record

CREATORSerafino Cicerone, Gabriele Di Stefano, Sandi Klavžar, Ismael G. Yero
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE65 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-16944

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Burning some myths on privacy properties of social networks against active attacks Serafino Cicerone, Gabriele Di Stefano, Sandi Klavžar, Ismael G. Yero Abstract This work focuses on showing some arguments addressed to dismantle the extended idea about that social networks completely lacks of privacy properties. We consider the so-called active attacks to the privacy of social networks and the counterpart ( k , ℓ ) (k,\ell) -anonymity measure, which is used to quantify the privacy satisfied by a social network against active attacks. To this end, we make use of the graph theoretical concept of k k -metric antidimensional graphs for which the case k = 1 k=1 represents those graphs achieving the worst scenario in privacy whilst considering the ( k , ℓ ) (k,\ell) -anonymity measure. As a product of our investigation, we present a large number of computational results stating that social networks might not be as insecure as one often thinks. In particular, we develop a large number of experiments on random graphs which show that the number of 1 1 -metric antidimensional graphs is indeed ridiculously small with respect to the total number of graphs that can be considered. Moreover, we search on several real networks in order to check if they are 1 1 -metric antidimensional, and obtain that none of them are such. Along the way, we show some theoretical studies on the mathematical properties of the k k -metric antidimensional graphs for any suitable k ≥ 1 k\geq 1 . In addition, we also describe some operations on graphs that are 1 1 -metric antidimensional so that they get embedded into another larger graphs that are not such, in order to obscure their privacy properties against active attacks. a Department of Information Engineering, Computer Science, and Mathematics, University of L’Aquila, Italy b Faculty of Mathematics and Physics, University of Ljubljana, Slovenia c Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia d Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia e Departamento de Matemáticas, Universidad de Cádiz, Algeciras Campus, Spain Keywords: k -metric antidimensional graphs; (k,\ell) -anonymity measure; privacy in social networks; k -metric antidimension; random graphs AMS Subj. Class. (2020): 05C12, 05C69, 05C76, 05C82, 05C85 1 Introduction Nowadays, it is a widely accepted fact that social networks usually provide very low privacy features. The data collected in social media platforms is frequently used in ways that their users are unaware of. Third-parties (like advertisers, for instance) use them and, many times, do not care about who has access to them, and moreover, do not know whether they are also shared with malicious entities. Social networks are targets for cyberattacks, and so, some platforms are often compromised, which leads to some information, like private messages, photos, financial data, etc. could be exposed. One reason for this might be that they indeed lack of a clear transparency. That is, many social media analyzers often do not clearly explain or expose their practices with respect to data-sharing, or make this in a confusing manner that users avoid considering or even reading, and so, they give their consent to such companies to manage their data. All these facts have created the “myth” that social networks present very low or even none privacy properties. However, there might be some arguments that could contribute to decrease these extended myths. In this work, we are precisely focused on presenting a few of these arguments, although we do not exactly state that social networks are secure with respect to the privacy they offer. Instead, we claim that they might be not that weak as it is usually understood. A reason for this is that we are considering only one kind of action among all that ones that malicious entities can perform in order to retrieve sensitive information. In fact, there are many different styles of processing a social network so that hidden private information can be exposed. Entities dedicated to such malicious actions (frequently called attackers) might develop numerous attacks to a data set to retrieve some information from it. Among such actions, it is probably the most well-known that one called an active attack. Given a social network, an active attack to its privacy is (roughly speaking) an action that an entity can perform on such a graph to control a set of nodes of it, in order to detect or identify some elements of the graph. While the objectives of such an attacker may vary widely, the successful execution of malicious actions would inevitably compromise the privacy of users. Consequently, the existence of privacy-preserving methods and privacy measures for social networks is critically necessary. The k -antiresolving sets and the k -metric antidimension of graphs were introduced in [ 21 ] as the theoretical basis of the privacy measure (k,\ell) -anonymity for social networks under active attacks to their privacy. There was specifically stated that a given social network G satisfies (k,\ell) -anonymity if k is the smallest integer such that the k -metric antidimension of G is at most \ell . This can be understood as follows. A given user of the social network G has probability 1/k to be identified in such a social network under the assumption that there are \ell attacker nodes in G . The number of attacker nodes \ell in a social network is usually statistically assumed, since it is significantly smaller than the number of users of the network. The privacy measure (k,\ell) -anonymity was indeed the first one of its type, and the first attempt into trying to quantify the privacy features that a social network achieves. Some improved variation of this measure was later on published in [ 13 ] . Formal definitions of the terms above are as follows. Let k\in\mathbb{N} and let G=(V(G),E(G)) be a connected graph. • The metric representation of a vertex x\in V(G) with respect to an ordered set S=\{v_{1},\dots,v_{t}\}\subset V(G) is the vector r(x|S)=(d_{G}(x,v_{1}),\dots,d_{G}(x,v_{t})) , where d_{G}(x,y) stands for the standard shortest-path distance between the two vertices x,y . • A set S\subset V(G) is a k - antiresolving set ( k - ARS for short) for G , if k is the largest integer such that for all u\notin S there exists a set S_{u}\subseteq V\setminus(S\cup\{u\}) with |S_{u}|\geq k-1 and where r(u|S)=r(x|S) for every x\in S_{u} . • The k - metric antidimension of G , denoted {\rm adim}_{k}(G) , is the cardinality of a smallest k -ARS for G . The concepts above can be also understood in the following way. Given a vertex set S\subset V(G) of a graph G , we define the following equivalence relation \mathcal{R}_{S} , where two vertices x,y\in V(G)\setminus S are related by \mathcal{R}_{S} if it follows that r(x|S)=r(y|S) . In this sense, given a set S\subset V(G) , we write \mathcal{Z}_{S}=\{Z^{1},\dots,Z^{r}\} , for some r\geq 1 , as the set of equivalence classes defined by \mathcal{R}_{S} . With such terminology in mind, we observe that an arbitrary set S\subseteq V(G) is a k -ARS of G with k=\min\{|Z^{i}|\,:\,Z^{i}\in\mathcal{Z}_{S}\} . Having the concepts above in mind, it is known that a given social network G achieves (k,\ell) -anonymity against active attacks to its privacy if k is the smallest integer such that {\rm

Read the complete text