Article Preview
TopIntroduction
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.