DQSSA: A Quantum-Inspired Solution for Maximizing Influence in Online Social Networks (Student Abstract)

Aryaman Rao, Parth Singh, Dinesh Kumar Vishwakarma, Mukesh PrasadAAAI 2024 · DOI

Introduction

The Influence Maximization (IM) problem is a fundamental challenge in network science: given a social network, how can one identify a small set of "seed" nodes that will trigger the largest possible cascade of information or influence? This problem is NP-hard and has critical applications in viral marketing, public health awareness, and social mobilization. Existing approaches often struggle with a trade-off between computational efficiency and solution quality; greedy algorithms can be slow on large networks, while standard meta-heuristics often get trapped in local optima, failing to identify the most influential nodes.

Methodology: The DQSSA Framework

To address these challenges, researchers have proposed the Discretized Quantum-based Salp Swarm Algorithm (DQSSA). This framework combines community detection with a quantum-enhanced meta-heuristic to optimize influence spread efficiently.

The DQSSA pipeline consists of three primary stages:

  1. Community Detection and Local Ranking: The algorithm first partitions the network into communities using the Louvain algorithm. Within these communities, nodes are ranked using a Local Influence Estimator (LIE). This step significantly reduces the search space by focusing on high-potential candidates within distinct clusters.
  2. Quantum-Inspired Optimization: The core of the method is a modified Salp Swarm Algorithm (SSA). To prevent the algorithm from converging prematurely on sub-optimal solutions, two quantum-inspired mechanisms are integrated:
  3. Reverse Learning (RL): This strategy explores the "opposite" regions of the search space, ensuring a more comprehensive search.
  4. Quantum Mutation (QM): Inspired by the Schrödinger Wave equation, this introduces stochastic variations that allow the algorithm to "jump" out of local optima and maintain population diversity.
  5. Discretization and Diffusion Simulation: Since social networks are discrete structures, the continuous search space of the SSA is mapped back to specific node IDs. The final influence spread is evaluated using the Independent Cascade (IC) model, which simulates how information propagates from the selected seeds.

Experimental Evaluation

The performance of DQSSA was evaluated against several benchmarks, including the Discrete Bat Algorithm (DBA) and Discrete Particle Swarm Optimization (DPSO), across four real-world datasets: Jazz (musician collaborations), Wiki-Vote (Wikipedia elections), Email-Univ (university communications), and Hamsterster (friendship network).

Influence Spread Performance

The primary metric for success is the Final Infected Scale (FIS), representing the total number of nodes reached by the influence cascade. As shown in Figure 2, DQSSA consistently achieves a higher FIS across all tested datasets compared to traditional meta-heuristic benchmarks.

Comparison of Final Infected Scale (FIS) across different algorithms and datasets, showing DQSSA's superior influence spread.

Computational Efficiency

Beyond influence quality, DQSSA demonstrates remarkable computational efficiency. In large-scale networks, the time required to find an optimal seed set is a critical factor.

Execution time (in seconds) for various algorithms across four datasets. DQSSA shows significant speed improvements over traditional benchmarks like DBA.

As detailed in the table above, DQSSA offers a substantial reduction in execution time. For instance, on the Hamsterster dataset, DQSSA completes its search in approximately 25.88 seconds, whereas the DBA benchmark requires over 517 seconds—a nearly 20-fold improvement in speed.

Conclusion and Future Directions

The DQSSA framework demonstrates that integrating quantum-inspired principles with community-aware heuristics can effectively solve the Influence Maximization problem. By overcoming the local optima trap and reducing the search space through community detection, DQSSA provides a scalable and high-performing solution for modern social networks.

Future research will focus on testing the algorithm's robustness across different diffusion models, such as the Linear Threshold (LT) model, and evaluating its performance on massive-scale graphs containing millions or billions of nodes. Additionally, investigating the sensitivity of the algorithm to varying infection probabilities will be crucial for real-world deployment.

Summary updated

BibTeX
@inproceedings{rao2024dqssa,
  author = {Aryaman Rao and Parth Singh and Dinesh Kumar Vishwakarma and Mukesh Prasad},
  title = {{DQSSA: A Quantum-Inspired Solution for Maximizing Influence in Online Social Networks (Student Abstract)}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i21.30501},
}
Figure