We consider a tomographic problem on graphs, called Minimum Surgical Probing , introduced by Bar-Noy et al. [4]. Each vertex v ∈ V of a graph G = ( V , E ) is associated with an (unknown) label ℓ v . The outcome of probing a vertex v is P v = ∑ u ∈ N [ v ] ℓ u , where N [ v ] denotes the closed neighborhood of v . The goal is to uncover the labels given probes P v for all v ∈ V . For some graphs, the labels cannot be determined (uniquely), and the use of surgical probes is permitted but must be minimized. A surgical probe at vertex v returns ℓ v . In this paper, we introduce convexity constraints to Minimum Surgical Probing . For binary labels, convexity imposes constraints such as if ℓ u = ℓ v = 1 , then for all vertices w on a shortest path between u and v , we must have that ℓ w = 1 . We show that convexity constraints reduce the number of required surgical probes for several graph families. Specifically, they allow us to recover the labels without using surgical probes for trees and bipartite graphs where otherwise ⌊| V |/2⌋ surgical probes might be needed. Our analysis is based on restricting the size of cliques in a graph using the concept of K h -free graphs (forbidden induced subgraphs). Utilizing this approach, we analyze grid graphs , the King’s graph , and (maximal-) outerplanar graphs .

Social media platforms are frequently targeted by entities engaging in automated or coordinated behavior, aiming to manipulate public opinion or conduct information operations without revealing their synthetic or managed nature. Research on detecting such actors faces the challenge of developing scalable, versatile methods that allow for consistent comparisons across diverse datasets. The challenge is even made more pressing by evidence of these actors on platforms beyond the extensively studied X (formerly Twitter), as well as the emergence of new platforms. We fill this gap by introducing a novel compression-based detection methodology, in addition to a new sparse method for network reconstruction that scales linearly under reasonable parameter choice. Being independent of the social media platform and the behavioral trace under study, our approach marks a departure from traditional methods that rely on multiple criteria or measures to assess user similarity. We evaluate our technique on multiple benchmark and real-world datasets, including widely known datasets related to political campaigns and emerging misinformation scenarios. We show that our approach provides a flexible unsupervised framework that effectively identifies both automated and coordinated activities across various behavioral traces, ensuring broad applicability.

The rise of digital platforms has enabled the large-scale observation of individual and collective behavior through high-resolution interaction data. This development has opened new analytical pathways for investigating how information circulates, how opinions evolve, and how coordination emerges in online environments. Yet despite a growing body of research, the field remains fragmented, marked by methodological heterogeneity, limited model validation, and weak integration across domains. In this survey, we address this gap by systematically reviewing the literature on online collective behavior, integrating empirical findings with formal modeling approaches. We examine platform-level regularities, the methodological choices used to identify them, and the extent to which existing modeling frameworks capture the observed dynamics. Rather than aiming for exhaustive coverage of individual subfields, we provide a structural and comparative synthesis of recurring empirical patterns, methodological approaches, and modeling assumptions that span across platforms and domains. The overarching goal is to consolidate a shared empirical baseline and to clarify the structural constraints shaping inference in this area, thereby laying the groundwork for more robust, comparable, and actionable analyses of online social media.

In the last few years, social media has gained an unprecedented amount of attention, playing a pivotal role in shaping the contemporary landscape of communication and connection. However, Coordinated inauthentic Behaviour (CIB), defined as orchestrated efforts by entities to deceive or mislead users about their identity and intentions, has emerged as a tactic to exploit the online discourse. In this study, we quantify the efficacy of CIB tactics by defining a general framework for evaluating the influence of a subset of nodes in a directed tree. We design two algorithms that provide optimal and greedy post-hoc placement strategies that lead to maximising the configuration influence. We then consider cascades from information spreading on X (formerly known as Twitter) to compare the observed behaviour with our algorithms. The results show that, according to our model, coordinated accounts are quite inefficient in terms of their network influence, thus suggesting that they may play a less pivotal role than expected. Moreover, the causes of these poor results may be found in two separate aspects: a bad placement strategy and a scarcity of resources.

Given a 3-uniform hypergraph H , its 2-intersection graph G has as vertex set the hyperedges of H and e e ′ is an edge of G whenever e and e ′ have exactly two common vertices in H . Di Marco et al. prove in Di Marco et al. (2023) that deciding whether a graph G is the 2-intersection graph of a 3-uniform hypergraph is N P -complete. Following this result, we study the class of claw-free graphs. We show that the recognition problem remains N P -complete for that class, but becomes polynomial if we consider triangulated claw-free graphs.

Social media platforms behave like giant arenas where users can rely on different content and express their opinions through likes, comments, and shares. However, do users welcome different perspectives or only listen to their preferred narratives? This article examines how users explore the digital space and allocate their attention among communities on two social networks, Voat and Reddit. By analyzing a massive dataset of about 215 million comments posted by about 16 million users on Voat and Reddit in 2019, we find that most users tend to explore new communities at a decreasing rate, meaning they have a limited set of preferred groups they visit regularly. Moreover, we provide evidence that preferred communities of users tend to cover similar topics throughout the year. We also find that communities have a high turnover of users, meaning that users come and go frequently showing a high volatility that strongly departs from a null model simulating users’ behavior.

Abstract Given a 3-uniform hypergraph H having a set V of vertices, and a set of hyperedges $$T\subset \mathcal {P}(V)$$ T ⊂ P ( V ) , whose elements have cardinality three each, a null labelling is an assignment of $$\pm 1$$ ± 1 to the hyperedges such that each vertex belongs to the same number of hyperedges labelled $$+1$$ + 1 and $$-1$$ - 1 . A sufficient condition for the existence of a null labelling of H (proved in Di Marco et al. Lect Notes Comput Sci 12757:282–294, 2021) is a Hamiltonian cycle in its 2-intersection graph. The notion of 2-intersection graph generalizes that of intersection graph of an (hyper)graph and extends its effectiveness. The present study first shows that this sufficient condition for the existence of a null labelling in H can not be weakened by requiring only the connectedness of the 2-intersection graph. Then some interesting properties related to their clique configurations are proved. Finally, the main result is proved, the NP-completeness of this characterization and, as a consequence, of the construction of the related 3-hypergraphs.