Social and Information Networks

We are interested in networks arising at the application layer, such as the social networks formed by people communicating and interacting over the physical network. These networks, besides representing interesting objects to study in their own right, provide an opportunity to develop new, valuable communication services. In particular, they can help in filtering, organizing, and searching the growing glut of information facing most users today, and in automating demanding communication tasks.

Social Spam Filtering: TrustMyMail.com

As a first example of a concrete service based on social networks, we have developed and implemented a novel method to defend against the increasing tide of spam email by filtering messages based on the social network connecting users, rather than based on the message content. The underlying hypothesis is that legitimate communication takes place between parties that are close in the social network (even if they are not directly connected). I have developed a prototype system based on this idea (available at www.trustmymail.com), a web-based email service where users are protected against spam through this method, which is used by a growing population of actual users.

In this system, the prior email communications between users of the service and external email addresses are used to infer a social network, which evolves over time. In other words, the social network is transparent, and does not have to be manually built up by users. We can then compute for every new message a trust metric between its sender and its recipient, based on how close they are in the social network. The central research question is what trust metrics provide a good tradeoff between legitimate messages that get blocked (false positives), and spam messages that get through, and that lend themselves to distributed implementation.

Structure and Dynamics of Social Networks

Developing new communications applications driven by social networks, such as the TrustMyMail service, requires an understanding of the structure and of the dynamics of complex networks. We are in the process of building a database of dynamic social networks, e.g., by inferring them from email exchanges in large organizations, with a goal of studying their behavior and of building models. We are particularly interested in network dynamics, i.e., the evolution of the network over time.

Papers:

  • On the Privacy of Anonymized Networks,
    P. Pedarsani and M. Grossglauser, KDD 11, San Diego, August 2011. [pdf]
  • Densification Arising from Sampling Fixed Graphs,
    P. Pedarsani, D. Figueiredo, and M. Grossglauser, ACM SIGMETRICS 2008, Annapolis MD, June 2008. [pdf]

People:

Links:

Student Projects:

  • Please check the LCA Projects page to find more information about semester and master projects in this area.