Research
Product Measure Approximations of Symmetric Graph Properties (with Prof. Dimitris Achlioptas)
Robustness and Emergence of Navigability (with Prof. Dimitri Achlioptas)

The Small World Phenomenon (SWP) has inspired researchers ranging from Sociology to Computer Science and Mathematics. An important breakthrough in its understanding was made by Jon Kleinberg through the introduction of the Rank Based Augmentation (RBA) scheme. Kleinberg's work has shown that given an underlying geometry on a set of vertices one can add a random link for each vertex, using an essentially unique probability distribution, such that greedy routing can successfully deliver messages between any two vertices in polylogarithmic number of steps. This property is known as emph{Navigability} of the network. Despite its significance, the RBA scheme seems too ‘‘engineered" to have risen naturally in the world and thus the understanding of the SWP is still incomplete. This raises a series of questions: (i) Under what conditions does RBA emerge from more basic considerations? (ii) How can we resolve the apparent fragility in terms of an essentially unique augmentation scheme? and (iii) When and why do we expect Navigability to have emerged in our history? In this work, we answer the above questions by showing that navigability arises naturally from the interplay of geometry, technology and economic activity.Read more…

Spectrum of Random Graphs with Weak Global Dependencies (with Prof. Andrea Montanari).

Spectral properties of random matrices are important in various fields from Physics, Mathematics to Signal Processing and Computer Science. The typical assumption is that of independent entries (up to a symmetry class) under which the Four Moments Theorem[TaoVu] shows universality of Wigner Semicircle Law. In this work, we consider a model of random graphs (matrices) where a number of small (finite) subgraphs are inserted in an initially empty graph. We show that despite the fact that our model exhibits strong local dependencies the limiting spectral distribution is again the Wigner Law. Our result along with the universality of Wigner law argues against using Spectral Statistics for distinguishing network models. Read more…

Influence and Exploit Strategies for Social Networks (with Prof. Dimitris Fotakis).

The mitigated effectiveness of traditional forms of advertising along with winnertakeall phenomena caused by globalization and the Internet necessitates a new approach in marketing. Hartline et al. (2008) 16 introduced a marketing model for social networks, where a seller is trying to exploit positive externalities between the buyers and to maximize his revenue by designing an intelligent series of individualized offers. Under this setting, we study the problem of revenue maximization and mostly focus on InfluenceandExploit (IE) marketing strategies. We show that in undirected social networks, revenue maximization is NPhard not only when we search for an optimal marketing strategy, but also when we search for the best IE strategy. Rather surprisingly, we observe that allowing IE strategies to offer prices smaller than the myopic price in the exploit step leads to a significant improvement on their performance. Thus, we show that the best IE strategy approximates the maximum revenue within a factor of 0.911 for undirected and of roughly 0.553 for directed social networks. Utilizing a connection between good IE strategies and large cuts in the underlying social network, we obtain polynomialtime algorithms that approximate the revenue of the best IE strategy within a factor of roughly 0.9. Hence, we significantly improve on the best known approximation ratio for revenue maximization to 0.8229 for undirected and to 0.5011 for directed networks (from 23 and 13, respectively). Read more…

