ML p(r)ior | Optimal De-Anonymization in Random Graphs with Community Structure

Optimal De-Anonymization in Random Graphs with Community Structure

2016-02-03
1602.01409 | cs.SI
Anonymized social network graphs published for academic or advertisement purposes are subject to de-anonymization attacks by leveraging side information in the form of a second, public social network graph correlated with the anonymized graph. This is because the two are from the same underlying graph of true social relationships. In this paper, we (i) characterize the maximum a posteriori (MAP) estimates of user identities for the anonymized graph and (ii) provide sufficient conditions for successful de-anonymization for underlying graphs with community structure. Our results generalize prior work that assumed underlying graphs of Erd\H{o}s-R\'enyi type, in addition to proving the optimality of the attack strategy adopted in the prior work.
PDF

Highlights - Most important sentences from the article

Login to like/save this paper, take notes and configure your recommendations

Related Articles

2018-04-24
1804.08796 | stat.ML

Although the computational and statistical trade-off for modeling single graphs, for instance, using… show more
PDF

Highlights - Most important sentences from the article

2018-05-29

Semi-supervised learning on graph structured data has received significant attention with the recent… show more
PDF

Highlights - Most important sentences from the article

2019-05-10

The spread of behavior over social networks depends on the contact structure among individuals, and … show more
PDF

Highlights - Most important sentences from the article

2018-10-02

Modern data analysis pipelines are becoming increasingly complex due to the presence of multi-view i… show more
PDF

Highlights - Most important sentences from the article

2017-03-16

Graphs and network data are ubiquitous across a wide spectrum of scientific and application domains.… show more
PDF

Highlights - Most important sentences from the article

2017-05-05
1705.02294 | math.ST

We consider the problem of graph matchability in non-identically distributed networks. In a general … show more
PDF

Highlights - Most important sentences from the article

2018-12-26

Given a pair of graphs with the same number of vertices, the inexact graph matching problem consists… show more
PDF

Highlights - Most important sentences from the article

2019-04-04

Clustering and community detection with multiple graphs have typically focused on aligned graphs, wh… show more
PDF

Highlights - Most important sentences from the article

2019-04-09

Mining community structures from the complex network is an important problem across a variety of fie… show more
PDF

Highlights - Most important sentences from the article

2017-12-30
1801.00132 | cs.SI

The discovery of community structures in social networks has gained significant attention since it i… show more
PDF

Highlights - Most important sentences from the article

2018-09-23

Community detection in social networks is widely studied because of its importance in uncovering how… show more
PDF

Highlights - Most important sentences from the article

2018-10-31
1810.13347 | cs.CR

In this paper, matching pairs of random graphs under the community structure model is considered. Th… show more
PDF

Highlights - Most important sentences from the article

2018-10-31

Community detection is, at its core, an attempt to attach an interpretable function to an otherwise … show more
PDF

Highlights - Most important sentences from the article

2018-09-07
1809.02630 | cs.LG

Deep generative models have achieved remarkable success in various data domains, including images, t… show more
PDF

Highlights - Most important sentences from the article

2018-06-10
1806.03571 | stat.ML

We consider the problem of model selection in Gaussian Markov fields in the sample deficient scenari… show more
PDF

Highlights - Most important sentences from the article

2014-06-10

This research establishes that many real-world networks exhibit bounded expansion, a strong notion o… show more
PDF

Highlights - Most important sentences from the article