SNStefan Neumann

Stefan Neumann

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Stefan Neumann has a total of 29 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Four-Cycle Counting in Low-Degeneracy Graph Streams

    by Sebastian Lüderssen, Stefan Neumann, Pan Peng

    We study the problem of (1+ε)-approximating the number of four-cycles in graphs given as arbitrary order edge streams. We propose two new algorithms based on sampling induced subgraphs. Our first contribution is a two-pass algorithm that uses Õ(κm / √T) space, where m is the number of edges, T is the number of four-cycles, and κ is the graph's degeneracy. This algorithm improves upon existing theoretical bounds and is provably optimal for constant-degeneracy graphs, matching the known Ω(m/√T) lower bound up to lower-order factors. Our second contribution is a one-pass algorithm that remains accurate when four-cycles are not highly concentrated on individual nodes, edges, or wedges; this structural property is common in sparse social and collaboration networks. We evaluate both algorithms on a variety of real-world graph streams. The two-pass algorithm consistently outperforms state-of-the-art methods, using substantially less space to achieve a desired accuracy. The one-pass algorithm is competitive when four cycles are evenly distributed, matching our theoretical analysis. Unlike several recent works, our algorithms perform well even on non-bipartite graphs such as social networks.


  • Open Access

    Calibrated and Diverse News Coverage

    by Tianyi Zhou, Stefan Neumann, Kiran Garimella, Aristides Gionis


  • Open Access

    The Impact of External Sources on the Friedkin–Johnsen Model

    by Charlotte Out, Sijing Tu, Stefan Neumann, Ahad N. Zehmakan

    To obtain a foundational understanding of timeline algorithms and viral content in shaping public opinions, computer scientists started to study augmented versions of opinion formation models from sociology. In this paper, we generalize the popular Friedkin--Johnsen model to include the effects of external media sources on opinion formation. Our goal is to mathematically analyze the influence of biased media, arising from factors such as manipulated news reporting or the phenomenon of false balance. Within our framework, we examine the scenario of two opposing media sources, which do not adapt their opinions like ordinary nodes, and analyze the conditions and the number of periods required for radicalizing the opinions in the network. When both media sources possess equal influence, we theoretically characterize the final opinion configuration. In the special case where there is only a single media source present, we prove that media sources which do not adapt their opinions are significantly more powerful than those which do. Lastly, we conduct the experiments on real-world and synthetic datasets, showing that our theoretical guarantees closely align with experimental simulations.


  • Open Access

    Sublinear-Time Opinion Estimation in the Friedkin--Johnsen Model

    by Stefan Neumann, Yinhao Dong, Pan Peng

    Online social networks are ubiquitous parts of modern societies and the discussions that take place in these networks impact people's opinions on diverse topics, such as politics or vaccination. One of the most popular models to formally describe this opinion formation process is the Friedkin--Johnsen (FJ) model, which allows to define measures, such as the polarization and the disagreement of a network. Recently, Xu, Bao and Zhang (WebConf'21) showed that all opinions and relevant measures in the FJ model can be approximated in near-linear time. However, their algorithm requires the entire network and the opinions of all nodes as input. Given the sheer size of online social networks and increasing data-access limitations, obtaining the entirety of this data might, however, be unrealistic in practice. In this paper, we show that node opinions and all relevant measures, like polarization and disagreement, can be efficiently approximated in time that is sublinear in the size of the network. Particularly, our algorithms only require query-access to the network and do not have to preprocess the graph. Furthermore, we use a connection between FJ opinion dynamics and personalized PageRank, and show that in d-regular graphs, we can deterministically approximate each node's opinion by only looking at a constant-size neighborhood, independently of the network size. We also experimentally validate that our estimation algorithms perform well in practice.


  • Open Access

    Adversaries with Limited Information in the Friedkin--Johnsen Model

    by Sijing Tu, Stefan Neumann, Aristides Gionis

    In recent years, online social networks have been the target of adversaries who seek to introduce discord into societies, to undermine democracies and to destabilize communities. Often the goal is not to favor a certain side of a conflict but to increase disagreement and polarization. To get a mathematical understanding of such attacks, researchers use opinion-formation models from sociology, such as the Friedkin--Johnsen model, and formally study how much discord the adversary can produce when altering the opinions for only a small set of users. In this line of work, it is commonly assumed that the adversary has full knowledge about the network topology and the opinions of all users. However, the latter assumption is often unrealistic in practice, where user opinions are not available or simply difficult to estimate accurately. To address this concern, we raise the following question: Can an attacker sow discord in a social network, even when only the network topology is known? We answer this question affirmatively. We present approximation algorithms for detecting a small set of users who are highly influential for the disagreement and polarization in the network. We show that when the adversary radicalizes these users and if the initial disagreement/polarization in the network is not very high, then our method gives a constant-factor approximation on the setting when the user opinions are known. To find the set of influential users, we provide a novel approximation algorithm for a variant of MaxCut in graphs with positive and negative edge weights. We experimentally evaluate our methods, which have access only to the network topology, and we find that they have similar performance as methods that have access to the network topology and all user opinions. We further present an NP-hardness proof, which was an open question by Chen and Racz [IEEE Trans. Netw. Sci. Eng., 2021].

  • Open Access

    Reducing Exposure to Harmful Content via Graph Rewiring

    by Corinna Coupette, Stefan Neumann, Aristides Gionis

    Most media content consumed today is provided by digital platforms that aggregate input from diverse sources, where access to information is mediated by recommendation algorithms. One principal challenge in this context is dealing with content that is considered harmful. Striking a balance between competing stakeholder interests, rather than block harmful content altogether, one approach is to minimize the exposure to such content that is induced specifically by algorithmic recommendations. Hence, modeling media items and recommendations as a directed graph, we study the problem of reducing the exposure to harmful content via edge rewiring. We formalize this problem using absorbing random walks, and prove that it is NP-hard and NP-hard to approximate to within an additive error, while under realistic assumptions, the greedy method yields a (1-1/e)-approximation. Thus, we introduce Gamine, a fast greedy algorithm that can reduce the exposure to harmful content with or without quality constraints on recommendations. By performing just 100 rewirings on YouTube graphs with several hundred thousand edges, Gamine reduces the initial exposure by 50%, while ensuring that its recommendations are at most 5% less relevant than the original recommendations. Through extensive experiments on synthetic data and real-world data from video recommendation and news feed applications, we confirm the effectiveness, robustness, and efficiency of Gamine in practice.


  • Open Access

    Adversaries with Limited Information in the Friedkin-Johnsen Model

    by Sijing Tu, Stefan Neumann, Aristides Gionis

    In recent years, online social networks have been the target of adversaries who seek to introduce discord into societies, to undermine democracies and to destabilize communities. Often the goal is not to favor a certain side of a conflict but to increase disagreement and polarization. To get a mathematical understanding of such attacks, researchers use opinion-formation models from sociology, such as the Friedkin--Johnsen model, and formally study how much discord the adversary can produce when altering the opinions for only a small set of users. In this line of work, it is commonly assumed that the adversary has full knowledge about the network topology and the opinions of all users. However, the latter assumption is often unrealistic in practice, where user opinions are not available or simply difficult to estimate accurately. To address this concern, we raise the following question: Can an attacker sow discord in a social network, even when only the network topology is known? We answer this question affirmatively. We present approximation algorithms for detecting a small set of users who are highly influential for the disagreement and polarization in the network. We show that when the adversary radicalizes these users and if the initial disagreement/polarization in the network is not very high, then our method gives a constant-factor approximation on the setting when the user opinions are known. To find the set of influential users, we provide a novel approximation algorithm for a variant of MaxCut in graphs with positive and negative edge weights. We experimentally evaluate our methods, which have access only to the network topology, and we find that they have similar performance as methods that have access to the network topology and all user opinions. We further present an NP-hardness proof, which was left as an open question by Chen and Racz [IEEE Transactions on Network Science and Engineering, 2021].


  • Open Access

    Analyzing the Communication Clusters in Datacenters✱

    by Klaus-Tycho Foerster, Thibault Marette, Stefan Neumann, Claudia Plant, Ylli Sadikaj, Stefan Schmid, Yllka Velaj

    Datacenter networks have become a critical infrastructure of our digital society and over the last years, great efforts have been made to better understand the communication patterns inside datacenters. In particular, existing empirical studies showed that datacenter traffic typically features much temporal and spatial structure, and that at any given time, some communication pairs interact much more frequently than others. This paper generalizes this study to communication groups and analyzes how clustered the datacenter traffic is, and how stable these clusters are over time. To this end, we propose a methodology which revolves around a biclustering approach, allowing us to identify groups of racks and servers which communicate frequently over the network. In particular, we consider communication patterns occurring in three different Facebook datacenters: a Web cluster consisting of web servers serving web traffic, a Database cluster which mainly consists of MySQL servers, and a Hadoop cluster. Interestingly, we find that in all three clusters, small groups of racks and servers can produce a large fraction of the network traffic, and we can determine these groups even when considering short snapshots of network traffic. We also show empirically that these clusters are fairly stable across time. Our insights on the size and stability of communication clusters hence uncover an interesting potential for resource optimizations in datacenter infrastructures.