Algorithmic applications to social networks, secretary problems and differential privacy
Citation & Export
Hide
Simple citation
Gupte, Mangesh.
Algorithmic applications to social networks, secretary problems and differential privacy. Retrieved from
https://doi.org/doi:10.7282/T3X929C0Export
Description
TitleAlgorithmic applications to social networks, secretary problems and differential privacy
Date Created2011
Other Date2011-10 (degree)
Extentxii, 117 p. : ill.
DescriptionThis dissertation is a study in the applications of algorithmic techniques to four specific problems in the domains of social networks, online algorithms and differential privacy. We start by looking at the structure of directed networks. In [Gupte, Shankar, Li, Muthukrishnan, and Iftode, 2011] we define a measure of hierarchy in directed online social networks, and using primal-dual techniques, present an efficient algorithm to compute this measure. Our experiments on different 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 specific 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-off between utility to information consumers and privacy of the database participants. Differential privacy [Dwork, McSherry, Nissim, and Smith, 2006] is a well-established definition 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 fixed 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.
NotePh.D.
NoteIncludes bibliographical references
Noteby Mangesh Gupte
Genretheses, ETD doctoral
Languageeng
CollectionGraduate School - New Brunswick Electronic Theses and Dissertations
Organization NameRutgers, The State University of New Jersey
RightsThe author owns the copyright to this work.
Statistical Profile