We study the nonlinear evolution of binary opinions in a population of agents connected by a directed network, influenced by two competing forces. On the one hand agents are stubborn, i.e., have a tendency for one of the two opinions; on the other hand there is a disruptive bias that drives the agents toward the opposite opinion. The disruptive bias models external factors such as market innovations or social controllers aiming to challenge the status quo, while stubbornness reinforces the initial opinion making it harder for the external bias to drive the process toward change. Each agent updates its opinion according to a nonlinear rule that takes into account the opinions of its neighbors and the strength of the disruptive bias. We focus on random directed graphs with prescribed in- and out-degree sequences and prove that the dynamics exhibits a phase transition. When the disruptive bias is stronger than a certain critical threshold, the entire population rapidly converges to a consensus on the disruptive opinion. When the bias is weaker than this threshold, the system enters a metastable state in which only a fraction of the population adopts the new opinion, and this partial adoption persists for a long time. We explicitly characterize both the critical threshold and the long-term adoption fraction, showing that they depend only on few simple statistics of the degree sequences. Our analysis relies on a dual system of coalescing, branching, and dying particles, whose behavior is equivalent and allows a rigorous characterization of the system's dynamics. Our results characterize the interplay between the degree of the agents, their stubbornness, and the external bias, shedding light on the tipping points of opinion dynamics in networks.

Given a weighted undirected graph, a number of clusters k, and an exponent z, the goal in the (k, z)-clustering problem on graphs is to select k vertices as centers that minimize the sum of the distances raised to the power z of each vertex to its closest center. This problem includes the well-known k-median (z = 1) and k-means (z = 2) clustering problems. In the dynamic setting, the graph is subject to adversarial edge updates, and the goal is to maintain explicitly an exact (k, z)-clustering solution in the induced shortest-path metric. Prior works by Bhattacharya, Costa, Garg, Lattanzi, and Parotsidis [FOCS 2024] and by Bhattacharya, Costa, and Farokhnejad [STOC 2025] consider the dynamic (k, z)-clustering problem for point sets in metric spaces. These algorithms support adversarial point insertions and deletions under a model with access to pairwise distances. This model differs significantly from the dynamic graph setting, where no oracle access is given to pairwise distances and a single edge update can affect many distances - making these approaches inefficient when applied to graphs. While efficient dynamic k-center approximation algorithms on graphs exist [Cruciani, Forster, Goranci, Nazari, and Skarlatos, SODA 2024], to the best of our knowledge, no prior work provides similar results for the dynamic (k,z)-clustering problem. As the main result of this paper, we develop a randomized incremental (k, z)-clustering algorithm that maintains with high probability a constant-factor approximation in a graph undergoing edge insertions with a total update time of Õ(k m^{1+o(1)} + k^{1+1/(λ)} m), where λ ≥ 1 is an arbitrary fixed constant. Our incremental algorithm also achieves an amortized update time of Õ(k n^o(1) + k^{1+1/(λ)}) and consists of two stages. In the first stage, we maintain a constant-factor bicriteria approximate solution of size Õ(k) with a total update time of m^{1+o(1)} (independent of the parameter k) over all adversarial edge insertions. This first stage is an intricate adaptation of the bicriteria approximation algorithm by Mettu and Plaxton [Machine Learning 2004] to incremental graphs. One of our key technical results is that the radii in their algorithm can be assumed to be non-decreasing while the approximation ratio remains constant - a property that may be of independent interest. In the second stage, we maintain a constant-factor approximate (k,z)-clustering solution on a dynamic weighted instance induced by the bicriteria approximate solution. For this subproblem, we employ a dynamic spanner algorithm together with a static (k,z)-clustering algorithm.

In this paper we give the first efficient algorithms for the k-center problem on dynamic graphs undergoing edge updates. In this problem, the goal is to partition the input into k sets by choosing k centers such that the maximum distance from any data point to its closest center is minimized. It is known that it is NP-hard to get a better than 2 approximation for this problem.

Opinion diffusion is a crucial phenomenon in social networks, often underlying the way in which a collection of agents develops a consensus on relevant decisions. Voter models are well-known theoretical models to study opinion spreading in social networks and structured populations. Their simplest version assumes that an updating agent will adopt the opinion of a neighboring agent chosen at random. These models allow us to study, for example, the probability that a certain opinion will fixate into a consensus opinion, as well as the expected time it takes for a consensus opinion to emerge. Standard voter models are oblivious to the opinions held by the agents involved in the opinion adoption process. We propose and study a context-dependent opinion spreading process on an arbitrary social graph, in which the probability that an agent abandons opinion a in favor of opinion b depends on both a and b. We discuss the relations of the model with existing voter models and then derive theoretical results for both the fixation probability and the expected consensus time for two opinions, for both the synchronous and the asynchronous update models.

Abstract Consider a graph where each of thennodes is either in state $$\mathcal {R}$$ R or $$\mathcal {B}$$ B . Herein, we analyze thesynchronousk-Majoritydynamics, where in each discrete-time round nodes simultaneously samplekneighbors uniformly at random with replacement and adopt the majority state among those of the nodes in the sample (breaking ties uniformly at random). Differently from previous work, we study the robustness of thek-Majorityinmaintaining a $$\mathcal {R}$$ R majority, when the dynamics is subject to two forms ofbiastoward state $$\mathcal {B}$$ B . The bias models an external agent that attempts to subvert the initial majority by altering the communication between nodes, with a probability of successpin each round: in the first form of bias, the agent tries to alter the communication links by transmitting state $$\mathcal {B}$$ B ; in the second form of bias, the agent tries to corrupt nodes directly by making them update to $$\mathcal {B}$$ B . Our main result shows asharp phase transitionin both forms of bias. By considering initial configurations in which every node has probability $$q \in (\frac{1}{2},1]$$ q∈(12,1] of being in state $$\mathcal {R}$$ R , we prove that for every $$k\ge 3$$ k≥3 there exists a critical value $$p_{k,q}^\star $$ pk,q⋆ such that, with high probability, the external agent is able to subvert the initial majority either in $$n^{\omega (1)}$$ nω(1) rounds, if $$p p<pk,q⋆ , or inO(1) rounds, if $$p>p_{k,q}^\star $$ p>pk,q⋆ . When $$k<3$$ k<3 , instead, no phase transition phenomenon is observed and the disruption happens inO(1) rounds for $$p>0$$ p>0 .

We propose a novel scalable approach for testing non-testable programs denoted as ARMED testing. The approach leverages efficient Association Rules Mining algorithms to determine relevant implication relations among features and actions observed while the system is in operation. These relations are used as the specification of positive and negative tests, allowing for identifying plausible or suspicious behaviors: for those cases when oracles are inherently unknownable, such as in social testing, ARMED testing introduces the novel concept of testing for plausibility. To illustrate the approach we walk-through an application example.

We study opinion dynamics in multi-agent networks when a bias toward one of two possible opinions exists, for example reflecting a status quo versus a superior alternative. Our aim is to investigate the combined effect of bias, network structure, and opinion dynamics on the convergence of the system of agents as a whole. Models of such evolving processes can easily become analytically intractable. In this paper, we consider a simple yet mathematically rich setting, in which all agents initially share an initial opinion representing the status quo. The system evolves in steps. In each step, one agent selected uniformly at random follows an underlying update rule to revise its opinion on the basis of those held by its neighbors, but with a probabilistic bias towards the superior alternative. We analyze convergence of the resulting process under well-known update rules. The framework we propose is simple and modular, but at the same time complex enough to highlight a nonobvious interplay between topology and underlying update rule.

Abstract The 2-Choices dynamics is a process that models voting behavior on networks and works as follows: Each agent initially holds either opinion blue or red; then, in each round, each agent looks at two random neighbors and, if the two have the same opinion, the agent adopts it. We study its behavior on a class of networks with core–periphery structure. Assume that a densely-connected subset of agents, the core, holds a different opinion from the rest of the network, the periphery. We prove that, depending on the strength of the cut between core and periphery, a phase-transition phenomenon occurs: Either the core’s opinion rapidly spreads across the network, or a metastability phase takes place in which both opinions coexist for superpolynomial time. The interest of our result, which we also validate with extensive experiments on real networks, is twofold. First, it sheds light on the influence of the core on the rest of the network as a function of its connectivity toward the latter. Second, it is one of the first analytical results which shows a heterogeneous behavior of a simple dynamics as a function of structural parameters of the network.

We investigate opinion dynamics in multi-agent networks when there exists a bias toward one of two possible opinions; for example, reflecting a status quo vs a superior alternative. Starting with all agents sharing an initial opinion representing the status quo, the system evolves in steps. In each step, one agent selected uniformly at random adopts with some probability a the superior opinion, and with probability 1 - a it follows an underlying update rule to revise its opinion on the basis of those held by its neighbors. We analyze the convergence of the resulting process under two well-known update rules, namely majority and voter. The framework we propose exhibits a rich structure, with a nonobvious interplay between topology and underlying update rule. For example, for the voter rule we show that the speed of convergence bears no significant dependence on the underlying topology, whereas the picture changes completely under the majority rule, where network density negatively affects convergence. We believe that the model we propose is at the same time simple, rich, and modular, affording mathematical characterization of the interplay between bias, underlying opinion dynamics, and social structure in a unified setting.

The recent push towards test automation and test-driven development continues to scale up the dimensions of test code that needs to be maintained, analysed, and processed side-by-side with production code. As a consequence, on the one side regression testing techniques, e.g., for test suite prioritization or test case selection, capable to handle such large-scale test suites become indispensable; on the other side, as test code exposes own characteristics, specific techniques for its analysis and refactoring are actively sought. We present JTeC, a large-scale dataset of test cases that researchers can use for benchmarking the above techniques or any other type of tool expressly targeting test code. JTeC collects more than 2.5M test classes belonging to 31K+ GitHub projects and summing up to more than 430 Million SLOCs of ready-to-use real-world test code.

We analyze the binary-state (either ℛ or ℬ) k-majority dynamics in a biased communication model where nodes have some fixed probability p, independent of the dynamics, of being seen in state ℬ by their neighbors. In this setting we study how p, as well as the initial unbalance between the two states, impact on the speed of convergence of the process, identifying sharp phase transitions.

Spectral techniques have proved amongst the most effective approaches to graph clustering. However, in general they require explicit computation of the main eigenvectors of a suitable matrix (usually the Laplacian matrix of the graph). Recent work (e.g., Becchetti et al., SODA 2017) suggests that observing the temporal evolution of the power method applied to an initial random vector may, at least in some cases, provide enough information on the space spanned by the first two eigenvectors, so as to allow recovery of a hidden partition without explicit eigenvector computations. While the results of Becchetti et al. apply to perfectly balanced partitions and/or graphs that exhibit very strong forms of regularity, we extend their approach to graphs containing a hidden k partition and characterized by a milder form of volume-regularity. We show that the class of k-volume regular graphs is the largest class of undirected (possibly weighted) graphs whose transition matrix admits k “stepwise” eigenvectors (i.e., vectors that have constant entries over the components corresponding to the same set of the hidden partition). To obtain this result, we highlight a connection between volume regularity and lumpability of Markov chains. Moreover, we prove that if the stepwise eigenvectors are those associated to the first k largest eigenvalues of the transition matrix of a random walk on the graph and the gap between the k-th and the (k+1)-th eigenvalues is sufficiently large, the Averaging dynamics of Becchetti et al. recovers the underlying community structure of the graph in logarithmic time, with high probability.

We investigate the behavior of a simple majority dynamics on networks of agents whose interaction topology exhibits a community structure. By leveraging recent advancements in the analysis of dynamics, we prove that, when the states of the nodes are randomly initialized, the system rapidly and stably converges to a configuration in which the communities maintain internal consensus on different states. This is the first analytical result on the behavior of dynamics for nonconsensus problems on non-complete topologies, based on the first symmetry-breaking analysis in such setting.Our result has several implications in different contexts in which dynamics are adopted for computational and biological modeling purposes. In the context of Label Propagation Algorithms, a class of widely used heuristics for community detection, it represents the first theoretical result on the behavior of a distributed label propagation algorithm with quasi-linear message complexity. In the context of evolutionary biology, dynamics such as the Moran process have been used to model the spread of mutations in genetic populations (Lieberman, Hauert, and Nowak 2005); our result shows that, when the probability of adoption of a given mutation by a node of the evolutionary graph depends super-linearly on the frequency of the mutation in the neighborhood of the node and the underlying evolutionary graph exhibits a community structure, there is a non-negligible probability for species differentiation to occur.

Test suite reduction approaches aim at decreasing software regression testing costs by selecting a representative subset from large-size test suites. Most existing techniques are too expensive for handling modern massive systems and moreover depend on artifacts, such as code coverage metrics or specification models, that are not commonly available at large scale. We present a family of novel very efficient approaches for similarity-based test suite reduction that apply algorithms borrowed from the big data domain together with smart heuristics for finding an evenly spread subset of test cases. The approaches are very general since they only use as input the test cases themselves (test source code or command line input). We evaluate four approaches in a version that selects a fixed budget B of test cases, and also in an adequate version that does the reduction guaranteeing some fixed coverage. The results show that the approaches yield a fault detection loss comparable to state-of-the-art techniques, while providing huge gains in terms of efficiency. When applied to a suite of more than 500K real world test cases, the most efficient of the four approaches could select B test cases (for varying B values) in less than 10 seconds.

We consider the election control problem in social networks which consists in exploiting social influence in a network of voters to change their opinion about a target candidate with the aim of increasing his chances to win (constructive control) or lose (destructive control) the election. Previous works on this problem focus on plurality voting systems and on a influence model in which the opinion of the voters about the target candidate can only change by shifting its ranking by one position, regardless of the amount of influence that a voter receives. We introduce Linear Threshold Ranking, a natural extension of Linear Threshold Model, which models the change of opinions taking into account the amount of exercised influence. In this general model, we are able to approximate the maximum score that a target candidate can achieve up to a factor of 1-1/e by showing submodularity of the objective function. We exploit this result to provide a 1/3(1-1/e)-approximation algorithm for the constructive election control problem and a 1/2(1-1/e)-approximation ratio in the destructive scenario. The algorithm can be used in arbitrary scoring rule voting systems, including plurality rule and borda count.

Many test case prioritization criteria have been proposed for speeding up fault detection. Among them, similarity-based approaches give priority to the test cases that are the most dissimilar from those already selected. However, the proposed criteria do not scale up to handle the many thousands or even some millions test suite sizes of modern industrial systems and simple heuristics are used instead. We introduce the FAST family of test case prioritization techniques that radically changes this landscape by borrowing algorithms commonly exploited in the big data domain to find similar items. FAST techniques provide scalable similarity-based test case prioritization in both white-box and black-box fashion. The results from experimentation on real world C and Java subjects show that the fastest members of the family outperform other black-box approaches in efficiency with no significant impact on effectiveness, and also outperform white-box approaches, including greedy ones, if preparation time is not counted. A simulation study of scalability shows that one FAST technique can prioritize a million test cases in less than 20 minutes.