Counting graphlets is a well-studied problem in graph mining and social network analysis. Recently, several papers explored very simple and natural algorithms based on Monte Carlo sampling of Markov Chains (MC), and reported encouraging results. We show, perhaps surprisingly, that such algorithms are outperformed by color coding (CC) [2], a sophisticated algorithmic technique that we extend to the case of graphlet sampling and for which we prove strong statistical guarantees. Our computational experiments on graphs with millions of nodes show CC to be more accurate than MC; furthermore, we formally show that the mixing time of the MC approach is too high in general, even when the input graph has high conductance. All this comes at a price however. While MC is very efficient in terms of space, CC’s memory requirements become demanding when the size of the input graph and that of the graphlets grow. And yet, our experiments show that CC can push the limits of the state-of-the-art, both in terms of the size of the input graph and of that of the graphlets.

Counting graphlets is a well-studied problem in graph mining and social network analysis. Recently, several papers explored very simple and natural approaches based on Monte Carlo sampling of Markov Chains (MC), and reported encouraging results. We show, perhaps surprisingly, that this approach is outperformed by a carefully engineered version of color coding (CC) [1], a sophisticated algorithmic technique that we extend to the case of graphlet sampling and for which we prove strong statistical guarantees. Our computational experiments on graphs with millions of nodes show CC to be more accurate than MC. Furthermore, we formally show that the mixing time of the MC approach is too high in general, even when the input graph has high conductance. All this comes at a price however. While MC is very efficient in terms of space, CC's memory requirements become demanding when the size of the input graph and that of the graphlets grow. And yet, our experiments show that a careful implementation of CC can push the limits of the state of the art, both in terms of the size of the input graph and of that of the graphlets.

Network creation games have been extensively studied, both by economists and computer scientists, due to their versatility in modeling individual-based community formation processes. These processes, in turn, are the theoretical counterpart of several economics, social, and computational applications on the Internet. In their several variants, these games model the tension of a player between the player’s two antagonistic goals: to be as close as possible to the other players and to activate a cheapest possible set of links. However, the generally adopted assumption is that players have a common and complete information about the ongoing network, which is quite unrealistic in practice. In this article, we consider a more compelling scenario in which players have only limited information about the network in whicy they are embedded. More precisely, we explore the game-theoretic and computational implications of assuming that players have a complete knowledge of the network structure only up to a given radius k , which is one of the most qualified local-knowledge models used in distributed computing. In this respect, we define a suitable equilibrium concept, and we provide a comprehensive set of upper and lower bounds to the price of anarchy for the entire range of values of k and for the two classic variants of the game, namely, those in which a player’s cost—besides the activation cost of the owned links—depends on the maximum/sum of all distances to the other nodes in the network, respectively. These bounds are assessed through an extensive set of experiments.

We study the problem of sorting N elements in the presence of persistent errors in comparisons: In this classical model, each comparison between two elements is wrong independently with some probability up to p, but repeating the same comparison gives always the same result. In this model, it is impossible to reliably compute a perfectly sorted permutation of the input elements. Rather, the quality of a sorting algorithm is often evaluated w.r.t. the maximum dislocation of the sequences it computes, namely, the maximum absolute difference between the position of an element in the returned sequence and the position of the same element in the perfectly sorted sequence. The best known algorithms for this problem have running time O(N²) and achieve, w.h.p., an optimal maximum dislocation of \(O(\log N)\) for constant error probability p. Note that no algorithm can achieve maximum dislocation \(o(\log N)\) w.h.p., regardless of its running time. In this work we present the first subquadratic time algorithm with optimal maximum dislocation. Our algorithm runs in \(\widetilde {O}(N^{3/2})\) time and it guarantees \(O(\log N)\) maximum dislocation with high probability for any p ≤ 1/16.