Graph-Based Generalization of Galam Model: Convergence Time and Influential Nodes

Abstract

We study a graph-based generalization of the Galam opinion formation model. Consider a simple connected graph which represents a social network. Each node in the graph is colored either blue or white, which indicates a positive or negative opinion on a new product or a topic. In each discrete-time round, all nodes are assigned randomly to groups of different sizes, where the node(s) in each group form a clique in the underlying graph. All the nodes simultaneously update their color to the majority color in their group. If there is a tie, each node in the group chooses one of the two colors uniformly at random. Investigating the convergence time of the model, our experiments show that the convergence time is a logarithm function of the number of nodes for a complete graph and a quadratic function for a cycle graph. We also study the various strategies for selecting a set of seed nodes to maximize the final cascade of one of the two colors, motivated by viral marketing. We consider the algorithms where the seed nodes are selected based on the graph structure (nodes' centrality measures such as degree, betweenness, and closeness) and the individual's characteristics (activeness and stubbornness). We provide a comparison of such strategies by conducting experiments on different real-world and synthetic networks.

arXiv commentChange the color of one paragraph on page 5

References in corpus (9)

• Minority Opinion Spreading in Random Geometry
• The role of inflexible minorities in the breaking of democratic opinion dynamics
• Heterogeneous believes, segregation and extremism in the making of public opinions
• Opinion dynamics in a three-choice system
• A Survey on Influence Maximization: From an ML-Based Combinatorial Optimization
• Agent-based opinion formation modeling in social network: a perspective of social psychology
• Influence maximization in unknown social networks: Learning Policies for Effective Graph Sampling
• Majority dynamics and the median process: connections, convergence and some new conjectures
• Random Majority Opinion Diffusion: Stabilization Time, Absorbing States, and Influential Nodes