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.

Autorentext

Wei Chen is a Senior Researcher in Microsoft Research Asia, Beijing, China. He is also an Adjunct Professor at Tsinghua University. He received Bachelor and Master of Engineering degrees from Tsinghua University, and a Ph.D. De gree from Cornell University. His research interests include computational and game theoretic aspects of social networks, algorithmic game theory, distributed computing, and fault tolerance. He won the William C. Carter Award in 2000 in the area of dependable computing for his dissertation research on failure de tection, and his co-authored paper on game-theoretic community detection won the best student paper award in ECML PKDD 2009. He has done a series of research work on social influence dynamics, and social influence maximization, which appeared in recent KDD, ICDM, SDM, WSDM, ICWSM, ICML and AAAI conferences. He is also active in the so cial network research community, including organizing an international workshop, guest-editing ACM TKDD special issue oncomputational aspects of social networks, and participating in pro gram committees of KDD, WWW, WSDM, etc. He is a member of Task Force on Big Data of Chinese Computer FederationCarlos Castillo is a Senior Scientist at the Qatar Computing Research Institute in Doha. He received his Ph.D. from the University of Chile (2004), and was a visiting scientist at Universitat Pompeu Fabra (2005) and Sapienza Univer sitá di Roma (2006) before working as a research scientist at Yahoo! Research (2006-2012). He has been influential in the areas of adversarial web search and web content quality and credibility. He has served in the PC or SPC of all ma jor conferences in his area (WWW, WSDM, SIGIR, KDD, CIKM, etc.), and co-organized the Adversarial Information Retrieval Workshop and Web Spam Challenge in 2007 and 2008, the ECML/PKDD Discovery Challenge in 2010 and the Web Quality Workshop from 2011-2013. His current research focuses in the application of web min ing methods to problems in the domainof on-line news and humanitarian crises.