Clique-DBA: Stabilizing Swarm Intelligence for Influence Maximization in Large-Scale Networks

TL;DR

Identifying the top-k influential nodes—the "seed set"—to maximize information spread is an NP-hard challenge. While the Discrete Bat Algorithm (DBA) offers a fast metaheuristic alternative to slow greedy algorithms, it is notoriously unstable. This paper introduces clique-DBA, which uses graph clique partitioning to anchor the search process, providing stable, high-performance influence maximization that rivals the greedy algorithm's accuracy at a fraction of the temporal cost.

Problem & Motivation: The Stability Gap

In the realm of Social Network Analysis (SNA), the Influence Maximization (IM) problem asks: Which $k$ nodes, if activated, will trigger the largest cascade?

Current SOTA falls into two camps:

1. Greedy Algorithms (e.g., CELF): High accuracy but poor scalability due to repeated Monte Carlo simulations.
2. Metaheuristics (e.g., DPSO, DBA): Fast and bio-inspired, but prone to "random walk" blindness.

The authors identify a critical flaw in the original DBA: its candidate seed pool often collapses around a few high-degree nodes, ignoring the diverse structural "pockets" of the network. This causes the algorithm to return wildly different solutions in different runs—a dealbreaker for practical deployment.

Methodology: Structuring Randomness with Cliques

The core innovation is the clique-based candidate pool. A clique is a complete subgraph where every node connects to every other node, representing the tightest possible social grouping.

1. The Partitioning Strategy

The algorithm first performs a greedy clique partition. By starting with the highest-degree nodes and extracting the largest possible cliques, the network is decomposed into a set of non-overlapping clusters.

2. Diversified Candidate Allocation

Instead of picking the "top 100 nodes globally," clique-DBA selects top nodes from different cliques. This ensures that the bats (potential solutions) explore diverse regions of the graph manifold. The size of the pool is mathematically balanced (typically $3k$ to $4k$) to maintain efficiency.

Figure 1: The Clique structure partition process identifies dense subgraphs to guide seed selection.

3. Evolutionary Rules

The bats evolve using a discretized frequency and velocity model. The Local Influence Estimation (LIE) function is used as the fitness metric, which approximates the spread within two hops to avoid the heavy cost of global simulations.

Experiments & Results: Consistency is Key

The researchers tested the method on networks ranging from small (NetScience) to large (CondMat, ~23k nodes).

Elimination of Fluctuations

The most striking result is found in the boxplot analysis of the LIE values. While the original DBA shows massive "whiskers" (high variance), clique-DBA collapses to a single point or a very tight range.

Figure 2: Boxplot comparison showing clique-DBA (far right in each subplot) achieving significantly higher stability compared to standard DBA.

Performance vs. Computational Cost

• Speed: Clique-DBA remains orders of magnitude faster than the Greedy approach. On the "Email" network, Greedy takes ~13,000 seconds; clique-DBA finishes in a negligible fraction of that time.
• Influence: Under the Independent Cascade (IC) model, the spread achieved by clique-DBA is often indistinguishable from the Greedy algorithm, and occasionally superior in fragmented networks like SynRand.

Critical Insight & Conclusion

Swarm intelligence algorithms often struggle with the "curse of dimensionality" in discrete spaces. By injecting graph-theoretic priors (cliques) into the initialization and exploration phases, clique-DBA effectively narrows the search space to the most promising structural candidates.

Takeaway: If you are using metaheuristics for graph problems, don't just let your "agents" roam free. Constrain their search using the topology of the network itself. This work proves that structural awareness is the bridge between the speed of heuristics and the reliability of greedy search.

Limitations: The method relies on a non-overlapping clique partition. In highly sparse networks or those with significant overlapping community structures, a more nuanced "overlapping clique" or "k-plex" approach might be required to further refine the seed selection.