In this work, we propose, analyze and empirically validate a lazy-update approach to maintain accurate approximations of the 2-hop neighborhoods of dynamic graphs resulting from sequences of edge insertions. We first show that under random input sequences, our algorithm exhibits an optimal trade-off between accuracy and insertion cost: it only performs [EQUATION] (amortized) updates per edge insertion, while the estimated size of any vertex's 2-hop neighborhood is at most a factor ε away from its true value in most cases, regardless of the underlying graph topology and for any ε > 0. As a further theoretical contribution, we explore adversarial scenarios that can force our approach into a worst-case behavior at any given time t of interest. We show that while worst-case input sequences do exist, a necessary condition for them to occur is that the girth of the graph released up to time t be at most 4. Finally, we conduct extensive experiments on a collection of real, incremental social networks of different sizes, which typically have low girth. Empirical results are consistent with and typically better than our theoretical analysis anticipates. This further supports the robustness of our theoretical findings: forcing our algorithm into a worst-case behavior not only requires topologies characterized by a low girth, but also carefully crafted input sequences that are unlikely to occur in practice. Combined with standard sketching techniques, our lazy approach proves an effective and efficient tool to support key neighborhood queries on large, incremental graphs, including neighborhood size, Jaccard similarity between neighborhoods and, in general, functions of the union and/or intersection of 2-hop neighborhoods.

The goal of recommender systems is to provide to users suggestions that match their interests, with the eventual goal of increasing their satisfaction, as measured by the number of transactions (clicks, purchases, and so forth). Often, this leads to providing recommendations that are of a particular type. For some contexts (e.g., browsing videos for information) this may be undesirable, as it may enforce the creation of filter bubbles. This is because of the existence of underlying bias in the input data of prior user actions. Reducing hidden bias in the data and ensuring fairness in algorithmic data analysis has recently received significant attention. In this article, we consider both the densest subgraph and the \(k\) -clustering problem, two primitives that are being used by some recommender systems. We are given a coloring on the nodes, respectively the points, and aim to compute a fair solution \(S\) , consisting of a subgraph or a clustering, such that none of the colors is disparately impacted by the solution. Unfortunately, introducing fair solutions typically makes these problems substantially more difficult. Unlike the unconstrained densest subgraph problem, which is solvable in polynomial time, the fair densest subgraph problem is NP-hard even to approximate, which means that with the standard computational model it is probably impossible to solve (or even approximate it sufficiently well) in polynomial time. For \(k\) -clustering, the fairness constraints make the problem very similar to capacitated clustering, which is a notoriously hard problem to even approximate. Despite such negative premises, we are able to provide positive results in important use cases. In particular, we are able to prove that a suitable spectral embedding allows recovery of an almost optimal, fair, dense subgraph hidden in the input data, whenever one is present, a result that is further supported by experimental evidence. We also show a polynomial-time, \(2\) -approximation algorithm to the problem of fair densest subgraph, assuming that there exist only two colors and both colors occur equally often in the graph. This result turns out to be optimal assuming the small set expansion hypothesis. For fair \(k\) -clustering, we show that we can recover high quality fair clusterings effectively and efficiently. For the special case of \(k\) -median and \(k\) -center, we offer additional, fast and simple approximation algorithms as well as new hardness results. The above theoretical findings drive the design of heuristics, which we experimentally evaluate on a scenario based on real data, in which our aim is to strike a good balance between diversity and highly correlated items from Amazon co-purchasing graphs and Facebook contacts. We additionally evaluated our algorithmic solutions for the fair \(k\) -median problem through experiments on various real-world datasets.

We study the minority-opinion dynamics over a fully-connected network of n nodes with binary opinions. Upon activation, a node receives a sample of opinions from a limited number of neighbors chosen uniformly at random. Each activated node then adopts the opinion that is least common within the received sample.

Opinion diffusion is a crucial phenomenon in social networks, often underlying the way in which a collection of agents develops a consensus on relevant decisions. Voter models are well-known theoretical models to study opinion spreading in social networks and structured populations. Their simplest version assumes that an updating agent will adopt the opinion of a neighboring agent chosen at random. These models allow us to study, for example, the probability that a certain opinion will fixate into a consensus opinion, as well as the expected time it takes for a consensus opinion to emerge. Standard voter models are oblivious to the opinions held by the agents involved in the opinion adoption process. We propose and study a context-dependent opinion spreading process on an arbitrary social graph, in which the probability that an agent abandons opinion a in favor of opinion b depends on both a and b. We discuss the relations of the model with existing voter models and then derive theoretical results for both the fixation probability and the expected consensus time for two opinions, for both the synchronous and the asynchronous update models.

We investigate opinion dynamics in a fully-connected system, consisting of n agents, where one of the opinions, called correct, represents a piece of information to disseminate. One source agent initially holds the correct opinion and remains with this opinion throughout the execution. The goal of the remaining agents is to quickly agree on this correct opinion. At each round, one agent chosen uniformly at random is activated: unless it is the source, the agent pulls the opinions of l random agents and then updates its opinion according to some rule. We consider a restricted setting, in which agents have no memory and they only revise their opinions on the basis of those of the agents they currently sample. This setting encompasses very popular opinion dynamics, such as the voter model and best-of-k majority rules. Qualitatively speaking, we show that lack of memory prevents efficient convergence. Specifically, we prove that any dynamics requires Omega(n^2) expected time, even under a strong version of the model in which activated agents have complete access to the current configuration of the entire system, i.e., the case l=n. Conversely, we prove that the simple voter model (in which l=1) correctly solves the problem, while almost matching the aforementioned lower bound. These results suggest that, in contrast to symmetric consensus problems (that do not involve a notion of correct opinion), fast convergence on the correct opinion using stochastic opinion dynamics may require the use of memory.

MOTIVATION: Over the past decade, network-based approaches have proven useful in identifying disease modules within the human interactome, often providing insights into key mechanisms and guiding the quest for therapeutic targets. This is all the more important, since experimental investigation of potential gene candidates is an expensive task, thus not always a feasible option. On the other hand, many sources of biological information exist beyond the interactome and an important research direction is the design of effective techniques for their integration. RESULTS: In this work, we introduce the Biological Random Walks (BRW) approach for disease gene prioritization in the human interactome. The proposed framework leverages multiple biological sources within an integrated framework. We perform an extensive, comparative study of BRW's performance against well-established baselines. AVAILABILITY AND IMPLEMENTATION: All codes are publicly available and can be downloaded at https://github.com/LeoM93/BiologicalRandomWalks. We used publicly available datasets, details on their retrieval and preprocessing are provided in the Supplementary Material. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

We study opinion dynamics in multi-agent networks when a bias toward one of two possible opinions exists, for example reflecting a status quo versus a superior alternative. Our aim is to investigate the combined effect of bias, network structure, and opinion dynamics on the convergence of the system of agents as a whole. Models of such evolving processes can easily become analytically intractable. In this paper, we consider a simple yet mathematically rich setting, in which all agents initially share an initial opinion representing the status quo. The system evolves in steps. In each step, one agent selected uniformly at random follows an underlying update rule to revise its opinion on the basis of those held by its neighbors, but with a probabilistic bias towards the superior alternative. We analyze convergence of the resulting process under well-known update rules. The framework we propose is simple and modular, but at the same time complex enough to highlight a nonobvious interplay between topology and underlying update rule.

We study expansion and information diffusion properties of dynamic networks, i.e., networks whose topologies evolve over time as nodes enter or leave the system and edges are continuously created or destroyed. In this scenario, we investigate flooding as a basic information diffusion mechanism. We are interested in models that are likely to result in sparse networks, i.e., in networks containing$O(n)$edges, with$n$the number of nodes that are present at any given time of interest, with a focus on models in which edges are created randomly according to simple probabilistic mechanisms, rather than according to carefully designed distributed algorithms. In this perspective, in all models we consider, upon joining the network, a node connects to$d=O(1)$random nodes currently in the system. On the other hand, an edge remains alive as long as both its endpoints are. For the case in which edges that fail (because one endpoint left the network) are not replaced, we show that, although the network is likely to contain$\Omega_{d}(n)$isolated nodes, flooding still informs a fraction$1-\exp(-\Omega(d))$of the nodes in time$\mathrm{O}(\log n)$with large, constant probability. Moreover, we are able to show, that at any given time, the graph exhibits a “large-set expansion” property. We further investigate models that exhibit edge regeneration, meaning that, whenever an edge$(v, w)$established by$v$fails because$w$leaves the network, it is replaced by a new random edge$(v, z)$. We show that models with edge regeneration result in evolving networks that, at any given time, are vertex expanders with high probability, so that flooding takes$\mathrm{O}(\log n)$time. The above results hold both for a simplfied streaming model of node churn and in a more realistic, continuous-time setting, in which the interval between two consecutive node arrivals follows a Poisson distribution, while nodes' lifetimes follow an exponential distribution. Previous work considered models in which either the vertex set is fixed or edges are established according to more or less sophisticated algorithms. Our motivation for studying models with simple and random edge creation mechanisms is to move one step further towards models that may eventually capture key aspects of the formation of social or peer-to-peer networks.

Reducing hidden bias in the data and ensuring fairness in algorithmic data analysis has recently received significant attention. In this paper, we address the problem of identifying a densest subgraph, while ensuring that none of one binary protected attribute is disparately impacted.

We investigate opinion dynamics in multi-agent networks when there exists a bias toward one of two possible opinions; for example, reflecting a status quo vs a superior alternative. Starting with all agents sharing an initial opinion representing the status quo, the system evolves in steps. In each step, one agent selected uniformly at random adopts with some probability a the superior opinion, and with probability 1 - a it follows an underlying update rule to revise its opinion on the basis of those held by its neighbors. We analyze the convergence of the resulting process under two well-known update rules, namely majority and voter. The framework we propose exhibits a rich structure, with a nonobvious interplay between topology and underlying update rule. For example, for the voter rule we show that the speed of convergence bears no significant dependence on the underlying topology, whereas the picture changes completely under the majority rule, where network density negatively affects convergence. We believe that the model we propose is at the same time simple, rich, and modular, affording mathematical characterization of the interplay between bias, underlying opinion dynamics, and social structure in a unified setting.

It follows from the Marcus-Spielman-Srivastava proof of the Kadison-Singer conjecture that if G = (V, E) is a Δ-regular dense expander then there is an edge-induced subgraph H = (V, Eh) of G of constant maximum degree which is also an expander. As with other consequences of the MSS theorem, it is not clear how one would explicitly construct such a subgraph. We show that such a subgraph (although with quantitatively weaker expansion and near-regularity properties than those predicted by MSS) can be constructed with high probability in linear time, via a simple algorithm. Our algorithm allows a distributed implementation that runs in O(log n) rounds and does O(n) total work with high probability. The analysis of the algorithm is complicated by the complex dependencies that arise between edges and between choices made in different rounds. We sidestep these difficulties by following the combinatorial approach of counting the number of possible random choices of the algorithm which lead to failure. We do so by a compression argument showing that such random choices can be encoded with a non-trivial compression. Our algorithm bears some similarity to the way agents construct a communication graph in a peer-to-peer network, and, in the bipartite case, to the way agents select servers in blockchain protocols.

Given an underlying graph, we consider the following dynamics: Initially, each node locally chooses a value in $\{-1,1\}$, uniformly at random and independently of other nodes. Then, in each consecutive round, every node updates its local value to the average of the values held by its neighbors, at the same time applying an elementary, local clustering rule that only depends on the current and the previous values held by the node. We prove that the process resulting from this dynamics produces a clustering that exactly or approximately (depending on the graph) reflects the underlying cut in logarithmic time, under various graph models that exhibit a sparse balanced cut, including the stochastic block model. We also prove that a natural extension of this dynamics performs community detection on a regularized version of the stochastic block model with multiple communities. Rather surprisingly, our results provide rigorous evidence for the ability of an extremely simple and natural dynamics to perform community detection, a computational problem which is nontrivial even in a centralized setting.

Spectral techniques have proved amongst the most effective approaches to graph clustering. However, in general they require explicit computation of the main eigenvectors of a suitable matrix (usually the Laplacian matrix of the graph). Recent work (e.g., Becchetti et al., SODA 2017) suggests that observing the temporal evolution of the power method applied to an initial random vector may, at least in some cases, provide enough information on the space spanned by the first two eigenvectors, so as to allow recovery of a hidden partition without explicit eigenvector computations. While the results of Becchetti et al. apply to perfectly balanced partitions and/or graphs that exhibit very strong forms of regularity, we extend their approach to graphs containing a hidden k partition and characterized by a milder form of volume-regularity. We show that the class of k-volume regular graphs is the largest class of undirected (possibly weighted) graphs whose transition matrix admits k “stepwise” eigenvectors (i.e., vectors that have constant entries over the components corresponding to the same set of the hidden partition). To obtain this result, we highlight a connection between volume regularity and lumpability of Markov chains. Moreover, we prove that if the stepwise eigenvectors are those associated to the first k largest eigenvalues of the transition matrix of a random walk on the graph and the gap between the k-th and the (k+1)-th eigenvalues is sufficiently large, the Averaging dynamics of Becchetti et al. recovers the underlying community structure of the graph in logarithmic time, with high probability.

This work proposes a unified framework to leverage biological information in network propagation-based gene prioritization algorithms. Preliminary results on breast cancer data show significant improvements over state-of-the-art baselines, such as the prioritization of genes that are not identified as potential candidates by interactome-based algorithms, but that appear to be involved in/or potentially related to breast cancer, according to a functional analysis based on recent literature.

We show that for n points in d-dimensional Euclidean space, a data oblivious random projection of the columns onto m∈ O((logk+loglogn)ε−6log1/ε) dimensions is sufficient to approximate the cost of all k-means clusterings up to a multiplicative (1±ε) factor. The previous-best upper bounds on m are O(logn· ε−2) given by a direct application of the Johnson-Lindenstrauss Lemma, and O(kε−2) given by [Cohen et al.-STOC’15].

We study the following synchronous process that we call repeated balls-into-bins. The process is started by assigning n balls to n bins in an arbitrary fashion. In every subsequent round, one ball is extracted from each non-empty bin according to some fixed strategy (random, FIFO, etc), and re-assigned to one of the n bins uniformly at random. We define a configuration legitimate if its maximum load is $$\mathcal {O}(\log n)$$ . We prove that, starting from any configuration, the process converges to a legitimate configuration in linear time and then only takes on legitimate configurations over a period of length bounded by any polynomial in n, with high probability (w.h.p.). This implies that the process is self-stabilizing and that every ball traverses all bins within $$\mathcal {O}(n\log ^2 n)$$ rounds, w.h.p.

Consider the following asynchronous, opportunistic communication model over a graph $G$: in each round, one edge is activated uniformly and independently at random and (only) its two endpoints can exchange messages and perform local computations. Under this model, we study the following random process: The first time a vertex is an endpoint of an active edge, it chooses a random number, say $\pm 1$ with probability $1/2$; then, in each round, the two endpoints of the currently active edge update their values to their average. We show that, if $G$ exhibits a two-community structure (for example, two expanders connected by a sparse cut), the values held by the nodes will collectively reflect the underlying community structure over a suitable phase of the above process, allowing efficient and effective recovery in important cases. In more detail, we first provide a first-moment analysis showing that, for a large class of almost-regular clustered graphs that includes the stochastic block model, the expected values held by all but a negligible fraction of the nodes eventually reflect the underlying cut signal. We prove this property emerges after a mixing period of length $\mathcal O(n\log n)$. We further provide a second-moment analysis for a more restricted class of regular clustered graphs that includes the regular stochastic block model. For this case, we are able to show that most nodes can efficiently and locally identify their community of reference over a suitable time window. This results in the first opportunistic protocols that approximately recover community structure using only polylogarithmic work per node. Even for the above class of regular graphs, our second moment analysis requires new concentration bounds on the product of certain random matrices that are technically challenging and possibly of independent interest.

Given an underlying graph, we consider the following dynamics: Initially, each node locally chooses a value in {-1,1}, uniformly at random and independently of other nodes. Then, in each consecutive round, every node updates its local value to the average of the values held by its neighbors, at the same time applying an elementary, local clustering rule that only depends on the current and the previous values held by the node. We prove that the process resulting from this dynamics produces a clustering that exactly or approximately (depending on the graph) reflects the underlying cut in logarithmic time, under various graph models that exhibit a sparse balanced cut, including the stochastic block model. We also prove that a natural extension of this dynamics performs community detection on a regularized version of the stochastic block model with multiple communities. Rather surprisingly, our results provide rigorous evidence for the ability of an extremely simple and natural dynamics to address a computational problem that is non-trivial even in a centralized setting. Distributed Algorithms, Averaging Dynamics, Community Detection, Spectral Analysis, Stochastic Block Models.

We consider the following distributed consensus problem: Each node in a complete communication network of size n initially holds an opinion, which is chosen arbitrarily from a finite set Σ. The system must converge toward a consensus state in which all, or almost all nodes, hold the same opinion. Moreover, this opinion should be valid, i.e., it should be one among those initially present in the system. This condition should be met even in the presence of a malicious adversary who can modify the opinions of a bounded subset of nodes, adaptively chosen in every round. We consider the 3-majority dynamics: At every round, every node pulls the opinion from three random neighbors and sets his new opinion to the majority one (ties are broken arbitrarily). Let k be the number of valid opinions. We show that, if k ≤ nα, where α is a suitable positive constant, the 3-majority dynamics converges in time polynomial in k and log n with high probability even in the presence of an adversary who can affect up to nodes at each round. Previously, the convergence of the 3-majority protocol was known for |Σ| = 2 only, with an argument that is robust to adversarial errors. On the other hand, no anonymous, uniform-gossip protocol that is robust to adversarial errors was known for |Σ| > 2.

Crowdsourcing is a computational paradigm whose distinctive feature is the involvement of human workers in key steps of the computation. It is used successfully to address problems that would be hard or impossible to solve for machines. As we highlight in this work, the exclusive use of nonexpert individuals may prove ineffective in some cases, especially when the task at hand or the need for accurate solutions demand some degree of specialization to avoid excessive uncertainty and inconsistency in the answers. We address this limitation by proposing an approach that combines the wisdom of the crowd with the educated opinion of experts. We present a computational model for crowdsourcing that envisions two classes of workers with different expertise levels. One of its distinctive features is the adoption of the threshold error model, whose roots are in psychometrics and which we extend from previous theoretical work. Our computational model allows to evaluate the performance of crowdsourcing algorithms with respect to accuracy and cost. We use our model to develop and analyze an algorithm for approximating the best, in a broad sense, of a set of elements. The algorithm uses naïve and expert workers to find an element that is a constant-factor approximation to the best. We prove upper and lower bounds on the number of comparisons needed to solve this problem, showing that our algorithm uses expert and naïve workers optimally up to a constant factor. Finally, we evaluate our algorithm on real and synthetic datasets using the CrowdFlower crowdsourcing platform, showing that our approach is also effective in practice.

We study Plurality Consensus in the Model over a network of n anonymous agents. Each agent supports an initial opinion or color. We assume that at the onset, the number of agents supporting the plurality color exceeds that of the agents supporting any other color by a sufficiently-large bias, though the initial plurality itself might be very far from absolute majority. The goal is to provide a protocol that, with high probability, brings the system into the configuration in which all agents support the (initial) plurality color. We consider the Undecided-State Dynamics, a well-known protocol which uses just one more state (the undecided one) than those necessary to store colors. We show that the speed of convergence of this protocol depends on the initial color configuration as a whole, not just on the gap between the plurality and the second largest color community. This dependence is best captured by a novel notion we introduce, namely, the monochromatic distance md which measures the distance of the initial color configuration from the closest monochromatic one. In the complete graph, we prove that, for a wide range of the input parameters, this dynamics converges within O(md log n) rounds. We prove that this upper bound is almost tight in the strong sense: Starting from any color configuration , the convergence time is Ω(md). Finally, we adapt the Undecided-State Dynamics to obtain a fast, random walk-based protocol for plurality consensus on regular expanders. This protocol converges in O(md polylog(n)) rounds using only polylog(n) local memory. A key-ingredient to achieve the above bounds is a new analysis of the maximum node congestion that results from performing n parallel random walks on regular expanders. All our bounds hold with high probability.

We study the following synchronous process that we call repeated balls-into-bins. The process is started by assigning n balls to n bins in an arbitrary way. Then, in every subsequent round, one ball is chosen according to some fixed strategy (random, FIFO, etc) from each non-empty bin, and re-assigned to one of the n bins uniformly at random. This process corresponds to a non-reversible Markov chain and our aim is to study its self-stabilization properties with respect to the maximum(bin) load and some related performance measures. We define a configuration (i.e., a state) legitimate if its maximum load is O(log n). We first prove that, starting from any legitimate configuration, the process will only take on legitimate configurations over a period of length bounded by any polynomial in n, with high probability (w.h.p.). Further we prove that, starting from any configuration, the process converges to a legitimate configuration in linear time, w.h.p. This implies that the process is self-stabilizing w.h.p. and, moreover, that every ball traverses all bins in O(n log2 n) rounds, w.h.p. The latter result can also be interpreted as an almost tight bound on the cover time for the problem of parallel resource assignment in the complete graph.

We design algorithms that, given a collection of documents and a distribution over user queries, return a small subset of the document collection in such a way that we can efficiently provide high-quality answers to user queries using only the selected subset. This approach has applications when space is a constraint or when the query-processing time increases significantly with the size of the collection. We study our algorithms through the lens of stochastic analysis and prove that even though they use only a small fraction of the entire collection, they can provide answers to most user queries, achieving a performance close to the optimal. To complement our theoretical findings, we experimentally show the versatility of our approach by considering two important cases in the context of Web search. In the first case, we favor the retrieval of documents that are relevant to the query, whereas in the second case we aim for document diversification. Both the theoretical and the experimental analysis provide strong evidence of the potential value of query covering in diverse application scenarios.

We study a Plurality Consensus process in which each of n anonymous agents of a communication network supports an initial opinion (a colorchosen from a finite set [k]) and, at every time step, he can revise his color according to a random sample of neighbors.

Performance bounds for opportunistic networks have been derived in a number of recent papers for several key quantities, such as the expected delivery time of a unicast message, or the flooding time (a measure of how fast information spreads). However, to the best of our knowledge, none of the existing results is derived under a mobility model which is able to reproduce the power law+exponential tail dichotomy of the pairwise node intercontact time distribution which has been observed in traces of several real opportunistic networks. The contributions of this paper are two-fold: first, we present a simple pairwise contact model—called the Home-MEG model—for opportunistic networks based on the observation made in previous work that pairs of nodes in the network tend to meet in very few, selected locations (home locations); this contact model is shown to be able to faithfully reproduce the power law+exponential tail dichotomy of intercontact time. Second, we use the Home-MEG model to analyze flooding time in opportunistic networks, presenting asymptotic bounds on flooding time that assume different initial conditions for the existence of opportunistic links. By comparing asymptotic bounds with the results of simulations performed using a realistic human mobility model, we demonstrate the capability of the proposed Home-MEG model to faithfully predict the speed of information spreading in large-scale opportunistic networks. Finally, our bounds provide some analytical evidences that the speed of information spreading in opportunistic networks can be much faster than that predicted by simple geometric mobility models.

We study the problem of online team formation. We consider a setting in which people possess different skills and compatibility among potential team members is modeled by a social network. A sequence of tasks arrives in an online fashion, and each task requires a specific set of skills. The goal is to form a new team upon arrival of each task, so that (i) each team possesses all skills required by the task, (ii) each team has small communication overhead, and (iii) the workload of performing the tasks is balanced among people in the fairest possible way.

In this paper we introduce the problem of query covering as a means to efficiently cache query results. The general idea is to populate the cache with documents that contribute to the result pages of a large number of queries, as opposed to caching the top documents for each query. It turns out that the problem is hard and solving it requires knowledge of the structure of the queries and the results space, as well as knowledge of the input query distribution. We formulate the problem under the framework of stochastic optimization; theoretically it can be seen as a stochastic universal version of set multicover. While the problem is NP-hard to be solved exactly, we show that for any distribution it can be approximated using a simple greedy approach. Our theoretical findings are complemented by experimental activity on real datasets, showing the feasibility and potential interest of query-covering approaches in practice.

The internet has enabled the collaboration of groups at a scale that was unseen before. A key problem for large collaboration groups is to be able to allocate tasks effectively. An effective task assignment method should consider both how fit teams are for each job as well as how fair the assignment is to team members, in terms that no one should be overloaded or unfairly singled out. The assignment has to be done automatically or semi-automatically given that it is difficult and time-consuming to keep track of the skills and the workload of each person. Obviously the method to do this assignment must also be computationally efficient.

In this paper we propose a fully decentralized approach for recommending new contacts in the social network of mobile phone users. With respect to existing solutions, our approach is characterized by some distinguishing features. In particular, the application we propose does not assume any centralized coordination: it transparently collects and processes user information that is accessible in any mobile phone, such as the log of calls, the list of contacts or the inbox/outbox of short messages and exchanges it with other users. This information is used to recommend new friendships to other users. Furthermore, the information needed to perform recommendation is collected and exchanged between users in a privacy preserving way. Finally, information necessary to implement the application is exchanged transparently and opportunistically, by using the residual space in standard short messages occasionally exchanged between users. As a consequence, we do not ask users to change their habits in using SMS.

Query recommendation is an integral part of modern search engines. The goal of query recommendation is to facilitate users while searching for information. Query recommendation also allows users to explore concepts related to their information needs.

In this article, we study the problem of approximate local triangle counting in large graphs. Namely, given a large graph G =( V,E ) we want to estimate as accurately as possible the number of triangles incident to every node v ∈ V in the graph. We consider the question both for undirected and directed graphs. The problem of computing the global number of triangles in a graph has been considered before, but to our knowledge this is the first contribution that addresses the problem of approximate local triangle counting with a focus on the efficiency issues arising in massive graphs and that also considers the directed case. The distribution of the local number of triangles and the related local clustering coefficient can be used in many interesting applications. For example, we show that the measures we compute can help detect the presence of spamming activity in large-scale Web graphs, as well as to provide useful features for content quality assessment in social networks. For computing the local number of triangles (undirected and directed), we propose two approximation algorithms, which are based on the idea of min-wise independent permutations [Broder et al. 1998]. Our algorithms operate in a semi-streaming fashion, using O (| V |) space in main memory and performing O (log | V |) sequential scans over the edges of the graph. The first algorithm we describe in this article also uses O (| E |) space of external memory during computation, while the second algorithm uses only main memory. We present the theoretical analysis as well as experimental results on large graphs, demonstrating the practical efficiency of our approach.

A sensor network consists of sensing devices which may exchange data through wireless communication; sensor networks are highly energy constrained since they are usually battery operated. Data aggregation is a possible way to save energy consumption: nodes may delay data in order to aggregate them into a single packet before forwarding them towards some central node (sink). However, many applications impose constraints on the maximum delay of data; this translates into latency constraints for data arriving at the sink. We study the problem of data aggregation to minimize maximum energy consumption under latency constraints on sensed data delivery, and we assume unique communication paths that form an intree rooted at the sink. We prove that the offline problem is strongly NP-hard and we design a 2-approximation algorithm. The latter uses a novel rounding technique. Almost all real-life sensor networks are managed online by simple distributed algorithms in the nodes. In this context we consider both the case in which sensor nodes are synchronized or not. We assess the performance of the algorithm by competitive analysis. We also provide lower bounds for the models we consider, in some cases showing optimality of the algorithms we propose. Most of our results also hold when minimizing the total energy consumption of all nodes.

In this paper we study the problem of local triangle counting in large graphs. Namely, given a large graph G = (V;E) we want to estimate as accurately as possible the number of triangles incident to every node υ ∈ V in the graph. The problem of computing the global number of triangles in a graph has been considered before, but to our knowledge this is the first paper that addresses the problem of local triangle counting with a focus on the efficiency issues arising in massive graphs. The distribution of the local number of triangles and the related local clustering coefficient can be used in many interesting applications. For example, we show that the measures we compute can help to detect the presence of spamming activity in large-scale Web graphs, as well as to provide useful features to assess content quality in social networks.

We propose link-based techniques for automatic detection of Web spam, a term referring to pages which use deceptive techniques to obtain undeservedly high scores in search engines. The use of Web spam is widespread and difficult to solve, mostly due to the large size of the Web which means that, in practice, many algorithms are infeasible. We perform a statistical analysis of a large collection of Web pages. In particular, we compute statistics of the links in the vicinity of every Web page applying rank propagation and probabilistic counting over the entire Web graph in a scalable way. These statistical features are used to build Web spam classifiers which only consider the link structure of the Web, regardless of page contents. We then present a study of the performance of each of the classifiers alone, as well as their combined performance, by testing them over a large collection of Web link spam. After tenfold cross-validation, our best classifiers have a performance comparable to that of state-of-the-art spam classifiers that use content attributes, but are orthogonal to content-based methods.

In the multicommodity rent-or-buy (MROB) network design problems, we are given a network together with a set of k terminal pairs ( s 1 , t 1 ), …, ( s k , t k . The goal is to provision the network so that a given amount of flow can be shipped between s i and t i for all 1 ≤ i ≤ k simultaneously. In order to provision the network, one can either rent capacity on edges at some cost per unit of flow, or buy them at some larger fixed cost. Bought edges have no incremental, flow-dependent cost. The overall objective is to minimize the total provisioning cost. Recently, Gupta et al. [2003a] presented a 12-approximation for the MROB problem. Their algroithm chooses a subset of the terminal pairs in the graph at random and then buys the edges of an approximate Steiner forest for these pairs. This technique had previously been introduced [Gupta et al. 2003b] for the single-sink rent-or-buy network design problem. In this article we give a 6.828-approximation for the MROB problem by refining the algorithm of Gupta et al. and simplifying their analysis. The improvement in our article is based on a more careful adaptation and simplified analysis of the primal-dual algorithm for the Steiner forest problem due to Agrawal et al. [1995]. Our result significantly reduces the gap between the single-sink and multisink case.

The empirical distribution of PageRank in a large sample of Web pages does not follow a powerlaw except for particular choices of the damping factor. The tail, comprising 5%10 % of the nodes, always follows a power law, but the distribution for the remaining 90%95 % of pages varies. This was observed in several Web samples having from 1 to 50 million pages with damping factors from 0.1 to 0.9 and the resulting behavior was very similar, specially if we restrict the sample to the main strongly connected component. DoublePareto Model As in [Mitzenmacher 2003], we can fit the powerlaw to the body and the tail of the distribution separately, as in the figure on the right. Given that the minimum value of PageRank is the baseline probability (1-α / N) if we assume the following: (i) The exponent of the body is equal to the exponent of the tail (ii)The distribution is normalized to 1, as in the case of PageRank (iii) N>> 1... we can show that the intersection point of the first figure, 1-F(1/N) does Conjecture not depend on N: 1-F(1/N) ≃ (1-α) θ-1 In a graph with powerlaw exponent θ for the indegree, calculating PageRank with: If we accept the hypothesis in [Pandurangan et al. 2002], that is, the powerlaw exponent for the distribution of the tail of the PageRank values is the same as for the indegree of pages, then: α = 1 θ – 1 In our collection of 1 million nodes with θ=2.2 and α=0.85, the Yields a powerlaw over the entire range of values value predicted for 1F(1/N) is 0.10 and the observed 0.12 In the WebBase collection of 130 million documents with θ=2.07 and α=0.85 the predicted value is 0.13, and the 0.16 Examples: θ=2.1, then α=0.90 yields a powerlaw θ=2.2, then α=0.83 yields a powerlawLognormal + Baseline Model Let X be a random variable distributed according to a lognormal distribution. We propose the following model for the PageRank distribution: X + (1-α)/N To obtain the lognormal parameters, we fit this to the distribution of PageRank with α=0.99. Then using the same parameters, we can fit the PageRank distribution obtained with other damping factors with high precision. Fit with our model: Fit with a powerlaw:

Abstract Next‐generation 3G/4G wireless data networks allow multiple codes (or channels) to be allocated to a single user, where each code can support multiple data rates. Providing fine‐grained QoS to users in such networks poses the two‐dimensional challenge of assigning both power (rate) and codes to every user. This gives rise to a new class of parallel scheduling problems. We abstract general downlink scheduling problems suitable for proposed next‐generation wireless data systems. Our contribution includes a communication‐theoretic model for multirate wireless channels. In addition, while conventional focus has been on throughput maximization, we attempt to optimize the maximum response time of jobs, which is more suitable for streams of user requests. We present provable results on the algorithmic complexity of these scheduling problems. In particular, we are able to provide very simple, on‐line algorithms for approximating the optimal maximum response time. We also perform an experimental study with realistic data of channel conditions and user requests that strengthens our theoretical results. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 45(1), 9–22 2005

Scheduling a sequence of jobs released over time when the processing time of a job is only known at its completion is a classical problem in CPU scheduling in time sharing operating systems. A widely used measure for the responsiveness of the system is the average flow time of the jobs, that is, the average time spent by jobs in the system between release and completion.The Windows NT and the Unix operating system scheduling policies are based on the Multilevel Feedback algorithm. In this article, we prove that a randomized version of the Multilevel Feedback algorithm is competitive for single and parallel machine systems, in our opinion providing one theoretical validation of the goodness of an idea that has proven effective in practice along the last two decades.The randomized Multilevel Feedback algorithm (RMLF) was first proposed by Kalyanasundaram and Pruhs for a single machine achieving an O (log n log log n ) competitive ratio to minimize the average flow time against the on-line adaptive adversary, where n is the number of jobs that are released. We present a version of RMLF working for any number m of parallel machines. We show for RMLF a first O (log n log n / m ) competitiveness result against the oblivious adversary on parallel machines. We also show that the same RMLF algorithm surprisingly achieves a tight O (log n ) competitive ratio against the oblivious adversary on a single machine, therefore matching the lower bound for this case.

In this paper, we introduce the notion of smoothed competitive analysis of online algorithms. Smoothed analysis has been proposed by Spielman and Teng [25] to explain the behavior of algorithms that work well in practice while performing very poorly from a worst-case analysis point of view. We apply this notion to analyze the multilevel feedback algorithm (MLF) to minimize the total flow time on a sequence of jobs released over time when the processing time of a job is only known at time of completion. The initial processing times are integers in the range [1, 2K]. We use a partial bit randomization model, i.e., the initial processing times are smoothed by changing the k least significant bits under a quite general class of probability distributions. We show that MLF admits a smoothed competitive ratio of O((2k/σ)3+ (2k/σ)22K-k), where σ denotes the standard deviation of the distribution. In particular, we obtain a competitive ratio of O(2K-k) if σ = Θ(2k). We also prove an Ω(2K-k) lower bound for any deterministic algorithm that is run on processing times smoothed according to the partial bit randomization model. For various other smoothing models, including the additive symmetric smoothing one, which is a variant of the model used by Spielman and Teng [25], we give a higher lower bound of Ω(2K). A direct consequence of our result is also the first average-case analysis of MLF. We show a constant expected ratio of the total flow time of MLF to the optimum under several distributions including the uniform one.

Next generation 3G/4G wireless data networks allow multiple codes (or channels) to be allocated to a single user, where each code can support multiple data rates. Providing fine-grained QoS to users in such networks poses the two dimensional challenge of assigning both power (rate) and codes for every user. This gives rise to a new class of parallel scheduling problems. We abstract general downlink scheduling problems suitable for proposed next generation wireless data systems. This includes a communication-theoretic model for multirate wireless channels. In addition, while conventional focus has been on throughput maximization, we attempt to optimize the maximum response time of jobs, which is more suitable for stream of user requests. We present provable results on the algorithmic complexity of these scheduling problems. In particular, we are able to provide very simple, online algorithms for approximating the optimal maximum response time. This relies on resource augmented competitive analysis. We also perform an experimental study with realistic data of channel conditions and user requests to show that our algorithms are more accurate than our worst case analysis shows, and they provide fine-grained QoS to users effectively.

Scheduling a sequence of jobs released over time when the processing time of a job is only known at its completion is a classical problem in CPU scheduling in time sharing operating systems. A widely used measure for the responsiveness of the system is the average flow time of the jobs, i.e. the average time spent by jobs in the system between release and completion.