A Survey of Models and Algorithms for Social Influence Analysis
Published 1 January 2011
Jimeng Sun, Jie Tang
Citations198
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This chapter surveys the research on social influence analysis with a focus on the computational aspects, and presents the researchOn social influence maximization which has many practical applications including marketing and advertisement.
Abstract
Social influence is the behavioral change of a person because of the perceived relationship with other people, organizations and society in general. Social influence has been a widely accepted phenomenon in social networks for decades. Many applications have been built based around the implicit notation of social influence between people, such as marketing, advertisement and recommendations. With the exponential growth of online social network services such as Facebook and Twitter, social influence can for the first time be measured over a large population. In this chapter, we survey the research on social influence analysis with a focus on the computational aspects. First, we present statistical measurements related to social influence. Second, we describe the literature on social similarity and influences. Third, we present the research on social influence maximization which has many practical applications including marketing and advertisement.
Keywords
Social SciencesPhysics and Astronomy
NatureCollective dynamics of ‘small-world’ networks
43,160 Citations1998Duncan J. Watts, Steven H. Strogatz
Simple models of networks that can be tuned through this middle ground: regular networks ‘rewired’ to introduce increasing amounts of disorder are explored, finding that these systems can be highly clustered, like regular lattices, yet have small characteristic path lengths, like random graphs.
American Journal of SociologyEconomic Action and Social Structure: The Problem of Embeddedness
28,211 Citations1985Mark Granovetter
Annual Review of SociologyBirds of a Feather: Homophily in Social Networks
18,576 Citations2001Miller McPherson, Lynn Smith‐Lovin +1 more
Social NetworksCentrality in social networks conceptual clarification
16,883 Citations1978Linton C. Freeman
Three distinct intuitive conceptions of centrality are uncovered and existing measures are refined to embody these conceptions, one absolute and one relative measure of the centrality of positions in a network and one reflecting the degree of centralization of the entire network.
Proceedings of the National Academy of SciencesCommunity structure in social and biological networks
15,656 Citations2002Michelle Girvan, M. E. J. Newman
This article proposes a method for detecting communities, built around the idea of using centrality indices to find community boundaries, and tests it on computer-generated and real-world graphs whose community structure is already known and finds that the method detects this known structure with high sensitivity and reliability.
SociometryA Set of Measures of Centrality Based on Betweenness
10,249 Citations1977Linton C. Freeman
A family of new measures of point and graph centrality based on early intuitions of Bavelas (1948) is introduced, used to index centrality in any large or small network of symmetrical relations, whether connected or unconnected.
Maximizing the spread of influence through a social network
7,314 Citations2003David Kempe, Jon Kleinberg +1 more
An analysis framework based on submodular functions shows that a natural greedy strategy obtains a solution that is provably within 63% of optimal for several classes of models, and suggests a general approach for reasoning about the performance guarantees of algorithms for these types of influence problems in social networks.
Annual Review of PsychologySocial Influence: Compliance and Conformity
5,925 Citations2004Robert B. Cialdini, Noah J. Goldstein
This review covers recent developments in the social influence literature, focusing primarily on compliance and conformity research published between 1997 and 2002, and emphasizes the ways in which these goals interact with external forces to engender social influence processes that are subtle, indirect, and outside of awareness.
American Journal of SociologyPower and Centrality: A Family of Measures
5,205 Citations1987Phillip Bonacich
New England Journal of MedicineThe Spread of Obesity in a Large Social Network over 32 Years
4,982 Citations2007Nicholas A. Christakis, James H. Fowler
Network phenomena appear to be relevant to the biologic and behavioral trait of obesity, and obesity appears to spread through social ties, which has implications for clinical and public health interventions.
Journal of Mathematical SociologyA faster algorithm for betweenness centrality*
4,926 Citations2001Ulrik Brandes
New algorithms for betweenness are introduced in this paper and require O(n + m) space and run in O(nm) and O( nm + n2 log n) time on unweighted and weighted networks, respectively, where m is the number of links.
Mathematical ProgrammingAn analysis of approximations for maximizing submodular set functions—I
4,458 Citations1978George L. Nemhauser, Laurence A. Wolsey +1 more
It is shown that a “greedy” heuristic always produces a solution whose value is at least 1 −[(K − 1/K]K times the optimal value, which can be achieved for eachK and has a limiting value of (e − 1)/e, where e is the base of the natural logarithm.
PsychometrikaA New Status Index Derived from Sociometric Analysis
3,863 Citations1953Leo Katz
A new method of computation which takes into account who chooses as well as how many choose is presented, which introduces the concept of attenuation in influence transmitted through intermediaries.
Journal of Mathematical SociologyFactoring and weighting approaches to status scores and clique identification
3,129 Citations1972Phillip Bonacich
Mining the network value of customers
2,868 Citations2001Pedro Domingos, Matt Richardson
It is proposed to model also the customer's network value: the expected profit from sales to other customers she may influence to buy, the customers those may influence, and so on recursively, taking advantage of the availability of large relevant databases.
Networks, crowds, and markets reasoning about a highly connected world
2,749 CitationsDavid Easley, Jon Kleinberg
This introductory book on the new science of networks takes an interdisciplinary approach, using economics, sociology, computing, information science and applied mathematics to address fundamental questions about the links that connect us, and the ways that the authors' decisions can have consequences for others.
Management ScienceA New Product Growth for Model Consumer Durables
2,455 Citations2004Frank M. Bass
A growth model for the timing of initial purchase of new products is developed and tested empirically against data for eleven consumer durables, and a long-range forecast is developed for the sales of color television sets.
Cost-effective outbreak detection in networks
2,446 Citations2007Jure Leskovec, Andreas Krause +4 more
This work exploits submodularity to develop an efficient algorithm that scales to large problems, achieving near optimal placements, while being 700 times faster than a simple greedy algorithm and achieving speedups and savings in storage of several orders of magnitude.
Social NetworksA measure of betweenness centrality based on random walks
2,435 Citations2005M. E. J. Newman
A betweenness measure is proposed that relaxes this assumption that information spreads only along those shortest paths, including contributions from essentially all paths between nodes, not just the shortest, although it still gives more weight to short paths.
New England Journal of MedicineThe Collective Dynamics of Smoking in a Large Social Network
2,401 Citations2008Nicholas A. Christakis, James H. Fowler
Despite the decrease in smoking in the overall population, the size of the clusters of smokers remained the same across time, suggesting that whole groups of people were quitting in concert.
Journal of Consumer ResearchSocial Ties and Word-of-Mouth Referral Behavior
2,366 Citations1987Jacqueline Johnson Brown, Peter H. Reingen
Efficient influence maximization in social networks
2,123 Citations2009Wei Chen, Yajun Wang +1 more
Based on the results, it is believed that fine-tuned heuristics may provide truly scalable solutions to the influence maximization problem with satisfying influence spread and blazingly fast running time.
New Product Diffusion Models in Marketing: A Review and Directions for Research
2,117 Citations1991Vijay Mahajan, Eitan Muller +1 more
The diffusion of an innovation traditionally has been defined as the process by which that innovation iscommunicated through certain channels over time among the members of a social system.
Marketing LettersTalk of the Network: A Complex Systems Look at the Underlying Process of Word-of-Mouth
1,995 Citations2001Jacob Goldenberg, Barak Libai +1 more
The results clearly indicate that information dissemination is dominated by both weak and strong w-o-m, rather than by advertising, which means that strong and weak ties become the main forces propelling growth.
BMJDynamic spread of happiness in a large social network: longitudinal analysis over 20 years in the Framingham Heart Study
1,943 Citations2008James H. Fowler, Nicholas A. Christakis
People’s happiness depends on the happiness of others with whom they are connected, providing further justification for seeing happiness, like health, as a collective phenomenon.
Scalable influence maximization for prevalent viral marketing in large-scale social networks
1,716 Citations2010Wei Chen, Chi Wang +1 more
The results from extensive simulations demonstrate that the proposed algorithm is currently the best scalable solution to the influence maximization problem and significantly outperforms all other scalable heuristics to as much as 100%--260% increase in influence spread.
Social NetworksA Graph-theoretic perspective on centrality
1,642 Citations2006Stephen P. Borgatti, Martin G. Everett
This paper develops a unified framework for the measurement of centrality and shows centrality to be intimately connected with the cohesive subgroup structure of a network.
Mining knowledge-sharing sites for viral marketing
1,635 Citations2002Matthew Richardson, Pedro Domingos
This research optimize the amount of marketing funds spent on each customer, rather than just making a binary decision on whether to market to him, and takes into account the fact that knowledge of the network is partial, and that gathering that knowledge can itself have a cost.
Proceedings of the National Academy of SciencesDistinguishing influence-based contagion from homophily-driven diffusion in dynamic networks
1,235 Citations2009Sinan Aral, Lev Muchnik +1 more
A dynamic matched sample estimation framework is developed to distinguish influence and homophily effects in dynamic networks, and this framework is applied to a global instant messaging network of 27.4 million users, finding that previous methods overestimate peer influence in product adoption decisions in this network by 300–700%, and thathomophily explains >50% of the perceived behavioral contagion.
Learning influence probabilities in social networks
1,011 Citations2010Amit Goyal, Francesco Bonchi +1 more
This paper proposes models and algorithms for learning the model parameters and for testing the learned models to make predictions, and develops techniques for predicting the time by which a user may be expected to perform an action.
Journal of MarketingNew Product Diffusion Models in Marketing: A Review and Directions for Research
917 Citations1990Vijay Mahajan, Eitan Muller +1 more
Social influence analysis in large-scale networks
909 Citations2009Jie Tang, Jimeng Sun +2 more
Topical Affinity Propagation (TAP) is designed with efficient distributed learning algorithms that is implemented and tested under the Map-Reduce framework and can take results of any topic modeling and the existing network structure to perform topic-level influence propagation.
Journal of Personality and Social PsychologyAlone in the crowd: The structure and spread of loneliness in a large social network.
814 Citations2009John T. Cacioppo, James H. Fowler +1 more
Management ScienceExceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
802 Citations1977Gérard Cornuéjols, Marshall L. Fisher +1 more
Relational learning via latent social dimensions
791 Citations2009Lei Tang, Huan Liu
This work proposes to extract latent social dimensions based on network information, and then utilize them as features for discriminative learning, and outperforms representative relational learning methods based on collective inference, especially when few labeled data are available.
Influence and correlation in social networks
684 Citations2008Aris Anagnostopoulos, Ravi Kumar +1 more
Two simple tests are proposed that can identify influence as a source of social correlation when the time series of user actions is available and are applied to real tagging data on Flickr, exhibiting that while there is significant social correlation in tagging behavior on this system, this correlation cannot be attributed to social influence.
Modeling relationship strength in online social networks
664 Citations2010Rongjing Xiang, Jennifer Neville +1 more
This work develops an unsupervised model to estimate relationship strength from interaction activity and user similarity and evaluates it on real-world data from Facebook and LinkedIn, showing that the estimated link weights result in higher autocorrelation and lead to improved classification accuracy.
Data mining for direct marketing: problems and solutions
653 Citations1998Charles X. Ling, LI Cheng-hui
This paper discusses methods of coping with problems during data mining based on the experience on direct-marketing projects using data mining, and suggests a simple yet effective way of evaluating learning methods.
Feedback effects between similarity and social influence in online communities
603 Citations2008David Crandall, Dan Cosley +3 more
Clear feedback effects between the two factors are found, with rising similarity between two individuals serving, in aggregate, as an indicator of future interaction -- but with similarity then continuing to increase steadily, although at a slower rate, for long periods after initial interactions.
Physical Review ENonequilibrium phase transition in the coevolution of networks and opinions
598 Citations2006Petter Holme, M. E. J. Newman
A simple model of the convergence of opinion in social systems, with a single parameter controlling the balance of the two processes, that undergoes a continuous phase transition as this parameter is varied, from a regime in which opinions are arbitrarily diverse to one in which most individuals hold the same opinion.
Annals of Internal MedicineThe Spread of Alcohol Consumption Behavior in a Large Social Network
586 Citations2010J. Niels Rosenquist, Joanne Murabito +2 more
Identifying the influential bloggers in a community
511 Citations2008Nitin Agarwal, Huan Liu +2 more
The challenges of identifying influential bloggers are discussed, what constitutes influential bloggers is investigated, a preliminary model attempting to quantify an influential blogger is presented, and the way for building a robust model that allows for finding various types of the influentials is paved.
ACM SIGKDD Explorations NewsletterDynamic social network analysis using latent space models
440 Citations2005Purnamrita Sarkar, Andrew Moore
This paper generalizes a successful static model of relationships into a dynamic model that accounts for friendships drifting over time and shows how to make it tractable to learn such models from data, even as the number of entities n gets large.
Management ScienceNote—On “Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms”
438 Citations1979Gérard Cornuéjols, Marshall L. Fisher +1 more
In the course of the deliberations of the 1977 Lanchester Prize Committee, Alan J. Goldman brought to the authors' attention an error in the proof of Lemma 1 of their paper, which is true and the original correct, but long and intricate, proof was provided.
Optimal marketing strategies over social networks
384 Citations2008Jason D. Hartline, Vahab Mirrokni +1 more
This work identifies a family of strategies called influence-and-exploit strategies that are based on the following idea: Initially influence the population by giving the item for free to carefully a chosen set of buyers, then extract revenue from the remaining buyers using a 'greedy' pricing strategy.
Social influence and the diffusion of user-created content
308 Citations2009Eytan Bakshy, Brian Karrer +1 more
An empirical study of user-to-user content transfer occurring in the context of a time-evolving social network in Second Life, a massively multiplayer virtual world finds that sharing among friends occurs more rapidly than sharing among strangers, but that content that diffuses primarily through social influence tends to have a more limited audience.
Yes, there is a correlation
293 Citations2008Parag Singla, Matthew Richardson
Data mining techniques are applied to study the relationship that exists between a person's social group and his/her personal behavior for a population of over 10 million people, by turning to online sources of data.
Fast Counting of Triangles in Large Real Networks without Counting: Algorithms and Laws
277 Citations2008Charalampos E. Tsourakakis
Two new power laws (degree-triangle and triangleparticipation laws) with surprising properties are discovered, and the eigentrianglelocal algorithm that gives the count of triangles that contain a desired node is provided.
Scalable learning of collective behavior based on sparse social dimensions
242 Citations2009Lei Tang, Huan Liu
This work proposes an edge-centric clustering scheme to extract sparse social dimensions that can efficiently handle networks of millions of actors while demonstrating comparable prediction performance as other non-scalable methods.
Identifying opinion leaders in the blogosphere
238 Citations2007Xiaodan Song, Yün Chi +2 more
The InfluenceRank algorithm ranks blogs according to not only how important they are as compared to other blogs, but also how novel the information they can contribute to the network.
Randomization tests for distinguishing social influence and homophily effects
230 Citations2010Timothy La Fond, Jennifer Neville
This paper presents a randomization technique for temporal network data where the attributes and links change over time and demonstrates the efficacy of the method on semi-synthetic data and then applies the method to a real-world social networks dataset, showing the impact of both influence and homophily effects.
Discovering leaders from community actions
181 Citations2008Amit Goyal, Francesco Bonchi +1 more
A novel frequent pattern mining approach to discover leaders and tribes in social networks where users perform actions, and considers alternative definitions of leaders based on frequent patterns and develops algorithms for their efficient discovery.
PLoS ONEThe Spread of Sleep Loss Influences Drug Use in Adolescent Social Networks
160 Citations2010Sara C. Mednick, Nicholas A. Christakis +1 more
The results indicate that interventions should focus on healthy sleep to prevent drug use and targeting specific individuals may improve outcomes across the entire social network.
Maryland Shared Open Access Repository (USMAI Consortium)Modeling the Spread of Influence on the Blogosphere
139 Citations2006Akshay Java, Pranam Kolari +2 more
This paper validate the effectiveness of some of the influence models on the blogosphere, and shows how PageRank based heuristics could be used to select an influential set of bloggers such that the authors could maximize the spread of information on theBlogosphere.
Social InfluenceIs it a game? Evidence for social influence in the virtual world
135 Citations2008Paul W. Eastwick, Wendi L. Gardner
Results revealed success for both techniques, suggesting that avatars are sensitive to influence tactics targeting both self‐perception and reciprocity norms, and raising the specter that real‐world racial biases may also emerge in virtual environments.
Audience selection for on-line brand advertising
120 Citations2009Foster Provost, B D'Alessandro +3 more
Evidence that the quasi-social network embeds a true social network is provided, which along with results from social theory offers one explanation for the increase in brand affinity of the selected audiences.
Probabilistic user behavior models
97 Citations2004Eren Manavoglu, D. Pavlov +1 more
It is shown that both maximum entropy and Markov based personal user behavior models are strong predictive models and that maximum entropy based mixture model outperforms Markov mixture models in recognizing complex user behavior patterns.
Preferential behavior in online groups
93 Citations2008Lars Bäckström, Ravi Kumar +3 more
It is shown that users who will go on to become long-lived, highly-engaged users experience significantly better treatment than other users from the moment they join the group, well before there is an opportunity for them to develop a long-standing relationship with members of the group.
Social action tracking via noise tolerant time-varying factor graphs
88 Citations2010Chenhao Tan, Jie Tang +3 more
Experimental results show that the proposed method outperforms several baseline methods for action prediction, and Qualitatively, the model can uncover some interesting patterns of the social dynamics.
User grouping behavior in online forums
86 Citations2009Xiaolin Shi, Jun Zhu +2 more
This paper builds social selection models, Bipartite Markov Random Field (BiMRF), and shows that some features carry supplementary information, and the effectiveness of different features vary in different types of forums.
Estimating campaign benefits and modeling lift
74 Citations1999Gregory Piatetsky-Shapiro, Brij Masand
It is conjecture that lift at T (where T is the target frequency) is usually about sqrt(1/T ) for a good model, and formulae for estimating the entire lift curve and estimating expected profits are presented.
SSRN Electronic JournalAlone in the Crowd: The Structure and Spread of Loneliness in a Large Social Network
46 Citations2008John T. Cacioppo, James H. Fowler +1 more
Network linkage data from the population-based Framingham Heart Study is used to trace the topography of loneliness in people’s social networks and the path through which loneliness spreads through these networks.
Measuring the effects of preprocessing decisions and network forces in dynamic network analysis
42 Citations2009Jerry Scripps, Pang‐Ning Tan +1 more
This paper investigates how different pre-processing decisions and different network forces such as selection and influence affect the modeling of dynamic networks, and demonstrates the effect of attribute drift.
Autocorrelation and Relational Learning: Challenges and Opportunities
25 Citations2004Jennifer Neville, Özgür Şimşek +1 more
An overview of research on autocorrelation in a number of fields with an emphasis on implications for relational learning is provided, and a numberof challenges and opportunities for model learning and inference are outlined.
SSRN Electronic JournalAudience Selection for On-Line Brand Advertising: Privacy-Friendly Social Network Targeting
18 Citations2011Foster Provost, B D'Alessandro +3 more
Social InfluenceTeaching social influence: Demonstrations and exercises from the discipline of social psychology
10 Citations2006Steven M. Elias, Anthony R. Pratkanis