In a social network, nodes correspond topeople or other social entities, and edges correspond to social links between them. In an effort to preserve privacy, the practice of anonymization replaces names with meaningless unique identifiers. We describe a family of attacks such that even from a single anonymized copy of a social network, it is possible for an adversary to learn whether edges exist or not between specific targeted pairs of nodes.

@inproceedings{Backstrom:2007:WAT:1242572.1242598, author = {Backstrom, Lars and Dwork, Cynthia and Kleinberg, Jon}, title = {Wherefore art thou r3579x?: anonymized social networks, hidden patterns, and structural steganography}, booktitle = {Proceedings of the 16th international conference on World Wide Web}, series = {WWW '07}, publisher = {ACM}, address = {New York, NY, USA}, year = {2007}, pages = {181--190}, url = {http://doi.acm.org/10.1145/1242572.1242598}, doi = {10.1145/1242572.1242598}, isbn = {978-1-59593-654-7}, keywords = {anonymizing, networks, social, sna, anonymous, de-anonymizing}, abstract = {In a social network, nodes correspond topeople or other social entities, and edges correspond to social links between them. In an effort to preserve privacy, the practice of anonymization replaces names with meaningless unique identifiers. We describe a family of attacks such that even from a single anonymized copy of a social network, it is possible for an adversary to learn whether edges exist or not between specific targeted pairs of nodes.} }

%0 = inproceedings %A = Backstrom, Lars and Dwork, Cynthia and Kleinberg, Jon %B = Proceedings of the 16th international conference on World Wide Web %C = New York, NY, USA %D = 2007 %I = ACM %T = Wherefore art thou r3579x?: anonymized social networks, hidden patterns, and structural steganography %U = http://doi.acm.org/10.1145/1242572.1242598

We study the structure of the social graph of active Facebook users, the
rgest social network ever analyzed. We compute numerous features of the graph
cluding the number of users and friendships, the degree distribution, path
ngths, clustering, and mixing patterns. Our results center around three main
servations. First, we characterize the global structure of the graph,
termining that the social network is nearly fully connected, with 99.91% of
dividuals belonging to a single large connected component, and we confirm the
ix degrees of separation" phenomenon on a global scale. Second, by studying
e average local clustering coefficient and degeneracy of graph neighborhoods,
show that while the Facebook graph as a whole is clearly sparse, the graph
ighborhoods of users contain surprisingly dense structure. Third, we
aracterize the assortativity patterns present in the graph by studying the
sic demographic and network properties of users. We observe clear degree
sortativity and characterize the extent to which "your friends have more
iends than you". Furthermore, we observe a strong effect of age on friendship
eferences as well as a globally modular community structure driven by
tionality, but we do not find any strong gender homophily. We compare our
sults with those from smaller social networks and find mostly, but not
tirely, agreement on common structural network characteristics.

@misc{ugander2011anatomy, author = {Ugander, Johan and Karrer, Brian and Backstrom, Lars and Marlow, Cameron}, title = {The Anatomy of the Facebook Social Graph}, year = {2011}, note = {cite arxiv:1111.4503Comment: 17 pages, 9 figures, 1 table}, url = {http://arxiv.org/abs/1111.4503}, keywords = {graph, facebook, social, network}, abstract = {We study the structure of the social graph of active Facebook users, thelargest social network ever analyzed. We compute numerous features of the graphincluding the number of users and friendships, the degree distribution, pathlengths, clustering, and mixing patterns. Our results center around three mainobservations. First, we characterize the global structure of the graph,determining that the social network is nearly fully connected, with 99.91% ofindividuals belonging to a single large connected component, and we confirm the"six degrees of separation" phenomenon on a global scale. Second, by studyingthe average local clustering coefficient and degeneracy of graph neighborhoods,we show that while the Facebook graph as a whole is clearly sparse, the graphneighborhoods of users contain surprisingly dense structure. Third, wecharacterize the assortativity patterns present in the graph by studying thebasic demographic and network properties of users. We observe clear degreeassortativity and characterize the extent to which "your friends have morefriends than you". Furthermore, we observe a strong effect of age on friendshippreferences as well as a globally modular community structure driven bynationality, but we do not find any strong gender homophily. We compare ourresults with those from smaller social networks and find mostly, but notentirely, agreement on common structural network characteristics.} }

%0 = misc %A = Ugander, Johan and Karrer, Brian and Backstrom, Lars and Marlow, Cameron %B = } %C = %D = 2011 %I = %T = The Anatomy of the Facebook Social Graph} %U = http://arxiv.org/abs/1111.4503

Predicting the occurrence of links is a fundamental problem in networks. In the link prediction problem we are given a snapshot of a network and would like to infer which interactions among existing members are likely to occur in the near future or which existing interactions are we missing. Although this problem has been extensively studied, the challenge of how to effectively combine the information from the network structure with rich node and edge attribute data remains largely open.</p> <p>We develop an algorithm based on <i>Supervised Random Walks</i> that naturally combines the information from the network structure with node and edge level attributes. We achieve this by using these attributes to guide a random walk on the graph. We formulate a supervised learning task where the goal is to learn a function that assigns strengths to edges in the network such that a random walker is more likely to visit the nodes to which new links will be created in the future. We develop an efficient training algorithm to directly learn the edge strength estimation function.</p> <p>Our experiments on the Facebook social graph and large collaboration networks show that our approach outperforms state-of-the-art unsupervised approaches as well as approaches that are based on feature extraction.

@inproceedings{backstrom2011supervised, author = {Backstrom, Lars and Leskovec, Jure}, title = {Supervised random walks: predicting and recommending links in social networks}, booktitle = {Proceedings of the fourth ACM international conference on Web search and data mining}, series = {WSDM '11}, publisher = {ACM}, address = {New York, NY, USA}, year = {2011}, pages = {635--644}, url = {http://doi.acm.org/10.1145/1935826.1935914}, doi = {10.1145/1935826.1935914}, isbn = {978-1-4503-0493-1}, keywords = {walks, recommending, random, supervised, predicting}, abstract = {Predicting the occurrence of links is a fundamental problem in networks. In the link prediction problem we are given a snapshot of a network and would like to infer which interactions among existing members are likely to occur in the near future or which existing interactions are we missing. Although this problem has been extensively studied, the challenge of how to effectively combine the information from the network structure with rich node and edge attribute data remains largely open.</p> <p>We develop an algorithm based on <i>Supervised Random Walks</i> that naturally combines the information from the network structure with node and edge level attributes. We achieve this by using these attributes to guide a random walk on the graph. We formulate a supervised learning task where the goal is to learn a function that assigns strengths to edges in the network such that a random walker is more likely to visit the nodes to which new links will be created in the future. We develop an efficient training algorithm to directly learn the edge strength estimation function.</p> <p>Our experiments on the Facebook social graph and large collaboration networks show that our approach outperforms state-of-the-art unsupervised approaches as well as approaches that are based on feature extraction.} }

%0 = inproceedings %A = Backstrom, Lars and Leskovec, Jure %B = Proceedings of the fourth ACM international conference on Web search and data mining %C = New York, NY, USA %D = 2011 %I = ACM %T = Supervised random walks: predicting and recommending links in social networks %U = http://doi.acm.org/10.1145/1935826.1935914

Tracking new topics, ideas, and "memes" across the Web has been an issue of considerable interest. Recent work has developed methods for tracking topic shifts over long time scales, as well as abrupt spikes in the appearance of particular named entities. However, these approaches are less well suited to the identification of content that spreads widely and then fades over time scales on the order of days - the time scale at which we perceive news and events. We develop a framework for tracking short, distinctive phrases that travel relatively intact through on-line text; developing scalable algorithms for clustering textual variants of such phrases, we identify a broad class of memes that exhibit wide spread and rich variation on a daily basis. As our principal domain of study, we show how such a meme-tracking approach can provide a coherent representation of the news cycle - the daily rhythms in the news media that have long been the subject of qualitative interpretation but have never been captured accurately enough to permit actual quantitative analysis. We tracked 1.6 million mainstream media sites and blogs over a period of three months with the total of 90 million articles and we find a set of novel and persistent temporal patterns in the news cycle. In particular, we observe a typical lag of 2.5 hours between the peaks of attention to a phrase in the news media and in blogs respectively, with divergent behavior around the overall peak and a "heartbeat"-like pattern in the handoff between news and blogs. We also develop and analyze a mathematical model for the kinds of temporal variation that the system exhibits.

@inproceedings{1557077, author = {Leskovec, Jure and Backstrom, Lars and Kleinberg, Jon}, title = {Meme-tracking and the dynamics of the news cycle}, booktitle = {KDD '09: Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining}, publisher = {ACM}, address = {New York, NY, USA}, year = {2009}, pages = {497--506}, url = {http://portal.acm.org/citation.cfm?id=1557077}, doi = {http://doi.acm.org/10.1145/1557019.1557077}, isbn = {978-1-60558-495-9}, keywords = {tracker, tracking, news, blog, memetracker, blogs, folgen, toread}, abstract = {Tracking new topics, ideas, and "memes" across the Web has been an issue of considerable interest. Recent work has developed methods for tracking topic shifts over long time scales, as well as abrupt spikes in the appearance of particular named entities. However, these approaches are less well suited to the identification of content that spreads widely and then fades over time scales on the order of days - the time scale at which we perceive news and events. We develop a framework for tracking short, distinctive phrases that travel relatively intact through on-line text; developing scalable algorithms for clustering textual variants of such phrases, we identify a broad class of memes that exhibit wide spread and rich variation on a daily basis. As our principal domain of study, we show how such a meme-tracking approach can provide a coherent representation of the news cycle - the daily rhythms in the news media that have long been the subject of qualitative interpretation but have never been captured accurately enough to permit actual quantitative analysis. We tracked 1.6 million mainstream media sites and blogs over a period of three months with the total of 90 million articles and we find a set of novel and persistent temporal patterns in the news cycle. In particular, we observe a typical lag of 2.5 hours between the peaks of attention to a phrase in the news media and in blogs respectively, with divergent behavior around the overall peak and a "heartbeat"-like pattern in the handoff between news and blogs. We also develop and analyze a mathematical model for the kinds of temporal variation that the system exhibits.} }

%0 = inproceedings %A = Leskovec, Jure and Backstrom, Lars and Kleinberg, Jon %B = KDD '09: Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining %C = New York, NY, USA %D = 2009 %I = ACM %T = Meme-tracking and the dynamics of the news cycle %U = http://portal.acm.org/citation.cfm?id=1557077

@inproceedings{conf/kdd/BackstromHKL06, author = {Backstrom, Lars and Huttenlocher, Daniel P. and Kleinberg, Jon M. and Lan, Xiangyang}, title = {Group formation in large social networks: membership, growth, and evolution.}, editor = {Eliassi-Rad, Tina and Ungar, Lyle H. and Craven, Mark and Gunopulos, Dimitrios}, booktitle = {KDD}, publisher = {ACM}, year = {2006}, pages = {44-54}, url = {http://dblp.uni-trier.de/db/conf/kdd/kdd2006.html#BackstromHKL06}, isbn = {1-59593-339-5}, keywords = {evolution, social, community, network, toread} }

%0 = inproceedings %A = Backstrom, Lars and Huttenlocher, Daniel P. and Kleinberg, Jon M. and Lan, Xiangyang %B = KDD %D = 2006 %I = ACM %T = Group formation in large social networks: membership, growth, and evolution. %U = http://dblp.uni-trier.de/db/conf/kdd/kdd2006.html#BackstromHKL06