We investigate the spread of innovations on a social network. The network consists of agents that are exposed to the introduction of a new product. Consumers decide whether or not to buy the product based on their own preferences and the decisions of their neighbors in the social network. We use and extend concepts from the literature on epidemics and herd behavior to study this problem. The central question of this paper is whether firms can learn about the network structure and consumer characteristics when only limited information is available, and use this information to evolve a successful directed-advertising strategy. In order to do so, we extend existing models to allow for heterogeneous agents and both positive and negative externalities. The firm can learn a directed-advertising strategy that takes into account both the topology of the social consumer network and the characteristics of the consumer. Such directed-advertising strategies outperform random advertising.