DEIM: Bridging Community Structure and User Autonomy for Influence Maximization

Executive Summary

TL;DR: The DEIM algorithm (Dynamic algorithm based on cohesive Entropy for Influence Maximization) solves the classic "influence maximization" problem by narrowing the search space through overlapping community discovery and simulating selective user sharing. By introducing cohesive entropy, it moves beyond simple node connectivity to model the "social distance" that dictates real-world information flow.

Background: Influence Maximization (IM) is the cornerstone of viral marketing—finding the $K$ nodes that trigger the largest cascade. This paper sits at the intersection of Heuristic Optimization and Community Discovery, refining the efficiency of traditional greedy frameworks which are often too slow for modern social graphs.

The "Autonomy" Gap in Prior Work

Most IM algorithms operate on a mechanical assumption: if Node A is active and connected to Node B, it will attempt to influence B. In reality, users have autonomy. We share memes with close friends but professional news with colleagues. Prior SOTA (like IMM or original Greedy) often treats all edges equally or uses static probabilities, ignoring:

1. Local Aggregation: How community density stabilizes information flow.
2. Uncertainty: The subjective choice of sharing objects.

Methodology: The DEIM Framework

The authors break the problem into three logical stages:

1. Quantifying Distance with Cohesive Entropy

Instead of Euclidean distance, DEIM uses Relative Entropy (Kullback-Leibler divergence) to measure the discrepancy between the local structural information of two nodes.

• Insight: If two nodes "see" the network similarly (similar local degree distributions), they are socially closer.
• Cohesive Power: $C{P}_{uw}=H_u-\frac{1}{C{E}_{uw}}$. This represents the "force" of influence between users, where $H_u$ is self-entropy (information richness) and $CE$ is cohesive entropy.

2. CeCOPRA and Candidate Selection

To avoid searching the entire graph, DEIM identifies two types of critical nodes:

• Aggregation Bridges: Overlapping nodes that span multiple communities (the "cross-pollinators").
• Aggregation Focuses: High-degree nodes within non-overlapping areas (the "local leaders").

Figure: The process of narrowing the search space to high-potential regions.

3. Optional Dynamic Propagation (ODP)

This is where "autonomy" is modeled. A propagation control factor $\alpha$ acts as a threshold. A node $u$ only tries to influence $v$ if their cohesive power exceeds $\alpha$. This prevents "meaningless" diffusion attempts across weak or distrusted ties.

Experimental Performance

The DEIM algorithm was tested against Greedy, PageRank, and IMM across scales from 954 nodes (DBLP) to 334,863 nodes (Amazon).

Key Findings:

• Superior Spread: In almost all datasets, DEIM achieved a wider influence range than benchmarks, especially as the number of seeds increased.
• Efficiency: DEIM was significantly faster than the Greedy algorithm because it only evaluates nodes in the candidate set (CS), which is much smaller than the total node set $V$.
• Threshold Sensitivity: High values of $\alpha$ prune the search space effectively, whereas low values allow for deeper but noisier cascades.

Figure: DEIM (Red line) showing stable, high-performance influence spread across different network types.

Critical Analysis & Takeaways

The "Why it Works": DEIM succeeds because it respects the topological boundaries of a network. By focusing on community bridges and focuses, it ensures that the selected seeds are strategically placed to jump between clusters and saturate their local environments.

Limitations:

• Iterative Bottleneck: On massive scales like the Amazon dataset, the iterative nature of overlapping community discovery (CeCOPRA) still incurs significant overhead.
• Parameter Tuning: The $\alpha$ factor is sensitive; a poorly chosen $\alpha$ can prematurely terminate a potent cascade.

Future Outlook: Transitioning from iterative community detection to embedding-based (Graph Neural Networks) community discovery could potentially eliminate the time-efficiency bottleneck observed in large-scale graphs, making DEIM-like logic applicable to social networks with billions of edges.