Frederik Mallmann-Trenn
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Frederik Mallmann-Trenn has a total of 56 co-authors. Here are the top co-authors by number of shared publications:
- Colin Cooper
King's College London, London, United Kingdom
3 shared publications - Matthew Cavorsi
School of Engineering and Applied Sciences, Harvard University, Cambridge, MA, USA
3 shared publications - Stephanie Gil
School of Engineering and Applied Sciences, Harvard University, Allston, MA, USA
3 shared publications - Tomasz Radzik
King's College London, London, United Kingdom
3 shared publications - Xin Liu
National Institute of Advanced Industrial Science and Technology, Tokyo, Japan
3 shared publications - Aurora Rossi2 shared publications
Latest Publications
- Open Access
- 6 November 2026
- Published by Association for Computing Machinery (ACM)
- p. 885-896
Degree-Mass Message Passing for Betweenness Ranking in Directed and Undirected Networks
- 6 November 2026
- Published by Association for Computing Machinery (ACM)
- p. 885-896
Open AccessDegree-Mass Message Passing for Betweenness Ranking in Directed and Undirected Networks
- Open Access
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 77-87
Undecided State Dynamics with Many Opinions
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 77-87
Open AccessUndecided State Dynamics with Many Opinions
- Open Access
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 425-436
Order Statistics in Population Protocols via Simple Dynamics
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 425-436
Open AccessOrder Statistics in Population Protocols via Simple Dynamics
- 2 April 2026
- Published by Agence Bibliographique de l'Enseignement Supérieur
Probabilistic analysis of distributed processes with focus on consensus
Analyse probabiliste de processus distribués axés sur les processus de consensus: Cette thèse est consacrée à l'étude des processus stochastiques décentralisés. Parmi les exemples typiques de ces processus figurent la dynamique météorologique, la circulation automobile, la façon dont nous rencontrons nos amis, etc. Dans cette thèse, nous exploitons une large palette d'outils probabilistes permettant d'analyser des chaînes de Markov afin d'étudier un large éventail de ces processus distribués : modèle des feux de forêt (réseaux sociaux), balls-into-bins avec suppression, et des dynamiques et protocoles de consensus fondamentaux tels que Voter Model, 2-Choices, et 3-Majority.
- 2 April 2026
- Published by Agence Bibliographique de l'Enseignement Supérieur
Probabilistic analysis of distributed processes with focus on consensus
Analyse probabiliste de processus distribués axés sur les processus de consensus: Cette thèse est consacrée à l'étude des processus stochastiques décentralisés. Parmi les exemples typiques de ces processus figurent la dynamique météorologique, la circulation automobile, la façon dont nous rencontrons nos amis, etc. Dans cette thèse, nous exploitons une large palette d'outils probabilistes permettant d'analyser des chaînes de Markov afin d'étudier un large éventail de ces processus distribués : modèle des feux de forêt (réseaux sociaux), balls-into-bins avec suppression, et des dynamiques et protocoles de consensus fondamentaux tels que Voter Model, 2-Choices, et 3-Majority.
- Open Access
BRAVA-GNN: Betweenness Ranking Approximation Via Degree MAss Inspired Graph Neural Network
Computing node importance in networks is a long-standing fundamental problem that has driven extensive study of various centrality measures.A particularly well‑known centrality measure is betweenness centrality, which becomes computationally prohibitive on large‑scale networks.Graph Neural Network (GNN) models have thus been proposed to predict node rankings according to their relative betweenness centrality. However, state‑of‑the‑art methods fail to generalize to high‑diameter graphs such as road networks.We propose BRAVA‑GNN, a lightweight GNN architecture that leverages the empirically observed correlation linking betweenness centrality to degree‑based quantities, in particular multi-hop degree mass. This correlation motivates the use of degree masses as size-invariant node features and synthetic training graphs that closely match the degree distributions of real networks.Furthermore, while previous work relies on scale-free synthetic graphs, we leverage the hyperbolic random graph model, which reproduces power‑law exponents outside the scale‑free regime, better capturing the structure of real‑world graphs like road networks.This design enables BRAVA-GNN to generalize across diverse graph families while using 54$\times$ fewer parameters than the most lightweight existing GNN baseline. Extensive experiments on 19 real-world networks, spanning social, web, email, and road graphs, show that BRAVA-GNN achieves up to 214\% improvement in Kendall–Tau correlation and up to 70$\times$ speedup in inference time over state-of-the-art GNN-based approaches, particularly on challenging road networks.
Open AccessBRAVA-GNN: Betweenness Ranking Approximation Via Degree MAss Inspired Graph Neural Network
Computing node importance in networks is a long-standing fundamental problem that has driven extensive study of various centrality measures.A particularly well‑known centrality measure is betweenness centrality, which becomes computationally prohibitive on large‑scale networks.Graph Neural Network (GNN) models have thus been proposed to predict node rankings according to their relative betweenness centrality. However, state‑of‑the‑art methods fail to generalize to high‑diameter graphs such as road networks.We propose BRAVA‑GNN, a lightweight GNN architecture that leverages the empirically observed correlation linking betweenness centrality to degree‑based quantities, in particular multi-hop degree mass. This correlation motivates the use of degree masses as size-invariant node features and synthetic training graphs that closely match the degree distributions of real networks.Furthermore, while previous work relies on scale-free synthetic graphs, we leverage the hyperbolic random graph model, which reproduces power‑law exponents outside the scale‑free regime, better capturing the structure of real‑world graphs like road networks.This design enables BRAVA-GNN to generalize across diverse graph families while using 54$\times$ fewer parameters than the most lightweight existing GNN baseline. Extensive experiments on 19 real-world networks, spanning social, web, email, and road graphs, show that BRAVA-GNN achieves up to 214\% improvement in Kendall–Tau correlation and up to 70$\times$ speedup in inference time over state-of-the-art GNN-based approaches, particularly on challenging road networks.
- Open Access
BRAVA-GNN: Betweenness Ranking Approximation Via Degree MAss Inspired Graph Neural Network
Computing node importance in networks is a long-standing fundamental problem that has driven extensive study of various centrality measures. A particularly well-known centrality measure is betweenness centrality, which becomes computationally prohibitive on large-scale networks. Graph Neural Network (GNN) models have thus been proposed to predict node rankings according to their relative betweenness centrality. However, state-of-the-art methods fail to generalize to high-diameter graphs such as road networks. We propose BRAVA-GNN, a lightweight GNN architecture that leverages the empirically observed correlation linking betweenness centrality to degree-based quantities, in particular multi-hop degree mass. This correlation motivates the use of degree masses as size-invariant node features and synthetic training graphs that closely match the degree distributions of real networks. Furthermore, while previous work relies on scale-free synthetic graphs, we leverage the hyperbolic random graph model, which reproduces power-law exponents outside the scale-free regime, better capturing the structure of real-world graphs like road networks. This design enables BRAVA-GNN to generalize across diverse graph families while using 54x fewer parameters than the most lightweight existing GNN baseline. Extensive experiments on 19 real-world networks, spanning social, web, email, and road graphs, show that BRAVA-GNN achieves up to 214% improvement in Kendall-Tau correlation and up to 70x speedup in inference time over state-of-the-art GNN-based approaches, particularly on challenging road networks.
Open AccessBRAVA-GNN: Betweenness Ranking Approximation Via Degree MAss Inspired Graph Neural Network
Computing node importance in networks is a long-standing fundamental problem that has driven extensive study of various centrality measures. A particularly well-known centrality measure is betweenness centrality, which becomes computationally prohibitive on large-scale networks. Graph Neural Network (GNN) models have thus been proposed to predict node rankings according to their relative betweenness centrality. However, state-of-the-art methods fail to generalize to high-diameter graphs such as road networks. We propose BRAVA-GNN, a lightweight GNN architecture that leverages the empirically observed correlation linking betweenness centrality to degree-based quantities, in particular multi-hop degree mass. This correlation motivates the use of degree masses as size-invariant node features and synthetic training graphs that closely match the degree distributions of real networks. Furthermore, while previous work relies on scale-free synthetic graphs, we leverage the hyperbolic random graph model, which reproduces power-law exponents outside the scale-free regime, better capturing the structure of real-world graphs like road networks. This design enables BRAVA-GNN to generalize across diverse graph families while using 54x fewer parameters than the most lightweight existing GNN baseline. Extensive experiments on 19 real-world networks, spanning social, web, email, and road graphs, show that BRAVA-GNN achieves up to 214% improvement in Kendall-Tau correlation and up to 70x speedup in inference time over state-of-the-art GNN-based approaches, particularly on challenging road networks.
- Open Access
Probably Approximately Correct Maximum A Posteriori Inference
Computing the conditional mode of a distribution, better known as the $\mathit{maximum\ a\ posteriori}$ (MAP) assignment, is a fundamental task in probabilistic inference. However, MAP estimation is generally intractable, and remains hard even under many common structural constraints and approximation schemes. We introduce $\mathit{probably\ approximately\ correct}$ (PAC) algorithms for MAP inference that provide provably optimal solutions under variable and fixed computational budgets. We characterize tractability conditions for PAC-MAP using information theoretic measures that can be estimated from finite samples. Our PAC-MAP solvers are efficiently implemented using probabilistic circuits with appropriate architectures. The randomization strategies we develop can be used either as standalone MAP inference techniques or to improve on popular heuristics, fortifying their solutions with rigorous guarantees. Experiments confirm the benefits of our method in a range of benchmarks.Open AccessProbably Approximately Correct Maximum A Posteriori Inference
Computing the conditional mode of a distribution, better known as the $\mathit{maximum\ a\ posteriori}$ (MAP) assignment, is a fundamental task in probabilistic inference. However, MAP estimation is generally intractable, and remains hard even under many common structural constraints and approximation schemes. We introduce $\mathit{probably\ approximately\ correct}$ (PAC) algorithms for MAP inference that provide provably optimal solutions under variable and fixed computational budgets. We characterize tractability conditions for PAC-MAP using information theoretic measures that can be estimated from finite samples. Our PAC-MAP solvers are efficiently implemented using probabilistic circuits with appropriate architectures. The randomization strategies we develop can be used either as standalone MAP inference techniques or to improve on popular heuristics, fortifying their solutions with rigorous guarantees. Experiments confirm the benefits of our method in a range of benchmarks. - 12 September 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Robotics
- Vol. 41 (15523098) , 5533-5549
quasi-Dynamic Crowd Vetting: Collaborative Detection of Malicious Robots in Dynamic Communication Networks
We are interested in the problem where robots traverse through an environment modeled by a graph of discrete sites, and an unknown subset of the multirobot team is malicious. Previous works require that each robot gathers information about the trustworthiness of all other robots, called trust observations, which can be time consuming in large networks. This article decreases the time required to estimate trustworthiness by building upon an algorithm that leverages the concept of “crowd vetting” and the opinion of trusted neighbors. This allows each robot to estimate trust in dynamic scenarios, where the team size, robot neighborhoods, and robot legitimacy can change. In particular, we employ an assumption that there exists quasi-dynamic time periods, where if a robot’s legitimacy remains fixed for a sufficient length of time, its trustworthiness can be characterized. In this setting, we develop a closed-form expression for the critical number of time-steps required for our algorithm to successfully identify the true legitimacy of each robot within a specified failure probability. We show that the number of time-steps required for robots to correctly estimate the trust of all other robots increases logarithmically with the number of robots when robots do not leverage neighboring opinions, called the direct protocol. Conversely, for most general graph topologies, the number of time-steps required remains constant as the number of robots increases when our proposed algorithm, called quasi-dynamic crowd vetting (DCV), is used, for a fixed ratio of legitimate to malicious robots. Finally, our theoretical results are successfully validated through simulated persistent surveillance tasks where robots maintain a desired distribution of robots over sites in the environment.
- 12 September 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Robotics
- Vol. 41 (15523098) , 5533-5549
quasi-Dynamic Crowd Vetting: Collaborative Detection of Malicious Robots in Dynamic Communication Networks
We are interested in the problem where robots traverse through an environment modeled by a graph of discrete sites, and an unknown subset of the multirobot team is malicious. Previous works require that each robot gathers information about the trustworthiness of all other robots, called trust observations, which can be time consuming in large networks. This article decreases the time required to estimate trustworthiness by building upon an algorithm that leverages the concept of “crowd vetting” and the opinion of trusted neighbors. This allows each robot to estimate trust in dynamic scenarios, where the team size, robot neighborhoods, and robot legitimacy can change. In particular, we employ an assumption that there exists quasi-dynamic time periods, where if a robot’s legitimacy remains fixed for a sufficient length of time, its trustworthiness can be characterized. In this setting, we develop a closed-form expression for the critical number of time-steps required for our algorithm to successfully identify the true legitimacy of each robot within a specified failure probability. We show that the number of time-steps required for robots to correctly estimate the trust of all other robots increases logarithmically with the number of robots when robots do not leverage neighboring opinions, called the direct protocol. Conversely, for most general graph topologies, the number of time-steps required remains constant as the number of robots increases when our proposed algorithm, called quasi-dynamic crowd vetting (DCV), is used, for a fixed ratio of legitimate to malicious robots. Finally, our theoretical results are successfully validated through simulated persistent surveillance tasks where robots maintain a desired distribution of robots over sites in the environment.
- Open Access
Modeling Feasible Locomotion of Nanobots for Cancer Detection and Treatment
Deploying motile nanosized particles, also known as ``nanobots'', in the human body promises to improve selectivity in drug delivery and reduce side effects. We consider a swarm of nanobots locating a single cancerous region and treating it by releasing an onboard payload of drugs at the site. At nanoscale, the computation, communication, sensing, and locomotion capabilities of individual agents are extremely limited, noisy, and/or nonexistent. We present a general model to formally describe the individual and collective behavior of agents in a colloidal environment, such as the bloodstream, for cancer detection and treatment by nanobots. This includes a feasible and precise model of agent locomotion, inspired by actual nanoparticles that, in the presence of an external chemical gradient, move towards areas of higher concentration by means of self-propulsion. We present two variants of our general model: The first assumes an endogenous chemical gradient that is fixed over time and centered at the targeted cancer site; the second is a more speculative and dynamic variant in which agents themselves create and amplify a chemical gradient centered at the cancer site. In both settings, agents can sense the gradient and ascend it noisily, locating the cancer site more quickly than via simple Brownian motion. For the first variant of the model, we present simulation results to show the behavior of agents under our locomotion model, as well as {analytical results} to bound the time it takes for the agents to reach the cancer site. For the second variant, simulation results highlight the collective benefit in having agents issue their own chemical signal. While arguably more speculative in its agent capability assumptions, this variant shows a significant improvement in runtime performance over the first variant, resulting from its chemical signal amplification mechanism.
Open AccessModeling Feasible Locomotion of Nanobots for Cancer Detection and Treatment
Deploying motile nanosized particles, also known as ``nanobots'', in the human body promises to improve selectivity in drug delivery and reduce side effects. We consider a swarm of nanobots locating a single cancerous region and treating it by releasing an onboard payload of drugs at the site. At nanoscale, the computation, communication, sensing, and locomotion capabilities of individual agents are extremely limited, noisy, and/or nonexistent. We present a general model to formally describe the individual and collective behavior of agents in a colloidal environment, such as the bloodstream, for cancer detection and treatment by nanobots. This includes a feasible and precise model of agent locomotion, inspired by actual nanoparticles that, in the presence of an external chemical gradient, move towards areas of higher concentration by means of self-propulsion. We present two variants of our general model: The first assumes an endogenous chemical gradient that is fixed over time and centered at the targeted cancer site; the second is a more speculative and dynamic variant in which agents themselves create and amplify a chemical gradient centered at the cancer site. In both settings, agents can sense the gradient and ascend it noisily, locating the cancer site more quickly than via simple Brownian motion. For the first variant of the model, we present simulation results to show the behavior of agents under our locomotion model, as well as {analytical results} to bound the time it takes for the agents to reach the cancer site. For the second variant, simulation results highlight the collective benefit in having agents issue their own chemical signal. While arguably more speculative in its agent capability assumptions, this variant shows a significant improvement in runtime performance over the first variant, resulting from its chemical signal amplification mechanism.
- 3 April 2025
- Published by Springer Nature
- p. 152-165
Harmonizing Vs Polarizing Platform Influence Functions
- 3 April 2025
- Published by Springer Nature
- p. 152-165
Harmonizing Vs Polarizing Platform Influence Functions