TitleAlgorithmic applications to social networks, secretary problems and differential privacy
NameGupte, Mangesh (author), Saks, Michael (chair), Muthukrishnan, S (internal member), Wright, Rebecca (internal member), Mirrokni, Vahab (outside member), Rutgers University, Graduate School - New Brunswick,
Online social networks—Security measures,
DescriptionThis dissertation is a study in the applications of algorithmic techniques to four speciﬁc problems in the domains of social networks, online algorithms and diﬀerential privacy. We start by looking at the structure of directed networks. In [Gupte, Shankar, Li, Muthukrishnan, and Iftode, 2011] we deﬁne a measure of hierarchy in directed online social networks, and using primal-dual techniques, present an eﬃcient algorithm to compute this measure. Our experiments on diﬀerent online social networks show how hierarchy emerges as we increase the size of the network. We study the dynamics of information propagation in online social networks in [Gupte, Hajiaghayi, Han, Iftode, Shankar, and Ursu, 2009]. For a suitable random graph model of a social network, we prove that news propagation follows a threshold phenomenon, hence, high-quality information provably spreads throughout the network assuming users are greedy. Starting from a sample of the Twitter graph, we show through simulations that the threshold phenomenon is exhibited by both the greedy and courteous user models. In chapter 4, we turn our attention from social networks to online algorithms. The speciﬁc problem we tackle is to select a large independent set from a general independence set systems when elements arrive online and we are in the random permutation model. Using a random sampling oracle, we give an algorithm which outputs a set of size Ω(s/ log n log log n) , where s is size of the largest set. This gives a O (log n log log n) approximation algorithm, which matches the lower bound within log log n factors. The last problem we discuss is a scheme for the private release of aggregate information [Gupte and Sundararajan, 2010]. Such a scheme must resolve the trade-oﬀ between utility to information consumers and privacy of the database participants. Diﬀerential privacy [Dwork, McSherry, Nissim, and Smith, 2006] is a well-established deﬁnition of privacy. In this work, we present a universal treatment of utility based on the standard minimax rule from decision theory. Under the assumption of rational behavior, we show that for every ﬁxed count query, a certain geometric mechanism is universally optimal for all minimax information consumers. Additionally, our solution makes it possible to release query results at multiple levels of privacy in a collusion-resistant manner.
NoteIncludes bibliographical references
Noteby Mangesh Gupte
CollectionGraduate School - New Brunswick Electronic Theses and Dissertations
Organization NameRutgers, The State University of New Jersey
RightsThe author owns the copyright to this work.