Front. Comput. Sci.

, 2012, 6(5): 611–620

DOI 10.1007/s11704-012-1176-1

Social influence and spread dynamics in social networks

Xiaolong ZHENG1 , Yongguang ZHONG2, Daniel ZENG1 , Fei-Yue WANG 1

1 State Key Laboratory of Management and Control for Complex Systems, Institute of Automation, Chinese Academy of
Sciences, Beijing 100190, China
2 Department of Management Science and Engineering, Qingdao University, Qingdao 266071, China


c Higher Education Press and Springer-Verlag Berlin Heidelberg 2012

Abstract Social networks often serve as a critical medium spreading. In these graphs, individuals and their relationships
for information dissemination, diffusion of epidemics, and are represented by the nodes and links of the network, re-
spread of behavior, by shared activities or similarities be- spectively. We can understand the structure and dynamic evo-
tween individuals. Recently, we have witnessed an explosion lution of social systems by analyzing these graphs. In the
of interest in studying social influence and spread dynamics past few years, this field has attracted a great deal of interest
in social networks. To date, relatively little material has been [1–6]. Since social influence and information spread in social
provided on a comprehensive review in this field. This brief systems is easily reproduced in such networks, this field has
survey addresses this issue. We present the current significant been recently addressed in the literature [7–11], as indicated
empirical studies on real social systems, including network by the large and rapidly increasing number of papers devoted
construction methods, measures of network, and newly em- to it.
pirical results. We then provide a concise description of some Traditional research on social influence and spread dy-
related social models from both macro- and micro-level per- namics in social networks has been constrained in accuracy,
spectives. Due to the difficulties in combining real data and breadth, and depth due to its reliance on self-report data
simulation data for verifying and validating real social sys- [12,13]. These studies generally involve both a small num-
tems, we further emphasize the current research results of ber of persons and some static time points. The detailed be-
computational experiments. We hope this paper can provide havior of many physiological and psychological processes is
researchers significant insights into better understanding the still largely unknown [13]. As a result, the analytical results
characteristics of personal influence and spread patterns in have been limited to examining small, well-bounded popula-
large-scale social systems. tions, involving a small number of snapshots of interaction
patterns [14].
Keywords social networks, spread dynamics, social influ-
However, this situation has been changing with the rapid
ence, computational experiment
growth of Web 2.0 and mobile communication technologies.
Recently, a large number of mobile-based applications and
1 Introduction online social systems such as Facebook, Myspace, and Twit-
ter have emerged. In these systems, social relationships be-
Social networks are graphs of people and their relationships, tween users play an important role in dictating their behav-
such as Email communication, scientific collaboration, so- ior. Users can induce their friends to behave in a similar way
cial tagging, diffusion of innovation, and even epidemic explicitly or implicitly via their social influence, e.g., shar-
ing interesting ideas and even rumors. This information can
Received October 19, 2011; accepted February 7, 2012
spread through a network just like an infectious disease. Iden-
E-mail: feiyue.wang@ia.ac.cn tifying social influence and understanding the spread patterns
612 Front. Comput. Sci., 2012, 6(5): 611–620

in social networks are of tremendous interest from an empir- paper and give an outlook over this field.
ical analysis point of view [4,9,12].
Based on these large-scale data sets, researchers have dis-
2 Empirical studies
covered surprising social phenomena including the small-
world effect and scale-free property. These results are differ- Empirical studies can provide critical insight into understand-
ent to classical hypotheses. The tendency to move toward the ing the characteristics of social influence and spread dynam-
formulation of simplified models and their quantitative anal- ics in social networks. However, this is largely an empirical
ysis has been instrumental in this change. The classical mod- matter, requiring network data combined with information
els used by scientists to describe social influence and spread about the attributes of individuals, group affiliations, sharing
dynamics in social networks are considered too simplified to information or ideas and their related activities. In this sec-
describe any real situation [13]. Therefore, a crucial step in tion, we systematically present the methods of existing em-
this perspective is the comparison with empirical data which pirical studies from a network perspective, including network
should be primarily intended as an investigation into whether construction, measures of the network, and some significant
the trends seen in real data are compatible to plausible macro- empirical results that we have obtained from real-world so-
scopic/microscopic models of the networks, and whether they cial systems.
are self-consistent or require additional elements. This has in-
2.1 Network construction
spired scientists in this field to develop new reasonable mod-
els. Most real-world social systems can be represented as so-
Traditionally, researchers validate these models through cial networks with a set of nodes representing individuals
simple simulation. However, simple simulation cannot solve and links the relationships between them. In the classical ap-
all problems due to the complexity of real-world social sys- proach, the method of network construction is very simple.
tems. As such, computational experimentation is now being Nodes in these networks always belong to the same type
applied more often. This emerging approach can be utilized and links are often undirected and unweighted. This will
to deal with validating the complex social systems. not explain certain real-world phenomena very well, since
Despite various reviews on social networks, relatively little significant information is removed in the construction pro-
material has provided a comprehensive survey on the network cess. In the past few years, with the development of the so-
presentation, characteristic measurement, social modeling, cial network research domain, more complex and feasible
and computational experiments for identifying the influence network construction methods have been developed. For in-
between behaviors and spread patterns in large-scale social stance, we can construct social networks in which nodes be-
systems. This brief survey addresses precisely this issue. long to two different types and links are both directed and
The framework of this paper is presented in Table 1. Section weighted [15–18]. In these networks, nodes may represent
2 describes and compares some empirical studies of social people of different genders, occupations, locations, or ages
influence and spread dynamics in social networks, including and links represent different friendships, communications, or
network construction, measures of network, and some signifi- enmities [3,19,20]. One can also construct social networks
cant empirical results. In Section 3, we discuss in detail some with hyperedges [21]: links that join more than two nodes
significant social models in this field from the macro- and together.
micro-level. Section 4 introduces a theoretical framework for According to our investigation, we generally classify ex-
computational experiments. In Section 5, we conclude this isting networks construction methods into five basic classes:
undirected networks, directed networks, weighted networks,
Table 1 The framework of main content in this paper
bipartite graphs, and hypergraphs. These five basic network
Main content Section
construction methods are compared in Table 2.
Introduction Background of this filed 1
Empirical studies Network construction 2.1 Table 2 Five basic network construction methods
Measures of network 2.2 Types of networks Main characteristics
Empirical results 2.3 Undirected network Links are undirected
Social models Macro-level models 3.1 Directed network Links are directed
Micro-level models 3.2 Weighted network Links are weighted
Computational experiments Theoretical framework 4 Bipartite graph Two different types of node
Concluding remarks Conclusions and outlook 5 Hyper-graph Links may join more than two nodes together
 Xiaolong ZHENG et al. Social influence and spread dynamics in social networks 613

2.2 Measures of network E [26], which is defined as

1 
With the rapid development of graph theories, researchers E= 1/di j. (4)
N(N − 1) i j
have developed several important measures of networks to
quantitatively describe the inherent properties of social net- Community structure: a community is also called a group,
works. Examples of these measures include: degree distribu- cluster, cohesive subgroup, or module [27]. The first network
tion, clustering coefficient, shortest path length, and commu- formalizations of this concept were proposed by Wasserman
nity structure. and Faust [28]. This measure attempts to obtain some clusters
Degree and strength distribution: the degree ki of node i is of groups of nodes that have a high density of connections
defined as the number of links incident with i. The strength within the group, and a lower density of connections between
si in a weighted network denotes the sum of weights of the the groups [29]. In real social networks, we do not know the
 number of existing communities. To address this problem,
corresponding links: si = j wi j , where wi j represents the
weight between node i and j. A large number of previous em- many researchers [27,30–34] have developed several useful
pirical results demonstrate that not all nodes in a social net- measures for detecting community structure. These measures
work have the same degree or strength [5,15,22,23]. For an can be utilized to deal with different types of networks such
unweighted network, this difference can be characterized by as heterogeneous networks. The most popular measure, mod-
the degree distribution P(k), which gives the probability that ularity Q, was proposed by Newman and Girvan [30]. In this
a randomly selected node has exactly k edges. For a weighted measure, if we want to divide a network into c communities,
network, we can use the strength distribution P(s) to describe we can calculate Q from the symmetric c × c mixing matrix E
the probability of selecting a node with strength s. whose main diagonal elements eii represent the ratio of links
Clustering coefficient: this is a measure of network tran- between nodes in the same community i while other elements
sitivity, which characterizes the fraction of members in cir- ei j capture the ratio of links between nodes in different com-
cles of friends or acquaintances that an individual knows. Re- munities i and j. The measure can be calculated as follows:
searchers have given several definitions of the clustering co-    2 
Q= eii − ei j = TrE−  E2  . (5)
efficient from different perspectives [1,21,24,25]. The most i j

popular definition of clustering coefficient was developed by Several other measures have also been used, including the
Watts and Strogatz [1]. In this definition, if a node with de- node/edge betweenness (the number of shortest paths going
gree ki is selected randomly in the graph G, then at most through a node/edge) [28,30], motif (a pattern of intercon-
ki (ki − 1)/2 links may exist between them. The clustering co- nections at a number significantly higher than that of random
efficient Ci of node i is computed as follows: graph), and graph spectra (for discovering the presence of co-
Ci = 2Ei /[ki (ki − 1)], (1) hesive subgroups and other local patterns) [29]. These mea-
where Ei is the number of edges that actually exist be- sures can help us to quantify the key influence factors and
tween these ki neighbors of node i. For a weighted network, dynamic patterns in our real-world social systems.
we can use the weighted clustering coefficient proposed by 2.3 Empirical results
Barthélemy et al. [25]. The weighted clustering coefficient
Ciw of node i in a weighted network is defined as Our real-world social systems embody a large number of in-
1  wi j + wik teresting phenomena. Most of them have not been perceived
Ciw = ai j aik a jk . (2) by humans until now. Previous reviews on social networks
si (ki − 1) j,k 2
[28] or diffusion of innovations [35] have given us some
Shortest path length: the shortest path length between node
significant empirical results, including strong/weak ties and
i and j is the shortest of the possible paths connecting nodes
structural holes. However, these results were built on small
i and j. The maximum value of di j is called the diameter of
social networks. Huge real-world social networks, with mil-
the graph. The average shortest path length L of a network is
lions of nodes and links, may exhibit different patterns. In this
defined as the mean of the shortest path lengths over all pairs
subsection, we present and compare significant empirical re-
of nodes [1]
1  sults.
L= di j , (3)
N(N − 1) i j Small-world effect: the small-word effect is characterized
where N is the number of nodes. To avoid the divergence of L, by small average shortest path lengths between pairs of nodes
researchers have proposed an alternative measure: efficiency and relatively high clustering coefficients. The most famous
614 Front. Comput. Sci., 2012, 6(5): 611–620

empirical study on small-world phenomenon was conducted search communities [40]. These studies have determined that
by Milgram [36], who gave us the concept of “six degrees of many real-world social networks exhibit self-similar proper-
separation”. This study concluded that any two randomly se- ties and the community size distribution follows a power-law.
lected persons in the USA are on average separated by only Cascading behavior: cascading behavior is a social phe-
six intermediate individuals. Dodds et al. [37] conducted a nomenon when an idea or action is widely spread and adopted
similar worldwide analysis and found that the diameter of through social influence [53]. This has been studied for many
these social networks ranged from 4 to 7. These studies have years by large number of researchers from several differ-
some limitations: relying much on individual motivation to ent domains [35,54]. A growing number of empirical studies
participate [37] or constraining the networks to a specific dy- suggest that diverse phenomena in physical world, including
namic behavior [38]. To solve this problem, researchers have obesity [55], happiness [56], ideas [57], and many other be-
recently attempted to use massive already-recorded log data haviors and affective states [58,59], can spread from person
sets and conducted significant empirical studies. Research to person. Recently some researchers have conducted many
objects of existing studies include auctions [39], movie actors significant empirical studies in cyberspace. Adar et al. [60]
[1], scientific collaboration [40], citations [41], and commu- and Gruhl et al. [61] extracted cascades in the blogophere
nication [42]. Empirical results have further emphasized that and found that while information propagates between blogs,
the small-world effect characterizes most of our real-world examples of genuine cascading behavior appeared relatively
social systems. rarely. Leskovec et al. [62,63] further analyzed cascades in
Scale-free property: traditional research, until a few years the blogophere and viral marketing. They find some novel
ago, had always considered that almost all nodes were topo- cascading patterns and observed that a cascade on n nodes
logically equivalent: like in regular lattices or in random follows a Zipf distribution: P(n) ∝ n−2 . Anagnostopoulos et
graphs. The distribution of the network is binomial or Poisson al. [64] and Aral et al. [65] analyzed the causes of correlation
at the limit of large graph size. However, recent massive em- in social networks and distinguished influence-based conta-
pirical studies on real-world social networks have shown that gion from homophily-driven diffusion in dynamic networks.
the distribution P(k) of these networks follows a power-law These findings are essential to both our understanding of the
shaped distribution, P(k) ∼ k−α , which significantly deviates mechanisms that drive contagion in networks and our knowl-
from that of traditional research. Examples include: tradi- edge of how to propagate them in diverse domains.
tional epidemic social networks [15], online social networks
[18,43,44], Internet news [45], and mobile communication
networks [46]. This demonstrates that in these networks there 3 Social models
exist a few nodes linking to many other nodes, and a large
number of nodes with poorly connected elements. Empirical findings have initiated a revival of network model-
Community structure: many real-world social networks ing, since the models proposed in mathematical graph theory
also display a strong community structure [27,34,47,48]. have turned out be far from the empirical observations. In past
In these networks, there exists a heterogeneous connecting few decades, social modeling for the process of social influ-
structure, which is mainly characterized by the presence of ence and spread dynamics in social networks has been studied
nodes which are more densely interconnected than the rest of in many areas, such as the spread of epidemics, the diffu-
the network. This community structure reflects in general the sion of technological innovations, and the effect of “word of
self-organization of individuals to achieve some intentions. mouth” in the promotion of new products. A large number
Traditional studies mainly focus on static community detec- of models have been developed. In this section, we classify
tion [34]. However, most real-world social networks tend to these existing models into two types: macro-level models and
evolve gradually, due to frequent changes in the activity and micro-level models. The macro-level models mainly encom-
interaction of their individuals [49]. The communities inside pass SIR (susceptible/infective/removed) model and Bass
a dynamic network may grow or shrink, and the community model, which mainly focus on capturing the spread behav-
membership of the individuals shifts regularly [50]. As such, iors at the population level. The micro-level models aim to
a number of researchers pay more interest to identifying criti- reveal the personal behavior integrating with the topological
cal events that characterize the evolution of communities and structure of social networks. These micro-level models in-
membership of individuals such as author communities in the clude the famous preferential attachment (PA) model, thresh-
blogosphere [51], mobile subscriber networks [52], and re- old model, cascade model, and competitive model. The key
 Xiaolong ZHENG et al. Social influence and spread dynamics in social networks 615

Table 3 Key characteristics and limitations of existing social models

Levels Models Key characteristics Limitations
SIR Dividing populations into three groups These models assume a homogenous mixed population where in-
Macro-level dividuals have equally probability to be influenced by others.
Bass Influence via both mass media and word-of-mouth
PA Preferential attachment
Threshold Node specific threshold These models cannot be evaluated easily. More specific issues
Micro-level such as the influence of correlations and dynamic rewiring
Cascade Adopting probability depends on neighbor influence
should be further considered.
Competitive Influence maximization game

characteristics and limitations of these models are presented bution function, which can be determined by several signifi-
in Table 3. cant parameters [66]. The resulting models are equivalent to
uniform bond percolation on the same network with edge oc-
3.1 Macro-level models cupation probability. We can further define a generation func-
Macro-level models can help us to evaluate the extent of an tion [24] to obtain the distribution of finite outbreak sizes, the
epidemic or information spreading qualitatively at different critical transmittability, and relative final size of an epidemic.
spread phases or across diverse groups. This field in the past Moreno and Vázquez [67] developed networks with corre-
few decades has attracted great attention including epidemi- lations between the degrees of nodes. Ancel et al. [68] and
ologists and economists. Many models have been developed Newman [66,68] introduced networks with different types of
and applied across diverse domains. Most of these interesting nodes. Wang et al. [69] also gave a model to describe the
models are extended or generalized from two basic models: spread behavior with non-uniform transmission. These net-
SIR model and Bass model. In this subsection we mainly fo- work models are not only applied to analyze the spread dy-
cus on these models and present their specific mechanisms. namics of epidemics, but also to study the social influence of
rumors [8,70].
SIR models: the most famous and classical SIR model was
originally developed to describe the spread dynamics of epi- Bass model: Bass model [71] is another classical macro-
demics and is now applied to several domains. This model level mathematical model for the underlying diffusion of in-
divides the population into three groups: susceptible (S ), in- novation in society. The Bass model assumes that potential
fectious (I), and removed (R). S indicates that people who adopters of an innovation are influenced by two means of
are not infected by the virus but can be easily infected. I rep- communication: mass media and word of mouth [72]. As
resents individuals who are infectious and can transmit the such, this model has two key characteristics [72–74]: one
virus to others. R denotes persons in the group who have captures the rate of individuals convinced by mass media (ex-
recovered from the disease or are now dead. This model is ternal influence), and the other describes the ratio by which
based on the hypothesis that any person who belongs to S individuals are influenced by word-of-mouth communication
has the uniform probability β to become infected and infected (internal influence).
people recover and becomes immune at rate γ. In the limit of In the Bass model, at each step t, individuals are convinced
populations, this model is represented by the following dif- by the mass media with probability p and by word-of-mouth
ferential equations: communication by fraction q. If we assume that the ratio of
individuals who will adopt the innovations or ideas is R(t),
ds di dr then the differential equation of this model takes the form
= −βis, = βis − γi, = γi, (6)
dt dt dt
where s(t), i(t), and r(t) are the fractions of individuals in R(t) = R(t − 1) + p(1 − R(t − 1)) + qR(t − 1)[1 − R(t − 1)]. (7)
S , I, R respectively and the sum of s(t), i(t), and r(t) is equal
to 1. In this form, the first term of the right side presents the ra-
The classic SIR model described above assumes that the tio of individuals who have adopted the innovations at time
population is fully mixed and all individuals are in contact t − 1. The second term describes the fraction of people who
with the others and transmit the disease with same probabil- have not yet adopted but have been convinced by the mass
ity. Newman [66] improved on this model and made several media. The third term captures the rate of the imitation pro-
modifications. In Newman’s model, the probability T i j that an cess that innovations spread by word-of-mouth communica-
infected node i transmits the virus to node j follows a distri- tion. The Bass model can also be represented in a continuous
616 Front. Comput. Sci., 2012, 6(5): 611–620

time form the inherent influence behavior between nodes. In this condi-
tion, we should consider another suitable micro-level social
dR(t)/dt = (1 − R(t))[p + qR(t)]. (8) influence and spread models such as the threshold model.
The earliest threshold models were developed by Gra-
Recently, some extensions of the Bass model have been
novetter [79] and Schelling [80] in 1978; they later became
applied in several domains such as pricing and advertising
the foundation for a large body of work in sociology [81–83].
[63,75].
In these models, nodes can be classified into two types: active
3.2 Micro-level models or inactive. An inactive node m is influenced by its neighbor

n with a weight wn,m , where n wn,m  1. Node m selects a
The SIR and Bass models described in Section 3.1 both as- threshold θm on the uniform interval [0, 1]. Given an initial
sume a homogeneous mixing population where individuals set of active nodes, the influence process can be divided into
have equal probability to be influenced by one another. This finite discrete steps: if nodes are active at step t − 1, then
does not accord with many empirical findings in heteroge- they will still remain active at step t; and if the total weight of

neous networks. Based on previous work, researchers have a nodes active neighbors is at least θm : na wna ,m  θm , then
developed some reasonable models at the micro-level aiming node m will be activated.
to describing the key influence factors and spread patterns of In the threshold models described above, different thresh-
each individual. olds θm indicate different potential tendencies of nodes to be
Preferential attachment models: the empirical studies dis- influenced (i.e., accepting a new product or an idea) by their
cussed in Section 2.3 demonstrate that many large networks neighbors. Kempe et al. [84,85] recently introduced a general
are scale-free, that is their degree distribution follows a threshold model. This model focused more on the cumula-
power-law. Previous random graph models cannot reproduce tive effect of a nodes’ influence than that of previous models.
this feature. Barabási and Albert [5] and other researchers Each node in this model has a monotone activation function
[76–78] introduced their networks and later were gener- and a threshold. One node becomes active when the value of
ally called preferential attachment (PA) models due to their the function is no less that the threshold. Easley and Klein-
growth mechanisms of preferential attachment. berg [86] further gave a heterogeneous threshold model. This
The network model developed by Barabási and Albert [5] model starts from a set of initial adopters. At each step, each
(BA model) starts with a fixed number of randomly connected node evaluates its decision according to its own threshold rule
nodes. At each time instant the network grows with the addi- and switches to one behavior if the value is no less than its
tion of new nodes. For each newly added node, new edges threshold. This model can explain the diversity of spread be-
are added between it and some old nodes. The nodes to re- havior in real-world heterogeneous networks.
ceive new edges are chosen following a linear preferential Cascade models: many real-world social systems exhibit
attachment rule, that is, the probability P(k) of an old node cascade behavior. However, previous network models includ-
receiving a new edge is proportional to its degree k, that is, ing PA models and threshold models cannot capture this char-
P(k) ∼ k. Replacing the linear preferential attachment of the acteristic. Due to this, researchers recently have proposed
BA model, Krapivsky, Redner, and Leyvraz [76] use a non- several cascade models. Of these, the independent cascade
linear preferential attachment rule. When choosing the nodes model (ICM) proposed by Goldenberg et al. [87] has been
to which a new node connects, the probability P(k) depends paid more and more attention. In this model, node m first be-
on kα , P(k) ∼ kα . comes active at step t − 1 and has only one chance to activate
Both models discussed above have a common character- its inactive neighbor n with a constant probability pn (m). If
istic: their preferential attachment rules depend only on the m succeeds, n will become active at step t. If multiple neigh-
degree of the old node. However, in applications such as ref- bors of n are active at step t − 1, activation attempts will be
erence networks, aging occurs: the authors rarely cite very executed randomly.
old papers. Dorogovtsev and Mendes [77] proposed an ex- Based on the ICM, Kempe et al. [84,85] further proposed
tended model in which the probability P(k) is dependent not a general cascade model (GCM) and a decreasing cascading
only on the degree k of the old node but also on its age τ, that model (DCM). In the GCM, the probability that node m suc-
is, P(k) ∼ kτ−β , where β is a tunable parameter. ceeds in activating its neighbor n depends the extent of n’s
Threshold models: although they reproduce the scale-free neighbors that have already tried to activate it. Specifically,
property well, the PA models described above cannot reflect given an incremental function pn (m, S ) ∈ [0, 1], where S and
 Xiaolong ZHENG et al. Social influence and spread dynamics in social networks 617

m are disjoint subset of n’s neighbors. m succeeds in acti- [90–92]. Based on this work, Zheng et al. [93] further pro-
vating n with probability pn (m, S ). Due to the phenomena of posed a theoretical framework of computational experiments
“marketing-saturated”, DCM further defines a non-increasing which can be applied in diverse domains such as the science
function pn (m, S ) in S , i.e., pn (m, S )  pn (m, T ) whenever of team science. This framework shown in Fig. 1 mainly en-
S ⊆ T . This condition indicates that node m’s probability of compasses artificial system construction, computational ex-
succeeding in activating node n decreases with the number of periment design, observation and evaluation, and feedback
nodes that have already attempted to activate n. and modification. At the level of artificial systems construc-
Competitive models: following the cascade model [85,87] tion, the fundamental research issues include agent interac-
described above, Bharathi et al. [11] introduced a competitive tions, the construction of interacting environments and rules.
model for the influence maximization game. In this model, At the computational experiment design level, we should be
each edge is allocated an activation probability Pe and each concerned with the specification of objectives, task assign-
node has one of these two states: active or inactive. In the ment, and experimental parameter selection. At the obser-
active state, the node is labeled by a color denoting that it has vation and evaluation level, we should focus on emergence-
been activated. based observation, validation of objectives, and evaluation of
This model is further augmented by adding the information social models. The feedback and modification of solutions for
of activation time for each activation attempt. When node m complex systems from the observation and evaluation levels
becomes active at time t, it will attempt to activate each first- can be used to improve artificial systems.
level inactive neighbor n. If m succeeds in activating n, n will
become active with the same color as m at time t +T mn , where
T mn are independent continuous random variables following
an exponential distribution. Subsequently, the active node n
will attempt to active its first-level inactive neighbors, and so
forth. In this influence maximization game, each player se-
lects a set S i of at most ki nodes. A node selected by multiple
players will be labeled by the color of one of these players.
This process unfolds as described above until no new acti-
vation occurs. Similar models have also been considered re-
cently by Lotker et al. [88] and Dubey et al. [89]. These mod-
els provide specific mechanisms that illustrate how to interact
with each other when multiple objects are competing within Fig. 1 The theoretical framework of computational experiments
a social network.
From an implementation viewpoint, to solve those prob-
lems, such as incomplete or unavailable real-world data [90],
4 Computational experiments we can utilize parallel execution [91], by executing one or
Section 3 above presented several types of social models for more artificial systems running in parallel with a real system
social influence and spread dynamics in social networks. Tra- and employing adaptive control methods for the experiments.
ditionally, researchers validate these models through simple Through comparison, evaluation, and interaction with artifi-
simulation. This method may be valuable and ethical when cial systems, we can provide more perfect strategies for man-
examining policies dealing with matters of life and death, aging the target social systems.
such as in epidemiology and terrorism [90]. However, due
to the difficulties of testing real systems that are inherently
5 Concluding Remarks
open, dynamic, complex, and unpredictable, simple simula-
tions cannot solve all the problems such as how to combine This paper has systematically presented existing significant
real data and simulation data for verifying and validating real results in the field of social influence and spread dynamics
social systems. in social networks, ranging from empirical studies and social
To deal with these problems, in recent years, computa- models to computational experiments. The section on empir-
tional experiments with artificial systems and more sophis- ical studies mainly focuses on network construction, mea-
ticated simulation techniques were developed by Wang et al. sures of networks and significant empirical results. Several
618 Front. Comput. Sci., 2012, 6(5): 611–620

significant social models in the section of social models have 8. Moreno Y, Nekovee M, Pacheco A F. Dynamics of rumor spreading in
been introduced and compared at both macro- and micro- complex networks. Physical Review E: Statistical, Nonlinear, and Soft
Matter Physics, 2004, 69(6): 066130
levels. The macro-level models encompass SIR and its gener- 9. Bakshy E, Hofman J M, Mason W A, Watts D J. Everyone’s an in-
alized models, and Bass models. We have compared the spe- fluencer: quantifying influence on twitter. In: Proceedings of the 4th
cific mechanisms of important micro-level models, including ACM International Conference on Web Search and Data Mining. 2011,
65–74
the preferential attachment models, threshold models, cas-
10. Chierichetti F, Lattanzi S, Panconesi A. Rumor spreading in social net-
cade models and competitive models. Due to the difficulties works. Theoretical Computer Science, 2011, 412(24): 2602–2610
in evaluation and validation of these models, we have also 11. Bharathi S, Kempe D, Salek M. Competitive influence maximization
explained a theoretical framework for computational experi- in social networks. In: Proceedings of the 3rd International Conference
on Internet and Network Economics. 2007: 306–311
ments.
12. Eagle N, Pentland A, Lazer D. Inferring friendship network structure
We believe that this paper can help researchers keep up by using mobile phone data. Proceedings of the National Academy
with the latest results in this field and may offer some in- of Sciences of the United States of America, 2009, 106(36): 15274–
sight into understanding related motivations, connections, 15278
13. Castellano C, Fortunato S, Loreto V. Statistical physics of social dy-
and open problems. In the future, the rapid growth of the
namics. Reviews of Modern Physics, 2009, 81(2): 591–646
Internet, mobile, and cloud computing technologies and their 14. Lazer D, Pentland A, Adamic L, Aral S, Barabási A-L, Brewer D,
applications will offer us a great deal of data sources. These Christakis N, Contractor N, Fowler J, Gutmann M, et al. Computa-
massive network data sets will provide us with more reliable tional social science. Science, 2009, 323(5915): 721–723
15. Zheng X, Zeng D, Sun A, Luo Y, Wang Q, Wang F Y. Network-based
evidence for studying social influence and spread dynamics analysis of Beijing SARS data. In: Proceedings of the 2008 Interna-
in social networks. Existing theoretical models can then be tional Workshop on Biosurveillance and Biosecurity. 2008: 64–73
validated and more reasonable models will be developed. 16. Newman M E J, Watts D J, Strogatz S H. Random graph models of
social networks. Proceedings of the National Academy of Sciences of
These models can be efficiently evaluated on computational
the United States of America, 2002, 99(Suppl 1): 2566–2572
experiment platforms and help us to comprehensively un- 17. Liljeros F, Edling C R, Amaral L A N, Stanley H E, Aberg Y. The web
derstand the evolution of real-world social systems and to of human sexual contacts. Nature, 2001, 411(6840): 907–908
make more reasonable strategies for controlling and manag- 18. Leskovec J, Backstrom L, Kumar R, Tomkins A. Microscopic evolu-
tion of social networks. In: Proceedings of the 14th ACM SIGKDD
ing these social systems.
International Conference on Knowledge Discovery and Data Mining.
2008, 462–470
Acknowledgements This work was supported in part by the follow-
19. Szell M, Lambiotte R, Thurner S. Multirelational organization of large-
ing grants: The National Natural Science Foundation of China (Grant
Nos. 71103180, 91124001, 60921061, 90924302, 70890084, 91024030, scale social networks in an online world. Proceedings of the National
60875028, and 40901219); The Humanities and Social Sciences General Ed- Academy of Sciences of the United States of America, 2010, 107(31):
ucation Project of Chinese Ministry of Education (10YJA630021); The Soft 13636–13641
Science Research Projects of Qingdao City (10-3-3-40-43-zhc); The Chinese 20. Zheng X, Zeng D, Cao Z, Wang Q, Wang F. Evolutionary patterns on
Academy of Sciences (2F09N06). SARS networks. In: Proceedings of the 2009 International Workshop
on Biosurveillance and Biosecurity. 2009
21. Newman M E J. The structure and function of complex networks.
References SIAM Review, 2003, 45(2): 167–256
22. Albert R, Barabási A L. Statistical mechanics of complex networks.
1. Watts D J, Strogatz S H. Collective dynamics of “small-world” net- Reviews of Modern Physics, 2002, 74(1): 47–97
works. Nature, 1998, 393(6684): 440–442 23. Barrat A, Barthélemy M, Vespignani R P S. The architecture of com-
2. Song C, Havlin S, Makse H A. Self-similarity of complex networks. plex weighted networks. Proceedings of the National Academy of Sci-
Nature, 2005, 433(7024): 392–395 ences of the United States of America, 2004, 101(11): 3747–3752
24. Newman M E J, Strogatz S H, Watts D J. Random graphs with arbi-
3. Kossinets G, Watts D J. Empirical analysis of an evolving social net-
trary degree distributions and their applications. Physical Review E:
work. Science, 2006, 311(5757): 88–90
Statistical, Nonlinear, and Soft Matter Physics, 2001, 64(2): 026118
4. Centola D. The spread of behavior in an online social network experi- 25. Barthélemy M, Barrat A, Pastor-Satorras R, Vespignani A. Characteri-
ment. Science, 2010, 329(5996): 1194–1197 zation and modeling of weighted networks. Physica A: Statistical Me-
5. Barabási A L, Albert R. Emergence of scaling in random networks. chanics and Its Applications, 2005, 346(1–2): 34–43
Science, 1999, 286(5439): 509–512 26. Latora V, Marchiori M. Efficient behavior of small-world networks.
6. Cui K, Cao Z, Zheng X, Zeng K, Zheng M. A geospatial analysis on the Physical Review Letters, 2001, 87(19): 198701
potential value of news comments in infectious disease surveillance. 27. Tang L, Liu H. Community detection and mining in social media. Syn-
In: Proceedings of the 6th Pacific Asia Conference on Intelligence and thesis Lectures on Data Mining and Knowledge Discovery, 2010, 2(1):
Security Informatics. 2011, 85–93 1–137
7. Lind P G, da Silva L R, Andrade J S Jr, Herrmann H J . Spreading gos- 28. Wasserman S, Faust K. Social Networks Analysis: Methods and Ap-
sip in social networks. Physical Review E: Statistical, Nonlinear, and plications. Cambridge: Cambridge University Press, 1994
Soft Matter Physics, 2007, 76(3): 036117 29. Boccaletti S, Latora V, Moreno Y, Chavez M, Hwang D U. Complex
 Xiaolong ZHENG et al. Social influence and spread dynamics in social networks 619

networks: structure and dynamics. Physics Reports, 2006, 424(4–5): tion in large social networks: membership, growth, and evolution. In:
175–308 Proceedings of the 12th ACM SIGKDD International Conference on
30. Newman M E J, Girvan M. Finding and evaluating community struc- Knowledge Discovery and Data Mining. 2006, 44–54
ture in networks. Physical Review E: Statistical, Nonlinear, and Soft 51. Lin Y R, Chi Y, Zhu S, Sundaram H, Tseng B L. Facetnet: a framework
Matter Physics, 2004, 69(2): 026113 for analyzing communities and their evolutions in dynamic networks.
31. Newman M E J. Modularity and community structure in networks. Pro- In: Proceedings of the 17th International Conference on World Wide
ceedings of the National Academy of Sciences of the United States of Web. 2008, 685–694
America, 2006, 103(23): 8577–8582 52. Wu B, Ye Q, Yang S, Wang B. Group CRM: a new telecom CRM
32. Deng C, Zheng S, He X F, Yan X F, Han J W. Mining hidden com- framework from social network perspective. In: Proceedings of the 1st
munity in heterogeneous social networks. In: Proceedings of the 3rd ACM International Workshop on Complex Networks Meet Information
International Workshop on Link Discovery. 2005, 58–65 & Knowledge Management. 2009, 3–10
33. Santo F. Community detection in graphs. Physics Reports, 2010, 53. Bikhchandani S, Hirshleifer D, Welch I. A theory of fads, fashion, cus-
486(3–5): 75–174 tom, and cultural change as informational cascades. Journal of Political
Economy, 1992, 100(5): 992–1026
34. Takaffoli M, Sangi F, Fagnan J, Zäıane O R. Community evolution
mining in dynamic social networks. Procedia-Social and Behavioral 54. Fowler J H, Christakis N A. Cooperative behavior cascades in human
Sciences, 2011, 22: 49–58. social networks. Proceedings of the National Academy of Sciences of
the United States of America, 2010, 107(12): 5334–5338
35. Rogers E M. Diffusion of Innovations. New York: Free Press, 1995
55. Christakis N A, Fowler J H. The spread of obesity in a large social net-
36. Milgram S. The small-wolrd problem. Psychology Today, 1967, 1(1):
work over 32 years. New England Journal of Medicine, 2007, 357(4):
61–67
370–379
37. Dodds P S, Muhamad R, Watts D J. An experimental study of search
56. Fowler J H, Christakis N A. The dynamic spread of happiness in a large
in global social networks. Science, 2003, 301(5634): 827–829
social network. British Medical Journal (Clinical Research Ed.), 2008,
38. Costa L D F, Oliveira O N, Travieso G, Rodrigues F A, Villas Boas 337: a2338
P, Antiqueira L, Viana M P, Correa Rocha L. Analyzing and modeling
57. Singh J. Collaborative networks as determinants of knowledge diffu-
real-world phenomena with complex networks: a survey of applica-
sion patterns. Management Science, 2005, 51(5): 756–770
tions. Advances in Physics, 2011, 60(3): 329–412
58. Christakis N A, Fowler J H. The collective dynamics of smoking
39. Wang J C, Chiu C C. Recommending trusted online auction sellers us-
in a large social network. New England Journal of Medicine, 2008,
ing social network analysis. Expert Systems with Applications, 2008,
358(21): 2249–2258
34(3): 1666–1679
59. Rosenquist J N, Murabito J, Fowler J H, Christakis N A. The spread
40. Palla G, Barabasi A L, Vicsek T. Quantifying social group evolution. of alcohol consumption behavior in a large social network. Annals of
Nature, 2007, 446(7136): 664–667
Internal Medicine, 2010, 152(7): 426–433
41. Bilke S, Peterson C. Topological properties of citation and metabolic 60. Adar E, Adar E, Adamic L A. Tracking information epidemics in
networks. Physical Review E: Statistical, Nonlinear, and Soft Matter blogspace. In: Proceedings of 2005 IEEE/WIC/ACM International
Physics, 2001, 64(3): 036106 Conference on Web Intelligence. 2005, 207–214
42. Guimerà R, Danon L, Díaz-Guilera A, Giralt F, Arenas A. Self-similar 61. Gruhl D, Guha R V, Liben-Nowell D, Tomkins A. Information diffu-
community structure in a network of human interactions. Physical Re- sion through blogspace. In: Proceedings of the 13th International Con-
view E: Statistical, Nonlinear, and Soft Matter Physics, 2003, 68(6): ference on World Wide Web. 2004, 491–501
065103
62. Leskovec J, McGlohon M, Faloutsos C, Glance N S, Hurst M. Pat-
43. Zheng X, Li H, Sun A. Exploring social dynamics in online bookmark- terns of cascading behavior in large blog graphs. In: Proceedings of
ing systems. In: Proceedings of 2008 International Workshop on Social 7th SIAM International Conference on Data Mining. 2007
Computing. 2008, 390–391 63. Leskovec J, Adamic L A, Huberman B A. The dynamics of viral mar-
44. Mislove A, Marcon M, Gummadi K P, Druschel P, Bhattacharjee B. keting. ACM Transactions on the Web, 2007, 1(1): 5
Measurement and analysis of online social networks. In: Proceedings 64. Anagnostopoulos A, Kumar R, Mahdian M. Influence and correlation
of the 7th ACM SIGCOMM Conference on Internet Measurement. in social networks. In: Proceedings of the 14th ACM SIGKDD Inter-
2007, 29–42. national Conference on Knowledge Discovery and Data Mining. 2008,
45. Wang Y, Zeng D, Zheng X, Wang F. Analyzing online media as com- 7–15
plex network. Complex Systems and Complexity Science, 2008, 6(3): 65. Aral S, Muchnik L, Sundararajan A. Distinguishing influence-based
11–21 contagion from homophily-driven diffusion in dynamic networks. Pro-
46. Onnela J P, Saramäki J, Hyvönen J, Szabó G, Lazer D, Kaski K, ceedings of the National Academy of Sciences of the United States of
Kertész J, Barabási A L. Structure and tie strengths in mobile commu- America, 2009, 106(51): 21544–21549
nication networks. Proceedings of the National Academy of Sciences 66. Newman M E J. The spread of epidemic disease on networks. Physical
of the United States of America, 2007, 104(18): 7332–7336 Review E: Statistical, Nonlinear, and Soft Matter Physics, 2002, 66(1):
47. Arenas A, Danon L, Díaz-Guilera A, Gleiser P M, Guimerá R. Com- 016128
munity analysis in social networks. The European Physical Journal B - 67. Moreno Y, Vázquez A. Disease spreading in structured scale-free net-
Condensed Matter and Complex Systems, 2004, 38(2): 373–380. works. The European Physical Journal B: Condensed Matter and Com-
48. Girvan M, Newman M E J. Community structure in social and biologi- plex Systems, 2003, 31(2): 265–271
cal networks. Proceedings of the National Academy of Sciences of the 68. Ancel L W, Newman M E J, Martin M, Schrag S. Applying network
United States of America, 2002, 99(12): 7821–7826 theory to epidemics: control measures for Mycoplasma pneumoniae
49. Newman M E J, Park J. Why social networks are different from other outbreaks. Emerging Infectious Diseases, 2001, 9(2): 204–210
types of networks. Physical Review E: Statistical, Nonlinear, and Soft 69. Wang J, Liu Z, Xu J. Epidemic spreading on uncorrelated heteroge-
Matter Physics, 2003, 68(3): 036122 nous networks with non-uniform transmission. Physica A: Statistical
50. Backstrom L, Huttenlocher D, Kleinberg J, Lan X. Group forma- Mechanics and its Applications, 2007, 382(2): 715–721
620 Front. Comput. Sci., 2012, 6(5): 611–620

70. Zanette D. Dynamics of rumor propagation on small-world networks. 2004, 16(5): 893–897
Physical Review E: Statistical, Nonlinear, and Soft Matter Physics, 93. Zheng X, Ke G, Zeng D, Ram S, Lu H. Next-generation team-science
2002, 65(4): 041908 platform for scientific collaboration. IEEE Intelligent Systems, 2011,
71. Bass F M. A new product growth for model consumer durables. Man- 26(6): 72–76
agement Science, 1969, 15(5): 215–227
72. Mahajan V, Muller E, Bass F M. New product diffusion models in
marketing: a review and directions for research. Journal of Marketing, Xiaolong Zheng is an assistant profes-
1990, 54(1): 1–26 sor in the State Key Laboratory of Man-
73. Jackson M O. Social and Economic Networks. Princeton: Princeton agement and Control for Complex Sys-
University Press, 2008
tems at the Institute of Automation of
74. Kempe D. Structure and Dynamics of Information in Networks. 2011
75. Young H P. The evolution of conventions. Econometrica: Journal of the Chinese Academy of Sciences. His
the Econometric Society, 1993, 61(1): 57–84 research interests include complex net-
76. Krapivsky P L, Redner S, Leyvraz F. Connectivity of growing random works, social computing, and data min-
networks. Physical Review Letters, 2000, 85(21): 4629–4632
ing. Specifically, he is interested in so-
77. Dorogovtsev S N, Mendes J F F. Evolution of reference networks with
aging. Physical Review E: Statistical Physics, Plasmas, Fluids, and Re- cial dynamics, social influence, spread
lated Interdisciplinary Topics, 2000, 62(2): 1842–1845 dynamics, and opinion and behavior mining in social media.
78. Zheng X, Zeng D, Li H, Wang F. Analyzing open-source software sys-
tems as complex networks. Physica A: Statistical Mechanics and its
Applications, 2008, 387(24): 6190–6200 Yongguang Zhong is a professor in
79. Granovetter M. Threshold models of collective behavior. American the Department of Management Sci-
Journal of Sociology, 1978, 83(6): 1420–1443 ence and Engineering at Qingdao Uni-
80. Schelling T. Micromotives and macrobehavior. New York: Norton, versity in China. His current research
1978
81. Macy I W. Chains of cooperation: threshold effects in collective action.
interests include system dynamics, op-
American Sociological Review, 1991, 56(6): 730–747 erations management, and reverse lo-
82. Macy M W, Willer R. From factors to actors: computational sociology gistics.
and agent-based modeling. Annual Review of Sociology, 2002, 28(1):
143–166
83. Berger E. Dynamic monopolies of constant size. Journal of Combina-
torial Theory Series B, 2001, 83(2): 191–200
84. Kempe D, Kleinberg J M, Tardos É. Influential nodes in a diffusion Daniel Zeng is a professor in the State
model for social networks. In: Proceedings of the 32nd International
Key Laboratory of Management and
Colloquium on Automata, Languages and Programming. 2005, 1127–
1138 Control for Complex Systems at the In-
85. Kempe D, Kleinberg J, Tardos V. Maximizing the spread of influence stitute of Automation of the Chinese
through a social network. In: Proceedings of the 9th ACM SIGKDD Academy of Sciences. His research
International Conference on Knowledge Discovery and Data Mining.
2003, 137–146 interests include multi-agent systems,
86. Easley D, Kleinberg J. Networks, Crowds, and Markets: Reasoning collaborative information and knowl-
About a Highly Connected World. New York: Cambridge University edge management, recommender sys-
Press, 2010
tems, and automated negotiations and
87. Goldenberg J, Libai B, Muller E. Using complex systems analysis to
advance marketing theory development. Academy of Marketing Sci- auctions. Specifically, he is interested in social computing, infor-
ence Review, 2001, 2001(9): 1–19 mation and security informatics, spatio-temporal data analysis, and
88. Lotker Z, Patt-Shamir B, Tuttle M R. Publish and perish: definition online surveillance.
and analysis of an n-person publication impact game. In: Proceedings
of the 18th Annual ACM Symposium on Parallelism in Algorithms and
Architectures. 2006, 11–18 Fei-Yue Wang is a professor in the State
89. Dubey P, Garg R, De Meyer B. Competing for customers in a social Key Laboratory of Management and
network: the quasi-linear case. In: Proceedings of the 2nd International
Control for Complex Systems at the In-
Workshop on Internet and Network Economics. 2006, 162–173
90. Wang F Y, Carley K M, Zeng D, Mao W. Social computing: from so- stitute of Automation of the Chinese
cial informatics to social intelligence. IEEE Intelligent Systems, 2007, Academy of Sciences. His current re-
22(2): 79–83 search interests include social comput-
91. Wang F Y. Toward a paradigm shift in social computing: the ACP ap-
ing, parallel control and management,
proach. IEEE Intelligent Systems, 2007, 22(5): 65–67
92. Wang F Y. Computational experiments for behavior analysis and de- web and services science, and agent-
cision evaluation in complex systems. Journal of System Simulation, based intelligent systems.