Maximizing influence problem

• Given a directed graph and information transmission probabilities, we aim to maximize the “influence diffusion” $\sigma (S)$.
  • Since $\sigma (S)$ is complex, it cannot be solved using BDD (NP-hard), but an approximation of $1-1/e$ (approximately 63%) is possible using an approximation algorithm.
• The set of paths from one node S to another node causes a combination explosion.
  • To avoid this, we convert it into a BDD.
    • This follows the pattern (framework) of Discrete Structure Processing techniques.
  • By using the basic operations of decision graphs (including BDD), we can maximize $\sigma (S)$.

#discrete Algorithm (Expert in Information Science)