Research

Random structures often present a trade-off between realism and tractability, the latter predominantly enabled by independence. In pioneering random graph theory, Erdos and Renyi originally studied the set of all graphs with a given number of edges, seeking to identify its typical properties under the uniform measure, i.e., the model of random graphs. However, this approach quickly presents major challenges, most notably the lack of independence, leading to the approximation of the model by the model, wherein edges appear independently with probability . Let be the set of all graphs on vertices. In this work we pursue the following question: What are general sufficient conditions for the uniform measure on a set of graphs to be approximable by a product measure?.Read more…

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…

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[Tao-Vu] 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…

The mitigated effectiveness of traditional forms of advertising along with winner-take-all 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 Influence-and-Exploit (IE) marketing strategies. We show that in undirected social networks, revenue maximization is NP-hard 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 polynomial-time 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…