Similarity choice data occur when humans make choices among alternatives based on their similarity to a target, \emph{e.g.}, in the context of information retrieval and in embedding learning settings. Classical metric-based models of similarity choice assume independence of irrelevant alternatives (IIA), a property that allows for a simpler formulation. While IIA violations have been detected in many discrete choice settings, the similarity choice setting has received scant attention. This is because the target-dependent nature of the choice complicates IIA testing. We propose two statistical methods to test for IIA: a classical goodness-of-fit test and a Bayesian counterpart based on the framework of Posterior Predictive Checks (PPC). This Bayesian approach, our main technical contribution, quantifies the degree of IIA violation beyond its mere significance. We curate two datasets: one with choice sets designed to elicit IIA violations, and another with randomly generated choice sets from the same item universe. Our tests confirmed significant IIA violations on both datasets, and notably, we find a comparable degree of violation between them. Further, we devise a new PPC test for population homogeneity. Results show that the population is indeed homogenous, suggesting that the IIA violations are driven by context effects—specifically, interactions within the choice sets. These results highlight the need for new similarity choice models that account for such context effects.

Classic network clustering tackles the problem of identifying sets of nodes (communities) that have similar connection patterns. However, in many scenarios nodes also have attributes that are correlated and can also be used to identify node clusters. Thus, network information (edges) and node information (attributes) can be jointly leveraged to design high-performance clustering algorithms. Under a general model for the network and node attributes, this work establishes an information-theoretic criteria for the exact recovery of community labels and characterizes a phase transition determined by the Chernoff-Hellinger divergence of the model. The criteria shows how network and attribute information can be exchanged in order to have exact recovery (e.g., more reliable network information requires less reliable attribute information). This work also presents an iterative clustering algorithm that maximizes the joint likelihood, assuming that the probability distribution of network interactions and node attributes belong to exponential families. This covers a broad range of possible interactions (e.g., edges with weights) and attributes (e.g., non-Gaussian models) while also exploring the connection between exponential families and Bregman divergences. Extensive numerical experiments using synthetic and real data indicate that the proposed algorithm outperforms algorithms that leverage only network or only attribute information as well as recently proposed algorithms that perform clustering using both sources of information. The contributions of this work provide insights into the fundamental limits and practical techniques for inferring community labels on node-attributed networks.

While Network Architecture Search (NAS) and network pruning have recently re-emerged as powerful techniques to design more effective networks with less parameters, their focus has been on improving deep neural network models with millions of parameters. However, the number of connections and the connectivity pattern between layers also influences the learning performance of shallow two-layer networks, such as the classic Restricted Boltzmann Machine (RBM). This work presents a comprehensive study of the connectivity space on the learning performance of RBMs using the bars and stripes (BAS) model and the MNIST dataset. For BAS, the main findings show that pattern and number of connections play a fundamental role on the learning performance, while for MNIST the number of connections is more important for the considered connection structures. Moreover, the fully connected network is outperformed by different patterns in both scenarios, indicating the importance of also designing more effective connectivity patterns for simple two-layer neural networks.

Individuals in affiliate marketing programs sign up with companies to promote or sell their products in independent venues and channels, receiving compensations for their actions. While a component of the e-commerce ecosystem for over a decade, affiliate marketing is increasingly being adopted by companies given its promises of boosting revenue at low investment costs. This work analyzes Clube Hurb, the affiliate marketing program of Hurb.com the largest online travel agency in Brazil. The analysis reveals the fragility of social network growth (very low virality coefficient) along with the strength of social referrals. It also reveals that almost all revenue generated by the program comes from a small set of affiliates, a property that has sustained over time. Indeed, great disparities are characterized by heavy-tailed distributions in statistics concerning both the network and revenue structure. Thus, while most affiliates play no effective role, a few are instrumental in keeping the program profitable. Such findings indicate that traditional average-based performance metrics can be flawed when assessing the success of such programs.

Serverless computing is an attractive cloud services paradigm, simultaneously promising reduced cost and greater flexibility for customers and increased revenues and higher resource utilization for cloud providers. In this paper, we present an analysis of the potential cost benefits of serverless computing for end customers and cloud providers. Using realistic cost models, queueing theoretic performance models, and a game theoretic formulation, we explore the tradeoffs between serverless computing (SC) and traditional cloud computing (virtual machine, VM). In the proposed framework, customers distribute their workload between SC and VM to minimize their cost while maintaining a particular performance constraint, while the cloud provider sets SC and VM prices to maximize its profit. We explore the impact of relative prices, customer workload, service capacity, and provider costs. Our main result is the identification and characterization of three optimal operational regimes for both customers and the provider that leverage either SC or VM only, or both, in a hybrid configuration. The various insights provided in this paper can help both cloud providers and customers better understand the tradeoffs and implications of a hybrid system that combines serverless and VM rental with corresponding pricing models.

Structural identity is a concept of symmetry in which network nodes are identified according to the network structure and their relationship to other nodes. Structural identity has been studied in theory and practice over the past decades, but only recently has it been addressed with representational learning techniques. This work presents struc2vec, a novel and flexible framework for learning latent representations for the structural identity of nodes. struc2vec uses a hierarchy to measure node similarity at different scales, and constructs a multilayer graph to encode structural similarities and generate structural context for nodes. Numerical experiments indicate that state-of-the-art techniques for learning node representations fail in capturing stronger notions of structural identity, while struc2vec exhibits much superior performance in this task, as it overcomes limitations of prior approaches. As a consequence, numerical experiments indicate that struc2vec improves performance on classification tasks that depend more on structural identity.

Cumulative advantage (CA) refers to the notion that accumulated resources foster the accumulation of further resources in competitions, a phenomenon that has been empirically observed in various contexts. The oldest and arguably simplest mathematical model that embodies this general principle is the Pólya urn process, which finds applications in a myriad of problems. The original model captures the dynamics of competitions between two equally fit agents under linear CA effects, which can be readily generalized to incorporate different fitnesses and nonlinear CA effects. We study two statistics of competitions under the generalized model, namely duration (i.e., time of the last tie) and intensity (i.e., number of ties). We give rigorous mathematical characterizations of the tail distributions of both duration and intensity under the various regimes for fitness and nonlinearity, which reveal very interesting behaviors. For example, fitness superiority induces much shorter competitions in the sublinear regime while much longer competitions in the superlinear regime. Our findings can shed light on the application of Pólya urn processes in more general contexts where fitness and nonlinearity may be present.

In this paper we study the behavior of a continuous time random walk (CTRW) on a stationary and ergodic time varying dynamic graph. We establish conditions under which the CTRW is a stationary and ergodic process. In general, the stationary distribution of the walker depends on the walker rate and is difficult to characterize. However, we characterize the stationary distribution in the following cases: i) the walker rate is significantly larger or smaller than the rate in which the graph changes (time-scale separation), ii) the walker rate is proportional to the degree of the node that it resides on (coupled dynamics), and iii) the degrees of node belonging to the same connected component are identical (structural constraints). We provide examples that illustrate our theoretical findings.

No abstract available.

NA

Due to the increased usage of NAT boxes and firewalls, it has become harder for applications to establish direct connections seamlessly among two end-hosts. A recently adopted proposal to mitigate this problem is to use relay nodes, end-hosts that act as intermediary points to bridge connections. Efficiently selecting a relay node is not a trivial problem, specially in a large-scale unstructured overlay system where end-hosts are heterogeneous. In such environment, heterogeneity among the relay nodes comes from the inherent differences in their capacities and from the way overlay networks are constructed. Despite this fact, good relay selection algorithms should effectively balance the aggregate load across the set of relay nodes. We address this problem using algorithms based on the two random choices method. We first prove that the classic load-based algorithm can effectively balance the load even when relays are heterogeneous, and that its performance depends directly on relay heterogeneity. Second, we propose an utilization-based random choice algorithm to distribute load in order to balance relay utilization. Numerical evaluations through simulations illustrate the effectiveness of this algorithm, indicating that it might also yield provable performance (which we conjecture). Finally, we support our theoretical findings through simulations of various large-scale scenarios, with realistic relay heterogeneity.

During the past decade, a number of different studies have identified several peculiar properties of networks that arise from a diverse universe, ranging from social to computer networks. A recently observed feature is known as network densification, which occurs when the number of edges grows much faster than the number of nodes, as the network evolves over time. This surprising phenomenon has been empirically validated in a variety of networks that emerge in the real world and mathematical models have been recently proposed to explain it. Leveraging on how real data is usually gathered and used, we propose a new model called Edge Sampling to explain how densification can arise. Our model is innovative, as we consider a fixed underlying graph and a process that discovers this graph by probabilistically sampling its edges. We show that this model possesses several interesting features, in particular, that edges and nodes discovered can exhibit densification. Moreover, when the node degree of the fixed underlying graph follows a heavy-tailed distribution, we show that the Edge Sampling model can yield power law densification, establishing an approximate relationship between the degree exponent and the densification exponent. The theoretical findings are supported by numerical evaluations of the model. Finally, we apply our model to real network data to evaluate its performance on capturing the previously observed densification. Our results indicate that edge sampling is indeed a plausible alternative explanation for the densification phenomenon that has been recently observed.

2706-2717

Peer-to-peer (P2P) anonymous communication systems are vulnerable to free-riders, peers that use the system while providing little or no service to others and whose presence limits the strength of anonymity as well as the efficiency of the system. Free-riding can be addressed by building explicit incentive mechanisms into system protocols to promote two distinct aspects of cooperation among peers-compliance with the protocol specification and the availability of peers to serve others. In this paper we study the use of payments to implement an incentive mechanism that attaches a real monetary cost to low availability. Through a game theoretic analysis, we evaluate the effectiveness of such an incentive, finding that peer availability can be significantly increased through the introduction of payments under many conditions. We also demonstrate how a payment-based incentive that preserves anonymity can be implemented and integrated with a popular class of P2P anonymity systems.

Peer-peer networking has recently emerged as a new paradigm for building distributed networked applications. We develop simple mathematical models to explore and illustrate fundamental performance issues of peer-peer file sharing systems. The modeling framework introduced and the corresponding solution methods are flexible enough to accommodate different characteristics of such systems. Through the specification of model parameters, we apply our framework to three different peer-peer architectures: centralized indexing, distributed indexing with flooded queries, and distributed indexing with hashing directed queries. Using our model, we investigate the effects of system scaling, freeloaders, file popularity and availability on system performance. In particular, we observe that a system with distributed indexing and flooded queries cannot exploit the full capacity of peer-peer systems. We further show that peer-peer file sharing systems can tolerate a significant number of freeloaders without suffering much performance degradation. In many cases, freeloaders can benefit from the available spare capacity of peer-peer systems and increase overall system throughput. Our work shows that simple models coupled with efficient solution methods can be used to understand and answer questions related to the performance of peer-peer file sharing systems.

Network performance evaluation through traditional packet-level simulation is becoming increasingly difficult as today's networks grow in scale along many dimensions. As a consequence, fluid simulation has been proposed to cope with the size and complexity of such systems. This study focuses on analyzing and comparing the relative efficiencies of fluid simulation and packet-level simulation for several network scenarios. We use the "simulation event" rate to measure the computational effort of the simulators and show that this measure is both adequate and accurate. For some scenarios, we derive analytical results for the simulation event rate and identify the major factors that contribute to the simulation event rate. Among these factors, the "ripple effect" is very important since it can significantly increase the fluid simulation event rate. For a tandem queueing system, we identify the boundary condition to establish regions where one simulation paradigm is more efficient than the other. Flow aggregation is considered as a technique to reduce the impact of the "ripple effect" in fluid simulation. We also show that WFQ scheduling discipline can limit the "ripple effect", making fluid simulation particularly well suited for WFQ models. Our results show that tradeoffs between parameters of a network model determines the most efficient simulation approach.