NS Seminar: Paper Presentation

Date and Location

Nov 07, 2016 - 2:00pm to 3:00pm
Network Science Lab, Bldg 434, Room 122


Isaac Mackey, Computer Science Trainee
Rachel Redberg, Computer Science Trainee


In today's seminar, Isaac and Rachel will each present one of the following papers:

Resisting structural re-identification in anonymized social networks

Michael Hay, Gerome Miklau, David Jensen, Don Towsley, Chao Li

We identify privacy risks associated with releasing network datasets and provide an algorithm that mitigates those risks. A network dataset is a graph representing entities connected by edges representing relations such as friendship, communication or shared activity. Maintaining privacy when publishing a network dataset is uniquely challenging because an individual’s network context can be used to identify them even if other identifying information is removed. In this paper, we introduce a parameterized model of structural knowledge available to the adversary and quantify the success of attacks on individuals in anonymized networks.We show that the risks of these attacks vary based on network structure and size and provide theoretical results that explain the anonymity risk in random networks.We then propose a novel approach to anonymizing network data that models aggregate network structure and allows analysis to be performed by sampling from the model. The approach guarantees anonymity for entities in the network while allowing accurate estimates of a variety of network measures with relatively little bias.


Competing Memes Propagation on Networks: A Case Study of Composite Networks

Xuetao Wei, Nicholas Valler, B. Aditya Prakashy, Iulian Neamtiu, Michalis Faloutsos, and Christos Faloutsosz

If a false rumor propagates via Twitter, while the truth propagates between friends in Facebook, which one will prevail? This question captures the essence of the problem we address here. We study the intertwined propagation of two competing "memes" (or viruses, rumors, products etc.) in a composite network. A key novelty is the use of a composite network, which in its simplest model is defined as a single set of nodes with two distinct types of edges interconnecting them. Each meme spreads across the composite network in accordance to an SIS-like propagation model (a u-like infection-recovery). To study the epidemic behavior of our system, we formulate it as a non-linear dynamic system (NLDS). We develop a metric for each meme that is based on the eigenvalue of an appropriately constructed matrix and argue that this metric plays a key role in determining the "winning" meme. First, we prove that our metric determines the tipping point at which both memes become extinct eventually. Second, we conjecture that the meme with the strongest metric will most likely prevail over the other, and we show evidence of that via simulations in both real and synthetic composite networks. Our work is among the first to study the interplay between two competing memes in composite networks.