Nicole Immorlica

Title: Influence Maximization in Unknown Networks

Abstract:  Social networks are a primary conduit through which individuals exchange information. As such, it is tempting for political and commercial entities to try and leverage these networks to spread information to a large population by influencing a few select individuals. Social workers, wishing to inform a marginalized population about new aid programs, rely on the help of peer leaders to spread the word. Advertisers, running word-of-mouth campaigns, recruit a key set of consumers with special promotions hoping they will influence their friends to buy the product. Influence maximization algorithms identify the most valuable target individuals for such campaigns. However, the most theoretically successful algorithms require detailed knowledge of the underlying social network structure. In many practical applications, the network is unknown. Instead, the algorithm has only limited access to the network structure, either through a local query process or by observing the footprint of prior influence maximization campaigns. We show how to leverage the inherent community structure of social networks to maximize influence even with such limited access to network structure.