[go: up one dir, main page]
© Copyright JASSS

JASSS logo ----

Jean-Philippe Cointet and Camille Roth (2007)

How Realistic Should Knowledge Diffusion Models Be?

Journal of Artificial Societies and Social Simulation vol. 10, no. 3 5
<https://www.jasss.org/10/3/5.html>

For information about citing this article, click here

Received: 13-Nov-2006    Accepted: 21-Apr-2007    Published: 30-Jun-2007

PDF version

* Abstract

Knowledge diffusion models typically involve two main features: an underlying social network topology on one side, and a particular design of interaction rules driving knowledge transmission on the other side. Acknowledging the need for realistic topologies and adoption behaviors backed by empirical measurements, it becomes unclear how accurately existing models render real-world phenomena: if indeed both topology and transmission mechanisms have a key impact on these phenomena, to which extent does the use of more or less stylized assumptions affect modeling results? In order to evaluate various classical topologies and mechanisms, we push the comparison to more empirical benchmarks: real-world network structures and empirically measured mechanisms. Special attention is paid to appraising the discrepancy between diffusion phenomena (i) on some real network topologies vs. various kinds of scale-free networks, and (ii) using an empirically-measured transmission mechanism, compared with canonical appropriate models such as threshold models. We find very sensible differences between the more realistic settings and their traditional stylized counterparts. On the whole, our point is thus also epistemological by insisting that models should be tested against simulation-based empirical benchmarks.

Keywords:
Agent-Based Simulation, Complex Systems, Empirical Calibration and Validation, Knowledge Diffusion, Model Comparison, Social Networks

* Outline

1.1
Although the issue of knowledge diffusion has usually been appraised from a theoretical viewpoint, it stands, above all, for an empirical challenge. Real-world features, yet, are often represented by stylized hypotheses, while it is unclear how much diffusion dynamics may be affected by such assumptions. After first recalling the context and literature on knowledge diffusion models in Section 2, we thus introduce a simulation framework in Section 3 in order to evaluate the accuracy of various classical topologies and mechanisms. In other words, we push the comparison to more empirical benchmarks: real-world network structures and empirically measured mechanisms. We therefore carry a two-step analysis: in Section 4, we contrast diffusion dynamics between two real networks and several traditional topologies, notably scale-free graphs; in Section 5, we address interaction rules and compare an empirically-backed transmission mechanism with its stylized counterparts, such as threshold or cascade models.

* Context and rationale

2.1
Models of knowledge diffusion within social networks have known an increased interest in the recent years, together with various kinds of studies on interaction networks. Initially, research on knowledge diffusion had been principally addressed by social scientists, both in sociology as well as, to a lesser extent, economics and organization & management sciences (Coleman et al. 1957; Rogers 2003). Authors in these fields have long had a qualitative approach, supported by ethnographic studies endeavoring at exhibiting mechanisms determinant of knowledge transmission and adoption behaviors (Robertson 1967; Rogers 1976; Granovetter 1987; Burt 1987; Valente 1995). In this area, quantitative models are eventually qualitative in their interpretation, as they are essentially featuring normative models within formerly acknowledged theoretical frameworks (Ellison and Fudenberg 1995; Abrahamson and Rosenkopf 1997; Deroian 2002).

2.2
As knowledge diffusion phenomena are conditioned by the intricate combination of agent behavior and structural effects, it progressively became apparent that it is crucial to correctly design and understand the effect of underlying network structures. This happened initially, still, on normative grounds, i.e. with stylized network structures (Morris 2000; Cowan and Jonard 2004; Keeling and Eames 2005), while an earlier emphasis by Rogers (1976) on empirical data had remained a longer term aim:
For network analysis to fulfill its potential, however, I feel we must improve the methods of data gathering and measurement (…). Longitudinal panel designs for networks analysis of diffusion process are also needed; along with field experiments, they help secure the necessary data to illuminate the over-time process of diffusion. (Rogers 1976)

2.3
Such empirical insight was additionally encouraged by recent findings from formal and natural sciences (particularly statistical physics and computer science) concerning several kinds of real-world networks, including social networks, and highlighting a series of notable topological features, such as power-law ("scale-free") degree distributions, high clustering, short network diameter (Watts and Strogatz 1998; Barabasi and Albert 1999, inter alia). Authors from these fields in turn started to investigate diffusion phenomena from a rather formal viewpoint: adopting a biological perspective first, building upon the epidemiological literature (Anderson and May 1979; Pastor-Satorras and Vespignani 2001; Lloyd and May 2001; Keeling and Eames 2005); then addressing topics increasingly related to social science, for instance rumor and behavior diffusion models (Newman 2002), thereby shedding light on both traditional issues, such as the extent of knowledge diffusion, and on more novel issues, such as, inter alia, effects of extremist fractions (Deffuant et al. 2002) or spread maximization (Kempe et al. 2003).

2.4
However, even if some authors insisted on the need for realistic topologies and diffusion behaviors backed by empirical measurements (Valente 1996; Wu et al. 2004; Leskovec et al. 2006), it is unclear how accurately present models and corresponding analytic solutions or simulations render real-world phenomena. If indeed both topology and transmission mechanisms have a key impact on these phenomena, to which extent does the use of more or less stylized assumptions affect modeling results?

2.5
First, network topology is often based on common social network morphogenesis models. Erdös and Rényi (1959) random graphs (ER) have long been a convincing reference (Barbour and Mollison 1990; Wasserman and Faust 1994; Zegura et al. 1996), while simpler settings use complete graphs or grid-based networks (Ellison and Fudenberg 1995; Deroian 2002). Small-world models (Watts and Strogatz 1998) have also occasionally been considered (Cowan and Jonard 2004), as well as less typical models, for instance featuring a central core everyone is connected to (Bala and Goyal 1998), or algebraically-constrained networks (Morris 2000). These models seemed rather less realistic when, as mentioned above, social networks among others were discovered to be "scale-free" — i.e. their connectivity distribution follows a power-law, which earlier models could not render. In the wake of a key result by Pastor-Satorras and Vespignani (2001) suggesting that such networks have radically distinct epidemiologic properties from those of ER networks[1], in more recent diffusion models, scale-free networks are hence often considered (Delgado 2002; Amblard and Deffuant 2004; Ganesh et al. 2005; Crépey et al. 2006). On the other hand, to our knowledge, cultural diffusion models has scarcely been effectively simulated on real social networks[2], while such approach obviously guarantees that all structural features of a real-world social network are present[3]. Such networks, additionally, are already widely available (Barabási and Albert 1999 ; Robins and Alexander 2004; Wu et al. 2004; Kossinets and Watts 2006).

2.6
Second, knowledge diffusion mechanisms, even if plausible, are often lacking empirical support; as Leskovec, Adamic and Huberman (2006) put it, "[while former] models address the question of maximizing the spread of influence in a network, they are based on assumed rather than measured influence effects." A wide variety of behaviors can be postulated, from pay-off based models, common in economics (Ellison and Fudenberg 1995; Morris 2000), to explicitly knowledge-based models, based in particular on opinions vectors, continuous or discrete, one-dimensional (Axelrod 1997; Deroian 2002; Deffuant et al. 2002) or n-dimensional (Gilbert et al. 2001; Cowan and Jonard 2004; Klemm et al. 2005), revised and updated according to diverse mechanisms. Yet, while such hypotheses yield enlightening models and stylized facts, it is unclear to what extent realistic classes of knowledge diffusion mechanisms could yield different classes of models and model behaviors. In this respect, projects such as that of Valente (1996) seem to be isolated.

2.7
In line with recent efforts at appraising the role of various topologies (Amblard and Deffuant 2004; Ganesh et al. 2005; Crépey et al. 2006) and distinct mechanisms (Deffuant 2006), the aim of this paper is thus to push the comparison to more realistic benchmarks: real-world network structures and empirically measured propagation mechanisms. As we lack empirical data appraising at the same time knowledge transmission behaviors and underlying social network topology, we have to restrain our analysis to issues pertaining to topology on one side and, separately, to transmission rules on the other side. More precisely, we will appraise the discrepancy between stylized (in particular scale-free) networks and real-world networks (Section 4) and between stylized (in particular threshold) knowledge transmission models and realistic mechanisms (Section 5).

* Simulation framework

Agents and information

3.1
We consider a set of N agents and a single piece of information which each agent may know of, or not. In other words, at any time t, the cultural state of the system can be described by a vector c(t) ∈ {0,1}N, such that ci(t)=1 if the i-th agent knows the piece of information at t, otherwise ci(t)=0.

3.2
We assume knowledge acquisition to be strictly growing: agents acquiring the piece of information cannot lose it afterwards. In epidemiological terms, this is close to a "SI" model (Hethcote 2000). Formally, this means that c is a growing function of time: t ≤ t2 ⇒ c(t) ≤ c(t2).

Simulations

3.3
The initial setting is such that a given proportion λ of agents are initially "informed" (i.e. λN agents), while others are "ignorant" (i.e. (1 – λ)N).

3.4
Our discrete time simulation features knowledge exchange between agents interacting with each other. At each time step one interaction occurs, possibly leading to transmission of knowledge: The algorithm is shown below in pseudo-code. 


SET number_of_nodes := number of agents
SET neighbor := ARRAY OF LISTS of size number_of_nodes
SET state := ARRAY OF BOOLEANS ("INFORMED"/"NOT_INFORMED") of size number_of_nodes
SET number_of_interactions := ARRAY OF INTEGERS of size number_of_nodes

INITIALIZE neighbor[i] with the neighbor list for node i
INITIALIZE state WITH "INFORMED" on a random selection of elements of 
                 size Integer_Part_Of(number_of_nodes*lambda)
INTIIALIZE number_of_interactions WITH 0 on the whole array

FOR each step of the simulation
	CHOOSE RANDOMLY an agent i
	IF state[i] IS "NOT_INFORMED"
	THEN
		CHOOSE RANDOMLY an agent j among neighbor[i]
		IF state[j] IS "INFORMED"
		THEN
			IF a uniform random variable in [[0, 1]] IS BELOW
	  Probability_Of_Adoption_After_N_Interactions(number_of_interactions[i])
			THEN
				state(i) := "INFORMED"
			END IF
			INCREMENT number_of_interactions(i)
		END IF
	END IF
END FOR
Algorithm

3.5
This kind of simple protocol belongs to the wider family of gossip-based models (see Kempe and Kleinberg (2002), for instance). In a descriptive rather than normative perspective, we therefore consider that the social network represents past acquaintances which potentially induce future interactions, rather than being a permanent interaction network, where individuals are concurrently subject to the influence of all their neighbors. While this later approach is indeed more plausible for computer or neuron networks, epidemiology in the broad sense calls for more asynchronous models, where interactions between agents are the basic unit of study. As such, we take the social network as a static framework wherein social interactions take place in a dynamic setting: for any given period, actual dyadic interactions are chosen within the set of links composing the wider social network.

3.6
We measure the ratio of informed agents ρ among the whole population over time, ρ(t)=[1/N] ∑i=1N ci(t), while using a totally random initial spread of informed agents (only ρ(0) = λ). Even if richer patterns could be thought of (such as e.g. infection time as a function of the distance, density of infected nodes) and richer initial conditions could also affect results (a particular choice of informed nodes consisting of, e.g., so-called superspreaders) (Crépey et al. 2006; Deffuant 2006), this part of the protocol remains extremely simple so that effects are both easily comparable across other conditions as well as already yielding very contrasted results.

* Effect of the topology

4.1
We first discuss dynamics of information acquisition by focusing on topology. We use several network topologies produced by a gradual impoverishment of two original real networks as explained below.

Figure Figure
Figure 1. Cumulated degree distributions for the various network structures, using the Medline-base collaboration network (left) and the board interlock network (right). x-axis: degree k, y-axis: N(k)=∑ k' ≥ kN(k').

Empirical real networks

4.2
We use two real networks. The first one comes from a scientific collaboration network: nodes are authors and links represent coauthorship. We use data from the "Medline" bibliographical database[4] for embryologists working on the model-animal zebrafish and consider articles mentioning "zebrafish" in their title or abstract (the field is such that authors working on this topic are unlikely not to mention it at least in the abstract) over years 2000-2004. We consider only the largest connected component. It is made of 6453 agents and 67392 undirected links, from a database of 2476 publications. The second network features directors jointly attending boards of major US firms or public institutions: nodes are directors and links are co-attendance relationships. This board interlock data comes from the website "Theyrule"[5]. The largest connect component of this network is made of 4656 nodes and 76600 undirected links from a database of 510 corporate boards. Their degree distributions, shown on Figure 1, exhibit a power-law tail with a flatter head, typical of collaboration networks (Barabási and Albert 1999; Newman and Park 2003; Guimera et al. 2005) and several other social networks (Boguna et al. 2004; Holme et al. 2004; Kossinets and Watts 2006). While this kind of connectivity is often called "scale-free" or "power-law" in the literature, it may also accurately be fitted and described as "broad scale", "stretched-exponential", "log-normal" or "q-exponential" (Amaral et al. 2000; Redner 2005; White et al. 2006) on finite networks.

Topologies

4.3
Starting from the original empirical network, we investigate several network topologies created by progressively degenerating the original structure, i.e. by keeping less and less topogical features:

Clustering structure

4.4
Apart from degree distributions, the clustering structure is of particular interest; some authors suggest it might significantly alter information diffusion (Bala and Goyal 1998). The usual definition of "clustering" relies on the proportion of transitive triples, or "friends who are also friends of friends." It may be defined by averaging the proportion of neighbors of node i who are also connected together:

Equation (1)

with ki the degree of node i. Empirical social networks are known to exhibit an abnormally high average clustering coefficient ‹c3›, compared to those found in SF and ER random networks (Newman and Park 2003); many models traditionally try to rebuild this statistical parameter as well. Our real networks do not derogate from this rule. RN1 exhibits a high ‹c3› of .827, while SF1 only has a ‹c3› of .00539. We observe the same discrepancy in the second network: clustering in RN2 is high (‹c3› = .889) while it is two orders of magnitude smaller in SF2 (‹c3› = .00395).

4.5
In an attempt to reconstruct a network topology that preserves both degree distribution and high ‹c3›, we consider a last network model mimicking the original event-based structure (i.e. its collaboration or co-appearance structure):

4.6
The EB model yields networks which are closer to RN than SF in the sense that they keep more topological features:
  1. We conserve the degree distribution, like in the SF case: the projection of a bipartite graph, whose distribution from agents to events exhibits a given power-law tail (as it does here) exhibits the same power-law tail (same exponent of the power law) (Guillaume and Latapy 2004).
  2. We also conserve the clustering structure, unlike in the SF case: indeed, the clustering coefficient of the projection is high because of the clique-addition process precisely due to the projection; put simply, it is due to the joint involvement in common events — the empirical networks come from collaborations or participations in a common board, which implies cliques and thus more triangles (Newman et al. 2001; Guillaume and Latapy 2004).
Empirically, EB rebuilds fairly well both the degree distribution and the ‹c3‹ clustering structure, with the same number of nodes and thus roughly the same number of links — see Figure 1 and Table 1.

4.7
A finer clustering structure has more recently been introduced, which relies on the proportion of transitive diamonds, or "friends of friends who are also friends of other friends." This "diamond coefficient" may be defined as the average proportion of common neighbors among the neighbors of a node i (Lind et al. 2005):

Equation (2)

where κj1,j2 is the number of nodes which the j1-th & j2-th neighbors of i have in common (leaving out i) and ηj1,j2 = 1 + κj1,j2 + θj1,j2 where θj1,j2 = 1 if j1 and j2 are connected, 0 otherwise. EB1 acceptably approaches the ‹c3› of RN1, but falls short of one order of magnitude for c4 , suggesting that even an event-based reconstruction still misses part of the community structure of RN1. On the other hand, EB2 yields a ‹c4› of .268 which is closer to the ‹c4› of .398 for RN2. Values for these statistical parameters are gathered on Table 1.

4.8
Other topological features could also have been explored -such as path lengths (Zegura et al. 1996), mutuality (Newman 2003), cycles (White et al. 2006), inter alia — yet this selection of basic features will already provide significant discrepancies in the results between realistic settings and traditional models, acting as a convincing counter-example of the adequacy of the latter to mimick the former, even for our selection of statistical parameters.

4.9
To summarize, for each of our two real networks, we considered five distinct topologies: (i) real network RN, (ii) event-based network EB, (iii) scale-free network SF, (iv) Erdös-Rényi random graph ER, (v) complete network CN.
Table 1: Main characteristics of the various network structures derived from the real networks RN1 and RN2 in terms of: number of agents N, number links M, density d, degree distribution shape and clustering coefficients ‹c3› & ‹c4‹ (averaged quantities over 1000 networks for SF, ER & EB).
RN1 SF1ER1CN1EB1
N6453
M6.741042.081077.62104
d.001621.00183
degree dist.power-law tailPoisson-power-law tail
‹c3›.827.00539.001991.753
‹c4›.400.000260.0001581.0694
RN2 SF2ER2CN2EB2
N4656
M7.66·1042.17·1077.68·104
d.00351.0035
degree dist.power-law tailPoisson-power-law tail
‹c3›.889.00395.004031.897
‹c4›.398.000261.0002171.268

Simulation

4.10
As we focus on topology, we consider here the simplest interaction rule possible: the target agent automatically acquires the piece of information when his interlocutor already has it. A set of one thousand random instances of each kind of network is created (excepted for real and complete networks which are naturally unique). For each instance, we only work with the largest connected component, which is never made of less than 99.9% of the nodes (i.e. in the worst case, a negligible number of nodes is disconnected and left out). We then cast randomly the fraction λ of initially informed nodes over this giant component, and start the simulation. With connected networks, as is the case, the final asymptotic state of the system is obviously ρ(∞)=1. We are thus essentially interested in the shape and speed of convergence to that final state.

4.11
On Figure 2 is plotted the temporal evolution of ρ for each network topology (averaged over simulations on 1000 random instances). We observe that the dynamics are pretty similar when comparing the two original networks. The closer we are from the real network, the slower the dynamics — CN performs the fastest, RN the slowest. More precisely and most surprisingly, ER and SF networks seem to behave identically by showing extremely similar convergence shapes. On the contrary, the behavior of EB is slower than other topologies, even being the best approximation of RN, although with contrasted results: while EB2 provides a satisfactory reconstruction of the diffusion dynamics on RN2, the reconstruction offered by EB1 still diverges significantly from the behavior of RN1.

4.12
Our results are qualitatively only marginally sensitive to the initial proportion of informed nodes λ even if, the smaller λ, the slower the dynamics (see Figure 2-inset for λ = .002 vs. λ = .02). Hierarchy in convergence speed is independent of λ: CN always performs fastest, followed by ER and SF, then EB, and finally RN. Asymptotically, when λ goes to 1 all dynamics become similar.

Figure Figure
Figure 2. Simulation results for complete, Erdös-Rényi, Scale-Free, Event-Based and real networks, using λ = 0.02 (outset) and λ = 0.002 (inset), along with associated 99% confidence intervals. Topologies built from the scientific collaboration network (left) and the board interlock network (right).

Degree distribution, clustering structure, and real networks

4.13
As such, diffusion on RN is slower than on any other topology studied here. This may be due to its complex underlying community structure, consistently with common claim in innovation studies that when agents are likely to interact more with agents they know and less with "remote" agents, it is less beneficial to knowledge propagation (Granovetter 1973 ; Bala and Goyal 1998) — denser clusters arguably provide more redundancies in the distribution of information among neighbors. More to the point, as Granovetter (1973) puts it, "if one tells a rumor to all his close friends, and they do likewise, many will hear the rumor a second and third time, since those linked by strong ties tend to share friends." A previous study by Bala and Goyal (1998) argued that overlapping neighborhoods tend to make the diffusion of innovation slower, Eguiluz and Klemm (2002) later noted that epidemic threshold in highly clustered scale-free networks exhibited differences with the result for randomly wired networks.

4.14
This might explain why we get slower diffusion with EB than with SF, and even slower diffusion with RN in general, whose alleged community structure — plausibly constrained by paradigmatic fields, communities of practice, etc. — could not be perfectly reproduced. However, ‹c4› values seem to provide a good assessment of the quality of this community structure reconstruction: when ‹c4› is one order of magnitude smaller in EB1 than in RN1, diffusion speed is indeed significantly different; whereas when ‹c4› is comparable, like in EB2 and RN2, diffusion speed too is comparable.

4.15
While it is likely that "the SF nature cannot be neglected in the practical estimates of epidemic and immunization thresholds in real networks" (Pastor-Satorras and Vespignani 2002), it may well be far from sufficient: not all SF networks are equal (May and Lloyd 2001; Boguna and Pastor-Satorras 2002; Eguiluz and Klemm 2002) and, here, the most random SF network actually displays a behavior more similar to ER than to RN — even if, for some other models, there may be a more or less sensible behavioral difference between SF and ER (Dorogovtsev and Mendes 2003; Barthélémy et al. 2005), under our protocol they are negligible compared to RN. In contrast and in particular, EB results suggest a special influence of community structure in general (Szendröi and Csányi 2004).

Concluding remarks

4.16
The jury may thus be still out as to indicate which topological features should absolutely be reconstructed for an artificial network to behave realistically with respect to some phenomena. Meanwhile, when possible, it could be safer to make an extensive usage of real network topologies when developing diffusion models. This attitude implies a pre-eminent role for simulations: if one needs analytical results on a given diffusion phenomenon, thereby requiring a theoretical social network model, one should check first that simulations provide matching behaviors on a real social network — or several ones, as it may also be interesting to compare how different diffusion dynamics behave on various empirical networks.

* Effect of transmission rules

5.1
The protocol we presented in the previous section, where any interaction entails information transmission, is simple yet wholly arbitrary. In this section, we investigate transmission rules: as mentioned in the introduction, many varied knowledge transmission processes have been proposed in the literature. In the case of discrete information propagation, in particular, the "threshold model" — agents adopt knowledge if a given number or fraction of their neighbors already have — is a widespread reference (Granovetter 1987; Valente 1995; Valente 1996; Abrahamson and Rosenkopf 1997; Lew 2000; Gruhl et al. 2004), while the "cascade model" is also commonly used — agents have a given probability of adopting after interacting with already-informed neighbors (Goldenberg et al. 2001; Kempe et al. 2003).

5.2
Thus, and more broadly, we wish to appraise the success of some of these traditional models in approaching empirically-measured behavior — as we have seen, real networks may behave quite differently than classical scale-free networks: now, how much canonical models may now deviate from empirical phenomena? How realistic, then, should diffusion mechanisms be? In a fashion similar to what we did for the topology, we start with real-world data and consider various "degenerate" knowledge adoption behaviors which rely on canonical models. The model parameters will be chosen as best approximations of empirically observed behavior. We use RN as the underlying social structure.

Empirical influence mechanism

5.3
To design our original "empirical-based" transmission mechanism, we use empirical data extracted from a case study by (Leskovec et al. 2006), in which the propagation of a buying behavior is described — recommendations for acquiring DVDs are transmitted over an e-mail-based social network, and could be followed or not. Rather than focusing on this precise case study and its particular context, we use this data as an empirical illustration of the shape of one adoption behavior, among others.

5.4
This empirical data features the probability of adopting a recommendation after a certain number of received recommendations, that is, it is a final observation. More precisely, we know the probability P(n) of having bought some item given that n recommending interactions for this item have occurred (see Figure 3). Assuming that this process is the final outcome of a series of interactions where adoption was possible and probable after each interaction, we may deduce the adoption probability for each particular interaction. In other words, we can deduce the probability of adoption exactly at the n-th recommending interaction, given that there have already been n – 1 recommending interactions. We call this probability p(n), which is precisely of interest for interaction-by-interaction models such as those we are working with here.

Figure
Figure 3. Final probability of adoption P(n) after n recommending interactions (Pmax=0.4). Empirical data adapted from (Leskovec et al. 2006), where Pmax=0.04 (see Figure 4 for a discussion on Pmax values).

5.5
We have:

Equation (3)

from which it is straightforward to deduce that:

Equation (4)

as we assume that p(i) are independent one each other. Thus, the probability of adopting at each n-th interaction with an informed neighbor is p(n).

5.6
It might be noted that empirical data used here is slightly mismatching — we eventually examine recommendation behavior over a scientific collaboration network. We acknowledge this, while it should also be irrelevant to our point, as we aim at investigating discrepancies between reality-inspired hypotheses and their traditional stylization. Anyhow, empirical data in this area is still scarce[6], and it is likely that the continuation of this kind of study would rather involve a comparative study between various real-world behaviors (and topologies). Indeed, even in this case, a great variance should be encountered — for instance when scientists from distinct fields do not behave similarly in forming their network (e.g. mathematicians and neuroscientists (Barabási et al. 2002)), or when adoption behaviors in a similar area are to be rather dissimilar (e.g. DVDs and books (Leskovec et al. 2006)).

Models

5.7
We focus on classical threshold and cascade models. The classical models have no reason a priori to be consistent with empirical data in the general case, nonetheless one could design a stylized mechanism such that it is the closest possible to the observed behavior, fitting model parameters in this regard.

5.8
It is also noteworthy that individuals should not be necessarily eventually convinced. Some pieces of information might be less convincing than others. Adoption mechanisms should consequently be "capped" by a maximal final probability of adoption Pmax, as is observed empirically ∀n, P(n) ≤ Pmax and ∃ n0, P(n0)=Pmax — after a certain number of interactions, no persuasion is possible anymore. In the original case study, Pmax ≈ 0.04.

5.9
We investigate three kinds of knowledge transmission behaviors: an empirical data-based model, and corresponding best-approximation threshold and cascade models for different value of Pmax. In the general case we have: Note that in terms of the simple model (SM) presented in Section 4.10 for the study of the topology, we would have Pmax =1 and, trivially, ∀n ≥ 1, both pSM(n)=1 and PSM(n)=1. Actually, SM is equivalently a TM with ν = 1 or a CM with p=1, ν > 0.

Simulation results

5.10
We simulated these different interaction rules on the real network 50 times, for different values of Pmax. Indeed, to study the influence of Pmax we use several values Pmax ∈ {0.04, 0.4, 0.7, 0.99}. To design the corresponding best-approximation TM and CM for each Pmax, we consider a simple homothetic transformation of the original empirical results. Then, we fit p and/or the threshold ν for both CM and TM by minimizing squared distance between the original empirical model RM and CM or TM; respectively ∑n(PCM(n) – PRM(n))2 and ∑n(PTM(n) – PRM(n))2. A graphical representation of fitted PTM and PCM is given on Figure 3 for Pmax=0.4.

5.11
For every given Pmax, we plot the average value of ρ over the 50 simulations — see Figure 4. All models converge towards an identical final state ρ(∞) ≤ Pmax.

Figure Figure
Figure Figure
Figure 4. Evolution of ρ for RM, TM and CM, given four distinct Pmax, from left to right and from top to bottom : Pmax =0.99, Pmax =0.7, Pmax =0.4, Pmax =0.04. Confidence intervals (99%) are also shown. Insets exhibit asymptotic behavior for large time steps.

5.12
We also observe that ρ(∞) decreases with smaller values of Pmax. Theoretically indeed, the expectancy of ρ(∞) is less or equal to (λ+(1 – λ)Pmax), because each initially ignorant node has at most probability Pmax to be convinced over the whole simulation; yet, some agents may never meet informed neighbors, especially if Pmax is low, hence having no chance at all to adopt the information. As Pmax decreases, the set of such isolated nodes grows, while ρ(∞)=1 for Pmax =1.

5.13
Convergence is also faster when Pmax increases, independently of the chosen model. Yet, as Pmax increases, both RM and CM are distinct from TM. For larger Pmax, TM does not provide a satisfactory model to retrieve real convergence dynamics. As plotted on Figure 5, the relative error between RM dynamics and TM or CM (computed as ||ρRM-ρTM||/||ρRM|| and ||ρRM-ρCM||/||ρRM|| respectively) invalidates TM for large Pmax while it appears to approximate better RM for lower Pmax. Still, CM is a better yet not perfect approximation of RM, even if the discrepancy between CM and RM seems small (Figure 3).

Figure
Figure 5. Relative error between Threshold and Cascade model compared to Realistic Model

5.14
Certainly, the classical TM could be improved within this kind of protocol by distinguishing various classes of agent with distinct thresholds, as in Valente's study, thus plausibly yielding better results. Many other improvements of diffusion models could be thought of: for instance for the cascade model, a decreasing probability of persuasion with the number of interactions, such as p(n)=p/αn with α > 1 — see also (Kempe et al. 2003) for a generalized framework. Our aim is however not to extensively review and compare the behaviors of various classes of models, venturing into the vast collection of adoption mechanisms. Rather, we wish to show how classical assumptions like Cascade and Threshold Models may yield contrasted results; as it was with the topology: classical assumptions that scale-free features are sufficiently valid easily prove to be surprisingly erroneous with respect to realistic settings.

5.15
On the other hand, new studies may uncover radically distinct behaviors for which both TM and CM models may altogether be invalidated: Leskovec et al's data on book recommendation (2006), in particular, exhibit a decrease in the final adoption probability, indicating indeed that a higher number of interactions makes buying behavior less probable, which is thus inconsistent with the assumption that there exists an adoption probability at each step p(n)[7]. On the whole, we suggest that future investigations of diffusion mechanisms should begin with adequate empirical protocols, then propose adapted modeling frameworks.

* Conclusion

6.1
Even for the simplest transmission mechanisms, results on our two real-world social networks cast strong doubt, as counter-examples, on the efficiency of classical stylized network models. Secondly, even very basic yet credible variations between usual knowledge transmission mechanisms and realistic ones may yield sensibly distinct outputs.

6.2
More to the point,

6.3
Beyond these conclusions, our point is also strongly epistemological, by insisting that, when it matters, empirical knowledge diffusion mechanisms should be appraised before any modeling attempt and, similarly, underlying social network topologies should, if possible, constitute an empirical benchmark. Obviously it is way beyond the scope of this paper to carry such study even on the partial typology of topologies and knowledge transmission mechanisms we sketched out in the introduction, yet, in front of the great variability in diffusion phenomena between even the most canonical and standard ones, it could be suggested that extreme care should be foremost given to empirical measurements towards realistic assumptions.

6.4
Eventually, theoretical frameworks (scale-free networks or threshold models) for which parameters are empirically fitted (exponent of the power law or the threshold itself) could be driven a priori by real-data-based mechanisms and topologies, and the subsequent simulation-based comparisons and validations.

* Acknowledgements

We warmly thank Clémence Magnien and three anonymous referees for thoughtful advices. Research for this paper has been partly funded by CNRS and the University of Modena.

* Notes

1 More precisely, there is no epidemic threshold for a particular disease epidemic model (SIS, susceptible-infected-susceptible) on infinite scale-free networks. Note that this result does not hold for finite networks, nor for SIR (susceptible-infected-removed) models (May and Lloyd 2001; Eguiluz and Klemm 2002).

2 This is especially relevant if the timescale of diffusion is smaller than that of social network evolution (e.g. in the case of rumors, hypes, etc.), then the social network can be considered static.

3 Wang et al. (2003) show that their model of virus diffusion is more efficient than that of Pastor-Satorras and Vespignani (2001) on various topologies, including a real computer network, while actually not directly comparing how diversely their model performs between real-world and modeled topologies. Similarly, Wu et al. (2004) simulate information propagation on a real e-mail network; yet not estimating how different the behavior would be in other kinds of (scale-free) networks.

4 Freely available from http://www.pubmed.com. Additionally, the particular network data used in this paper is here.

5 Data freely available from http://www.theyrule.net, Additionaly, the particular network data used in this paper is here.

6 Similarly to Leskovec et al. (2006), Backstrom et al. (2006) have measured the propension to join a "LiveJournal" community as a function of the number of friends already present in the community.

7 It is unclear whether such feature may or may not be accounted for by the aggregation of different categories of products and/or agents.

* References

ABRAHAMSON, E. and Rosenkopf, L. (1997). Social Network Effects on the Extent of Innovation Diffusion: A Computer Simulation. Organization Science, 8(3), pp. 289-309.

AMARAL, L. A. N., Scala, A., Barthélémy, M. and Stanley, H. E. (2000). Classes of small-world networks. PNAS, 97(21), pp. 11149-11152.

AMBLARD, F. and Deffuant, G. (2004). The role of network topology on extremism propagation with the relative agreement opinion dynamics. Physica A, 343, pp. 725-738.

ANDERSON, R. M. and May, R. M. (1979). Population biology of infectious diseases. Nature, 280, pp. 361-367 & 455-461. Part I & II.

AXELROD, R. (1997). The Complexity of Cooperation: Agent-Based Models of Competition and Collaboration. Princeton, N.J.: Princeton University Press.

BACKSTROM, L., Huttenlocher, D., Kleinberg, J. and Lan, X. (2006). Group formation in large social networks: membership, growth, and evolution. In KDD '06: Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining. New York, NY, USA: ACM Press, pp. 44-54.

BALA, V. and Goyal, S. (1998). Learning from Neighbours. Review of Economic Studies, 65(3), pp. 595-621.

BARABSI, A.-L. and Albert, R. (1999). Emergence of Scaling in Random Networks. Science, 286, pp. 509-512.

BARABASI, A.-L., Jeong, H., Ravasz, R., Neda, Z., Vicsek, T. and Schubert, T. (2002). Evolution of the social network of scientific collaborations. Physica A, 311, pp. 590-614.

BARBOUR, A. and Mollison, D. (1990). Epidemics and random graphs. In J.-P. Gabriel, C. Lefevre and P. Picard (Eds.) Stochastic Processes in Epidemic Theory, Lecture Notes in Biomaths, 86. Springer, pp. 86-89.

BARTHELEMY, M., Barrat, A., Pastor-Satorras, R. and Vespignani, A. (2005). Dynamical patterns of epidemic outbreaks in complex heterogeneous networks. Journal of Theoretical Biology, 235, p. 275.

BOGUNA, M. and Pastor-Satorras, R. (2002). Epidemic spreading in correlated complex networks. Physical Review E, 66, p. 047104.

BOGUNA, M., Pastor-Satorras, R., Diaz-Guilera, A. and Arenas, A. (2004). Models of social networks based on social distance attachment. Physical Review E, 70, p. 056122.

BOLLOBAS, B. (1985). Random Graphs. London: Academic Press.

BURT, R. S. (1987). Social Contagion and Innovation: Cohesion Versus Structural Equivalence. American Journal of Sociology, 92(6), pp. 1287-1335.

COLEMAN, J., Katz, E. and Menzel, H. (1957). The Diffusion of an Innovation Among Physicians. Sociometry, 20(4), pp. 253-270.

COWAN, R. and Jonard, N. (2004). Network structure and the diffusion of knowledge. Journal of Economic Dynamics and Control, 28, pp. 1557-1575.

CREPEY, P., Alvarez, F. P. and BarthÈlemy, M. (2006). Epidemic variability in complex networks. Physical Review E, 73(4), p. 046131.

DEFFUANT, G. (2006). Comparing Extremism Propagation Patterns in Continuous Opinion Models. Journal of Artificial Societies and Social Simulation, 9(3), p. 8.

DEFFUANT, G., Amblard, F., Weisbuch, G. and Faure, T. (2002). How can extremism prevail? A study based on the relative agreement interaction model. Journal of Artificial Societies and Social Simulation, 5(4), p. 1.

DELGADO, J. (2002). Emergence of social conventions in complex networks. Artificial Intelligence, 141, pp. 171-185.

DEROIAN, F. (2002). Formation of social networks and diffusion of innovations. Research Policy, 31, pp. 835-846.

DOROGOVTSEV, S. N. and Mendes, J. F. F. (2003). Evolution of Networks: From Biological Nets to the Internet and WWW. Oxford University Press, Oxford.

EGUILUZ, V. M. and Klemm, K. (2002). Epidemic threshold in structured scale-free networks. Physical Review Letters, 89, p. 108701.

ELLISON, G. and Fudenberg, D. (1995). Word-of-Mouth Communication and Social Learning. Quarterly Journal of Economics, 110(1), pp. 93-125.

ERDÖS, P. and Rényi, A. (1959). On random graphs. Publicationes Mathematicae, 6, pp. 290-297.

GANESH, A., Massoulié, L. and Towsley, D. (2005). The effect of network topology on the spread of epidemics. In IEEE Infocom, vol. 2. pp. 1455-1466.

GILBERT, N., Pyka, A. and Ahrweiler, P. (2001). Innovation Networks — A Simulation Approach. Journal of Artificial Societies and Social Simulation, 4(3), p. 8.

GOLDENBERG, J., Libai, B. and Muller, E. (2001). Talk of the network: A complex systems look at the underlying process of word-of-mouth. Marketing Letters, 12(3), pp. 211-223.

GRANOVETTER, M. (1987). Threshold models of collective behavior. American Journal of Sociology, 83(6), pp. 1420-1443.

GRANOVETTER, M. S. (1973). The Strength of Weak Ties. The American Journal of Sociology, 78(6), pp. 1360-1380.

GRUHL, D., Guha, R., Liben-Nowell, D. and Tomkins, A. (2004). Information Diffusion Through Blogspace. In WWW2004: Proceedings of the 13th Intl Conf on World Wide Web. NYC, NY, USA, pp. 491-501.

GUILLAUME, J.-L. and Latapy, M. (2004). Bipartite structure of all complex networks. Information Processing Letters, 90(5), pp. 215-221.

GUIMERA, R., Uzzi, B., Spiro, J. and Amaral, L. A. N. (2005). Team Assembly Mechanisms Determine Collaboration Network Structure and Team Performance. Science, 308, pp. 697-702.

HETHCOTE, H. W. (2000). The Mathematics of Infectious Diseases. SIAM Review, 42(4), pp. 599-653.

HOLME, P., Edling, C. R. and Liljeros, F. (2004). Structure and time evolution of an Internet dating community. Social Networks, 26, pp. 155-174.

KEELING, M. J. and Eames, K. T. D. (2005). Networks and epidemics models. Journal of the Royal Society Interface, 2, pp. 295-307.

KEMPE, D., Kleinberg, J. and Tardos, E. (2003). Maximizing the spread of influence through a social network. In KDD '03: Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining. New York, NY, USA: ACM Press, pp. 137-146.

KEMPE, D., Kleinberg, J. and Tardos, E. (2005). Influential Nodes in a Diffusion Model for Social Networks. In ICALP, vol. 3580 of Lecture Notes in Computer Science. Springer, pp. 1127-1138.

KEMPE, D. and Kleinberg, J. M. (2002). Protocols and Impossibility Results for Gossip-Based Communication Mechanisms. In I. C. Society (Ed.) FOCS '02: Proceedings of the 43rd Symposium on Foundations of Computer Science. Washington, DC, USA, pp. 471-480.

KLEMM, K., Eguiluz, V. M., Toral, R. and Miguel, M. S. (2005). Globalization, polarization and cultural drift. Journal of Economic Dynamics and Control, 29, pp. 321-334.

KOSSINETS, G. and Watts, D. J. (2006). Empirical Analysis of an Evolving Social Network. Science, 311, pp. 88-90.

LESKOVEC, J., Adamic, L. A. and Huberman, B. A. (2006). The Dynamics of Viral Marketing. In ACM Conference on Electronic Commerce. pp. 228-237.

LEW, B. (2000). The Diffusion of Tractors on the Canadian Prairies: The Threshold Model and the Problem of Uncertainty. Explorations in Economic History, 37(2), pp. 189-216.

LIND, P. G., Gonzalez, M. C. and Herrmann, H. J. (2005). Cycles and clustering in bipartite networks. Physical Review E, 72, p. 056127.

LLOYD, A. L. and May, R. M. (2001). How Viruses Spread Among Computers and People. Science, 292(5520), pp. 1316-1317.

MAY, R. M. and Lloyd, A. L. (2001). Infection dynamics on scale-free networks. Physical Review E, 64(6), p. 066112.

MOLLOY, M. and Reed, B. (1995). A critical point for random graphs with a given degree sequence. Random Structures and Algorithms, 161(6), pp. 161-179.

MORRIS, S. (2000). Contagion. Review of Economic Studies, 67(1), pp. 57-78.

NEWMAN, M. E. J. (2002). Spread of Epidemic Disease on Networks. Physical Review E, 66(016128).

NEWMAN, M. E. J. (2003). Ego-centered networks and the ripple effect — or — Why all your friends are weird. Social Networks, 25, pp. 83-95.

NEWMAN, M. E. J. and Park, J. (2003). Why social networks are different from other types of networks. Physical Review E, 68(036122).

NEWMAN, M. E. J., Strogatz, S. and Watts, D. (2001). Random graphs with arbitrary degree distributions and their applications. Physical Review E, 64(026118).

PASTOR-SATORRAS, R. and Vespignani, A. (2001). Epidemic Spreading in Scale-Free Networks. Physical Review Letters, 86(14), pp. 3200-3203.

PASTOR-SATORRAS, R. and Vespignani, A. (2002). Epidemic dynamics in finite size scale-free networks. Physical Review E, 65, p. 035108.

REDNER, S. (2005). Citation Statistics from 110 Years of Physical Review. Physics Today, 58, pp. 49-54.

ROBERTSON, T. S. (1967). The Process of Innovation and the Diffusion of Innovation. Journal of Marketing, 31(1), pp. 14-19.

ROBINS, G. and Alexander, M. (2004). Small Worlds Among Interlocking Directors: Network Structure and Distance in Bipartite Graphs. Computational and Mathematical Organization Theory, 10, pp. 69-94.

ROGERS, E. M. (1976). New Product Adoption and Diffusion. The Journal of Consumer Research, 2(4), pp. 290-301.

ROGERS, E. M. (2003). Diffusion of Innovations, 5th Edition. Free Press.

SZENDRÖI, B. and Csányi, G. (2004). Polynomial epidemics and clustering in contact networks. Proceedings of the Royal Society London, B Biological sciences, 271, pp. S364-S366.

VALENTE, T. W. (1995). Network Models of the Diffusion of Innovations. Hampton Press.

VALENTE, T. W. (1996). Social network thresholds in the diffusion of innovations. Social Networks, 18, pp. 69-89.

WANG, Y., Chakrabarti, D., Wang, C. and Faloutsos, C. (2003). Epidemic Spreading in Real Networks: An Eigenvalue Viewpoint. In Proceedings of the 22nd Symposium on Reliable Distributed Systems (SRDS 2003). IEEE Computer Society, pp. 25-34.

WASSERMAN, S. and Faust, K. (1994). Social Network Analysis: Methods and Applications. Cambridge: Cambridge University Press.

WATTS, D. J. and Strogatz, S. H. (1998). Collective dynamics of "small-world" networks. Nature, 393, pp. 440-442.

WHITE, D. R., Kejzar, N., Tsallis, C., Farmer, D. and White, S. D. (2006). A generative model for feedback networks. Physical Review E, 73, p. 016119.

WU, F., Huberman, B. A., Adamic, L. A. and Tyler, J. R. (2004). Information Flow in Social Groups. Physica A, 337, pp. 327-335.

ZEGURA, E. W., Calvert, K. L. and Bhattacharjee, S. (1996). How to Model an Internetwork. In IEEE Infocom, vol. 2. San Francisco, CA: IEEE, pp. 594-602.

----

ButtonReturn to Contents of this issue

© Copyright Journal of Artificial Societies and Social Simulation, [2007]