MIMA: Decoding Influence in the World of Friends and Foes

TL;DR

Social networks aren't just about "likes"—they are balanced (or unbalanced) by "dislikes" and hostile interactions. This paper presents MIMA, a hybrid Memetic Algorithm that mines top influencers in Signed Social Networks (SSNs). By combining global genetic exploration with local refinement and a novel Status Influential Strength (SIS) metric, MIMA identifies the most powerful nodes even when the network is riddled with negative links.

Academic Context: This work moves beyond traditional "trust-only" diffusion models to a more realistic "trust-distrust" paradigm, achieving SOTA results on the Epinions benchmark.

The Problem: The Blind Spot of Positive-Only Mining

Most viral marketing and influence models assume that every connection is a recommendation. If I follow you, I trust you. But in Signed Social Networks (like Epinions or Slashdot), a link can be a badge of distrust or hostility.

Current Evolutionary Algorithms (EAs) attempt to find influencer sets, but they often:

1. Ignore the Negative: They fail to account for how a high-status "villain" might spread influence differently than a "hero."
2. Get Stuck: Standard genetic algorithms often converge prematurely on sub-optimal solutions in the massive search space of social graphs.

Methodology: High-Status + Strong Ties

The authors' core "secret sauce" is the Status Influential Strength (SIS) fitness function.

1. The Physics of Status

Based on Status Theory, the status of a user is not just their popularity. It is a balance of:

• Incoming positives & Outgoing negatives: These increase your relative status.
• Outgoing positives & Incoming negatives: These decrease your relative status.

2. Tie Strength

The model integrates the intuition that "the more friends you have, the less strength each individual bond carries." This prevents the algorithm from simply picking "hub" nodes with thousands of weak connections that don't actually trigger action.

3. The Memetic Advantage (Global + Local)

MIMA utilizes a Memetic Algorithm (MA). While the Genetic Algorithm part explores the whole network for potential "influencer sets," a local Hill Climbing search tweaks those sets to ensure they are the absolute best in their local neighborhood.

Figure 1: The Genetic Crossover process used to explore the social search space.

Experiments and Results

The researchers tested MIMA against the Epinions dataset (5,000 nodes) and compared it with:

• MIEA: A standard Genetic Algorithm.
• JIP: A traditional Joint Influential Power metric.
• Random: Baseline selection.

Key Findings:

• Influence Spread (IS): MIMA captured a significantly larger portion of the network than MIEA and JIP at every group size (k).
• Consistency: Across 10 different partitions of data, MIMA remained stable, proving it isn't sensitive to initial random noise.

Figure 2: MIMA (top line) showing superior Influence Spread compared to other methods.

Critical Insight: Why it Works

The success of MIMA lies in its Inductive Bias. By specifically mathematicalizing "Status" in a signed context, the fitness function naturally gravitates toward nodes that are genuinely respected (high incoming +) or successfully critical (high outgoing -), rather than just "noisy" nodes. The local search then acts as a polisher, ensuring that the selected influencer set isn't just "good," but "locally optimal."

Conclusion & Future Work

MIMA proves that to master social influence, you must acknowledge the "foes" as much as the "friends." For practitioners, this means viral marketing campaigns should analyze competitor "distrust" networks to find the most strategically placed ambassadors.

Limitations: The current study uses a static snapshot of the network. Real-world influence is temporal and dynamic. Future iterations of MIMA will likely need to incorporate time-decay factors into the tie-strength calculation.