Search

Numerous discussions have advocated the presence of a so-called rabbit-hole (RH) phenomenon on social media, interested in advanced personalization to their users. This phenomenon is loosely understood as a collapse of mainstream recommendations, in favor of ultra-personalized ones that lock users into narrow and specialized feeds. Yet quantitative studies are often ignoring personalization, are of limited scale, and rely on manual tagging to track this collapse. This precludes a precise understanding of the phenomenon based on reproducible observations, and thus the continuous audits of platforms. In this paper, we first tackle the scale issue by proposing a user-sided bot-centric approach that enables large-scale data collection, through autoplay walks on recommendations. We then propose a simple theory that explains the appearance of these RHs. While this theory is a simplifying viewpoint on a complex and planet-wide phenomenon, it carries multiple advantages: it can be analytically modeled, and provides a general yet rigorous definition of RHs. We define them as an interplay between (i) user interaction with personalization and (ii) the attraction strength of certain video categories, which cause users to quickly step apart of mainstream recommendations made to fresh user profiles. We illustrate these concepts by highlighting some RHs found after collecting more than 16 million personalized recommendations on YouTube. A final validation step compares our automatically identified RHs against manually identified RHs from a previous research work. Together, those results pave the way for large-scale and automated audits of the RH effect in recommendation systems. [ABSTRACT FROM AUTHOR]

In network optimization problems, from traffic engineering to network monitoring, the routing model is typically considered as something given and frozen. This paper is motivated by the fundamental question how the ability to change and optimize the routing model itself influences the efficiency at which communication networks can be operated. To this end, we identify two main dimensions of a routing model: consistency (of a single route) and coherence (of sets of routes). We present analytical results on the impact of the routing model on the achievable route diversity as well as on the runtime of solving optimization problems underlying different case studies. We also uncover that it can sometimes be beneficial to artificially restrict the routing model, to significantly reduce the computational complexity without negatively affecting the route diversity much. [ABSTRACT FROM AUTHOR]

In our digital societies, individuals massively interact through digital interfaces whose impact on collective dynamics can be important. In particular, the combination of social media filters and recommender systems can lead to the emergence of polarized and fragmented groups. In some social contexts, such segregation processes of human groups have been shown to share similarities with phase separation phenomena in physics. Here, we study the impact of information filtering on collective segregation behaviour of human groups. We report a series of experiments where groups of 22 subjects have to perform a collective segregation task that mimics the tendency of individuals to bond with other similar individuals. More precisely, the participants are each assigned a colour (red or blue) unknown to them, and have to regroup with other subjects sharing the same colour. To assist them, they are equipped with an artificial sensory device capable of detecting the majority colour in their 'environment' (defined as their k nearest neighbours, unbeknownst to them), for which we control the perception range, k = 1, 3, 5, 7, 9, 11, 13. We study the separation dynamics (emergence of unicolour groups) and the properties of the final state, and show that the value of k controls the quality of the segregation, although the subjects are totally unaware of the precise definition of the 'environment'. We also find that there is a perception range k = 7 above which the ability of the group to segregate does not improve. We introduce a model that precisely describes the random motion of a group of pedestrians in a confined space, and which faithfully reproduces and allows interpretation of the results of the segregation experiments. Finally, we discuss the strong and precise analogy between our experiment and the phase separation of two immiscible materials at very low temperature. [ABSTRACT FROM AUTHOR]

Reliable and highly available computer networks must implement resilient fast rerouting mechanisms: upon a link or node failure, an alternative route is determined quickly, without involving the network control plane. Designing such fast failover mechanisms capable of dealing with multiple concurrent failures, however, is challenging, as failover rules need to be installed proactively, i.e., ahead of time, without knowledge of the actual failures happening at runtime. Indeed, only little is known today about the design of resilient routing algorithms. This paper introduces a general framework to reason about and design local failover algorithms that minimize the resulting load after failover on dense networks, beyond destination-based routing. We show that due to the inherent locality of the failover decisions at runtime, the problem is fundamentally related to the field of distributed algorithms without coordination. We derive an intriguing lower bound on the inherent network load overhead any local fast failover scheme that will introduce in the worst case, even though globally seen, much more balanced traffic allocations exist. We then present different randomized and deterministic failover algorithms and analyze their overhead load. In particular, we build upon the theory of combinatorial designs and develop a novel deterministic failover mechanism based on symmetric block design theory, which tolerates a maximal number of link failures while ensuring low loads. [ABSTRACT FROM AUTHOR]

Powerline communication networks assume an interesting position in the communication network space: similarly to wireless networks, powerline networks are based on a shared broadcast medium; unlike wireless networks, however, the signal propagation is constrained to the power lines of the electrical infrastructure, which is essentially a graph. This article presents an algorithmic model to study the design of communication services over powerline communication networks. As a case study, we focus on the fundamental broadcast problem, and present and analyze a distributed algorithm $$\textsc {Color}\textsc {Cast}$$ which terminates in at most n communication rounds, where n denotes the network size, even in a model where link qualities are unpredictable and time-varying. For comparison, the achieved broadcast time is lower than what can be achieved by any unknown-topology algorithm (lower bounds $$\varOmega (n\log n / \log (n/D))$$ and $$\varOmega (n \log D)$$ are proved in Kowalski and Pelc (Distrib Comput 18(1):43-57, ) resp. Clementi et al. () where D is the network diameter). Moreover, existing known-topology broadcast algorithms often fail to deliver the broadcast message entirely in this model. This article also presents a general broadcast lower bound for the powerline model. [ABSTRACT FROM AUTHOR]

Network virtualization is a new Internet paradigm which allows multiple virtual networks (VNets) to share the resources of a given physical infrastructure. The virtualization of entire networks is the natural next step after the virtualization of nodes and links. While the problem of how to embed a VNet ('guest network') on a given resource network ('host network') is algorithmically well-understood, much less is known about the security implications of this new technology. This paper introduces a new model to reason about one particular security threat: the leakage of information about the physical infrastructure-often a business secret. We initiate the study of this new problem and introduce the notion of request complexity which describes the number of VNet requests needed to fully disclose the substrate topology. We derive lower bounds and present algorithms achieving an asymptotically optimal request complexity for important graph classes such as trees, cactus graphs (complexity $$O(n)$$ ) as well as arbitrary graphs (complexity $$O(n^2)$$ ). Moreover, a general motif-based topology discovery framework is described which exploits the poset structure of the VNet embedding relation. [ABSTRACT FROM AUTHOR]

In many large-scale distributed systems and on the Web, agents need to interact with other unknown agents to carry out some tasks or transactions. The ability to reason about and assess the potential risks in carrying out such transactions is essential for providing a safe and reliable interaction environment. A traditional approach to reason about the risk of a transaction is to determine if the involved agent is trustworthy on the basis of its behavior history. As a departure from such traditional trust models, we propose a generic, trust framework based on machine learning where an agent uses its own previous transactions (with other agents) to build a personal knowledge base. This is used to assess the trustworthiness of a transaction on the basis of the associated features, particularly using the features that help discern successful transactions from unsuccessful ones. These features are handled by applying appropriate machine learning algorithms to extract the relationships between the potential transaction and the previous ones. Experiments based on real data sets show that our approach is more accurate than other trust mechanisms, especially when the information about past behavior of the specific agent is rare, incomplete, or inaccurate. [ABSTRACT FROM AUTHOR]

Traceroute measurements are one of the main instruments to shed light onto the structure and properties of today's complex networks such as the Internet. This article studies the feasibility and infeasibility of inferring the network topology given traceroute data from a worst-case perspective, i.e., without any probabilistic assumptions on, e.g., the nodes' degree distribution. We attend to a scenario where some of the routers are anonymous, and propose two fundamental axioms that model two basic assumptions on the traceroute data: (1) each trace corresponds to a real path in the network, and (2) the routing paths are at most a factor $$1/\alpha $$ off the shortest paths, for some parameter $$\alpha \in (0,1]$$. In contrast to existing literature that focuses on the cardinality of the set of (often only minimal) inferrable topologies, we argue that a large number of possible topologies alone is often unproblematic, as long as the networks have a similar structure. We hence seek to characterize the set of topologies inferred with our axioms. We introduce the notion of star graphs whose colorings capture the differences among inferred topologies; it also allows us to construct inferred topologies explicitly. We find that in general, inferrable topologies can differ significantly in many important aspects, such as the nodes' distances or the number of triangles. These negative results are complemented by a discussion of a scenario where the trace set is best possible, i.e., 'complete'. It turns out that while some properties such as the node degrees are still hard to measure, a complete trace set can help to determine global properties such as the connectivity. [ABSTRACT FROM AUTHOR]