History Sensitive Cascade Model

History Sensitive Cascade Model

Yu Zhang (Trinity University, USA), Maksim Tsikhanovich (Bard College, USA) and Georgi Smilyanov (Bard College, USA)
Copyright: © 2011 |Pages: 14
DOI: 10.4018/jats.2011040104
OnDemand PDF Download:
List Price: $37.50


Diffusion is a process by which information, viruses, ideas, or new behavior spread over social networks. Traditional diffusion models are history insensitive, i.e. only giving activated nodes a one-time chance to activate each of its neighboring nodes with some probability. But history dependent interactions between people are often observed in the real world. This paper proposes the History Sensitive Cascade Model (HSCM), a model of information cascade through a network over time. The authors consider the “activation” problem of finding the probability of that a particular node receives information given that some nodes are initially informed. In this paper it is also proven that selecting a set of k nodes with greatest expected influence is NP-hard, and results from submodular functions are used to provide a greedy approximation algorithm with a 1–1/e–e lower bound, where e depends polynomially on the precision of the solution to the “activation” problem. Finally, experiments are performed comparing the greedy algorithm to three other approximation algorithms.
Article Preview


Network diffusion is the process by which some nodes in a network influence their neighboring nodes. Depending on different diffusion models (introduced in Related Work and Background), the nodes that are already active can influence their neighbors to become active as well.

Many real-world phenomena can be seen as network diffusion. Examples include the spread of infectious diseases (Gladwell, 2000), the spread of new ideas and technologies (Surowiecki, 2004), marketing (Domingos & Richardson, 2001; Wortman, 2008), technology transfers (Bass, 1969; Brow & Reinegen, 1987), computer virus transmission (Albert, Jeong, & Barabasi, 2000), and power systems (Watts, 2002). Classic instance of diffusion is found in marketing and experimental economics (Wortman, 2008; Kempe, Kleinberg, & Tardos, 2003, 2005). Consider a company that introduces a new product to the market. It might try to identify the consumers with the largest willingness to pay and sell it to them. But this might not guarantee profit maximization in the long run. Suppose instead that the company finds the people with most influence over some group (e.g. friends, family) and offers the product to them. Building on this plausible scenario, Domingos and Richardson (2001) introduce the notion of “network value” of a consumer and define it as the influence the consumer has on others in her social network:

“A customer whose intrinsic value is lower than the cost of marketing may in fact be worth marketing to when her network value is considered. Conversely, marketing to a profitable customer may be redundant if network effects already make her very likely to buy.”

A diffusion model is commonly used to answer the influence maximization problem: What is the best set of nodes to activate initially so that the number of active nodes in the end of the diffusion process is maximized? It is NP-Hard in all models we mention in Related Work and Background. However, approximation algorithms for obtaining reasonably good solutions exist.

As described by Kempe et al. (2003), there are two basic diffusion models: 1) the linear threshold model (Granovetter, 1978), in which a node becomes active if a predetermined fraction, called a threshold, of the node's neighbors are active, and 2) the independent cascade model (Culotta, 2003), whenever a node becomes active, it gets a one-time chance to activate each of its neighboring nodes with some probability. There is a rich literature in both models; especially the independent cascade model has gained much attention in present day. Goldenberg et al. (2001) simulate Word-of-Mouth information diffusion through strong ties among members of the same network and weak ties among individuals belonging to different network. They found the influence of weak ties on the information diffusion is almost as strong as the influence of strong ties. Cowan and Jonard (2004) study diffusion of knowledge in different network structures. They find that the performance of the system exhibits clear “small world” properties, in that the steady-state level of average knowledge is maximal when the structure is a small world (that is, when most connections are local, but roughly 10 percent of them are long distance). In viral marketing, Leskovec et al (2007) simulate information cascade in a real person-to-person recommendation network. They discover that the distribution of cascade sizes is approximately heavy-tailed; cascades tend to be shallow, but occasional large bursts of propagation can occur.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 9: 2 Issues (2017): Forthcoming, Available for Pre-Order
Volume 8: 1 Issue (2016): Forthcoming, Available for Pre-Order
Volume 7: 3 Issues (2015)
Volume 6: 4 Issues (2014)
Volume 5: 4 Issues (2013)
Volume 4: 4 Issues (2012)
Volume 3: 4 Issues (2011)
Volume 2: 4 Issues (2010)
Volume 1: 4 Issues (2009)
View Complete Journal Contents Listing