We present novel graph kernels for graphs with node and edge labels that have ordered neighborhoods, i.e. when neighbor nodes follow an order. Graphs with ordered neighborhoods are a natural data representation for evolving graphs where edges are created over time, which induces an order. Combining convolutional subgraph kernels and string kernels, we design new scalable algorithms for generation of explicit graph feature maps using sketching techniques. We obtain precise bounds for the approximation accuracy and computational complexity of the proposed approaches and demonstrate their applicability on real datasets. In particular, our experiments demonstrate that neighborhood ordering results in more informative features. For the special case of general graphs, i.e. graphs without ordered neighborhoods, the new graph kernels yield efficient and simple algorithms for the comparison of label distributions between graphs.

We study online robust matrix completion on graphs. At each iteration a vector with some entries missing is revealed and our goal is to reconstruct it by identifying the underlying low-dimensional subspace from which the vectors are drawn. We assume there is an underlying graph structure to the data, that is, the components of each vector correspond to nodes of a certain known and fixed graph, and their values are related accordingly. We propose an algorithm that exploits the graph to reconstruct the incomplete data, in the scenario where there is outlier noise. The theoretical properties of the algorithms are studied and numerical experiments using both synthetic and real world datasets verify the improved performance of the proposed technique compared to other state of the art algorithms.

Matrix Completion (MC) i.e., estimating the missing values of an unknown matrix based on limited information, has been a prominent topic of study in the last decades. In this paper, we focus more precisely on a little-known aspect of MC, namely how the recommendation of new entries can help improve the accuracy of the reconstruction. We present an efficient online algorithm to solve the MC task, and propose an Adaptive Sampling under Smoothness Assumption (AdSSA) strategy, which is suitable for operation on smooth low-rank matrices. This technique is able to predict iteratively which entries are the most informative. Our numerical examples illustrate that AdSSA performs significantly better than the Uniform Random Sampling (URS) and the Query by Committee (QbC). In addition, AdSSA algorithm can be straightforwardly implemented in an online and efficient manner, which constitutes another advantage.

The centralized control in Software Defined Networks paves the way for new services like Bandwidth Calendaring (BWC), where the possibility to shift temporally future bandwidth requests allows to efficiently use network resources. Assuming perfect knowledge of the calendar for all future bandwidth reservations is unrealistic. In this paper, we study the online version of the BWC problem presented in [1], where for unpredictable incoming demands an admission decision, scheduling and path allocation must be taken instantaneously. We design an algorithm for solving the online version of the BWC problem and proposes two heuristic approaches to exploit the scheduling flexibility of demands. Our numerical results reveal that the proposed solution approach outperforms state-of-the art methods by up to 70% in terms of accepted traffic.

This work presents a distributed algorithm for nonlinear adaptive learning. In particular, a set of nodes obtain measurements, sequentially one per time step, which are related via a nonlinear function; their goal is to collectively minimize a cost function by employing a diffusion based Kernel Least Mean Squares (KLMS). The algorithm follows the Adapt Then Combine mode of cooperation. Moreover, the theoretical properties of the algorithm are studied and it is proved that under certain assumptions the algorithm suffers a no regret bound. Finally, comparative experiments verify that the proposed scheme outperforms other variants of the LMS.

Accurate coverage maps are an important tool for network planning and operation but it is often impossible to obtain these maps completely from measurements. In this paper we describe two new methods that enable operators to minimize the cost for obtaining a complete coverage map at high accuracy. Our first method applies the Singular Value Thresholding (SVT) algorithm to reconstruct a complete map from a sparse matrix of coverage data. We then use the Query by Committee (QbC) rationale to identify the areas where further measurements would maximize accuracy of the completed map. This second method allows operators to plan their drive tests such that a given budget is spent at highest efficiency. Our numerical examples illustrate that our proposed completion technique outperforms relevant state of the art and that QbC further enhances reconstruction accuracy.

This paper addresses a fundamental limitation for the adoption of caching for wireless access networks due to small population sizes. This shortcoming is due to two main challenges: making timely estimates of varying content popularity and inferring popular content from small samples. We propose a framework which alleviates such limitations. To timely estimate varying popularity in a context of a single cache we propose an Age-Based Threshold (ABT) policy which caches all contents requested more times than a threshold N (τ), where τ is the content age. We show that ABT is asymptotically hit rate optimal in the many contents regime, which allows us to obtain the first characterization of the optimal performance of a caching system in a dynamic context. We then address small sample sizes focusing on L local caches and one global cache. On the one hand we show that the global cache learns L times faster by aggregating all requests from local caches, which improves hit rates. On the other hand, aggregation washes out local characteristics of correlated traffic which penalizes hit rate. This motivates coordination mechanisms which combine global learning of popularity scores in clusters and Least-Recently-Used (LRU) policy with prefetching.

By offloading the control plane to powerful computing platforms running on commodity hardware, Software Defined Networking (SDN) unleashes the potential to operate computation intensive machine learning tools and solve complex optimization problems in a centralized fashion. This paper studies such an opportunity under the framework of the centralized SDN Admission Control (AC) problem. We first review and adapt some of the key AC algorithms from the literature, and evaluate their performance under realistic settings. We then propose to take a step further and build an AC meta-algorithm that is able to track the best AC algorithm under unknown traffic conditions. To this aim, we exploit a machine learning technique called Strategic Expert meta-Algorithm (SEA).

SDN unleashes the potential to perform computational intensive machine learning algorithms to solve complex routing problems. This demo presents an architecture for the SDN controller that integrates several online routing algorithms for the real-time admission control of new connection requests. The demonstrator permits to compare the evolution of the network according to the admission decisions taken by different online algorithms and to simulate future scenarios to support strategic decisions aimed at improving the infrastructure.

In this paper, we introduce and examine two new models for competitive contagion in networks, a game-theoretic generalization of the viral marketing problem. In our setting, firms compete to maximize their market share in a network of consumers whose adoption decisions are stochastically determined by the choices of their neighbors. Building on the switching-selecting framework introduced by Goyal and Kearns, we first introduce a new model in which the payoff to firms comprises not only the number of vertices who adopt their (competing) technologies, but also the network connectivity among those nodes. For a general class of stochastic dynamics driving the local adoption process, we derive upper bounds on (1) the (pure strategy) Price of Anarchy (PoA), which measures the inefficiency of resource use at equilibrium, and (2) the Budget Multiplier, which captures the extent to which the network amplifies the imbalances in the firms' initial budgets. These bounds depend on the firm budgets and the maximum degree of the network, but no other structural properties. In addition, we give general conditions under which the PoA and the Budget Multiplier can be unbounded. We also introduce a model in which budgeting decisions are endogenous, rather than externally given as is typical in the viral marketing problem. In this setting, the firms are allowed to choose the number of seeds to initially infect (at a fixed cost per seed), as well as which nodes to select as seeds. In sharp contrast to the results of Goyal and Kearns, we show that for almost any local adoption dynamics, there exists a family of graphs for which the PoA and Budget Multiplier are unbounded.

Motivated by the distributed binary consensus algorithm in Perron et al. [(2009) Using Three States for Binary Consensus on Complete Graphs. INFOCOM 2009, IEEE, April, pp. 2527–2535], we propose a distributed algorithm for the multivalued consensus problem. In the multivalued consensus problem, each node initially chooses from one of k available choices and the objective of all nodes is to find the choice which was initially chosen by the majority in a distributed fashion. Although the voter model (e.g. Hassin, Y. and Peleg, D. (2002) Distributed probabilistic polling and applications to proportionate agreement. Inf. Comput., 171, 248–268) can be used to find a consensus on multiple choices, it only guarantees consensus and not the consensus on the majority. We derive the time of convergence and an upper bound for the probability of error of our proposed algorithm which shows that, similar to Perron et al. [(2009) Using Three States for Binary Consensus on Complete Graphs. INFOCOM 2009, IEEE, pp. 2527–2535], having an additional state would result in significant improvement of both the convergence time and the probability of error for complete graphs. We also show that our algorithm could be used in Erdös–Rényi and regular graphs by simulations.

We show that parametric multi-armed bandit (MAB) problems with large state and action spaces can be algorithmically reduced to the supervised learning model known as Knows What It Knows or KWIK learning. We give matching impossibility results showing that the KWIK learnability requirement cannot be replaced by weaker supervised learning assumptions. We provide such results in both the standard parametric MAB setting, as well as for a new model in which the action space is finite but growing with time.

We consider the design and implementation of the binary consensus algorithm in wireless sensor networks (WSN) under real life environment. This algorithm is applied for the evaluation of a consensus of a measured values in presence of a faulty/attacked node. As this algorithm has been tested theoretically, we deploy it for real-life environment including distributed and routing features. In this paper, we propose the development and the implementation of the distributed binary consensus algorithm in WSN under Tinyos environment. The implementation was tested on sensor nodes using the TinyOSSimulator for a WSN with a large number of nodes and a testbed with limited number of nodes. We evaluate the performances related to the average convergence time of nodes states to a consensus value. As in analytical results, in the simulations, we applied the distributed algorithm for fully connected, ring, cycle, Erdos Reny random, and star-shaped topologies.

In this paper, we study the impact of edge weights on distances in sparse random graphs. We interpret these weights as delays and take them as independent and identically distributed exponential random variables. We analyze the weighted flooding time defined as the minimum time needed to reach all nodes from one uniformly chosen node and the weighted diameter corresponding to the largest distance between any pair of vertices. Under some standard regularity conditions on the degree sequence of the random graph, we show that these quantities grow as the logarithm of $n$ when the size of the graph $n$ tends to infinity. We also derive the exact value for the prefactor. These results allow us to analyze an asynchronous randomized broadcast algorithm for random regular graphs. Our results show that the asynchronous version of the algorithm performs better than its synchronized version: in the large size limit of the graph, it will reach the whole network faster even if the local dynamics are similar on average.

We consider the convergence time for solving the binary interval consensus problem using a distributed algorithm proposed by Benezit at al (2009) for computing the quantized average value. In the binary consensus problem, each node initially holds one of two states and the goal for each node is to correctly decide which one of the two states was initially held by a majority of nodes. We derive an upper bound on the expected convergence time that holds for arbitrary connected graphs, which is based on the location of eigenvalues of some contact rate matrices. We instantiate our bound for particular networks of interest, including complete graphs, star-shaped networks, and Erdos-Renyi random graphs, and in the former two cases compare with alternative computations. We find that for all these examples our bound is of exact order with respect to the number of nodes. We pinpoint the fact that the expected convergence time critically depends on the voting margin defined as the difference between the fraction of the nodes that initially held the majority and the minority states, respectively. We derive an exact relation between the expected convergence time and the voting margin, for some of these graphs, which reveals how the expected convergence time tends to infinity as the voting margin approaches zero. Our results provide insights on how the expected convergence time depends on the network topology which can be used for performance evaluation and network design. The results are of interest in the context of peer-to-peer systems; in particular, for sensor networks and distributed databases.