Minimizing Influence Time: Tackling Social Networks with Fuzzy Costs

TL;DR

In modern viral marketing, the cost of "buying" an influencer’s attention isn't always a fixed number—it's often a "fuzzy" estimate based on subjective factors. This paper introduces three optimization models to minimize the Complete Influence Time (CIT)—the time it takes for a message to reach every single person in a network—while navigating these fuzzy budget constraints using a hybrid intelligent algorithm.

Background: Why "Fuzzy" Matters

Most influence diffusion research assumes we know exactly how much it costs to target a node (e.g., $5 to target User A). Some studies assume costs follow a bell curve (stochastic). But what if you have zero historical data? What if the cost depends on a user's subjective mood?

This is where Fuzzy Logic and Credibility Theory come in. Instead of a hard number or a probability, costs are treated as Fuzzy Variables (like "approximately $10"or"somewherebetween$5 and $15").

The Core Challenge: Complete Influence

The authors focus on the Incremental Chance Model (ICM). Unlike simple models where influence stops, ICM guarantees that if a network is connected, everyone will eventually be influenced. The goal isn't just to reach "many" people, but to reach "all" people as fast as possible under a fuzzy budget.

Three Ways to Decide:

1. Expected Value Model (EVM): Aim for the best average-case scenario.
2. Chance-Constrained (CCP): Ensure the budget isn't exceeded with a high confidence level (e.g., 90%).
3. Dependent-Chance (DCP): Maximize the probability of finishing the task before a strict deadline.

Methodology: The Hybrid Intelligent Algorithm

Solving these fuzzy models is computationally "heavy." The authors designed a two-part solution:

1. Fuzzy Simulation

Since fuzzy functions rarely have a simple math formula, the algorithm uses Fuzzy Simulation to estimate expected values and credibility measures by generating thousands of samples.

2. Modified Greedy Search (Heuristics)

Calculating the effect of every node in a 1000-node network is slow. The authors use three geometric "shortcuts" to find the best influencers:

• Shortest Path Length (SPL): Target nodes that are far away from current influencers.
• Maximin Path Reduction (MPLR): Target nodes that most significantly reduce the "maximum distance" in the network.
• Shortest Path Forest weight Reduction (SPLWR): Optimizing the overall "spanning forest" of the network.

Note: The algorithm selects top 'r' candidates via heuristics before performing full simulation to save time.

Experimental Validation

The authors tested their approach on 1000-node social networks.

Key Insights:

• The Power of Greedy: Their hybrid algorithm consistently beat simpler strategies like "Target the people with the most friends" (High-degree) or "Random selection."
• Density Speeds Diffusion: In denser networks (higher $p$), the time to influence the whole crowd drops significantly.
• The Efficiency Frontier: They found that calculating the top 50 candidates ($r=50$) provided the best balance between finding a great solution and not crashing the computer.

Comparison of the proposed CCP model against baseline strategies.

Critical Perspective: What's Next?

Limitations: The current approach, while robust, relies on Fuzzy Simulation, which the authors admit is "time-consuming." For networks with millions of nodes (like Twitter or WeChat), the simulation phase would likely become a bottleneck.

Future Outlook: The true value of this paper lies in its Decision Models. By applying Credibility Theory, they've moved social network analysis closer to the "messy" reality of human decision-making. Future work involving Graph Neural Networks (GNNs) could potentially replace the greedy step, allowing this fuzzy logic to scale to massive real-world data.

Summary

By bridging the gap between rigorous mathematical Credibility Theory and social network dynamics, this research provides a blueprint for marketers and policy-makers to spread information quickly and reliably, even when costs are uncertain.