In this talk, we examine two distinct problems, distributed search and matching markets with externalities, through the lens of social networks.  In the first, we focus on the problem of distributed search in social networks - forwarding a message using only local contact information.  In order to model networks that are "searchable" by such an algorithm, we construct a generalization of stochastic Kronecker graphs for generating random social networks, introducing a Kronecker-like operator and defining a family of generator matrices dependent on distances between nodes in a specific graph embedding.  Using this model, we highlight a few of our results on the performance of greedy message forwarding algorithms and demonstrate that "distance-dependent Kronecker graphs" can generate searchable networks. <?xml:namespace prefix = o />

In the second problem, we focus on matching markets, such as those used to match medical interns to hospital residencies and assign housing to college students.  Externalities such as complementarities and peer effects can severely complicate the preference ordering of each agent and lead to serious problems for market stability.  We note that peer effects are often the result of underlying social connections, and so we explore a formulation of the market where peer effects are derived from an underlying social network. The key feature of our model is that it captures peer effects and complementarities using utility functions, rather than traditional preference ordering. With this model and considering a slightly different notion of stability, we prove that stable matchings always exist and characterize the set of stable matchings in terms of social welfare.  To characterize the efficiency of matching markets with externalities, we provide "price of stability" and "price of anarchy" bounds and find that the structure of the social network (e.g. how well clustered the network is) plays a large role.  Finally, we demonstrate the performance of two matching algorithms on a real-world matching problem: assigning students to housing at Caltech while incorporating their social network structure.