PaperlayerView exact revision on arXiv

Source-linked AI summary

Evolutionary Dynamics of Information Diffusion over Social Networks

Chunxiao Jiang, Yan Chen, K. J. Ray Liu

arXiv:1312.0317v1cs.SIphysics.soc-ph

TL;DR

The paper addresses how user decisions and interactions shape information diffusion in large, changing social networks, beyond empirical machine-learning analyses. It develops an evolutionary game-theoretic model across several network types and finds scale-free, equivalent dynamics at sufficiently large scale, with simulations and Twitter data supporting the framework.

  • Problem

    Existing diffusion analyses often depend on fixed empirical datasets and network structures while ignoring users’ actions and decision making.

  • Method

    The paper models information forwarding as an evolutionary game and derives diffusion dynamics for complete, uniform-degree, and non-uniform-degree networks.

  • Results

    Theoretical dynamics were consistent with synthetic-network and Facebook simulations, while the model fit and predicted real-world Twitter hashtag diffusion.

  • Takeaways & Limitations

    The framework links information diffusion to users’ interactions and decision making while describing diffusion across multiple social-network structures.

Abstract

from arXiv · show

Current social networks are of extremely large-scale generating tremendous information flows at every moment. How information diffuse over social networks has attracted much attention from both industry and academics. Most of the existing works on information diffusion analysis are based on machine learning methods focusing on social network structure analysis and empirical data mining. However, the dynamics of information diffusion, which are heavily influenced by network users' decisions, actions and their socio-economic interactions, is generally ignored by most of existing works. In this paper, we propose an evolutionary game theoretic framework to model the dynamic information diffusion process in social networks. Specifically, we derive the information diffusion dynamics in complete networks, uniform degree and non-uniform degree networks, with the highlight of two special networks, Erdős-Rényi random network and the Barabási-Albert scale-free network. We find that the dynamics of information diffusion over these three kinds of networks are scale-free and the same with each other when the network scale is sufficiently large. To verify our theoretical analysis, we perform simulations for the information diffusion over synthetic networks and real-world Facebook networks. Moreover, we also conduct experiment on Twitter hashtags dataset, which shows that the proposed game theoretic model can well fit and predict the information diffusion over real social networks.

I. INTRODUCTION

The paper addresses information diffusion in large social networks, where users’ decisions and interactions shape whether information spreads or disappears. It proposes evolutionary game theory to model diffusion dynamics beyond dataset-dependent machine-learning analyses.

  • Motivation: Large social networks generate substantial information flows, making diffusion dynamics important to study and predict.The paper cites Facebook’s nearly one billion active users in September 2012 and 175 million daily tweets throughout 2012.
  • Motivation: Diffusion outcomes depend on users’ interests, social interactions, mutual influence, and word-of-mouth effects.
  • Applications: Twitter hashtag dynamics illustrate how diffusion analysis can inform applications such as advertising strategy and political approval estimation.
  • Research gap: Existing machine-learning analyses rely on empirical datasets and network structures that may not generalize to changing future networks.They also generally ignore users’ actions and decision making during diffusion.
  • Approach: Evolutionary game theory models users as interacting decision makers whose forwarding strategies evolve through learning and influence.The framework treats a user with new information as analogous to a mutant spreading through a population.
  • Scope and contribution: The paper derives diffusion dynamics for complete, uniform-degree, and non-uniform-degree networks, including Erdős-Rényi and Barabási-Albert networks.It reports that these dynamics become scale-free and equivalent when network scale is sufficiently large.

B. Evolutionary Game Formulation

The formulation maps social-network information forwarding onto an evolutionary game, with users’ strategies and payoffs evolving through interactions. For complete networks, replicator dynamics describe how forwarding changes according to relative fitness and yield scale-free population dynamics.

  • Evolutionary game formulation: Users form the players and population, while forwarding or not forwarding information are the two available strategies.
  • Evolutionary game formulation: Users’ payoffs combine forwarding costs and rewards, with normalized payoff values varying across application scenarios.The paper assumes a symmetric payoff structure and allows different payoff orderings for different information contexts.
  • Complete networks: In a complete network, each user can interact with every other user, and forwarding decisions evolve through observed strategies and fitness.
  • Complete networks: The network state uses xf for the forwarding proportion, with Ψf, Ψn, and Ψ denoting forwarding, non-forwarding, and population-average fitness.
  • Complete networks: The forwarding population increases when its average fitness exceeds the population average, whereas non-forwarding increases under the opposite condition.
  • Complete networks: Theorem 1 characterizes complete-network population dynamics, with selection intensity α controlling the speed of observation and strategy adjustment.
  • Complete networks: The complete-network diffusion equation is scale-free because it depends on the initial forwarding state and payoff values, not network size.

III. DIFFUSION DYNAMICS OVER UNIFORM DEGREE NETWORKS

Graphical evolutionary game theory extends diffusion modeling to incomplete social networks by incorporating topology and local strategy correlations. Uniform-degree analysis tracks population, relationship, and influence dynamics under strategy-update rules such as BD.

  • Graphical formulation: Graphical evolutionary game theory adds a graph structure to evolutionary games for populations with incomplete connections.
  • Graphical formulation: Graphical replicator dynamics are commonly analyzed with birth-death, death-birth, and imitation strategy-update rules.
  • Uniform-degree networks: Uniform-degree analysis considers an N-user homogeneous graph with general degree k and forwarding proportion xf as the global diffusion state.
  • Uniform-degree networks: Limited dispersal creates clusters of users adopting the same strategy, so local neighbor states cannot generally be inferred from global xf.
  • Uniform-degree networks: The model tracks population dynamics, relationship dynamics of global edge states, and influence dynamics of local neighbor states.
  • Uniform-degree networks: Under BD updating, a fitness-proportional user reproduces and one neighbor adopts that user’s forwarding or non-forwarding strategy.
  • Uniform-degree networks: The BD process represents information diffusion as users’ strategies changing through neighbor influence under weak selection.

1) Influence Dynamics and Relationship Dynamics:

The analysis separates local influence and relationship dynamics from global population change in networked diffusion. Under weak selection, local states converge faster, enabling a two-timescale treatment of the global state.

  • Influence dynamics: A user may abandon forwarding after observing little attention to previously forwarded information.
  • Relationship dynamics: Each time slot contains N sub-slots, with one strategy update occurring per sub-slot.
  • Relationship dynamics: Expected changes in global edge states describe relationship dynamics, with Nk/2 representing the network’s total number of edges.
  • Influence dynamics: Local network states change at order 1 while the global state changes at order α under weak selection.
  • Influence dynamics: This rate difference creates two timescales in which local states reach equilibrium faster than the global network state changes.
  • Population dynamics: After deriving local equilibria, the analysis obtains global population dynamics from users’ strategy updates.

2) Population Dynamics:

The paper derives population dynamics for information diffusion on uniform-degree networks under evolutionary strategy updates. These dynamics depend on initial state, payoff values, and network degree, and become equivalent across update rules at sufficiently large degree.

  • A strategy change from Sn to Sf increases the global forwarding state xf, whereas the reverse change decreases it.
  • Theorem 2 describes information-diffusion population dynamics on uniform-degree networks under the Birth-Death strategy update rule.
  • The dynamics depend on xf(0), payoff-matrix values, and network degree, but not network scale, yielding a scale-free property.
  • Uniform-degree dynamics have the same form as complete-network dynamics because sufficiently many neighbors approximate complete-network influence.
  • When network degree is sufficiently large, Birth-Death, Death-Birth, and Imitation update rules produce equivalent population dynamics.

A. General Case

The paper extends its evolutionary-game analysis to networks with non-uniform degree distributions and examines Erdős-Rényi and Barabási-Albert special cases. The resulting dynamics retain the general form, while scale-free behavior depends on network structure and sufficiently large network scale.

  • General Case: The derivation follows the uniform-degree case but takes expectations over different user-degree distributions to obtain population dynamics.
  • General Case: Non-uniform networks retain a form similar to the complete- and uniform-degree cases, but the scale-free property may not hold because a k^2 expectation can contain network-scale information.
  • Two Special Cases: Erdős-Rényi dynamics have the same form as complete- and sufficiently high-degree uniform networks, and become scale-free under the stated large-network approximation.
  • Two Special Cases: Barabási-Albert dynamics also share the complete-network form and become scale-free when the model parameters satisfy the stated approximation.

V. EXPERIMENTS

Experiments compare theoretical information-diffusion dynamics with simulations on synthetic networks and a real-world Facebook network. The simulations generally agree with theory, while payoff ordering produces distinct diffusion outcomes and degree dependence explains small gaps.

  • Synthetic Networks and Real-World Network: The experiments simulate information diffusion on complete, uniform-degree, Erdős-Rényi, and Barabási-Albert networks using multiple payoff matrices.
  • Synthetic Networks and Real-World Network: All complete- and uniform-degree simulation results agree with theoretical results across the tested payoff settings.
  • Synthetic Networks and Real-World Network: When uff > ufn > unn, forwarding converges toward universal adoption, whereas unn > ufn > uff produces no forwarding.
  • Synthetic Networks and Real-World Network: For intermediate payoff orderings, more than half of users forward when uff > unn, and fewer than half forward when uff < unn.
  • Synthetic Networks and Real-World Network: Erdős-Rényi and Barabási-Albert simulations agree well with theory, with a Barabási-Albert gap attributed to neglected weak dependence between global state and degree.
  • Synthetic Networks and Real-World Network: Facebook simulations also match theoretical results, with small gaps mainly attributed to neglected dependence between global network state and degree.

B. Twitter Hashtags Dataset Evaluation

The Twitter hashtag evaluation fits the evolutionary game model to observed diffusion curves, estimates payoff parameters, compares it with a data-mining model, and tests prediction from partial data.

  • Parameter estimation: The model estimates payoff-matrix parameters by fitting its closed-form diffusion dynamics to hourly mention-time series for 1,000 highly mentioned Twitter hashtags.The dataset contains the 1,000 hashtags with the highest total mention counts among 6 million hashtags from June to December 2009.
  • Curve fitting: Least-squares fits for four hashtags closely match normalized cumulative mention times, supporting accurate prediction of the global network state.The fitted curves use normalized hourly mention counts accumulated over time.
  • Popularity interpretation: The payoff difference uff − unn measures hashtag popularity: positive values indicate high popularity, whereas negative values indicate low popularity.The paper uses this difference to categorize hashtags and potentially identify groups of users with shared interests.
  • Comparison: The proposed model fits real-world diffusion dynamics better than the compared data-mining method because it incorporates users’ interactions and decision-making behavior.The comparison normalizes hourly hashtag mention times to [0, 1] and compares them with the model’s diffusion derivative.
  • Prediction: Using only 25% of the #googlewave data to estimate the payoff matrix, the model predicts diffusion effectively through time index 40.The experiment evaluates whether estimated payoffs can reproduce the remaining diffusion dynamics.

VI. CONCLUSION

The paper develops an evolutionary game-theoretic model of information diffusion across several network types and validates it through synthetic, Facebook, and Twitter experiments.

  • Framework: The study formulates information diffusion over social networks using evolutionary game theory with players, strategies, and payoff matrices.It explicitly links the evolutionary-game formulation to information diffusion.
  • Network analysis: The analysis derives diffusion dynamics for complete, uniform-degree, and non-uniform-degree networks, including Erdős-Rényi and Barabási-Albert networks.These network classes are treated as the paper’s principal theoretical cases.
  • Validation: Experiments on synthetic networks, real-world Facebook networks, and Twitter hashtags produced results consistent with the corresponding theoretical analysis.The paper presents this consistency as evidence that the proposed model is effective and practical for modeling information diffusion.

APPENDIX A PROOF OF THEOREM 2

The appendix derives global-state diffusion dynamics under the BD strategy-update rule by analyzing state-increase and state-decrease events and applying weak-selection approximations.

  • State increase: Under the BD rule, the global state increases by 1/N when an Sf user reproduces and replaces a neighboring Sn user.The replacement probability depends on the fraction of neighboring users adopting Sn.
  • State decrease: The dual event decreases the global state by 1/N when an Sn user reproduces and replaces a neighboring Sf user.The appendix identifies this as the expected probability of the global network state decreasing 1/N.
  • Expected dynamics: Assuming N unit periods per time slot, the expected one-slot change combines the probabilities of the two opposing state transitions.Only one update occurs in each sub-slot.
  • Approximation: When selection is weak, α is sufficiently small and U is dominated by 1, enabling approximation of the global-state dynamics using local equilibria.The approximation substitutes the local equilibria into the transition expression.

APPENDIX B PROOF OF THEOREM 3

The appendix extends the diffusion-dynamics derivation to the DB strategy-update rule, using stable influence equilibria, dual transition analysis, and approximations analogous to the BD case.

  • Proof strategy: The proof extends the analysis to DB and IM rules and compares their approximated diffusion dynamics when network degree is sufficiently large.The stated goal is to establish equivalence across the three strategy-update rules under that condition.
  • DB derivation: For the DB rule, the stable point of influence dynamics is the same as under the BD rule, so its detailed derivation is omitted.The population-dynamics analyses are described as dual because the DB and BD rules are dual.
  • Transition analysis: The DB proof analyzes the two opposing state-transition cases and combines their expected probabilities to obtain the one-slot change in global state.The resulting expression is then approximated using the local equilibrium and the appendix’s analogous approximation.
  • Result: The resulting expression is identified as the diffusion dynamics under the DB strategy-update rule.The appendix labels the derived expression as the DB diffusion dynamics.

B. Diffusion Dynamics under IM Rule

Under the IM strategy update rule, the diffusion dynamics can be derived similarly to the DB rule while accounting for users who retain their strategies. For non-uniform degree networks, the analysis averages local dynamics over degree distributions and yields corresponding equilibrium and global dynamics.

  • IM strategy update rule: The IM-rule diffusion dynamics are derived by incorporating the probability that a user imitates their own strategy and remains unchanged.The IM and DB rules differ because IM permits users to imitate their own strategy.
  • Equivalence of update rules: The BD, DB, and IM update rules have the same diffusion-dynamics expression, differing only in their coefficients.This comparison is stated for the three strategy update rules represented by equations (50), (55), and (56).
  • Equivalence of update rules: When network degree k is sufficiently large, all three coefficients tend to α, making the update rules equivalent on uniform-degree networks.The equivalence follows from the convergence of the coefficients to α as k increases.
  • Non-uniform degree networks: For non-uniform networks, the replaced neighbor’s degree follows a distribution, and a randomly selected endpoint has degree distribution proportional to kλ(k), not λ(k).The degree-weighted distribution reflects selection through network pairs.
  • Non-uniform degree networks: The non-uniform analysis computes local and global diffusion dynamics by taking expectations over user degrees and adjusting the edge-count denominator.The local dynamics use expectations over the replaced neighbor’s degree, while global dynamics average over the selected user’s degree distribution.
  • Non-uniform degree networks: The resulting non-uniform degree analysis specifies both a local equilibrium and global diffusion dynamics.The local equilibrium is stated separately from the global dynamics obtained by averaging over users’ degrees.
Loading 1312.0317v1…