Past-aware game-theoretic centrality in complex contagion dynamics

In this paper, we introduce past-aware game-theoretic centrality, a class of centrality measures that captures the collaborative contribution of nodes in a network, accounting for both uncertain and certain collaborators. A general framework for computing standard game-theoretic centrality is extended to the past-aware case. As an application, we develop a new heuristic for different versions of the influence maximization problem in complex contagion, which models processes requiring reinforcement from multiple neighbors to spread. A computationally efficient explicit formula for the corresponding past-aware centrality score is derived, leading to scalable algorithms for identifying the most influential nodes, which in most cases outperform the standard greedy approach in both efficiency and solution quality.

• Publication year

  2025

• Venue

  arXiv.org

• Publication date

  2025-11-10

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.48550/arXiv.2511.07157arXiv 2511.07157
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Complex Contagion Influence Maximization: A Reinforcement Learning Approach

  2023cited by this paper
• Think Globally, Act Locally: On the Optimal Seeding for Nonsubmodular Influence Maximization

  2020cited by this paper
• Consensus and Information Cascades in Game-Theoretic Imitation Dynamics with Static and Dynamic Network Topologies

  2019cited by this paper
• Axiomatic Characterization of Game-Theoretic Centrality

  2018cited by this paper
• Complex Contagions: A Decade in Review

  2017cited by this paper
• Information cascades in complex networks

  2017cited by this paper
• Game-theoretic Network Centrality: A Review

  2017cited by this paper
• How Complex Contagions Spread Quickly in Preferential Attachment Models and Other Time-Evolving Networks

  2017cited by this paper
• Temporal Evolution of Social Innovation: What Matters?

  2016cited by this paper
• Don't Be Greedy: Leveraging Community Structure to Find High Quality Seed Sets for Influence Maximization

  2016cited by this paper
• The Network Data Repository with Interactive Graph Analytics and Visualization

  2015cited by this paper
• Efficient Computation of Semivalues for Game-Theoretic Network Centrality

  2015influential reference
• Influence Maximization in Near-Linear Time: A Martingale Approach

  2015cited by this paper
• Efficient Computation of the Shapley Value for Game-Theoretic Network Centrality

  2014influential reference
• How good is the Shapley value-based approach to the influence maximization problem?

  2014cited by this paper
• Complex Contagions in Kleinberg's Small World Model

  2014cited by this paper
• Complex contagion and the weakness of long ties in social networks: revisited

  2013cited by this paper
• Axioms for Centrality

  2013cited by this paper
• A new approach to betweenness centrality based on the Shapley Value

  2012cited by this paper
• Maximizing Social Influence in Nearly Optimal Time

  2012cited by this paper
• CELF++: optimizing the greedy algorithm for influence maximization in social networks

  2011cited by this paper
• Scalable Influence Maximization in Social Networks under the Linear Threshold Model

  2010cited by this paper
• Polynomial calculation of the Shapley value based on sampling

  2009cited by this paper
• Navigation in a small world

  2008cited by this paper
• Exploring Network Structure, Dynamics, and Function using NetworkX

  2008cited by this paper
• Determining the top-k nodes in social networks using the Shapley value

  2008cited by this paper
• Complex Contagions and the Weakness of Long Ties1

  2007cited by this paper
• Maximizing the spread of influence through a social network

  2003cited by this paper
• The centrality of groups and classes

  1999cited by this paper
• Concrete Mathematics, a Foundation for Computer Science

  1991cited by this paper
• A Value for n-person Games

  1988cited by this paper
• Value Theory Without Efficiency

  1981cited by this paper
• Threshold Models of Collective Behavior

  1978cited by this paper
• An analysis of approximations for maximizing submodular set functions—I

  1978influential reference

• No citing papers are available for this paper.