Search

In many applications of Bloom filters, it is possible to exploit the patterns present in the inserted and non-inserted keys to achieve more compression than the standard Bloom filter. A new class of Bloom filters called Learned Bloom filters use machine learning models to exploit these patterns in the data. In practice, these methods and their variants raise many questions: the choice of machine learning models, the training paradigm to achieve the desired results, the choice of thresholds, the number of partitions in case multiple partitions are used, and other such design decisions. In this paper, we present a simple partitioned Bloom filter that works as follows: we partition the Bloom filter into segments, each of which uses a simple projection-based hash function computed using the data. We also provide a theoretical analysis that provides a principled way to select the design parameters of our method: number of hash functions and number of bits per partition. We perform empirical evaluations of our methods on various real-world datasets spanning several applications. We show that it can achieve an improvement in false positive rates of up to two orders of magnitude over standard Bloom filters for the same memory usage, and upto 50% better compression (bytes used per key) for same FPR, and, consistently beats the existing variants of learned Bloom filters.

Food delivery, today, is a multi-billion dollar industry. Minimizing food delivery time is a key contributor towards building positive customer experiences. More precisely, given a stream of food orders and available delivery vehicles, how should orders be assigned to vehicles so the delivery time is minimized? Several decisions have to be made: (1) assignment of orders to vehicles, (2) grouping orders into batches to cope with limited vehicle availability, (3) adapting to dynamic positions of delivery vehicles, and (4) ensuring scalability to the demands of real-world workloads. We show that the minimization problem is not only NP-hard but inapproximable in polynomial time. To mitigate this computational bottleneck, we develop an algorithm called FoodMatch , which maps the vehicle assignment problem to that of minimum weight perfect matching on a bipartite graph. To further reduce the quadratic construction cost of the bipartite graph, we deploy best-first search to only compute a subgraph that is highly likely to contain the minimum matching. The solution quality is further enhanced by reducing batching to a graph batching problem and anticipating dynamic positions of vehicles through angular distance . We perform extensive experiments on real food-delivery data from large metropolitan cities. Our results establish that FoodMatch imparts substantial improvements over baseline strategies across a host of metrics such as food delivery time, waiting time at restaurants, and orders delivered per kilometer. Furthermore, FoodMatch is efficient enough to handle real-world workloads.

Regular simple path query (RPQ) is one of the fundamental operators in graph analytics. In an RPQ, the input is a graph, a source node and a regular expression. The goal is to identify all nodes that are connected to the source through a simple path whose label sequence satisfies the given regular expression. The regular expression acts as a formal specification of the search space that is of interest to the user. Although regular expressions have high expressive power, they act as barrier to non-technical users. Furthermore, to fully realize the power of regular expressions, the user must be familiar with the domain of the graph dataset. In this study, we address this bottleneck by bridging RPQs with the query-by-example paradigm. More specifically, we ask the user for an exemplar pair that characterizes the paths of interest, and the regular expression is automatically inferred from this exemplar. This novel problem introduces several new challenges. How do we infer the regex? Given that answering RPQs is NP-hard, how do we scale to large graphs? We address these challenges through a unique combination of Biermann and Feldman's algorithm with NFA-guided random walks with restarts. Extensive experiments on multiple real, million-scale datasets establish that RQuBE is at least 3 orders of magnitude faster than baseline strategies with an average accuracy in excess of 90%.

In this paper, we provide a family of bounds for the rate at which the functions of many inputs can be computed in-network on general topologies. Going beyond simple symmetric functions where the output is invariant to the permutation of the operands, e.g., average, parity, we describe an algorithm that is analyzed to provide throughput bounds (both lower and upper) for the general functions. In particular, we analyze our algorithm when the function to be computed is given as a binary tree schema. Our lower bounds depend on schema parameters like the number of operands and graph parameters like the second largest eigenvalue of the transition matrix of simple random walk on network graph, the maximum and minimum degree of any node in the network. The lower bounding technique that we have used is based on the network flows and can capture general multi-commodity flow settings. Our proposed algorithm uses the well-known simple random walk on a network as its basic primitive for routing. We show that the lower bound obtained on the rate of computation is tight for the complete network topology, the hypercube and the star topology. We also present an upper bound on the expected latency of any data operand in terms of the height of schema, well-studied random walk parameter like the hitting time, and the relative distance from the critical data rate. For the computation time of symmetric functions on the random geometric graph under the gossip model, our approach achieves an order-optimal $$\widetilde{O}(n)$$ time despite enforcing a binary tree schema for function computation. In general, Big-O notation represents an upper bound and $$\widetilde{O}$$ hides $$\text {poly}\log n$$ factors.

In scientific computing and data science disciplines, it is often necessary to share application workflows and repeat results. Current tools containerize application workflows, and share the resulting container for repeating results. These tools, due to containerization, do improve sharing of results. However, they do not improve the efficiency of replay. In this paper, we present the multiversion replay problem which arises when multiple versions of an application are containerized, and each version must be replayed to repeat results. To avoid executing each version separately, we develop CHEX, which checkpoints program state and determines when it is permissible to reuse program state across versions. It does so using system call-based execution lineage. Our capability to identify common computations across versions enables us to consider optimizing replay using an in-memory cache, based on a checkpoint-restore-switch system. We show the multiversion replay problem is NP-hard, and propose efficient heuristics for it. CHEX reduces overall replay time by sharing common computations but avoids storing a large number of checkpoints. We demonstrate that CHEX maintains lightweight package sharing, and improves the total time of multiversion replay by 50% on average., Comment: 13 pages, 13 figures, VLDB

Along with the rapid growth and rise to prominence of food delivery platforms, concerns have also risen about the terms of employment of the gig workers underpinning this growth. Our analysis on data derived from a real-world food delivery platform across three large cities from India show that there is significant inequality in the money delivery agents earn. In this paper, we formulate the problem of fair income distribution among agents while also ensuring timely food delivery. We establish that the problem is not only NP-hard but also inapproximable in polynomial time. We overcome this computational bottleneck through a novel matching algorithm called FairFoody. Extensive experiments over real-world food delivery datasets show FairFoody imparts up to 10 times improvement in equitable income distribution when compared to baseline strategies, while also ensuring minimal impact on customer experience., Comment: Appeared in Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI) 2022

Several applications, like malicious URL detection and web spam detection, require classification on very high-dimensional data. In such cases anomalous data is hard to find but normal data is easily available. As such it is increasingly common to use a one-class classifier (OCC). Unfortunately, most OCC algorithms cannot scale to datasets with extremely high dimensions. In this paper, we present Fast Random projection-based One-Class Classification (FROCC), an extremely efficient, scalable and easily parallelizable method for one-class classification with provable theoretical guarantees. Our method is based on the simple idea of transforming the training data by projecting it onto a set of random unit vectors that are chosen uniformly and independently from the unit sphere, and bounding the regions based on separation of the data. FROCC can be naturally extended with kernels. We provide a new theoretical framework to prove that that FROCC generalizes well in the sense that it is stable and has low bias for some parameter settings. We then develop a fast scalable approximation of FROCC using vectorization, exploiting data sparsity and parallelism to develop a new implementation called ParDFROCC. ParDFROCC achieves up to 2 percent points better ROC than the next best baseline, with up to 12× speedup in training and test times over a range of state-of-the-art benchmarks for the OCC task.

Instead of measuring the betweenness of a node with respect to an individual source and an individual target node, we consider the case where the source, as well as the target, are two groups of nodes. To concretize this, we present Group-to-group random walk betweenness centrality, which is a generalization of random walk betweenness proposed by Newman (2005). We also show an interesting connection between the Laplacian equations and the hitting times of random walks, which allows us to use Laplacian solvers to compute our metric efficiently. Using our new centrality, we study a setting where a source group of nodes is infected and we wish to vaccinate or quarantine a limited number of uninfected nodes in such a way that the target group of nodes is protected and the infection is controlled. Empirical evaluation on real-world networks establishes that our group-to-group centrality metric is more effective at controlling infection than the natural baseline methods for this problem.

We use queueing networks to present a new approach to solving Laplacian systems. This marks a significant departure from the existing techniques, mostly based on graph-theoretic constructions and sampling. Our distributed solver works for a large and important class of Laplacian systems that we call “one-sink” Laplacian systems. Specifically, our solver can produce solutions for systems of the form $$L\varvec{x} = \varvec{b}$$ where exactly one of the coordinates of $$\varvec{b}$$ is negative. Our solver is a distributed algorithm that takes $${\widetilde{O}}(t_{\text{ hit }}\hat{d}_{\max })$$ time (where $${\widetilde{O}}$$ hides $${\text {poly}}\log n$$ factors) to produce an approximate solution where $$t_{\text{ hit }}$$ is the worst-case hitting time of the random walk on the graph, which is $$\Theta (n)$$ for a large set of important graphs, and $$\hat{d}_{\max }$$ is the maximum degree of the graph. The class of one-sink Laplacians includes the important voltage computation problem and allows us to compute the effective resistance between nodes in a distributed setting. As a result, our Laplacian solver can be used to adapt the approach by Kelner and Mądry (2009) to give the first distributed algorithm to compute approximate random spanning trees efficiently.

The recently proposed paradigm of learned Bloom filters (LBF) seems to offer significant advantages over traditional Bloom filters in terms of low memory footprint and overall performance as evidenced by empirical evaluations over static data. Its behavior in presence of updates to the set of keys being stored in Bloom filters is not very well understood. At the same time, maintaining the false positive rates (FPR) of traditional Bloom filters in presence of dynamics has been studied and extensions to carefully expand memory footprint of the filters without sacrificing FPR have been proposed. Building on these, we propose two distinct approaches for handling data updates encountered in practical uses of LBF: (i) CA-LBF, where we adjust the learned model (e.g., by retraining) to accommodate the new "unseen" data, resulting in classifier adaptive methods, and (ii) IA-LBF, where we replace the traditional Bloom filter with its adaptive version while keeping the learned model unchanged, leading to an index adaptive method. In this paper, we explore these two approaches in detail under incremental workloads, evaluating them in terms of their adaptability, memory footprint and false positive rates. Our empirical results using a variety of datasets and learned models of varying complexity show that our proposed methods' ability to handle incremental updates is quite robust.

In signed networks, each edge is labeled as either positive or negative. The edge sign captures the polarity of a relationship. Balance of signed networks is a well-studied property in graph theory. In a balanced (sub)graph, the vertices can be partitioned into two subsets with negative edges present only across the partitions. Balanced portions of a graph have been shown to increase coherence among its members and lead to better performance. While existing works have focused primarily on finding the largest balanced subgraph inside a graph, we study the network design problem of maximizing balance of a target community (subgraph). In particular, given a budget $b$ and a community of interest within the signed network, we aim to make the community as close to being balanced as possible by deleting up to $b$ edges. Besides establishing NP-hardness, we also show that the problem is non-monotone and non-submodular. To overcome these computational challenges, we propose heuristics based on the spectral relation of balance with the Laplacian spectrum of the network. Since the spectral approach lacks approximation guarantees, we further design a greedy algorithm, and its randomized version, with provable bounds on the approximation quality. The bounds are derived by exploiting pseudo-submodularity of the balance maximization function. Empirical evaluation on eight real-world signed networks establishes that the proposed algorithms are effective, efficient, and scalable to graphs with millions of edges., Comment: To appear as a full paper in WSDM 2021

A fundamental query in labeled graphs is to determine if there exists a path between a given source and target vertices, such that the path satisfies a given label constraint. One of the powerful forms of specifying label constraints is through regular expressions, and the resulting problem of reachability queries under regular simple paths (RSP) form the core of many practical graph query languages such as SPARQL from W3C, Cypher of Neo4J, Oracle's PGQL and LDBC's G-CORE. Despite its importance, since it is known that answering RSP queries is NP-Hard, there are no scalable and practical solutions for answering reachability with full-range of regular expressions as constraints. In this paper, we circumvent this computational bottleneck by designing a random-walk based sampling algorithm called ARRIVAL, which is backed by theoretical guarantees on its expected quality. Extensive experiments on billion-sized real graph datasets with thousands of labels show that ARRIVAL to be 100 times faster than baseline strategies with an average accuracy of 95%.

In taxi ride-sharing, multiple customers are allotted to the same taxi as long as they are compatible, i.e., if none of them suffers a detour beyond a permissible threshold. To attract customers to ride-sharing, taxi operators promise a reduced fare upfront. As a result, if the taxi fails to pair the initial customer with additional compatible passengers, the taxi operator incurs a financial loss. Hence, it is important to ensure that the taxi finds compatible customers once it has picked up the initial customer. In the current scenario, the appearance of subsequent compatible customers is left to luck: a taxi moves along the shortest (or quickest) path for the existing customer and hopes to find additional compatible customers on its way. In this paper, we ask: Is the shortest path the optimal path for ride-sharing? To investigate this question, we develop a route recommendation algorithm called Share, which predicts the route with the highest probability of finding compatible customers, while staying within the detour limits. Through extensive evaluations on real datasets, we show that Share reduces failure rate in ride-sharing by up to 40%, while also improving waiting time for customers by 20%. Technically, the route recommendation problem is NP-hard. We overcome this bottleneck, by reducing the search space of the entire road network into a smaller directed acyclic graph, on which we perform dynamic programming to identify the optimal route. This strategy allows us to answer queries within 0.2 seconds, and thereby making Share deployable on real road conditions.

Efficiently answering reachability queries on a directed graph is a fundamental problem and many solutions - theoretical and practical - have been proposed. A common strategy to make reachability query processing efficient, accurate and scalable is to precompute indexes on the graph. However this often becomes impractical, particularly when dealing with large graphs that are highly dynamic or when queries have additional constraints known only at the time of querying. In the former case, indexes become stale very quickly and keeping them up to date at the same speed as changes to the graph is untenable. For the latter setting, currently proposed indexes are often quite bulky and are highly customized to handle only a small class of constraints. In this paper, we propose a first practical attempt to address these issues by abandoning the traditional indexing approach altogether and operating directly on the graph as it evolves. Our approach, called ARROW, uses random walks to efficiently approximate reachability between vertices, building on ideas that have been prevalent in the theory community but ignored by practitioners. Not only is ARROW well suited for highly dynamic settings - as it is index-free, but it can also be easily adapted to handle many different forms of ad-hoc constraints while being competitive with custom-made index structures. In this paper, we show that ARROW, despite its simplicity, is near-accurate and scales to graphs with tens of millions of vertices and hundreds of millions of edges. We present extensive empirical evidence to illustrate these advantages.

In this work we characterize the session-level behavior of users on an Indian mobile phone comparison shopping website. We also correlate the popularity of handset on various news sources to its popularity on the shopping website. There are three aspects to our study: data analysis, correlation between news sources of product information and popularity of a handset, and behavior prediction. We have used KL divergence to show that a time-homogeneous Markov chain is observed when the number of clicks varies from 5 to 30. Our results depict that Markov chain model does not hold in entirety for comparison shopping setting but tells us how far the Markov chain model holds for this setting. Our analysis corroborates intuition that increasing price leads to decrease in popularity. After the strong correlation between various variables and user behavior was found, we predict the users macro (the overall sales of handset) and micro behavior (whether a user will convert or exit the site) using Markov logic networks. Our predictive model validates the intuition that past browsing behavior is an important predictor for future behavior. Methodology of combining data analysis with machine learning is, in our opinion, a new approach to the empirical study of such data sets.

We present a distributed algorithm for solving Laplacian systems on strongly connected directed graphs, the first that can be analyzed in terms of the underlying graph's parameters. Our distributed solver works for a large and important class of Laplacian systems that we call “one-sink” Laplacian systems, which includes the important electrical flow computation problem. Specifically, given D out as the diagonal out-degree matrix and A → as the adjacency matrix of the directed graph with L = D out − A → , our solver can produce solutions for systems of the form x T L = b T , where exactly one of the coordinates of b is negative. Our solver takes O ˜ ( t hit d max in ) time (where O ˜ hides poly log ⁡ n factors) to produce an approximate solution where t hit is the worst-case hitting time of the random walk on the graph, which is Θ ( n ) for a large set of important graphs and d max in is the maximum in-degree of the graph.

Session E: Networks; International audience; —We study the possibility of creating a fully connected ad-hoc network with bidirectional links between nodes equipped with randomly oriented directional antennas deployed in a circular planar region. The major contribution of our paper is to show that in the directional antenna setting there are always isolated nodes, no matter how high the transmission power of the antennas. We observe, however, that the isolated nodes are confined to a narrow annulus near the boundary of the region. We propose two solutions to achieve full connectivity in the directional setting: T-core that reorients isolated antennas towards the centre of the circular region, and Greedy that simply flips the antenna orientation. We show that the former heuristic, which needs information of the location of the centre of the region, achieves full connectivity with high probability and that, even the latter, which requires no extra information, is able to eliminate most of the isolation.

Popular users tweet slightly earlier than ordinary users during the growth of Twitter eventsPopular users engage with a Twitter event for slightly longer than ordinary usersPopular users write more original tweets than retweets, while the trend is the reverse for ordinary usersTweets by popular users are retweeted more than tweets by ordinary usersPopular users are the quickest to retweet tweetsThe volume of tweeting by popular users is however not different from that of ordinary usersPopular users also do not seem to have an influence on the event growth ratesEventual popularity attained by an event is positively correlated with participation by popular users, but causality is hard to establish Online social networking (OSN) websites such as Twitter and Facebook are known to have a wide heterogeneity in the popularity of their users, which is counted typically in terms of the number of followers or friends of the users. We add to the large body of work on information diffusion on online social networking websites, by studying how the behavior of the small minority of very popular users on Twitter differs from that of the bulk of the population of ordinary users, and how these differences may impact information diffusion. Our findings are somewhat counter intuitive. We find that on aggregate metrics such as the tweeting volume and degree of participation on different topics, popular users and ordinary users seem similar to each other. We also find that although popular users do seem to command an influential position in driving the popularity of topics on Twitter, in practice they do not affect growth rates of user participation and the causality of popular users driving event popularity is hard to establish. Our observations corroborate the findings of other researchers who show that user popularity in terms of number of followers does not translate into driving event popularity, but that event popularity may be driven by extraneous factors to do with the importance of the event.

This paper presents a novel algorithm for joint routing and scheduling in TDM wireless mesh networks. We introduce a new construct, called a "space---time graph," which incorporates the spatial and temporal aspects of routing in one structure by replicating a spatial network connectivity graph in layers along the time dimension. The power of the space---time graph lies in the fact that a path from one node to another in it specifies both a physical route in space as well as a schedule in time for a message. Hence the complicated and intractable problem of routing and scheduling reduces to the relatively simpler problem of determining shortest paths in a graph. Through simulations we show that a simply greedy algorithm on the space---time graph outperforms two state-of-the-art methods in terms of time taken to successfully transmit a set of messages from their sources to their destinations.

Monitoring the formation and evolution of communities in large online social networks such as Twitter is an important problem that has generated considerable interest in both industry and academia. Fundamentally, the problem can be cast as studying evolving sugraphs (each subgraph corresponding to a topical community) on an underlying social graph - with users as nodes and the connection between them as edges. A key metric of interest in this setting is tracking the changes to the conductance of subgraphs induced by edge activations. This metric quantifies how well or poorly connected a subgraph is to the rest of the graph relative to its internal connections. Conductance has been demonstrated to be of great use in many applications, such as identifying bursty topics, tracking the spread of rumors, and so on. However, tracking this simple metric presents a considerable scalability challenge - the underlying social network is large, the number of communities that are active at any moment is large, the rate at which these communities evolve is high, and moreover, we need to track conductance in real-time. We address these challenges in this paper. We propose an in-memory approximation called BloomGraphs to store and update these (possibly overlapping) evolving subgraphs. As the name suggests, we use Bloom filters to represent an approximation of the underlying graph. This representation is compact and computationally efficient to maintain in the presence of updates. This is especially important when we need to simultaneously maintain thousands of evolving subgraphs. BloomGraphs are used in computing and tracking conductance of these subgraphs as edge-activations arrive. BloomGraphs have several desirable properties in the context of this application, including a small memory footprint and efficient updateability. We also demonstrate mathematically that the error incurred in computing conductance is one-sided and that in the case of evolving subgraphs the change in approximate conductance has the same sign as the change in exact conductance in most cases. We validate the effectiveness of BloomGraphs through extensive experimentation on large Twitter graphs and other social networks.

In this paper, we address the problem of sampling from a set and reconstructing a set stored as a Bloom filter. To the best of our knowledge our work is the first to address this question. We introduce a novel hierarchical data structure called BloomSampleTree that helps us design efficient algorithms to extract an almost uniform sample from the set stored in a Bloom filter and also allows us to reconstruct the set efficiently. In the case where the hash functions used in the Bloom filter implementation are partially invertible, in the sense that it is easy to calculate the set of elements that map to a particular hash value, we propose a second, more space-efficient method called HashInvert for the reconstruction. We study the properties of these two methods both analytically as well as experimentally. We provide bounds on run times for both methods and sample quality for the BloomSampleTree based algorithm, and show through an extensive experimental evaluation that our methods are efficient and effective.

In recent times, Question-Answer communities have engaged much user attention and have become a major platform for knowledge sharing and discussion. Stack Exchange (SE) is one such successful community which is a collection of various domain-specific forums, each acting as an independent community in itself. In this paper, we undertake a comparative measurement study across a large number of these domain-specific forums within Stack Exchange. We analyse a number of user activity-based features of each forum and try to cluster different forums based on their similarities on this feature set. For our study, we model Stack Exchange as an Across "Forum Graph" based on inter-forum similarity, and its individual forums as: (a) A user-to-user graph (question asker-answerer) (b) A bipartite graph between questions and answerers, and (c) A bipartite graph between questions and answers. Through these graphs we present a measurement study of Stack Exchange which focuses on the similarities and differences between various forums based on the patterns of user activity on them. The clusters obtained give a high level idea of similar forums based on common users and content. We observe that communities can be classified as "discussion-based" and "fact-based" and further we classify forums on the basis of question answering patterns.

We study the problem of intruder tracking with non-stealthy sensors, i.e., sensors whose ON/OFF state can be detected by an intruder, sometimes in advance. The sensor field is assumed to be operating with a sleep schedule to conserve energy. Both motion sensors and presence sensors are considered. We provide a rigorous basis for the study of this scenario by defining a new intruder model, the Ideal Intruder, that knows the entire sleep schedule of all the sensors in the field. More realistic intruders that have spatially and temporally limited knowledge of the sensor states are also defined. We study the well-known Random Independent Sleep RIS scheduling scheme with a single parameter p, giving mathematical bounds for the ideal intruder's crossing time in the motion sensor case and showing that the crossing probability in the presence sensor case undergoes a sharp transition as p increases. Further, we show that non-ideal intruders perform almost as well as the ideal intruder against RIS. Motivated by this finding and by the comparison between Barrier Coverage and RIS, we define a new sleep scheduling scheme, Spotlight, that is more robust to faults than Barrier Coverage and more effective than RIS. But more than that, Spotlight is shown to be specifically suited to the non-stealthy case because a non-ideal intruder, that is, one with limited information performs significantly worse against it than the ideal intruder. Spotlight, therefore, apart from being a novel and interesting sleep scheduling scheme in its own right, also illustrates the power of the analytical framework we introduce in this paper. Copyright © 2013 John Wiley & Sons, Ltd.

We study an open discrete-time queueing network that models the collection of data in a multi-hop sensor network. We assume data is generated at the sensor nodes as a discrete-time Bernoulli process. All nodes in the network maintain a queue and relay data, which is to be finally collected by a designated sink. We prove that the resulting multi-dimensional Markov chain representing the queue size of nodes has two behavior regimes depending on the value of the rate of data generation. In particular, we show that there is a non-trivial critical value of data rate below which the chain is ergodic and converges to a stationary distribution and above which it is non-ergodic, i.e., the queues at the nodes grow in an unbounded manner. We show that the rate of convergence to stationarity is geometric in the sub-critical regime. We also show the connections of this process to a class of Laplacian systems of equations whose solutions include the important problem of finding the effective resistance between two nodes, a subroutine that has been widely used to develop efficient algorithms for a number of computational problems. Hence our work provides the theoretical basis for a new class of distributed algorithms for these problems.

Rumor is a potentially harmful social phenomenon that has been observed in all human societies in all times. Social networking sites provide a platform for the rapid interchange of information and hence, for the rapid dissemination of unsubstantiated claims that are potentially harmful. In this paper, we study different methods for combating rumors in social networks actuated by the realization that authoritarian methods for fighting rumor have largely failed. Our major insight is that in situations where populations do not answer to the same authority, it is the trust that individuals place in their friends that must be leveraged to fight rumor. In other words, rumor is best combated by something which acts like itself, a message which spreads from one individual to another. We call such messages anti-rumors. We study three natural anti-rumor processes to counter the rumor and present mean field equations that characterize the system. Several metrics are proposed to capture the properties of rumor and anti-rumor processes. The metrics are geared to capture temporal evolution as well as global properties of the processes. We evaluate our methods by simulating rumor and anti-rumor processes on a large data set of around 10^5 nodes derived from the social networking site Twitter and on a synthetic network of the same size generated according to the Barab\'asi-Albert model.

In this paper we consider the $k$ edge-disjoint paths problem ($k$-EDP), a generalization of the well-known edge-disjoint paths problem. Given a graph $G=(V,E)$ and a set of terminal pairs (or requests) $T$, the problem is to find a maximum subset of the pairs in $T$ for which it is possible to select paths such that each pair is connected by $k$ edge-disjoint paths and the paths for different pairs are mutually disjoint. To the best of our knowledge, no nontrivial result is known for this problem for $k>1$. To measure the performance of our algorithms we use the recently introduced flow number $F$ of a graph. This parameter is known to fulfill $F=O(\Delta \alpha^{-1} \log n)$, where $\Delta$ is the maximum degree, $\alpha$ is the edge expansion of $G$, and $n$ is the number of vertices in $G$. We show that a simple greedy online algorithm achieves a competitive ratio of $O(k^3 F)$ which naturally extends the best known bound of $O(F)$ for $k=1$ to higher $k$. To achieve this competitive ratio, we introduce a new method of converting a system of $k$ disjoint paths into a system of $k$ length-bounded disjoint paths. We also show that any deterministic online algorithm has a competitive ratio of $\Omega(k F)$. In addition, we study the $k$ disjoint flows problem ($k$-DFP), which is a generalization of the previously studied unsplittable flow problem. The difference between the $k$-DFP and the $k$-EDP is that now we consider a graph with edge capacities and our requests are allowed to have arbitrary demands $d_i$. The aim is to find a subset of requests of maximum total demand for which it is possible to select flow paths such that all the capacity constraints are maintained and each selected request with demand $d_i$ is connected by $k$ disjoint paths, each of flow value $d_i/k$. The $k$-EDP and $k$-DFP problems have important applications in fault-tolerant (virtual) circuit switching, which plays a key role in optical networks.

Many database applications that need to disseminate dynamic information from a server to various clients can suffer from heavy communication costs. Data caching at a client can help mitigate these costs, particularly when individual PUSH-PULL decisions are made for the different semantic regions in the data space. The server is responsible for notifying the client about updates in the PUSH regions. The client needs to contact the server for queries that ask for data in the PULL regions. We call the idea of partitioning the data space into PUSH-PULL regions to minimize communication cost data gerrymandering. In this paper, we present solutions to technical challenges in adopting this simple but powerful idea. We give a provably optimal-cost dynamic programming algorithm for gerrymandering on a single query attribute. We propose a family of efficient heuristics for gerrymandering on multiple query attributes. We handle the dynamic case in which the workloads of queries and updates evolve over time. We validate our methods through extensive experiments on real and synthetic data sets

We consider a special subgraph of a weighted directed graph: one comprising only the k heaviest edges incoming to each vertex. We show that the maximum weight branching in this subgraph closely approximates the maximum weight branching in the original graph. Specifically, it is within a factor of k/(k + 1). Our interest in finding branchings in this subgraph is motivated by a data compression application in which calculating edge weights is expensive but estimating which are the heaviest k incoming edges is easy. An additional benefit is that since algorithms for finding branchings run in time linear in the number of edges our results imply faster algorithms although we sacrifice optimality by a small factor. We also extend our results to the case of edge-disjoint branchings of maximum weight and to maximum weight spanning forests.

P2P systems are highly vulnerable to pollution attacks in which attackers inject multiple versions of corrupted content into the system, which is then further proliferated by unsuspecting users. However, to our knowledge, there are no closed-form solutions that describe this phenomenon, nor are there models that describe how the injection of multiple versions of corrupted content impacts a clients' ability to receive a valid copy. In this paper we develop a suite of fluid models that model pollution proliferation in P2P systems. These fluid models lead to systems of non-linear differential equations. We obtain closed-form solutions for the differential equations; for the remaining models, we efficiently solve the differential equations numerically. The models capture a variety of user behaviors, including propensity for popular versions, abandonment after repeated failure to obtain a good version, freeloading, and local version blacklisting. Our analysis reveals intelligent strategies for attackers as well as strategies for clients seeking to recover non-polluted content within large-scale P2P networks.

In the minimum path coloring problem, we are given a graph and a set of pairs of vertices of the graph and we are asked to connect the pairs by colored paths in such a way that paths of the same color are edge disjoint. In this paper we deal with a generalization of this problem where we are asked to connect each pair by k edge disjoint paths of the same color. The objective is to minimize the number of colors. The reason for multiple paths between the same pair of vertices is to ensure fault tolerance of the connections. We propose an O(k2F)=O(k2Δα-1logn) approximation algorithm for this problem where F is the flow number of the graph, Δ is the maximum degree and α is the expansion. This is an improvement even for the special case k=1 where, to our knowledge, the best previously known bound is weaker by a factor of logn.The underlying problem is that of finding several disjoint paths between a given pair of vertices. Menger's theorem provides a necessary and sufficient condition for the existence of k such paths. However, it does not say anything about the length of the paths although in communication problems the number of links used is an issue. We show that any two k-connected vertices are connected by k edge disjoint paths of average length O(kF) which improves an earlier result of Galil and Yu (Proceedings of the 27th Annual ACM Symposium on Theory of Computing, 1995) for several classes of graphs. In fact, this is only a corollary of a stronger result for multicommodity flow on networks with unit edge capacities: any multicommodity flow with k units for each commodity can be rerouted such that the flow for each commodity is shipped through k-tuples of edge disjoint paths of average length O(kF) without exceeding the edge capacities significantly.

We design a variation of skip lists that performs well for generally biased access sequences. Given n items, each with a positive weight wi, 1 ≤ i ≤ n, the time to access item i is O(1 + log (W/wi)), where W=∑i=1 nwi; the data structure is dynamic. We present two instantiations of biased skip lists, one of which achieves this bound in the worst case, the other in the expected case. The structures are nearly identical; the deterministic one simply ensures the balance condition that the randomized one achieves probabilistically. We use the same method to analyze both.

We study mesh networks formed by nodes equipped with directional antennas in a high node-density setting. To do so we create a random geometric graph with n nodes placed uniformly at random. The antenna at each node chooses a direction of orientation at random and edges are placed between pairs of nodes based on their distance from each other and their directions of orientation according to the gain function of the antennas. To model the directionality of the antennas we consider a realistic gain function where the signal fades away from the direction of orientation. We also consider an idealised function that concentrates the gain uniformly in a sector of angle $$2\theta $$ centred around the direction of orientation. In this setting we show theoretically that with probability tending to 1 the optimal power required for achieving connectivity is significantly lower than that needed for connectivity in an omnidirectional setting. We capture mathematically the relationship between this optimal power level and the maximum gain of the antenna, showing that as the directionality of the antenna increases the power needed for connectivity decreases. However this optimal power level is also inversely proportional to the probability of connectivity of two randomly placed nodes, which decreases as directionality increases. We validate these results through simulation.

In this paper, we present overview of our approach for clustering tweets. Due to short text of tweets, traditional text clustering mechanisms alone may not produce optimal results. We believe that there is an underlying theme/topic present in majority of tweets which is evident in growing usage of hashtag feature in the Twitter network. Clustering tweets based on these themes seems a more natural way for grouping. We propose to use Wikipedia topic taxonomy to discover the themes from the tweets and use the themes along with traditional word based similarity metric for clustering. We show some of our initial results to demonstrate the effectiveness of our approach.

In this work we study the behavior of users on online comparison shopping using session traces collected over one year from an Indian mobile phone comparison website: http://smartprix.com. There are two aspects to our study: data analysis and behavior prediction. The first aspect of our study, data analysis, is geared towards providing insights into user behavior that could enable vendors to offer the right kinds of products and prices, and that could help the comparison shopping engine to customize the search based on user preferences. We discover the correlation between the search queries which users write before coming on the site and their future behavior on the same. We have also studied the distribution of users based on geographic location, time of the day, day of the week, number of sessions which have a click to buy (convert), repeat users, phones/brands visited and compared. We analyze the impact of price change on the popularity of a product and how special events such as launch of a new model affect the popularity of a brand. Our analysis corroborates intuitions such as increasing price leads to decrease in popularity and vice-versa. Further, we characterize the time lag in the effect of such phenomena on popularity. We characterize the user behavior on the website in terms of sequence of transitions between multiple states (defined in terms of the kind of page being visited e.g. home, visit, compare etc.). We use KL divergence to show that a time-homogeneous Markov chain is the right model for session traces when the number of clicks varies from 5 to 30. Finally, we build a model using Markov logic that uses the history of the user's activity in a session to predict whether a user is going to click to convert in that session. Our methodology of combining data analysis with machine learning is, in our opinion, a new approach to the empirical study of such data sets.

In this paper a complex network model is used to analyze the game of cricket. The nodes of this network are individual players and edges are placed between players who have scored runs in partnership. Results of these complex network models based on partnership are compared with performance of teams. Our study examines Test cricket, One Day Internationals (ODIs) and T20 cricket matches of the Indian Premier League (IPL). We find that complex network properties: average degree, average strength and average clustering coefficient are directly related to the performance (win over loss ratio) of the teams, i.e., teams having higher connectivity and well-interconnected groups perform better in Test matches but not in ODIs and IPL. For our purpose, the basic difference between different forms of the game is duration of the game: Test cricket is played for 5-days, One day cricket is played only for a single day and T20 is played only for 20 overs in an inning. In this regard, we make a clear distinction in social network properties between the Test, One day, and T20 cricket networks by finding relationships between average weight with their end point's degrees. We know that performance of teams varies with time - for example West Indies, who had established themselves as the best team during 1970s now is one of the worst teams in terms of results. So we have looked at evolution of team's performances with respect to their network properties for every decade. We have observed that, the average degree and average clustering coefficient follow similar trends as the performance of the team in Test cricket but not in One day cricket and T20. So partnership actually plays a more significant role in team performance in Test cricket as compared to One day cricket and T20 cricket.

We investigate the temporal aspects of user behavior in this paper and relate it to the evolution of particular topics being discussed on the Twitter OSN. Studies have shown that a small number of frequent users are responsible for the maximum percentage of tweets. We further hypothesize that users deviate from their usual tweeting hours when a major event occurs. With these as our underlying concepts, we introduce a new metric called "tweet strength" that gives more weight to tweets by users who in general tweet less or those who do not usually tweet at a given time. We study the evolution of a set of topics through the lens of tweet strength and try to identify the classes of users driving the popularity at different times. We also study word-of-mouth diffusion mechanism through the network by defining a "copying" behavior. When a follower of a user tweets on the same topic as the user, the follower is said to have copied. We further make the definition time-dependent by imposing temporal thresholds on it.

Providing the history and context(s) of a news article that emerges in the middle of an evolving news story--sometimes multiple news stories--is a complex task. The complexity of the task is compounded by the fact that different users are interested in different contexts of the article, and it is impossible to guess what a particular user is most interested in. In this paper, we introduce ESTHETE, a system that provides rich context(s) (through what we call personalized flexible context extraction), by preprocessing and storing articles in a structured representation (directed graphs) that makes it easy for the user to explore different contexts. The advantage of this approach is that the incremental computational expense in incorporating new articles as they are published is minimal. Our system is available at: http://konfrap.com/esthete.

We present the first comprehensive characterization of the diffusion of ideas on Twitter, studying more than 5.96 million topics that include both popular and less popular topics. On a data set containing approximately 10 million users and a comprehensive scraping of 196 million tweets, we perform a rigorous temporal and spatial analysis, investigating the time-evolving properties of the subgraphs formed by the users discussing each topic. We focus on two different notions of the spatial: the network topology formed by follower-following links on Twitter, and the geospatial location of the users. We investigate the effect of initiators on the popularity of topics and find that users with a high number of followers have a strong impact on topic popularity. We deduce that topics become popular when disjoint clusters of users discussing them begin to merge and form one giant component that grows to cover a significant fraction of the network. Our geospatial analysis shows that highly popular topics are those that cross regional boundaries aggressively.

A large contributor to the growing Internet traffic is user generated content shared via online social networking websites. Our insight is that these websites can reveal valuable information that can be used in content delivery networks for better caching and pre-fetching performance. In this paper, we combine five different datasets from Twitter and other sources, and make several observations that can lead to helpful heuristics for better content placement. In particular, we study the temporal growth and decay, the geographical spread, and the social spread, of topics on the social network. We also describe in detail our methodologies for data collection, that can be useful for other researchers working in this space as well. In the future, we will use these observations to design heuristics for improved CDN performance.

We introduce hierarchical neighbor graphs, a new topology control mechanism for wireless sensor networks. This mechanism is a randomized one that takes a single parameter, 0 < p < 1, and uses it to build a structure that is fully distributed in the sense that it requires only local knowledge at each node to be formed and repaired, and moreover requires minimal computation in this process. Hierarchical neighbor graphs naturally account for differences in the battery power of nodes and are able to use energy efficiently by reorganizing dynamically when the battery power of heavily utilized nodes decreases, without any global coordination or communication. In this paper we study the lifetime and delay of hierarchical neighbor graphs, giving analytical characterizations of both. We present the results of extensive simulations that demonstrate how the lifetime and delay vary with various network parameters and the parameter p, also studying the effects of application-specific data aggregation policies. Through this simulation study we compare hierarchical neighbor graphs against other leading proposals for data collection in wireless sensor networks and demonstrate that in general our structure provides better lifetime values, and, importantly, is able to deal with heterogeneous distributions of initial battery power much better than previous proposals.

In this paper we study and evaluate rumor-like methods for combating the spread of rumors on a social network. We model rumor spread as a diffusion process on a network and suggest the use of an "anti-rumor" process similar to the rumor process. We study two natural models by which these anti-rumors may arise. The main metrics we study are the belief time, i.e., the duration for which a person believes the rumor to be true and point of decline, i.e., point after which anti-rumor process dominates the rumor process. We evaluate our methods by simulating rumor spread and anti-rumor spread on a data set derived from the social networking site Twitter and on a synthetic network generated according to the Watts and Strogatz model. We find that the lifetime of a rumor increases if the delay in detecting it increases, and the relationship is at least linear. Further our findings show that coupling the detection and anti-rumor strategy by embedding agents in the network, we call them beacons, is an effective means of fighting the spread of rumor, even if these beacons do not share information.

In this paper we introduce a new randomized method for constructing a bounded degree connected structure on points in Euclidean space: p-hierarchical neighbor graphs. The structure has a flavor of hierarchical clustering and requires only local knowledge and minimal computation at each node to be formed and repaired. Hence it is a suitable interconnection model for an ad hoc wireless network. Our structure has expected constant degree, diameter logarithmic in the size of the set and good spanner-like properties in a probabilistic sense.

We argue that relationships between Web pages are functions of the user's intent. We identify a class of Web tasks - information-gathering - that can be facilitated by a search engine that provides links to pages which are related to the page the user is currently viewing. We define three kinds of intentional relationships that correspond to whether the user is a) seeking sources of information, b) reading pages which provide information, or c) surfing through pages as part of an extended information-gathering process. We show that these three relationships can be productively mined using a combination of textual and link information and provide three scoring mechanisms that correspond to them: {\em SeekRel}, {\em FactRel} and {\em SurfRel}. These scoring mechanisms incorporate both textual and link information. We build a set of capacitated subnetworks - each corresponding to a particular keyword - that mirror the interconnection structure of the World Wide Web. The scores are computed by computing flows on these subnetworks. The capacities of the links are derived from the {\em hub} and {\em authority} values of the nodes they connect, following the work of Kleinberg (1998) on assigning authority to pages in hyperlinked environments. We evaluated our scoring mechanism by running experiments on four data sets taken from the Web. We present user evaluations of the relevance of the top results returned by our scoring mechanisms and compare those to the top results returned by Google's Similar Pages feature, and the {\em Companion} algorithm proposed by Dean and Henzinger (1999)., In Proceedings of ACM Hypertext 2009

In this paper, we present a general framework to quantify changes in temporally evolving data. We focus on changes that materialize due to evolution and interactions of features extracted from the data. The changes are captured by the following key transformations: create, merge, split, continue, and cease. First, we identify various factors which influence the importance of each transformation. These factors are then combined using a weight vector. The weight vector encapsulates domain knowledge. We evaluate our algorithm using the following datasets: DBLP, IMDB, Text and Scientific Dataset.

We study the graph NN(d,k) constructed on a Poisson point process in d dimensions by connecting each point to the k points nearest to it. We show that if k geq 188, NN(2,k) has an infinite connected component and this infinite component has an infinite subset of points with the property that the distance along the edges of the graphs between any pair of these points is at most a constant factor larger than their Euclidean distance. Finally we discuss the relevance of our results to the study of wireless sensor networks.