CINEMA: Bridging Social Psychology and Greedy Optimization for Influence Maximization

Executive Summary

TL;DR: CINEMA is a high-performance greedy algorithm that redefines the Influence Maximization (IM) problem by introducing a "conformity-aware" perspective. By combining a novel $c^2$ cascade model with a network-partitioning architecture, it achieves superior seed quality and scalability compared to traditional models like IC or LT.

Background Positioning: This work bridges the gap between social psychology and discrete optimization. It moves beyond the "influence-only" paradigm and provides a scalable, partitioning-based framework that makes rigorous greedy algorithms viable for networks with millions of nodes—a space previously dominated by faster but less reliable heuristics.

The Missing Variable: Why Conformity Matters

Most IM research focuses on a node's "power" to influence. However, as social psychologists like Solomon Asch famously demonstrated, influence is a two-way street. A "powerful" influencer (e.g., a celebrity) might fail to move an audience with low conformity (the inclination to adapt to others' beliefs).

The paper identifies two critical pain points in SOTA work:

1. Conformity-Obliviousness: Existing models ignore the target's predisposition, leading to seeds that look good on paper but fail in real-world scenarios.
2. The Scalability Wall: Standard greedy approaches (like CELF or MixGreedy) suffer from the "curse of global updates," where every seed selection requires reconsidering the entire network's marginal gains.

Methodology: The $c^2$ Model and Partitioned Optimization

1. The Conformity-Aware Cascade ($c^2$) Model

The authors redefine propagation probability. In the $c^2$ model, the probability of node $u$ influencing node $v$ is proportional to the product of $u$'s influence $(\Phi )$ and $v$'s conformity $(\Omega )$: $P(uov)=\Phi (u)\cdot \Omega (v)$ This ensures that influence only flows easily when the source is powerful and the target is receptive.

2. The MAG-list Architecture

To solve the scalability issue, CINEMA partitions the graph $G$ into subnetworks $\Gamma$.

• $cog$-sublists: Each subnetwork maintains its own sorted list of nodes based on local marginal gains.
• MAG-list: A global list containing only the "best" node from each subnetwork.

Figure: The hierarchical relationship between the global MAG-list and local component gain sublists.

By selecting seeds through this hierarchy, CINEMA limits property updates to the specific subnetwork where a node was chosen, fundamentally reducing the computational complexity from $O(n)$ to $O(n^{\prime })$, where $n^{\prime }$ is the size of the largest partition.

Experiments & Results

The authors validated CINEMA on academic collaboration networks (Phy, Hep) and the massive Wiki-talk dataset.

Performance Gains

CINEMA-c² consistently generated 30-60% better influence spread than traditional heuristics. Even when compared to heavy-duty greedy algorithms like MixGreedy, CINEMA maintained a quality lead by leveraging the more realistic $c^2$ propagation model.

Figure: Influence spread of CINEMA compared to various baselines. Note the significant gap over heuristic-based methods (LDAG, SimPath).

Efficiency and Scaling

While the "On-demand Update" strategy ensures that marginal gains are only recalculated when a node is a candidate for the seed set, the partitioning strategy allows the algorithm to handle the Wiki-talk network (2.3M nodes, 5M edges) efficiently. The study shows that as the number of partitions ($\ell$) increases, the execution time decreases significantly without a drastic loss in seed quality.

Critical Analysis & Conclusion

Takeaway

The core contribution of CINEMA is the realization that locality matters. Social influence is often a community-level phenomenon. By partitioning the network, we don't just gain speed; we align the algorithm with the natural "cluster-like" structure of human organizations.

Limitations

• Edge Cuts: Partitioning inevitably removes cross-component edges. While the authors argue these are "weak ties" in many cases, in extremely dense networks, this could lead to an underestimation of global influence.
• Data Requirement: Calculating $\Phi$ and $\Omega$ indices requires sentiment-aware edges (positive/negative), which may not be present in all raw social datasets.

Future Outlook

CINEMA’s architecture is "embarrassingly parallel." The move to a distributed platform (e.g., Spark/GraphX) where each subnetwork is handled by a different worker node is the natural next step, potentially allowing for IM on billion-node graphs in near real-time.