Seed Selection for Spread of Influence in Social Networks: Temporal vs. Static Approach

Abstract

The problem of finding optimal set of users for influencing others in the social network has been widely studied. Because it is NP-hard, some heuristics were proposed to find sub-optimal solutions. Still, one of the commonly used assumption is the one that seeds are chosen on the static network, not the dynamic one. This static approach is in fact far from the real-world networks, where new nodes may appear and old ones dynamically disappear in course of time. The main purpose of this paper is to analyse how the results of one of the typical models for spread of influence - linear threshold - differ depending on the strategy of building the social network used later for choosing seeds. To show the impact of network creation strategy on the final number of influenced nodes - outcome of spread of influence, the results for three approaches were studied: one static and two temporal with different granularities, i.e. various number of time windows. Social networks for each time window encapsulated dynamic changes in the network structure. Calculation of various node structural measures like degree or betweenness respected these changes by means of forgetting mechanism - more recent data had greater influence on node measure values. These measures were, in turn, used for node ranking and their selection for seeding. All concepts were applied to experimental verification on five real datasets. The results revealed that temporal approach is always better than static and the higher granularity in the temporal social network while seeding, the more finally influenced nodes. Additionally, outdegree measure with exponential forgetting typically outperformed other time-dependent structural measures, if used for seed candidate ranking.

References in corpus (3)

• Quantifying social group evolution
• Small But Slow World: How Network Topology and Burstiness Slow Down Spreading
• Quantifying Social Network Dynamics

Cited by in corpus (8)

• A picture is worth a thousand words: an empirical study on the influence of content visibility on diffusion processes within a virtual world
• Influence maximization on temporal networks
• Effective Influence Spreading in Temporal Networks with Sequential Seeding
• Seeds Buffering for Information Spreading Processes
• Effective submodularity of influence maximization on temporal networks
• Nodal heterogeneity can induce ghost triadic effects in relational event models
• Rank-Refining Seed Selection Methods for Budget Constrained Influence Maximisation in Multilayer Networks under Linear Threshold Model
• Network Diffusion -- Framework to Simulate Spreading Processes in Complex Networks