Search

More and more social interactions happen online. On online social networks such as Instagram, millions of users share, like, and comment on photos and videos every day, interacting with other users world wide, at large scale and at a high rate. These networks do not only introduce new user experiences, but they also enable new insights into human behavior. Here, we use these new possibilities to study homophilic behavior—the tendency of individuals to bond with people similar to themselves. While homophilic behavior has been observed in many contexts, little is known about gender-specific differences and the extent of homophilic behavior of female and male users in online social networks. Based on a unique and extensive data set, covering over 800,000 (directed) Instagram interactions and a time span of three years, we shed light on differences between genders and uncover an intriguing asymmetry of homophily. In particular, we show that female users exhibit homophily to a larger extent than male users. The magnitude of this asymmetry depends on the type of interaction, as differences are more pronounced for 'comment'-interactions than for 'like'-interactions. Given these empirical observations, we further study the implications of such gender differences on the spread of information in social networks in a basic model. We find that on average, a piece of information that originates from a female group reaches significantly more female users than male users. [ABSTRACT FROM AUTHOR]

Most modern asset transfer systems use consensus to maintain a totally ordered chain of transactions. It was recently shown that consensus is not always necessary for implementing asset transfer. More efficient, asynchronous solutions can be built using reliable broadcast instead of consensus. This approach has been originally used in the closed (permissioned) setting. In this paper, we extend it to the open (permissionless) environment. We present Pastro, a permissionless and asynchronous asset-transfer implementation, in which quorum systems, traditionally used in reliable broadcast, are replaced with a weighted Proof-of-Stake mechanism. Pastro tolerates a dynamic adversary that is able to adaptively corrupt participants. [ABSTRACT FROM AUTHOR]

Blockchains, in general, and cryptocurrencies such as Bitcoin, in particular, are realized using distributed systems and hence critically rely on the performance and security of the interconnecting network. The requirements on these networks and their usage, however, can differ significantly from traditional communication networks, with implications on all layers of the protocol stack. This article is motivated by these differences and, in particular, by the observation that many fundamental design aspects of these networks are not well-understood today. To support the networking community to contribute to this emerging application domain, we present a structured overview of the field, from topology and neighbor discovery, over block and transaction propagation, to sharding and off-chain networks, also reviewing existing empirical results from different measurement studies. In particular, for each of these domains, we provide the context, highlighting differences and commonalities with traditional networks, review the state-of-the-art, and identify open research challenges. Our article can hence also be seen as a call-to-arms to improve the foundation on top of which blockchains are built. [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]

Randomness beacons are services that periodically emit a random number, allowing users to base decisions on the same random value without trusting anyone: ideally, the randomness beacon does not only produce unpredictable values, but is also of low computational complexity for the users, bias-resistant and publicly verifiable. Such randomness beacons can serve as an important primitive for smart contracts in a variety of contexts. This paper first presents a structured security analysis, based on which we then design, implement, and evaluate a trustworthy and efficient randomness beacon. Our approach does not require users to register or run any computationally intensive operations. We then compare different implementation and deployment options on distributed ledgers, and report on an Ethereum smart contract-based lottery using our beacon. [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]

A common two-tier structure for social networks is based on partitioning society into two parts, referred to as the elite and the periphery, where the “elite” is the relatively small but well-connected and highly influential group of powerful individuals around which the society is centered, and the “periphery” consists of the rest of society. It is observed that the relative sizes of economic and social elites in various societies appear to be continually declining. One possible explanation is that this is a natural social phenomenon, resembling Price’s “square root” law for the fraction of good scientists in the scientific community. We try to assess the validity of this explanation by studying the elite-periphery structure via introducing a novel axiom-based model for representing and measuring the influence between the elite and the periphery. The model is accompanied by a set of axioms that capture the elite’s dominance, robustness and density, as well as a compactness property. Relying on the model and the accompanying axioms, we are able to draw a number of insightful conclusions about the elite-periphery structure. In particular, we show that in social networks that respect our axioms, the size of a compact elite is sublinear in the network size. This agrees with Price’s principle but appears to contradict the common belief that the elite size tends to a linear fraction of society (recently claimed to be around 1%). We propose a natural method to create partitions with nice properties, based on the key observation that an elite-periphery partition is at what we call a ‘balance point’, where the elite and the periphery maintain a balance of powers. Our method is based on setting the elite to be the k most influential nodes in the network and suggest the balance point as a tool for choosing k and therefore the size of the elite. When using nodes degrees to order the nodes, the resulting k-rich club at the balance point is the elite of a partition we refer to as the balanced edge-based partition. We accompany these findings with an empirical study on 32 real-world social networks, which provides evidence that balanced edge-based partitions which satisfying our axioms commonly exist. [ABSTRACT FROM AUTHOR]

The throughput capacity of arbitrary wireless networks under the physical Signal to Interference Plus Noise Ratio (SINR) model has received much attention in recent years. In this paper, we investigate the question of how much the worst-case performance of uniform and non-uniform power assignments differ under constraints such as a bound on the area where nodes are distributed or restrictions on the maximum power available. We determine the maximum factor by which a non-uniform power assignment can outperform the uniform case in the SINR model. More precisely, we prove that in one-dimensional settings the capacity of a non-uniform assignment exceeds a uniform assignment by at most a factor of $$O(\log L_{\max })$$ when the length of the network is $$L_{\max }$$ . In two-dimensional settings, the uniform assignment is at most a factor of $$O(\log P_{\max })$$ worse than the non-uniform assignment if the maximum power is $$P_{\max }$$ . We provide algorithms that reach this capacity in both cases. These bounds are tight in the sense that previous work gave examples of networks where the lack of power control causes a performance loss in the order of these factors. To complement our theoretical results and to evaluate our algorithms with concrete input networks, we carry out simulations on random wireless networks. The results demonstrate that the link sets generated by the algorithms contain around 20-35 % of all links. As a consequence, engineers and researchers may prefer the uniform model due to its simplicity if this degree of performance deterioration is acceptable. [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]

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]

A dominating set is a subset of the nodes of a graph such that all nodes are in the set or adjacent to a node in the set. A minimum dominating set approximation is a dominating set that is not much larger than a dominating set with the fewest possible number of nodes. This article summarizes the state-of-the-art with respect to finding minimum dominating set approximations in distributed systems, where each node locally executes a protocol on its own, communicating with its neighbors in order to achieve a solution with good global properties. Moreover, we present a number of recent results for specific families of graphs in detail. A unit disk graph is given by an embedding of the nodes in the Euclidean plane, where two nodes are joined by an edge exactly if they are in distance at most one. For this family of graphs, we prove an asymptotically tight lower bound on the trade-off between time complexity and approximation ratio of deterministic algorithms. Next, we consider graphs of small arboricity, whose edge sets can be decomposed into a small number of forests. We give two algorithms, a randomized one excelling in its approximation ratio and a uniform deterministic one which is faster and simpler. Finally, we show that in planar graphs, which can be drawn in the Euclidean plane without intersecting edges, a constant approximation factor can be ensured within a constant number of communication rounds. [ABSTRACT FROM AUTHOR]

This article studies how a mechanism designer can influence games by promising payments to the players depending on their mutual choice of strategies. First, we investigate the cost of implementing a desirable behavior and present algorithms to compute this cost. Whereas a mechanism designer can decide efficiently whether strategy profiles can be implemented at no cost at all our complexity analysis indicates that computing an optimal implementation is generally NP-hard. Second, we introduce and analyze the concept of leverage in a game. The leverage captures the benefits that a benevolent or a malicious mechanism designer can achieve by implementing a certain strategy profile region within economic reason, i.e., by taking the implementation cost into account. Mechanism designers can often manipulate games and change the social welfare by a larger extent than the amount of money invested. Unfortunately, computing the leverage turns out to be intractable as well in the general case. [ABSTRACT FROM AUTHOR]