Source-linked AI summary
Opinion Maximization in Social Networks
Aristides Gionis, Evimaria Terzi, Panayiotis Tsaparas
TL;DR
The paper asks which individuals should be targeted so that social-opinion dynamics produce the maximum overall positive opinion in equilibrium. It formalizes this as CAMPAIGN, analyzes its complexity, develops exact and approximate algorithms, and finds scalable heuristics with performance comparable to greedy methods on very large graphs.
Problem
The paper studies which individuals should be convinced to adopt positive expressed opinions so that equilibrium dynamics maximize the network's overall positive opinion.
Method
The paper models opinion formation as best-response dynamics among rational individuals, formulates CAMPAIGN by fixing selected target nodes' expressed opinions to 1, and uses absorbing random walks to derive algorithms and theoretical results.
Results
The objective is submodular, enabling a (1 −1/e) greedy approximation, while proposed heuristics have comparable practical performance and scale to very large graphs.
Takeaways & Limitations
CAMPAIGN can be addressed with approximation and scalable heuristic algorithms rather than only expensive exact computation on large social graphs.
Takeaways & Limitations
The optimal-vector algorithm requires O(nmkI) time, which is superquadratic and therefore not scalable to very large datasets.
Abstract
from arXiv · showhide
The process of opinion formation through synthesis and contrast of different viewpoints has been the subject of many studies in economics and social sciences. Today, this process manifests itself also in online social networks and social media. The key characteristic of successful promotion campaigns is that they take into consideration such opinion-formation dynamics in order to create a overall favorable opinion about a specific information item, such as a person, a product, or an idea. In this paper, we adopt a well-established model for social-opinion dynamics and formalize the campaign-design problem as the problem of identifying a set of target individuals whose positive opinion about an information item will maximize the overall positive opinion for the item in the social network. We call this problem CAMPAIGN. We study the complexity of the CAMPAIGN problem, and design algorithms for solving it. Our experiments on real data demonstrate the efficiency and practical utility of our algorithms.
1 Introduction
The paper frames campaign design as selecting individuals whose positive expressed opinions maximize network-wide opinion under rational, equilibrium-based social dynamics. It develops theory and algorithms for this problem, including scalable heuristics and structural results.
- Motivation: Online campaigns must account for opinion formation through synthesis and contrast of viewpoints that propagate through social connections.The paper distinguishes opinion formation from simply spreading a binary action or product adoption.
- Campaign problem: Campaign selects k individuals whose expressed opinions are fixed at 1 so equilibrium opinions elsewhere are as positive as possible on average.Opinions are modeled numerically from zero, meaning negative, to one, meaning positive.
- Model: Unlike standard influence-maximization models, the framework treats individuals as rational agents whose opinions arise through best-response dynamics.The dynamics are inspired by classical economic opinion-formation models.
- Algorithms and theory: The analysis connects Campaign to absorbing random walks and shows its objective is submodular, enabling a greedy approximation within factor (1 −1/e).The paper uses this connection to study complexity and approximability.
- Algorithms and theory: Scalable heuristics perform comparably to the greedy algorithm in practice and handle very large graphs.The experiments evaluate these methods on real data.
- Problem variants: For undirected graphs, the network’s average opinion depends only on individuals’ internal opinions, not on network structure.This property arises in the discussion of two natural Campaign variants.
2 Related Work
The paper builds on repeated-averaging and selfish-opinion models while redirecting the objective from consensus, social cost, or product spread toward maximizing equilibrium positive inclination through targeted campaigns.
- Opinion dynamics: Earlier opinion-dynamics work studied repeated averaging and the conditions under which opinions converge to consensus.This paper also adopts repeated averaging but focuses on campaign design rather than consensus conditions.
- Selfish opinion formation: Bindel et al. use the same selfish opinion-dynamics model but study price of anarchy and network design to reduce equilibrium social cost.The present paper instead maximizes overall positive inclination toward an item.
- Influence maximization: Targeted-advertisement research generally maximizes product or idea spread under probabilistic propagation models.The paper shares the high-level goal of selecting individuals but addresses opinion formation instead of adoption.
3 Problem definition
The paper models expressed opinions as equilibrium compromises between persistent internal beliefs and neighbors’ weighted opinions, then defines Campaign as choosing fixed-positive targets to maximize aggregate opinion. It analyzes this equilibrium through absorbing random walks.
- Social graph: A social graph contains people as nodes, social-affinity edges, and nonnegative edge weights representing influence strength.The framework permits directed or undirected graphs unless stated otherwise.
- Opinion model: Each person has a persistent internal opinion s_i and an expressed opinion z_i shaped by the internal belief and neighbors’ expressed opinions.Both opinion types are real values in [0, 1].
- Opinion model: Selfish cost minimization makes each expressed opinion a weighted average of the person’s internal opinion and neighbors’ expressed opinions.The weights w_ij encode the relative importance of these influences.
- Equilibrium: Iterative updates converge to a unique Nash equilibrium in which no node can improve its cost by changing its expressed opinion.The equilibrium vector is the basis for evaluating campaign outcomes.
- Campaign definition: Overall opinion g(z) is proportional to the network’s average expressed opinion, and Campaign maximizes g(z | T) by fixing target nodes’ expressed opinions to 1.For non-target nodes, equilibrium opinions are recomputed under the fixed-target constraint.
- Random-walk connection: The equilibrium can be computed using an absorbing random walk on an augmented graph, where expected absorbed values reproduce opinion values.Transient states, absorbing states, transition probabilities, and absorption probabilities provide the computational representation.
4 Problem complexity
The Campaign problem is NP-hard, but its objective is monotone and submodular, enabling a constant-factor greedy approximation. The proof uses an absorbing-random-walk interpretation of opinion formation.
- Campaign is NP-hard, via a reduction from Vertex Cover on Regular Graphs.
- Because g(z | T) is monotone and submodular, greedy selection provides a constant-factor approximation to the optimum.
- The objective g(z | T) is monotone and submodular.
- The absorbing-walk interpretation expresses each node’s opinion as an expected opinion at the absorption point of a walk starting there.
- Adding a targeted node can only increase the objective because its maximum opinion value is fixed at 1; diminishing returns establish submodularity.
5 Algorithms
The paper combines greedy optimization with scalable heuristics for selecting campaign targets. Greedy offers approximation guarantees but is computationally expensive, motivating alternatives based on graph structure, opinions, and random walks.
- Estimating the Nash-equilibrium vector z: Matrix inversion for estimating g(z | T) is inefficient because it destroys the sparsity of the social graph.
- Estimating the Nash-equilibrium vector z: Power iteration estimates equilibrium opinions using neighbor averaging and requires O(mI) time, converging in about 50–100 iterations in the experiments.
- Greedy algorithm: Greedy adds the node producing the largest marginal increase and inherits a (1 − 1/e)-approximation guarantee for cardinality constraints.
- Greedy algorithm: O(nmkI) total time makes Greedy superquadratic and unsuitable for very large datasets.
- Scalable heuristics: Scalable heuristics are introduced because marginal-gain caching still requires O(n) power-iteration computations in the first iteration.
- Designing the heuristics: Greedy tends to select high-degree nodes, high free-degree nodes, and nodes with low internal opinion s_i.
- Heuristic algorithms: Degree sorts by decreasing in-degree in O(n log n), while FreeDegree selects iteratively by highest free degree in O(kn).
- Heuristic algorithms: RWR combines high degree with low internal opinion by using restart probabilities proportional to r_i = s_max − s_i.
6 Experimental evaluation
The experiments compare the proposed heuristics with Greedy on small and large real networks. Greedy performs best on small networks, while heuristic performance varies with network structure and internal-opinion patterns.
- The experiments compare the heuristics against Greedy and evaluate scalability using the objective g(z) as solution size |T| = k varies.
- Small networks: Greedy achieves the best results on small networks, while Degree, FreeDegree, and RWR perform similarly and come close.
- Small networks: Min-S and Min-Z perform worst on small networks, although both improve for larger k and Min-S can surpass some heuristics.
- Bibliographic datasets: RWR outperforms Degree and FreeDegree on bibsonomy because it incorporates both node degrees and internal-opinion values s_i.
- Bibliographic datasets: On dblp, the three heuristics perform almost identically because large degree correlates with small internal-opinion values, causing all to select high-degree nodes.
7 Problem variants
The paper considers variants that modify internal opinions or network edges rather than fixing expressed opinions. For undirected graphs, an invariant makes internal-opinion modification simple and edge modification ineffective for changing average opinion.
- The i-Campaign variant selects nodes whose internal opinions s_i are changed to 1, unlike Campaign, which fixes expressed opinions z_i.
- The i-Campaign optimization is computationally simpler than Campaign because it modifies internal rather than expressed opinions.
- For undirected graphs, the overall opinion g(z) is invariant to network structure and depends only on the internal opinions.
- Maximizing g(z) after modifying k internal opinions therefore means selecting the k smallest s_i values and setting them to 1.
- Changing edges cannot increase overall goodwill in the undirected-graph variant, although network structure still affects individuals’ opinions.
8 Conclusions
The paper formulates opinion-targeting as an equilibrium optimization problem, develops exact and approximate algorithms, and analyzes it through absorbing random walks. Experiments on real datasets demonstrate algorithm efficacy and structural effects on performance.
- The paper asks which individuals should be convinced to adopt positive opinions so the equilibrium network maximizes overall positive opinion.
- The authors study the problem’s computational complexity and propose algorithms that solve it exactly or approximately.
- Theoretical analysis and algorithm design rely on a connection between opinion dynamics and absorbing random walks.
- Experiments on real datasets demonstrate algorithm efficacy and show that underlying network structure affects performance.
A Proof of Theorem 4.1
The proof reduces Vertex Cover on Regular Graphs to the decision version of Campaign. It uses absorbing random walks to relate Campaign values to absorption probabilities and establish the reduction’s threshold behavior.
- The theorem is proved by reducing Vertex Cover on Regular Graphs to the decision version of Campaign.
- A Campaign decision instance asks whether a set T of at most k nodes achieves g(z | T) ≥ θ.
- The reduction sets the graph equal to the regular-graph instance, assigns every internal opinion s_i = 0, sets k = K, and chooses θ = (n−k)d/(d+1).
- With selected nodes absorbing at value 1, each other node’s expressed value equals the probability that a random walk starting there is absorbed in T.
- If T is a vertex cover, each non-absorbing vertex connects to d absorbing selected nodes and one absorbing auxiliary node, yielding g(z | T) < (n − k)d/(d+1).
B Proof of Lemma 4.2
The proof models expressed opinions through absorbing random walks and shows that adding target nodes cannot decrease the objective, while marginal gains diminish as the target set grows.
- Random-walk formulation: The vector z is interpreted through random walks on an augmented graph with absorbing nodes whose values are fixed opinions.For target set T, original absorbing nodes retain internal opinions, while selected targets receive expressed opinion 1.
- Random-walk formulation: For a target node i, absorption occurs at i with probability 1, so its expressed opinion value is z(i | T) = 1.
- Monotonicity: Adding a non-absorbing node j to T changes absorption probabilities by separating paths absorbed at j from paths absorbed at other nodes.The decomposition combines the probability of reaching j first with a new walk from j to an absorbing node.
- Monotonicity: The objective g(z | T) is monotone with respect to the target set T.
- Submodularity: The marginal gain from adding j decreases when moving from T to a superset T′, establishing that g(z | T) is submodular.The proof uses two absorbing random walks and the fact that increasing absorbing nodes lowers the probability of absorption at a specific node.
C Graph invariants
The graph invariant relates non-absorbing opinion values to absorbing-node values using only boundary edges, yielding consequences for opinion modification and social-graph rewiring.
- Invariant setup: The invariant is established for an undirected weighted graph partitioned into non-absorbing nodes U and absorbing nodes B.Absorbing nodes carry values that represent either internal opinions or fixed expressed opinions.
- General invariant: The general invariant relates zi and fj through edge weights wij on edges between absorbing and non-absorbing nodes.Edges between non-absorbing nodes do not enter the invariant.
- Specialized invariant: In the paper’s augmented graphs, each user connects to one absorbing node carrying that user’s internal opinion, with equal absorbing-edge weight w.
- Implications: For i-Campaign, maximizing g(z) by changing only internal opinions selects the k smallest si values and sets them to 1.This observation motivates the Min-S algorithm.
- Implications: Adding or removing social-graph edges cannot change g(z) when internal and expressed opinion values remain fixed.The reason is that g(z) is independent of the non-absorbing-edge structure EU.