2024 [ nach oben ]

Friedrich, Tobias; Göbel, Andres; Klodt, Nicolas; Krejca, Martin S.; Pappik, Marcus Analysis of the survival time of the SIRS process via expansionElectronic Journal of Probability 2024: 1–29
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We study the SIRS process---a continuous-time Markov chain modeling the spread of infections on graphs. In this model, vertices are either susceptible, infected, or recovered. Each infected vertex becomes recovered at rate 1 and infects each of its susceptible neighbors independently at rate~\(\lambda\), and each recovered vertex becomes susceptible at a rate~\(\varrho\), which we assume to be independent of the graph size. A central quantity of the SIRS process is the time until no vertex is infected, known as the survival time. Surprisingly though, to the best of our knowledge, all known rigorous theoretical results that exist so far immediately carry over from the related SIS model and do not completely explain the behavior of the SIRS process. We address this imbalance by conducting theoretical analyses of the SIRS process via the expansion properties of the underlying graph. Our first result shows that the expected survival time of the SIRS process on stars is at most polynomial in the graph size for any value of~\(\lambda\). This behavior is fundamentally different from the SIS process, where the expected survival time is exponential already for small infection rates. This raises the question of which graph properties result in an exponential survival time. Our main result is an exponential lower bound of the expected survival time of the SIRS process on expander graphs. Specifically, we show that on expander graphs \(G\) with \(n\) vertices, degree close to \(d\), and sufficiently small spectral expansion, the SIRS process has expected survival time at least exponential in \(n\) when \(\lambda \geq c/d\) for a constant \(c > 1\). Previous results on the SIS process show that this bound is almost tight. Additionally, our result holds even if \(G\) is a subgraph. Notably, our result implies an almost-tight threshold for Erdos-Renyi-graphs and a regime of exponential survival time for complex network models. The proof of our main result draws inspiration from Lyapunov functions used in mean-field theory to devise a two-dimensional potential function and from applying a negative-drift theorem to show that the expected survival time is exponential.
@article{friedrich2024analysis, abstract = {We study the SIRS process—a continuous-time Markov chain modeling the spread of infections on graphs. In this model, vertices are either susceptible, infected, or recovered. Each infected vertex becomes recovered at rate 1 and infects each of its susceptible neighbors independently at rate \(\lambda\), and each recovered vertex becomes susceptible at a rate \(\varrho\), which we assume to be independent of the graph size. A central quantity of the SIRS process is the time until no vertex is infected, known as the survival time. Surprisingly though, to the best of our knowledge, all known rigorous theoretical results that exist so far immediately carry over from the related SIS model and do not completely explain the behavior of the SIRS process. We address this imbalance by conducting theoretical analyses of the SIRS process via the expansion properties of the underlying graph. Our first result shows that the expected survival time of the SIRS process on stars is at most polynomial in the graph size for any value of \(\lambda\). This behavior is fundamentally different from the SIS process, where the expected survival time is exponential already for small infection rates. This raises the question of which graph properties result in an exponential survival time. Our main result is an exponential lower bound of the expected survival time of the SIRS process on expander graphs. Specifically, we show that on expander graphs \(G\) with \(n\) vertices, degree close to \(d\), and sufficiently small spectral expansion, the SIRS process has expected survival time at least exponential in \(n\) when \(\lambda \geq c/d\) for a constant \(c > 1\). Previous results on the SIS process show that this bound is almost tight. Additionally, our result holds even if \(G\) is a subgraph. Notably, our result implies an almost-tight threshold for Erdos-Renyi-graphs and a regime of exponential survival time for complex network models. The proof of our main result draws inspiration from Lyapunov functions used in mean-field theory to devise a two-dimensional potential function and from applying a negative-drift theorem to show that the expected survival time is exponential.}, author = {Friedrich, Tobias and Göbel, Andres and Klodt, Nicolas and Krejca, Martin S. and Pappik, Marcus}, journal = {Electronic Journal of Probability}, keywords = {nicolasklodt marcuspappik martinskrejca andreasgoebel tobiasfriedrich ejp year2024}, pages = {1-29}, title = {Analysis of the survival time of the SIRS process via expansion}, volume = 29, year = 2024 }

Friedrich, Tobias; Göbel, Andreas; Klodt, Nicolas; Krejca, Martin S.; Pappik, Marcus The Irrelevance of Influencers: Information Diffusion with Re-Activation and Immunity Lasts Exponentially Long on Social Network ModelsAnnual AAAI Conference on Artificial Intelligence 2024
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Information diffusion models on networks are at the forefront of AI research. The dynamics of such models typically follow stochastic models from epidemiology, used to model not only infections but various phenomena, including the behavior of computer viruses and viral marketing campaigns. A core question in this setting is how to efficiently detect the most influential vertices in the host graph such that the infection survives the longest. In processes that incorporate re-infection of the vertices, such as the SIS process, theoretical studies identify parameter thresholds where the survival time of the process rapidly transitions from logarithmic to super-polynomial. These results contradict the intuition that the starting configuration is relevant, since the process will always either die out fast or survive almost indefinitely. A shortcoming of these results is that models incorporating short-term immunity (or creative advertisement fatigue) have not been subjected to such a theoretical analysis so far. We reduce this gap in the literature by studying the SIRS process, a more realistic model, which besides re-infection additionally incorporates short-term immunity. On complex network models, we identify parameter regimes for which the process survives exponentially long, and we get a tight threshold for random graphs. Underlying these results is our main technical contribution, showing a threshold behavior for the survival time of the SIRS process on graphs with large expander subgraphs, such as social network models.
@inproceedings{friedrich2024irrelevance, abstract = {Information diffusion models on networks are at the forefront of AI research. The dynamics of such models typically follow stochastic models from epidemiology, used to model not only infections but various phenomena, including the behavior of computer viruses and viral marketing campaigns. A core question in this setting is how to efficiently detect the most influential vertices in the host graph such that the infection survives the longest. In processes that incorporate re-infection of the vertices, such as the SIS process, theoretical studies identify parameter thresholds where the survival time of the process rapidly transitions from logarithmic to super-polynomial. These results contradict the intuition that the starting configuration is relevant, since the process will always either die out fast or survive almost indefinitely. A shortcoming of these results is that models incorporating short-term immunity (or creative advertisement fatigue) have not been subjected to such a theoretical analysis so far. We reduce this gap in the literature by studying the SIRS process, a more realistic model, which besides re-infection additionally incorporates short-term immunity. On complex network models, we identify parameter regimes for which the process survives exponentially long, and we get a tight threshold for random graphs. Underlying these results is our main technical contribution, showing a threshold behavior for the survival time of the SIRS process on graphs with large expander subgraphs, such as social network models.}, author = {Friedrich, Tobias and Göbel, Andreas and Klodt, Nicolas and Krejca, Martin S. and Pappik, Marcus}, booktitle = {Annual AAAI Conference on Artificial Intelligence}, keywords = {nicolasklodt marcuspappik martinskrejca andreasgoebel tobiasfriedrich aaai year2024}, title = {The Irrelevance of Influencers: Information Diffusion with Re-Activation and Immunity Lasts Exponentially Long on Social Network Models}, year = 2024 }

Friedrich, Tobias; Göbel, Andreas; Klodt, Nicolas; Krejca, Martin S.; Pappik, Marcus From Market Saturation to Social Reinforcement: Understanding the Impact of Non-Linearity in Information Diffusion ModelsThe 23rd International Conference on Autonomous Agents and Multi-Agent Systems 2024
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Diffusion of information in networks is at the core of many problems in AI. Common examples include the spread of ideas and rumors as well as marketing campaigns. Typically, information diffuses at a non-linear rate, for example, if markets become saturated or if users of social networks reinforce each other's opinions. Despite these characteristics, this area has seen little research, compared to the vast amount of results for linear models, which exhibit less complex dynamics. Especially, when considering the possibility of re-infection, no fully rigorous guarantees exist so far. We address this shortcoming by studying a very general non-linear diffusion model that captures saturation as well as reinforcement. More precisely, we consider a variant of the SIS model in which vertices get infected at a rate that scales polynomially in the number of their infected neighbors, weighted by an infection coefficient \(\lambda\). We give the first fully rigorous results for thresholds of \(\lambda\) at which the expected survival time becomes super-polynomial. For cliques we show that when the infection rate scales sub-linearly, the threshold only shifts by a poly-logarithmic factor, compared to the standard SIS model. In contrast, super-linear scaling changes the process considerably and shifts the threshold by a polynomial term. For stars, sub-linear and super-linear scaling behave similar and both shift the threshold by a polynomial factor. Our bounds are almost tight, as they are only apart by at most a poly-logarithmic factor from the lower thresholds, at which the expected survival time is logarithmic.
@inproceedings{friedrich2024market, abstract = {Diffusion of information in networks is at the core of many problems in AI. Common examples include the spread of ideas and rumors as well as marketing campaigns. Typically, information diffuses at a non-linear rate, for example, if markets become saturated or if users of social networks reinforce each other's opinions. Despite these characteristics, this area has seen little research, compared to the vast amount of results for linear models, which exhibit less complex dynamics. Especially, when considering the possibility of re-infection, no fully rigorous guarantees exist so far. We address this shortcoming by studying a very general non-linear diffusion model that captures saturation as well as reinforcement. More precisely, we consider a variant of the SIS model in which vertices get infected at a rate that scales polynomially in the number of their infected neighbors, weighted by an infection coefficient \(\lambda\). We give the first fully rigorous results for thresholds of \(\lambda\) at which the expected survival time becomes super-polynomial. For cliques we show that when the infection rate scales sub-linearly, the threshold only shifts by a poly-logarithmic factor, compared to the standard SIS model. In contrast, super-linear scaling changes the process considerably and shifts the threshold by a polynomial term. For stars, sub-linear and super-linear scaling behave similar and both shift the threshold by a polynomial factor. Our bounds are almost tight, as they are only apart by at most a poly-logarithmic factor from the lower thresholds, at which the expected survival time is logarithmic.}, author = {Friedrich, Tobias and Göbel, Andreas and Klodt, Nicolas and Krejca, Martin S. and Pappik, Marcus}, booktitle = {The 23rd International Conference on Autonomous Agents and Multi-Agent Systems}, keywords = {nicolasklodt marcuspappik martinskrejca andreasgoebel tobiasfriedrich aamas year2024}, title = {From Market Saturation to Social Reinforcement: Understanding the Impact of Non-Linearity in Information Diffusion Models}, year = 2024 }

2023 [ nach oben ]

Friedrich, Tobias; Göbel, Andreas; Krejca, Martin S.; Pappik, Marcus Polymer Dynamics via Cliques: New Conditions for ApproximationsTheoretical Computer Science 2023: 230–252
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Abstract polymer models are systems of weighted objects, called polymers, equipped with an incompatibility relation. An important quantity associated with such models is the partition function, which is the weighted sum over all sets of compatible polymers. Various approximation problems reduce to approximating the partition function of a polymer model. Central to the existence of such approximation algorithms are weight conditions of the respective polymer model. Such conditions are derived either via complex analysis or via probabilistic arguments. We follow the latter path and establish a new condition—the clique dynamics condition—, which is less restrictive than the ones in the literature. We introduce a new Markov chain where the clique dynamics condition implies rapid mixing by utilizing cliques of incompatible polymers that naturally arise from the translation of algorithmic problems into polymer models. This leads to improved parameter ranges for several approximation algorithms, such as a factor of at least \(2^{1/\alpha}\) for the hard-core model on bipartite \(\alpha\)-expanders.
@article{friedrich2023polymer, abstract = {Abstract polymer models are systems of weighted objects, called polymers, equipped with an incompatibility relation. An important quantity associated with such models is the partition function, which is the weighted sum over all sets of compatible polymers. Various approximation problems reduce to approximating the partition function of a polymer model. Central to the existence of such approximation algorithms are weight conditions of the respective polymer model. Such conditions are derived either via complex analysis or via probabilistic arguments. We follow the latter path and establish a new condition—the clique dynamics condition—, which is less restrictive than the ones in the literature. We introduce a new Markov chain where the clique dynamics condition implies rapid mixing by utilizing cliques of incompatible polymers that naturally arise from the translation of algorithmic problems into polymer models. This leads to improved parameter ranges for several approximation algorithms, such as a factor of at least \(2^{1/\alpha}\) for the hard-core model on bipartite \(\alpha\)-expanders.}, author = {Friedrich, Tobias and Göbel, Andreas and Krejca, Martin S. and Pappik, Marcus}, journal = {Theoretical Computer Science}, keywords = {tcs marcuspappik martinskrejca andreasgoebel tobiasfriedrich year2023}, pages = {230-252}, title = {Polymer Dynamics via Cliques: New Conditions for Approximations}, volume = 942, year = 2023 }

Baguley, Samuel; Friedrich, Tobias; Neumann, Aneta; Neumann, Frank; Pappik, Marcus; Zeif, Ziena Fixed Parameter Multi-Objective Evolutionary Algorithms for the W-Separator ProblemGenetic and Evolutionary Computation Conference (GECCO) 2023
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Parameterized analysis provides powerful mechanisms for obtaining fine-grained insights into different types of algorithms. In this work, we combine this field with evolutionary algorithms and provide parameterized complexity analysis of evolutionary multi-objective algorithms for the W-separator problem, which is a natural generalization of the vertex cover problem. The goal is to remove the minimum number of vertices such that each connected component in the resulting graph has at most W vertices. We provide different multi-objective formulations involving two or three objectives that provably lead to fixed-parameter evolutionary algorithms with respect to the value of an optimal solution OPT and W. Of particular interest are kernelizations and the reducible structures used for them. We show that in expectation the algorithms make incremental progress in finding such structures and beyond. The current best known kernelization of the W-separator uses linear programming methods and requires a non-trivial post-process to extract the reducible structures. We provide additional structural features to show that evolutionary algorithms with appropriate objectives are also capable of extracting them. Our results show that evolutionary algorithms with different objectives guide the search and admit fixed parameterized runtimes to solve or approximate (even arbitrarily close) the W-separator problem.
@inproceedings{baguley2023fixed, abstract = {Parameterized analysis provides powerful mechanisms for obtaining fine-grained insights into different types of algorithms. In this work, we combine this field with evolutionary algorithms and provide parameterized complexity analysis of evolutionary multi-objective algorithms for the W-separator problem, which is a natural generalization of the vertex cover problem. The goal is to remove the minimum number of vertices such that each connected component in the resulting graph has at most W vertices. We provide different multi-objective formulations involving two or three objectives that provably lead to fixed-parameter evolutionary algorithms with respect to the value of an optimal solution OPT and W. Of particular interest are kernelizations and the reducible structures used for them. We show that in expectation the algorithms make incremental progress in finding such structures and beyond. The current best known kernelization of the W-separator uses linear programming methods and requires a non-trivial post-process to extract the reducible structures. We provide additional structural features to show that evolutionary algorithms with appropriate objectives are also capable of extracting them. Our results show that evolutionary algorithms with different objectives guide the search and admit fixed parameterized runtimes to solve or approximate (even arbitrarily close) the W-separator problem.}, author = {Baguley, Samuel and Friedrich, Tobias and Neumann, Aneta and Neumann, Frank and Pappik, Marcus and Zeif, Ziena}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {anetaneumann sys:relevantfor:ae zienazeif marcuspappik samuelbaguley tobiasfriedrich gecco frankneumann year2023}, title = {Fixed Parameter Multi-Objective Evolutionary Algorithms for the W-Separator Problem}, year = 2023 }

Anand, Konrad; Göbel, Andreas; Pappik, Marcus; Perkins, Will Perfect Sampling for Hard Spheres from Strong Spatial MixingInternational Conference on Randomization and Computation (Random) 2023: 38:1–38:18
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We provide a perfect sampling algorithm for the hard-sphere model on subsets of ℝd with expected running time linear in the volume under the assumption of strong spatial mixing. A large number of perfect and approximate sampling algorithms have been devised to sample from the hard-sphere model, and our perfect sampling algorithm is efficient for a range of parameters for which only efficient approximate samplers were previously known and is faster than these known approximate approaches. Our methods also extend to the more general setting of Gibbs point processes interacting via finite-range, repulsive potentials.
@inproceedings{anand2023perfect, abstract = {We provide a perfect sampling algorithm for the hard-sphere model on subsets of ℝd with expected running time linear in the volume under the assumption of strong spatial mixing. A large number of perfect and approximate sampling algorithms have been devised to sample from the hard-sphere model, and our perfect sampling algorithm is efficient for a range of parameters for which only efficient approximate samplers were previously known and is faster than these known approximate approaches. Our methods also extend to the more general setting of Gibbs point processes interacting via finite-range, repulsive potentials.}, author = {Anand, Konrad and Göbel, Andreas and Pappik, Marcus and Perkins, Will}, booktitle = {International Conference on Randomization and Computation (Random)}, keywords = {random sys:relevantfor:ae marcuspappik andreasgoebel tobiasfriedrich year2023}, pages = {38:1–38:18}, title = {Perfect Sampling for Hard Spheres from Strong Spatial Mixing}, year = 2023 }

2022 [ nach oben ]

Friedrich, Tobias; Göbel, Andreas; Krejca, Martin S.; Pappik, Marcus A Spectral Independence View on Hard Spheres via Block DynamicsSIAM Journal on Discrete Mathematics 2022: 2282–2322
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
The hard-sphere model is one of the most extensively studied models in statistical physics. It describes the continuous distribution of spherical particles, governed by hard-core interactions. An important quantity of this model is the normalizing factor of this distribution, called the partition function. We propose a Markov chain Monte Carlo algorithm for approximating the grand canonical partition function of the hard-sphere model in \(d\) dimensions. Up to a fugacity of \(\lambda < \mathrm{e / 2d\), the runtime of our algorithm is polynomial in the volume of the system. Key to our approach is to define a discretization that closely approximates the partition function of the continuous model. This results in a discrete hard-core instance that is exponential in the size of the initial hard-sphere model. Our approximation bound follows directly from the correlation decay threshold of an infinite regular tree with degree equal to the maximum degree of our discretization. To cope with the exponential blow-up of the discrete instance, we use block dynamics, a Markov chain that generalizes the more frequently studied Glauber dynamics by grouping the vertices of the graph into blocks and updating an entire block instead of a single vertex in each step. We prove rapid mixing of block dynamics, based on disjoint cliques as blocks, up to the tree threshold of the univariate hard-core model. This is achieved by adapting the spectral expansion method, which was recently used for bounding the mixing time of Glauber dynamics within the same parameter regime.
@article{friedrich2022spectral, abstract = {The hard-sphere model is one of the most extensively studied models in statistical physics. It describes the continuous distribution of spherical particles, governed by hard-core interactions. An important quantity of this model is the normalizing factor of this distribution, called the partition function. We propose a Markov chain Monte Carlo algorithm for approximating the grand canonical partition function of the hard-sphere model in \(d\) dimensions. Up to a fugacity of \(\lambda < \mathrm{e} / 2d\), the runtime of our algorithm is polynomial in the volume of the system. Key to our approach is to define a discretization that closely approximates the partition function of the continuous model. This results in a discrete hard-core instance that is exponential in the size of the initial hard-sphere model. Our approximation bound follows directly from the correlation decay threshold of an infinite regular tree with degree equal to the maximum degree of our discretization. To cope with the exponential blow-up of the discrete instance, we use block dynamics, a Markov chain that generalizes the more frequently studied Glauber dynamics by grouping the vertices of the graph into blocks and updating an entire block instead of a single vertex in each step. We prove rapid mixing of block dynamics, based on disjoint cliques as blocks, up to the tree threshold of the univariate hard-core model. This is achieved by adapting the spectral expansion method, which was recently used for bounding the mixing time of Glauber dynamics within the same parameter regime.}, author = {Friedrich, Tobias and Göbel, Andreas and Krejca, Martin S. and Pappik, Marcus}, journal = {SIAM Journal on Discrete Mathematics}, keywords = {marcuspappik martinskrejca andreasgoebel tobiasfriedrich year2022}, number = 3, pages = {2282-2322}, title = {A Spectral Independence View on Hard Spheres via Block Dynamics}, volume = 36, year = 2022 }

Friedrich, Tobias; Göbel, Andreas; Katzmann, Maximilian; Krejca, Martin S.; Pappik, Marcus Algorithms for hard-constraint point processes via discretizationInternational Computing and Combinatorics Conference (COCOON) 2022: 242–254
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
We study the algorithmic applications of a natural discretization for the hard-sphere model and the Widom--Rowlinson model in a region of \(d\)-dimensional Euclidean space \(V \subset \mathbf{R}^{d}\). These continuous models are frequently used in statistical physics to describe mixtures of one or multiple particle types subjected to hard-core interactions. For each type, particles are distributed according to a Poisson point process with a type-specific activity parameter, called fugacity. The Gibbs distribution over all possible system states is characterized by the mixture of these point processes conditioned that no two particles are closer than some type-dependent distance threshold. A key part in better understanding the Gibbs distribution is its normalizing constant, called partition function. Our main algorithmic result is the first deterministic approximation algorithm for the partition function of the hard-sphere model and the Widom--Rowlinson model in box-shaped regions of Euclidean space. Our algorithms have quasi-polynomial running time in the volume of the region \(\nu(V)\) if the fugacity is below a certain threshold. For the \(d\)-dimensional hard-sphere model with particles of unit volume, this threshold is \(\mathrm{e}/2^d\). As the number of dimensions \(d\) increases, this bound asymptotically matches the best known results for randomized approximation of the hard-sphere partition function. We prove similar bounds for the Widom--Rowlinson model. To the best of our knowledge, this is the first rigorous algorithmic result for this model.
@inproceedings{friedrich2022algorithms, abstract = {We study the algorithmic applications of a natural discretization for the hard-sphere model and the Widom&ndash;Rowlinson model in a region of \(d\)-dimensional Euclidean space \(V \subset \mathbf{R}^{d}\). These continuous models are frequently used in statistical physics to describe mixtures of one or multiple particle types subjected to hard-core interactions. For each type, particles are distributed according to a Poisson point process with a type-specific activity parameter, called fugacity. The Gibbs distribution over all possible system states is characterized by the mixture of these point processes conditioned that no two particles are closer than some type-dependent distance threshold. A key part in better understanding the Gibbs distribution is its normalizing constant, called partition function. Our main algorithmic result is the first deterministic approximation algorithm for the partition function of the hard-sphere model and the Widom&ndash;Rowlinson model in box-shaped regions of Euclidean space. Our algorithms have quasi-polynomial running time in the volume of the region \(\nu(V)\) if the fugacity is below a certain threshold. For the \(d\)-dimensional hard-sphere model with particles of unit volume, this threshold is \(\mathrm{e}/2^d\). As the number of dimensions \(d\) increases, this bound asymptotically matches the best known results for randomized approximation of the hard-sphere partition function. We prove similar bounds for the Widom&ndash;Rowlinson model. To the best of our knowledge, this is the first rigorous algorithmic result for this model.}, author = {Friedrich, Tobias and Göbel, Andreas and Katzmann, Maximilian and Krejca, Martin S. and Pappik, Marcus}, booktitle = {International Computing and Combinatorics Conference (COCOON)}, keywords = {marcuspappik martinskrejca andreasgoebel tobiasfriedrich cocoon maximiliankatzmann year2022}, pages = {242–254}, title = {Algorithms for hard-constraint point processes via discretization}, year = 2022 }

Baguley, Samuel; Friedrich, Tobias; Timo, Kötzing; Li, Xiaoyue; Pappik, Marcus; Zeif, Ziena Analysis of a Gray-Box Operator for Vertex CoverGenetic and Evolutionary Computation Conference (GECCO) 2022: 1363–1371
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Combinatorial optimization problems are a prominent application area of evolutionary algorithms, where the (1+1) EA is one of the most investigated. We extend this algorithm by introducing some problem knowledge with a specialized mutation operator which works under the assumption that the number of 1s of a solution is critical, as frequently happens in combinatorial optimization. This slight modification increases the chance to correct wrongly placed bits while preserving the simplicity and problem independence of the (1+1) EA. As an application of our algorithm we examine the vertex cover problem on certain instances, where we show that it leads to asymptotically better runtimes and even finds with higher probability optimal solutions in comparison with the usual (1+1) EA. Precisely, we compare the performance of both algorithms on paths and on complete bipartite graphs of size \(n\). Regarding the path we prove that, for a particular initial configuration, the (1+1) EA takes in expectation \(\Theta(n^4)\) iterations while the modification reduces this to \(\Theta(n^3)\), and present experimental evidence that such a configuration is reached. Concerning the complete bipartite graph our modification finds the optimum in polynomial time with probability \(1-1/2^{\Omega(n^\xi)}\) for every positive constant \(\xi < 1\), which improves the known probability of \(1-1/\)poly\((n)\) for the (1+1) EA.
@inproceedings{baguley2022analysis, abstract = {Combinatorial optimization problems are a prominent application area of evolutionary algorithms, where the (1+1) EA is one of the most investigated. We extend this algorithm by introducing some problem knowledge with a specialized mutation operator which works under the assumption that the number of 1s of a solution is critical, as frequently happens in combinatorial optimization. This slight modification increases the chance to correct wrongly placed bits while preserving the simplicity and problem independence of the (1+1) EA. As an application of our algorithm we examine the vertex cover problem on certain instances, where we show that it leads to asymptotically better runtimes and even finds with higher probability optimal solutions in comparison with the usual (1+1) EA. Precisely, we compare the performance of both algorithms on paths and on complete bipartite graphs of size \(n\). Regarding the path we prove that, for a particular initial configuration, the (1+1) EA takes in expectation \(\Theta(n^4)\) iterations while the modification reduces this to \(\Theta(n^3)\), and present experimental evidence that such a configuration is reached. Concerning the complete bipartite graph our modification finds the optimum in polynomial time with probability \(1-1/2^{\Omega(n^\xi)}\) for every positive constant \(\xi < 1\), which improves the known probability of \(1-1/\)poly\((n)\) for the (1+1) EA.}, author = {Baguley, Samuel and Friedrich, Tobias and Timo, Kötzing and Li, Xiaoyue and Pappik, Marcus and Zeif, Ziena}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {sys:relevantfor:ae zienazeif marcuspappik samuelbaguley xiaoyueli timokoetzing tobiasfriedrich gecco year2022}, pages = {1363&ndash;1371}, title = {Analysis of a Gray-Box Operator for Vertex Cover}, year = 2022 }

2021 [ nach oben ]

Friedrich, Tobias; Göbel, Andreas; Krejca, Martin S.; Pappik, Marcus A spectral independence view on hard spheres via block dynamicsInternational Colloquium on Automata, Languages and Programming (ICALP) 2021: 66:1–66:15
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
The hard-sphere model is one of the most extensively studied models in statistical physics. It describes the continuous distribution of spherical particles, governed by hard-core interactions. An important quantity of this model is the normalizing factor of this distribution, called the partition function. We propose a Markov chain Monte Carlo algorithm for approximating the grand-canonical partition function of the hard-sphere model in \(d\) dimensions. Up to a fugacity of \( \lambda < \text{e}/2^d\), the runtime of our algorithm is polynomial in the volume of the system. This covers the entire known real-valued regime for the uniqueness of the Gibbs measure. Key to our approach is to define a discretization that closely approximates the partition function of the continuous model. This results in a discrete hard-core instance that is exponential in the size of the initial hard-sphere model. Our approximation bound follows directly from the correlation decay threshold of an infinite regular tree with degree equal to the maximum degree of our discretization. To cope with the exponential blow-up of the discrete instance we use clique dynamics, a Markov chain that was recently introduced in the setting of abstract polymer models. We prove rapid mixing of clique dynamics up to the tree threshold of the univariate hard-core model. This is achieved by relating clique dynamics to block dynamics and adapting the spectral expansion method, which was recently used to bound the mixing time of Glauber dynamics within the same parameter regime.
@inproceedings{fgkp-asivohsvbd-2021, abstract = {The hard-sphere model is one of the most extensively studied models in statistical physics. It describes the continuous distribution of spherical particles, governed by hard-core interactions. An important quantity of this model is the normalizing factor of this distribution, called the partition function. We propose a Markov chain Monte Carlo algorithm for approximating the grand-canonical partition function of the hard-sphere model in \(d\) dimensions. Up to a fugacity of \( \lambda < \text{e}/2^d\), the runtime of our algorithm is polynomial in the volume of the system. This covers the entire known real-valued regime for the uniqueness of the Gibbs measure. Key to our approach is to define a discretization that closely approximates the partition function of the continuous model. This results in a discrete hard-core instance that is exponential in the size of the initial hard-sphere model. Our approximation bound follows directly from the correlation decay threshold of an infinite regular tree with degree equal to the maximum degree of our discretization. To cope with the exponential blow-up of the discrete instance we use clique dynamics, a Markov chain that was recently introduced in the setting of abstract polymer models. We prove rapid mixing of clique dynamics up to the tree threshold of the univariate hard-core model. This is achieved by relating clique dynamics to block dynamics and adapting the spectral expansion method, which was recently used to bound the mixing time of Glauber dynamics within the same parameter regime.}, author = {Friedrich, Tobias and Göbel, Andreas and Krejca, Martin S. and Pappik, Marcus}, booktitle = {International Colloquium on Automata, Languages and Programming (ICALP)}, keywords = {marcuspappik martinskrejca andreasgoebel tobiasfriedrich icalp year2021}, pages = {66:1-66:15}, title = {A spectral independence view on hard spheres via block dynamics}, volume = 198, year = 2021 }

2019 [ nach oben ]

Echzell, Hagen; Friedrich, Tobias; Lenzner, Pascal; Molitor, Louise; Pappik, Marcus; Schöne, Friedrich; Sommer, Fabian; Stangl, David Convergence and Hardness of Strategic Schelling SegregationWeb and Internet Economics (WINE) 2019: 156–170
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
The phenomenon of residential segregation was captured by Schelling's famous segregation model where two types of agents are placed on a grid and an agent is content with her location if the fraction of her neighbors which have the same type as her is at least \(\tau\), for some \(0<\tau<1\). Discontent agents simply swap their location with a randomly chosen other discontent agent or jump to a random empty cell. We analyze a generalized game-theoretic model of Schelling segregation which allows more than two agent types and more general underlying graphs modeling the residential area. For this we show that both aspects heavily influence the dynamic properties and the tractability of finding an optimal placement. We map the boundary of when improving response dynamics (IRD), i.e., the natural approach for finding equilibrium states, are guaranteed to converge. For this we prove several sharp threshold results where guaranteed IRD convergence suddenly turns into the strongest possible non-convergence result: a violation of weak acyclicity. In particular, we show such threshold results also for Schelling's original model, which is in contrast to the standard assumption in many empirical papers. Furthermore, we show that in case of convergence, IRD find an equilibrium in \(O(m)\) steps, where \(m\) is the number of edges in the underlying graph and show that this bound is met in empirical simulations starting from random initial agent placements.
@inproceedings{echzell2019convergence, abstract = {The phenomenon of residential segregation was captured by Schelling's famous segregation model where two types of agents are placed on a grid and an agent is content with her location if the fraction of her neighbors which have the same type as her is at least \(\tau\), for some \(0<\tau<1\). Discontent agents simply swap their location with a randomly chosen other discontent agent or jump to a random empty cell. We analyze a generalized game-theoretic model of Schelling segregation which allows more than two agent types and more general underlying graphs modeling the residential area. For this we show that both aspects heavily influence the dynamic properties and the tractability of finding an optimal placement. We map the boundary of when improving response dynamics (IRD), i.e., the natural approach for finding equilibrium states, are guaranteed to converge. For this we prove several sharp threshold results where guaranteed IRD convergence suddenly turns into the strongest possible non-convergence result: a violation of weak acyclicity. In particular, we show such threshold results also for Schelling's original model, which is in contrast to the standard assumption in many empirical papers. Furthermore, we show that in case of convergence, IRD find an equilibrium in \(O(m)\) steps, where \(m\) is the number of edges in the underlying graph and show that this bound is met in empirical simulations starting from random initial agent placements.}, author = {Echzell, Hagen and Friedrich, Tobias and Lenzner, Pascal and Molitor, Louise and Pappik, Marcus and Schöne, Friedrich and Sommer, Fabian and Stangl, David}, booktitle = {Web and Internet Economics (WINE)}, keywords = {marcuspappik louisemolitor year2019 tobiasfriedrich pascallenzner wine}, pages = {156-170}, title = {Convergence and Hardness of Strategic Schelling Segregation}, year = 2019 }

2018 [ nach oben ]

Kumar Shekar, Arvind; Pappik, Marcus; Iglesias Sánchez, Patricia; Müller, Emmanuel Selection of Relevant and Non-Redundant Multivariate Ordinal Patterns for Time Series ClassificationDiscovery Science (DS) 2018: 224–240
[ Abstract ] [ BibTeX ] [ DOI ]
 
Transformation of multivariate time series into feature spaces are common for data mining tasks like classification. Ordinality is one important property in time series that provides a qualitative representation of the underlying dynamic regime. In a multivariate time series, ordinalities from multiple dimensions combine together to be discriminative for the classification problem. However, existing works on ordinality do not address the multivariate nature of the time series. For multivariate ordinal patterns, there is a computational challenge with an explosion of pattern combinations, while not all patterns are relevant and provide novel information for the classification. In this work, we propose a technique for the extraction and selection of relevant and non-redundant multivariate ordinal patterns from the high-dimensional combinatorial search space. Our proposed approach Ordinal feature extraction (ordex), simultaneously extracts and scores the relevance and redundancy of ordinal patterns without training a classifier. As a filter-based approach, ordex aims to select a set of relevant patterns with complementary information. Hence, using our scoring function based on the principles of Chebyshev’s inequality, we maximize the relevance of the patterns and minimize the correlation between them. Our experiments on real world datasets show that ordinality in time series contains valuable information for classification in several applications.
@inproceedings{kumarshekar2018selection, abstract = {Transformation of multivariate time series into feature spaces are common for data mining tasks like classification. Ordinality is one important property in time series that provides a qualitative representation of the underlying dynamic regime. In a multivariate time series, ordinalities from multiple dimensions combine together to be discriminative for the classification problem. However, existing works on ordinality do not address the multivariate nature of the time series. For multivariate ordinal patterns, there is a computational challenge with an explosion of pattern combinations, while not all patterns are relevant and provide novel information for the classification. In this work, we propose a technique for the extraction and selection of relevant and non-redundant multivariate ordinal patterns from the high-dimensional combinatorial search space. Our proposed approach Ordinal feature extraction (ordex), simultaneously extracts and scores the relevance and redundancy of ordinal patterns without training a classifier. As a filter-based approach, ordex aims to select a set of relevant patterns with complementary information. Hence, using our scoring function based on the principles of Chebyshev’s inequality, we maximize the relevance of the patterns and minimize the correlation between them. Our experiments on real world datasets show that ordinality in time series contains valuable information for classification in several applications.}, author = {Kumar Shekar, Arvind and Pappik, Marcus and Iglesias Sánchez, Patricia and Müller, Emmanuel}, booktitle = {Discovery Science (DS)}, keywords = {marcuspappik year2018 ds}, pages = {224-240}, title = {Selection of Relevant and Non-Redundant Multivariate Ordinal Patterns for Time Series Classification}, year = 2018 }

2017 [ nach oben ]

Kirsch, Louis; Riekenbrauck, Niklas; Thevessen, Daniel; Pappik, Marcus; Stebner, Axel; Kunze, Julius; Meissner, Alexander; Kumar Shekar, Arvind; Müller, Emmanuel Framework for Exploring and Understanding Multivariate CorrelationsMachine Learning and Knowledge Discovery in Databases (ECML/PKDD) 2017: 404–408
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Feature selection is an essential step to identify relevant and non-redundant features for target class prediction. In this context, the number of feature combinations grows exponentially with the dimension of the feature space. This hinders the user’s understanding of the feature-target relevance and feature-feature redundancy. We propose an interactive Framework for Exploring and Understanding Multivariate Correlations (FEXUM), which embeds these correlations using a force-directed graph. In contrast to existing work, our framework allows the user to explore the correlated feature space and guides in understanding multivariate correlations through interactive visualizations.
@inproceedings{kirsch2017framework, abstract = {Feature selection is an essential step to identify relevant and non-redundant features for target class prediction. In this context, the number of feature combinations grows exponentially with the dimension of the feature space. This hinders the user’s understanding of the feature-target relevance and feature-feature redundancy. We propose an interactive Framework for Exploring and Understanding Multivariate Correlations (FEXUM), which embeds these correlations using a force-directed graph. In contrast to existing work, our framework allows the user to explore the correlated feature space and guides in understanding multivariate correlations through interactive visualizations.}, author = {Kirsch, Louis and Riekenbrauck, Niklas and Thevessen, Daniel and Pappik, Marcus and Stebner, Axel and Kunze, Julius and Meissner, Alexander and Kumar Shekar, Arvind and Müller, Emmanuel}, booktitle = {Machine Learning and Knowledge Discovery in Databases (ECML/PKDD)}, keywords = {marcuspappik ecml year2017 pkdd}, pages = {404-408}, title = {Framework for Exploring and Understanding Multivariate Correlations}, year = 2017 }

2020 [ nach oben ]

Pappik, Marcus New Conditions via Markov Chains: Approximating Partition Functions of Abstract Polymer Models without Cluster Expansionmaster’s thesis, Hasso Plattner Institute 2020
[ Abstract ] [ BibTeX ] [ Download ]
 
Abstract polymer models are combinatorial structures that consist of a set of weighted objects, called polymers, together with a reflexive and symmetric incompatibility relation that describes which polymers cannot occur together. In this thesis we present the first Markov chain approach for sampling from the Gibbs distribution of abstract polymer models. Known Markov chains for polymer models from vertex and edge spin systems can be seen as special cases of this polymer Markov chain. We introduce the concept of polymer cliques and propose a generalized polymer mixing condition as a way to guarantee rapid mixing of our chain. The form of this condition is similar to conditions from cluster expansion approaches, such as the Kotecký-Preiss condition and the Fernández-Procacci condition, but it is less restrictive. To obtain an efficient sampling scheme for the Gibbs distribution from our polymer Markov chain, we prove that it suffices to draw each step of the chain approximately according to its transition probabilities. As one way to approximate each transition of the chain, we suggest to truncate each polymer clique based on some notion of size. We introduce the clique truncation condition as a general tool to determine the maximum size of polymers that we have to consider for the steps of the chain. We prove that our sampling scheme can be used to construct an FPRAS for the partition function. By this, we obtain the first Markov chain Monte Carlo method that works for abstract polymer models in a similar regime as cluster expansion approaches and beyond, while avoiding their complicated analytical assumptions and arguments. Further, we illustrate how our approach can be applied to algorithmic problems like the hard-core model on bipartite \(\alpha\)-expander graphs and the perfect matching polynomial to obtain new trade-offs between runtime and weight bounds. We emphasize that similar results can be obtained for a variety of other applications.
@mastersthesis{pappik2020conditions, abstract = {Abstract polymer models are combinatorial structures that consist of a set of weighted objects, called polymers, together with a reflexive and symmetric incompatibility relation that describes which polymers cannot occur together. In this thesis we present the first Markov chain approach for sampling from the Gibbs distribution of abstract polymer models. Known Markov chains for polymer models from vertex and edge spin systems can be seen as special cases of this polymer Markov chain. We introduce the concept of polymer cliques and propose a generalized polymer mixing condition as a way to guarantee rapid mixing of our chain. The form of this condition is similar to conditions from cluster expansion approaches, such as the Kotecký-Preiss condition and the Fernández-Procacci condition, but it is less restrictive. To obtain an efficient sampling scheme for the Gibbs distribution from our polymer Markov chain, we prove that it suffices to draw each step of the chain approximately according to its transition probabilities. As one way to approximate each transition of the chain, we suggest to truncate each polymer clique based on some notion of size. We introduce the clique truncation condition as a general tool to determine the maximum size of polymers that we have to consider for the steps of the chain. We prove that our sampling scheme can be used to construct an FPRAS for the partition function. By this, we obtain the first Markov chain Monte Carlo method that works for abstract polymer models in a similar regime as cluster expansion approaches and beyond, while avoiding their complicated analytical assumptions and arguments. Further, we illustrate how our approach can be applied to algorithmic problems like the hard-core model on bipartite \(\alpha\)-expander graphs and the perfect matching polynomial to obtain new trade-offs between runtime and weight bounds. We emphasize that similar results can be obtained for a variety of other applications.}, annote = {master's thesis, Hasso Plattner Institute}, author = {Pappik, Marcus}, keywords = {marcuspappik theses year2020}, school = {Hasso Plattner Institute}, title = {New Conditions via Markov Chains: Approximating Partition Functions of Abstract Polymer Models without Cluster Expansion}, year = 2020 }