SASP: Breaking the Scalability Barrier in Social Influence Maximization

TL;DR

The spread of information in Online Social Networks (OSN) is a critical study for digital marketing and public opinion. However, finding the most influential "seed users" (the Influence Maximization Problem) is an NP-hard challenge. This paper presents SASP, a modified Simulated Annealing algorithm that partitions the search space to prevent local optima, achieving a staggering 37% performance boost over traditional methods on large-scale networks.

Problem & Motivation: The Curse of Dimensionality in OSNs

In a social graph $G(V,E)$, the goal is to select a subset of nodes $A$ (seeds) that maximize the expected number of influenced nodes $\sigma (A)$. As $V$ grows into the hundreds of thousands, the search space becomes astronomical.

Traditional approaches like Greedy Algorithms are computationally prohibitive because they require repeated Monte Carlo simulations for each node addition. On the other hand, Metaheuristics like Genetic Algorithms (GA) or standard Simulated Annealing (SA) often converge too quickly to a local optimum (stagnation), especially when the search space is vast and "rugged."

The Authors' Insight: The key to solving large-scale IMP is the balance between Diversification (exploring new areas) and Intensification (refining known good solutions). By partitioning the nodes into regions, they force the algorithm to look for influence potential in diverse clusters before attempting a global merge.

Methodology: The Divide, Search, and Conquer Strategy

The proposed SASP (Simulated Annealing with Search Partition) operates through a structured two-phase convergence process:

1. Search Space Division

The total node set $V$ is divided into $h$ regions. Each region $r_j$ contains a slice of the network nodes. This acts as a constraint on the CreateNeighbor function during the local phase.

2. The Two-Stage Search

• Local Search (50% Budget): The algorithm runs $h$ independent Simulated Annealing sessions. Crucially, the "exchange" of nodes is restricted to the specific region $r_j$. This forces the algorithm to find the "local heroes" of influence within sub-communities.
• Global Search (50% Budget): The best local solutions are then used as a starting point for a global SA run across the entire search space, allowing for cross-regional optimization.

The probability of acceptance $P_a$ follows the standard Boltzmann distribution, but its application is constrained by the partition logic.

Experiments & Results: Scalability is Key

The authors tested SASP against standard SA and GA across four datasets, ranging from 75k to 403k nodes.

Analysis of Results

• Small Networks: On smaller graphs (DS1, DS2), standard SA is sufficient. The partitioning in SASP doesn't provide additional value because the global optimum is easier to reach.
• Large Networks: On DS3 and DS4, SASP dominates. This confirms that Search Space Division is an effective strategy for high-dimensional combinatorial problems. It prevents the algorithm from "focusing" on one local cluster of high-degree nodes too early.

Critical Analysis & Conclusion

Takeaway

SASP demonstrates that structural constraints on search algorithms (like partitioning) can actually lead to better global outcomes. By preventing the algorithm from exploring the whole space simultaneously, it maintains population diversity without the overhead of complex Genetic Algorithm operators (like crossover/mutation).

Limitations

• Partition Logic: The current partitioning is based on simple index division. In real-world graphs, partitioning based on Community Detection (e.g., Louvain method) might yield even better results by respecting the natural topology of the network.
• Static Probability: The propagation probability is assumed to be constant (e.g., 0.04). In reality, influence is heterogeneous and time-varying.

Future Outlook

This "Search Space Partitioning" framework is widely applicable beyond IMP. It could be adapted for Wireless Sensor Network (WSN) layout optimization or Cloud Resource Allocation where the search space is similarly massive and cluster-based.