The proliferation of social-networks on the Internet, has allowed companies to collect information about social-network users and their social relationships. Social networks like MySpace, Facebook, and Orkut allow us to determine who is acquainted with whom, how frequently they interact online, what interests they have in common, etc. Users are spending increasing amounts of time on social network websites. For instance, a recent survey [11] that ranks websites based on ‘average time spent by a user’, identifies MySpace and Facebook among the top 10 websites. There have been several efforts to monetize social networks [15, 17]. While most proposals are based on advertising [20], the focus of this paper is to monetize.
