The influence maximization (IM) problem is a discrete optimization problem [Kempe et al. [1]] of selecting the k most influential nodes in a network, and has ample applications ranging from viral marketing to outbreak detection. The IM problem is as follows: given a budget k and a graph G, our goal is to find a seed set S consisting of k nodes of G which maximizes the expected number of nodes influenced by S, according to some model of influence diffusion. The classic IM problem, which is also referred to as the nonadaptive IM, selects the seed set S before starting the diffusion process. Therefore, the focus is on the efficiency of the solution. A few years later, Golovin and Krause [2] introduced the adaptive IM (AIM) to target the efficacy of the problem. In the adaptive setting, selection of the k seed nodes occurs one at a time, such that the jth seed node is selected after observing the actual influence from the previously selected j − 1 seeds. There are two main feedback models that have been studied: fulladoption, where the entire diffusion carried out by a seed node in the previous step is observed, and myopic, where only the neighbours of the previously selected seed nodes are considered as a feedback. While adaptive policies are strictly stronger than nonadaptive ones, the latter are much easier to design and implement. Golovin and Krause [2] proposed a measure called the adaptivity gap (AG), which is the ratio between the adaptive and nonadaptive optima. If the AG is small, we say that the nonadaptive policy provides a good approximation of the adaptive optimum. In this thesis, we study AG with both feedback models. Under the full adoption feedback, we investigate the upper bound of AG over several graph classes, from inarborescences to general graphs. We show the first sublinear upper bound on AG that holds for any graph. Next, we have the experimental part, where we take different network mod els, such as random, scalefree and real world networks, and draw several comparisons between the adaptive greedy and the nonadaptive greedy algorithms under various net work settings and parameters. Eventually, we move on to the myopic feedback model, which lacks the property of submodularity. To recover from the drawbacks of being nonsubmodular, an artificial diffusion process is taken into account. We introduce a new technique to bound the AG without using the commonly used approaches, such as multilinear extensions or random walks. We also study the adaptive greedy algorithm under the new setting and compare it to optimal adaptive policy. Our approach is of independent interest and can be used for further studies related to different adaptive optimization problems.
Adaptive Influence Maximization: Bounding Adaptivity Gaps and Beyond / Poddar, Debashmita.  (2023 Mar 10).
Adaptive Influence Maximization: Bounding Adaptivity Gaps and Beyond
PODDAR, DEBASHMITA
20230310
Abstract
The influence maximization (IM) problem is a discrete optimization problem [Kempe et al. [1]] of selecting the k most influential nodes in a network, and has ample applications ranging from viral marketing to outbreak detection. The IM problem is as follows: given a budget k and a graph G, our goal is to find a seed set S consisting of k nodes of G which maximizes the expected number of nodes influenced by S, according to some model of influence diffusion. The classic IM problem, which is also referred to as the nonadaptive IM, selects the seed set S before starting the diffusion process. Therefore, the focus is on the efficiency of the solution. A few years later, Golovin and Krause [2] introduced the adaptive IM (AIM) to target the efficacy of the problem. In the adaptive setting, selection of the k seed nodes occurs one at a time, such that the jth seed node is selected after observing the actual influence from the previously selected j − 1 seeds. There are two main feedback models that have been studied: fulladoption, where the entire diffusion carried out by a seed node in the previous step is observed, and myopic, where only the neighbours of the previously selected seed nodes are considered as a feedback. While adaptive policies are strictly stronger than nonadaptive ones, the latter are much easier to design and implement. Golovin and Krause [2] proposed a measure called the adaptivity gap (AG), which is the ratio between the adaptive and nonadaptive optima. If the AG is small, we say that the nonadaptive policy provides a good approximation of the adaptive optimum. In this thesis, we study AG with both feedback models. Under the full adoption feedback, we investigate the upper bound of AG over several graph classes, from inarborescences to general graphs. We show the first sublinear upper bound on AG that holds for any graph. Next, we have the experimental part, where we take different network mod els, such as random, scalefree and real world networks, and draw several comparisons between the adaptive greedy and the nonadaptive greedy algorithms under various net work settings and parameters. Eventually, we move on to the myopic feedback model, which lacks the property of submodularity. To recover from the drawbacks of being nonsubmodular, an artificial diffusion process is taken into account. We introduce a new technique to bound the AG without using the commonly used approaches, such as multilinear extensions or random walks. We also study the adaptive greedy algorithm under the new setting and compare it to optimal adaptive policy. Our approach is of independent interest and can be used for further studies related to different adaptive optimization problems.File  Dimensione  Formato  

2023_PhDThesis_Poddar.pdf
accesso aperto
Tipologia:
Tesi di dottorato
Licenza:
Accesso gratuito
Dimensione
1.37 MB
Formato
Adobe PDF

1.37 MB  Adobe PDF  Visualizza/Apri 
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.