CINEMA: Bridging Social Psychology and Influence Maximization via Conformity-Awareness

TL;DR

Influence Maximization (IM) has long focused on finding "who is powerful," but it has largely ignored "who is willing to follow." This paper introduces CINEMA (Conformity-aware INfluEnce MAximization), a framework that integrates human conformity into the information cascade. By combining a novel C² Cascade Model with a partitioning-based greedy algorithm, the authors achieve superior seed set quality and scalability, outperforming traditional SOTA methods on networks with millions of individuals.

Problem & Motivation: The Missing Link in Influence

In the classic IM problem, we seek $k$ seed nodes to maximize the "spread." However, current models like Independent Cascade (IC) or Linear Threshold (LT) treat nodes as passive receivers.

The Insight: Social psychology (Asch, 1951) proves humans conform to group beliefs regardless of the source's objective correctness. Standard IM assumes influence is source-centric $P(uov)=f(Influenc{e}_u)$. CINEMA argues it is a dyadic interplay: $P(uov)=f(Influenc{e}_u,Conformit{y}_v)$.

Furthermore, global greedy algorithms are computationally "heavy." Updating the marginal gain for every node in a million-node graph after every seed selection is a bottleneck that prevents these algorithms from scaling to real-world datasets like LiveJournal.

Methodology: The C² Model and CINEMA Architecture

1. Quantifying Influence and Conformity (CASINO)

Before maximizaton, the authors use the CASINO algorithm to compute values for every node. Unlike prior work requiring action logs, CASINO uses Signed Social Networks.

• Influence Index ($\Phi$): Increases when people who trust you have high conformity.
• Conformity Index ($\Omega$): Increases when you trust people with high influence.

This recursive relationship is solved iteratively, much like PageRank, but uniquely identifies "influence-biased" vs. "conformity-biased" users.

2. The C² and C³ Cascade Models

The core of the methodology is the Conformity-aware Cascade (C²) model. The probability of node $v$ being activated by $u$ is: $P_{u,v}=\Phi (u)\cdot \Omega (v)$ For context-aware networks (like Twitter topics), the C³ model applies topic-specific indices.

3. Scaling via MAG-list and Partitioning

To solve the scalability issue, CINEMA implements a "Divide and Conquer" strategy:

1. Graph Partitioning: Segregate the network into non-overlapping subnetworks.
2. MAG-list (MArginal Gain list): A data structure that stores only the "top" candidate from each partition.
3. On-demand Updates: Instead of updating all nodes, CINEMA only re-calculates the marginal gains within a specific subnetwork when its top candidate is picked from the MAG-list.

Fig 1. Graph representation of the proposed interplay between influencers and conformers.

Experiments & Results: Quality vs. Efficiency

The authors evaluated CINEMA against standard greedy and heuristic models (MixGreedy, PMIA, DegreeDiscount) across datasets like Hep, Wiki, and LiveJournal.

Superior Influence Spread

The C² model proved that targeting highly conformant neighbors of influencers yields a larger total spread than just targeting "high-degree" nodes.

• Result: CINEMA-C² consistently outperformed conformity-unaware heuristics, with the gap widening as the seed set size increased.
• Context Awareness: On Twitter data, the C³ variant (topic-specific) drastically outperformed general models because it could distinguish "who influences whom about iPad vs. Politics."

Scalability and Distributed Power

While MixGreedy failed on the LiveJournal dataset (10M nodes, 34M edges) due to memory overflow, CINEMA’s partitioning allowed it to handle the graph with ease.

Fig 2. Comparative influence spread results showing CINEMA's dominance over traditional heuristic and greedy methods.

By using MapReduce, the authors speed up the process even further. Distributing partitions across 10 slave machines reduced the selection time from over 80 hours to roughly 5.8 hours.

Critical Analysis & Conclusion

The Takeaway: CINEMA successfully grounds Influence Maximization in social psychology. It proves that "Influence" is not a solo attribute of a node but a result of the social force between an influencer and a conformer.

Limitations:

• The model relies on sentiment analysis to determine edge signs. If the text mining (LingPipe) is inaccurate, the indices fluctuate.
• Partitioning inherently "cuts" edges. While the authors prove the loss is minimal, extreme fragmentation could lead to suboptimal global seeds in highly interconnected graphs.

Future Outlook: This work paves the way for "Personas" in AI-driven marketing. Future models might extend this to multi-stage cascades where conformity changes over time as a topic becomes "viral," reflecting the dynamic nature of human groupthink.