Research on social networks has exploded over the last decade. To a large extent this has been
fueled by the spectacular growth of social media and online social networking sites which
continue growing at a very fast pace as well as by the increasing availability of very large
social network datasets for purposes of research. A rich body of this research has been devoted
to the analysis of the propagation of information influence innovations infections
practices and customs through networks. Can we build models to explain the way these
propagations occur? How can we validate our models against any available real datasets
consisting of a social network and propagation traces that occurred in the past? These are just
some questions studied by researchers in this area. Information propagation models find
applications in viral marketing outbreak detection finding key blog posts to read in order to
catch important stories finding leaders or trendsetters information feed ranking etc. A
number of algorithmic problems arising in these applications have been abstracted and studied
extensively by researchers under the garb of influence maximization. This book starts with a
detailed description of well-established diffusion models including the independent cascade
model and the linear threshold model that have been successful at explaining propagation
phenomena. We describe their properties as well as numerous extensions to them introducing
aspects such as competition budget and time-criticality among many others. We delve deep
into the key problem of influence maximization which selects key individuals to activate in
order to influence a large fraction of a network. Influence maximization in classic diffusion
models including both the independent cascade and the linear threshold models is
computationally intractable more precisely #P-hard and we describe several approximation
algorithms and scalable heuristics that have been proposed in the literature. Finally we also
deal with key issues that need to be tackled in order to turn this research into practice such
as learning the strength with which individuals in a network influence each other as well as
the practical aspects of this research including the availability of datasets and software
tools for facilitating research. We conclude with a discussion of various research problems
that remain open both from a technical perspective and from the viewpoint of transferring the
results of research into industry strength applications.
