IICEA: Rethinking Budgeted Influence Maximization via Local and Global Insights

    ## TL;DR
    In social networks, "influence" isn't free. The **Budgeted Influence Maximization (BIM)** problem challenges us to find the most influential node set without exceeding a financial cap. This paper presents **IICEA**, an evolutionary algorithm that uses a unique hybrid indicator—combining local neighbors and global overlapping communities—to pick the best "seeds" more accurately than traditional degree-based or purely greedy methods.

    ## Background: The Hidden Cost of Influence
    Most classic Influence Maximization models assume every user costs the same to "activate." In the real world, an A-list celebrity costs more than a local influencer. While greedy algorithms provide theoretical guarantees, they are painfully slow on massive networks. Conversely, fast heuristics often miss nodes that sit at the intersection of multiple social circles—the "bridge makers" who are the true keys to virality.

    ## Methodology: The Local-Global Dual Perspective
    The core innovation of IICEA is its **Influence Indicator (I)**. Instead of just looking at how many friends a person has (Degree), it measures:
    1.  **Local Influence ($I_l$):** Direct and indirect effects on one-hop and two-hop neighbors.
    2.  **Global Influence ($I_g$):** How a node sits within overlapping communities. This considers how easily a node can spread a message *inside* its community ($I_{intra}$) and *between* different communities ($I_{inter}$).

    ![IICEA Overall Framework](https://cdn.atominnolab.com/wisdoc/images/20260527-56fc6bfb-a651-465c-baf5-d3ad56fb9cda/page_004_block_021.png)

    ### The Evolutionary Engine
    IICEA isn't just a static formula; it's a dynamic search process. It uses:
    *   **Adaptive Mutation & Crossover**: Uses the "Influence-Cost ratio" (IC) to decide which nodes to keep or replace. High-value, low-cost nodes are prioritized.
    *   **Repairment Strategy**: If a seed set goes over budget, the algorithm intelligently swaps expensive, low-impact nodes for cheaper, high-impact alternatives.

    ## Experiments: Scaling Virality
    The authors tested IICEA against heavyweights like **IMAGE** and **ComBIM** on networks ranging from small friendship groups to the massive **LiveMocha** (100k+ nodes).

    ![Performance Comparison Table](https://cdn.atominnolab.com/wisdoc/tables/20260527-56fc6bfb-a651-465c-baf5-d3ad56fb9cda/page_009_block_004.png)

    ### Key Findings:
    *   **Effectiveness**: IICEA consistently found seed sets with higher influence spread than all baselines.
    *   **Efficiency**: Despite being an iterative evolutionary algorithm, its throughput is comparable to fast community heuristics and much faster than DAG-based greedy methods.
    *   **The Overlap Advantage**: A key ablation study showed that treating communities as *overlapping* (as they are in real life) significantly beats models that assume people belong to only one group.

    ![Running Time Analysis](https://cdn.atominnolab.com/wisdoc/images/20260527-56fc6bfb-a651-465c-baf5-d3ad56fb9cda/page_010_block_002.png)

    ## Critical Insights: Why It Works
    The success of IICEA stems from its **Inductive Bias**. By baking the physics of social communities directly into the evolutionary operators (Crossover/Mutation), the algorithm doesn't have to wander aimlessly in the search space. It "knows" that nodes at the boundary of communities are valuable, and it actively protects them during the simulation.

    ## Conclusion
    IICEA effectively bridges the gap between high-precision greedy methods and high-speed heuristics. Its ability to balance the "cost" of a user against their "local-global" topological value makes it a highly practical tool for marketers and researchers dealing with the realities of limited resources in complex networks.

    **Future Outlook**: The next frontier for this research involves **Competitive BIM**—calculating how to maximize influence when a rival brand is trying to do the exact same thing in the same network.