Over the past decade, Determinantal Point Processes (DPPs) have proven to be a mathematically elegant framework for modeling diversity. Given a set of items N, DPPs define a probability distribution over subsets of N, with sets of larger diversity having greater probability. Recently, DPPs have achieved success in the domain of recommendation systems, as a method to enforce diversity of recommendations in addition to relevance. In large-scale recommendation applications however, the input typically comes in the form of a stream too large to fit into main memory. However, the natural greedy algorithm for DPP-based recommendations is memory intensive, and cannot be used in a streaming setting.

The Adwords and Online Bipartite Matching problems have enjoyed a renewed attention over the past decade due to their connection to Internet advertising. Our community has contributed, among other things, new models (notably stochastic) and extensions to the classical formulations to address the issues that arise from practical needs. In this paper, we propose a new generalization based on matroids and show that many of the previous results extend to this more general setting. Because of the rich structures and expressive power of matroids, our new setting is potentially of interest both in theory and in practice.

We define a general framework for a large class of combinatorial multi-armed bandit (CMAB) problems, where subsets of base arms with unknown distributions form super arms. In each round, a super arm is played and the base arms contained in the super arm are played and their outcomes are observed. We further consider the extension in which more base arms could be probabilistically triggered based on the outcomes of already triggered arms. The reward of the super arm depends on the outcomes of all played arms, and it only needs to satisfy two mild assumptions, which allow a large class of nonlinear reward instances. We assume the availability of an offline $(\alpha,\beta)$-approximation oracle that takes the means of the outcome distributions of arms and outputs a super arm that with probability $\beta$ generates an $\alpha$ fraction of the optimal expected reward. The objective of an online learning algorithm for CMAB is to minimize $(\alpha,\beta)$-approximation regret, which is the difference in total expected reward between the $\alpha\beta$ fraction of expected reward when always playing the optimal super arm, and the expected reward of playing super arms according to the algorithm. We provide CUCB algorithm that achieves $O(\log n)$ distribution-dependent regret, where $n$ is the number of rounds played, and we further provide distribution-independent bounds for a large class of reward functions. Our regret analysis is tight in that it matches the bound of UCB1 algorithm (up to a constant factor) for the classical MAB problem, and it significantly improves the regret bound in an earlier paper on combinatorial bandits with linear rewards. We apply our CMAB framework to two new applications, probabilistic maximum coverage (PMC) for online advertising and social influence maximization for viral marketing, both having nonlinear reward structures. In particular, application to social influence maximization requires our extension on probabilistically triggered arms.

A topic propagating in a social network reaches its tipping point if the number of users discussing it in the network exceeds a critical threshold such that a wide cascade on the topic is likely to occur. In this paper, we consider the task of selecting initial seed users of a topic with minimum size so that {\em with a guaranteed probability} the number of users discussing the topic would reach a given threshold. We formulate the task as an optimization problem called {\em seed minimization with probabilistic coverage guarantee (SM-PCG)}. This problem departs from the previous studies on social influence maximization or seed minimization because it considers influence coverage with {\em probabilistic} guarantees instead of guarantees on {\em expected} influence coverage. We show that the problem is not submodular, and thus is harder than previously studied problems based on submodular function optimization. We provide an approximation algorithm and show that it approximates the optimal solution with both a multiplicative ratio and an additive error. The multiplicative ratio is tight while the additive error would be small if influence coverage distributions of certain seed sets are well concentrated. For one-way bipartite graphs we analytically prove the concentration condition and obtain an approximation algorithm with an $O(\log n)$ multiplicative ratio and an $O(\sqrt{n})$ additive error, where $n$ is the total number of nodes in the social graph. Moreover, we empirically verify the concentration condition in real-world networks and experimentally demonstrate the effectiveness of our proposed algorithm comparing to commonly adopted benchmark algorithms.

The problem of identifying rumors is of practical importance especially in online social networks, since information can diffuse more rapidly and widely than the offline counterpart. In this paper, we identify characteristics of rumors by examining the following three aspects of diffusion: temporal, structural, and linguistic. For the temporal characteristics, we propose a new periodic time series model that considers daily and external shock cycles, where the model demonstrates that rumor likely have fluctuations over time. We also identify key structural and linguistic differences in the spread of rumors and non-rumors. Our selected features classify rumors with high precision and recall in the range of 87% to 92%, that is higher than other states of the arts on rumor classification.

We define a general framework for a large class of combinatorial multi-armed bandit (CMAB) problems, where simple arms with unknown istributions form \em super arms. In each round, a super arm is played and the outcomes of its related simple arms are observed, which helps the selection of super arms in future rounds. The reward of the super arm depends on the outcomes of played arms, and it only needs to satisfy two mild assumptions, which allow a large class of nonlinear reward instances. We assume the availability of an (α,β)-approximation oracle that takes the means of the distributions of arms and outputs a super arm that with probability βgenerates an αfraction of the optimal expected reward. The objective of a CMAB algorithm is to minimize \em (α,β)-approximation regret, which is the difference in total expected reward between the αβfraction of expected reward when always playing the optimal super arm, and the expected reward of playing super arms according to the algorithm. We provide CUCB algorithm that achieves O(\log n) regret, where n is the number of rounds played, and we further provide distribution-independent bounds for a large class of reward functions. Our regret analysis is tight in that it matches the bound for classical MAB problem up to a constant factor, and it significantly improves the regret bound in a recent paper on combinatorial bandits with linear rewards. We apply our CMAB framework to two new applications, probabilistic maximum coverage (PMC) for online advertising and social influence maximization for viral marketing, both having nonlinear reward structures.

In this paper, we study incentive mechanisms for retrieving information from networked agents. Following the model in [Kleinberg and Raghavan 2005], the agents are represented as nodes in an infinite tree, which is generated by a random branching process. A query is issued by the root, and each node possesses an answer with an independent probability p=1/n. Further, each node in the tree acts strategically to maximize its own payoff. In order to encourage the agents to participate in the information acquisition process, an incentive mechanism is needed to reward agents who provide the information as well as agents who help to facilitate such acquisition.

We study the matroid secretary problems with submodular valuation functions. In these problems, the elements arrive in random order. When one element arrives, we have to make an immediate and irrevocable decision on whether to accept it or not. The set of accepted elements must form an independent set in a predefined matroid. Our objective is to maximize the value of the accepted elements. In this paper, we focus on the case that the valuation function is a non-negative and monotonically non-decreasing submodular function. We introduce a general algorithm for such submodular matroid secretary problems. In particular, we obtain constant competitive algorithms for the cases of laminar matroids and transversal matroids. Our algorithms can be further applied to any independent set system defined by the intersection of a constant number of laminar matroids, while still achieving constant competitive ratios. Notice that laminar matroids generalize uniform matroids and partition matroids. On the other hand, when the underlying valuation function is linear, our algorithm achieves a competitive ratio of 9.6 for laminar matroids, which significantly improves the previous result.

Influence diffusion and influence maximization in large-scale online social networks (OSNs) have been extensively studied because of their impacts on enabling effective online viral marketing. Existing studies focus on social networks with only friendship relations, whereas the foe or enemy relations that commonly exist in many OSNs, e.g., Epinions and Slashdot, are completely ignored. In this paper, we make the first attempt to investigate the influence diffusion and influence maximization in OSNs with both friend and foe relations, which are modeled using positive and negative edges on signed networks. In particular, we extend the classic voter model to signed networks and analyze the dynamics of influence diffusion of two opposite opinions. We first provide systematic characterization of both short-term and long-term dynamics of influence diffusion in this model, and illustrate that the steady state behaviors of the dynamics depend on three types of graph structures, which we refer to as balanced graphs, anti-balanced graphs, and strictly unbalanced graphs. We then apply our results to solve the influence maximization problem and develop efficient algorithms to select initial seeds of one opinion that maximize either its short-term influence coverage or long-term steady state influence coverage. Extensive simulation results on both synthetic and real-world networks, such as Epinions and Slashdot, confirm our theoretical analysis on influence diffusion dynamics, and demonstrate that our influence maximization algorithms perform consistently better than other heuristic algorithms.

We study a natural information dissemination problem for multiple mobile agents in a bounded Euclidean space.Agents are placed uniformly at random in the d-dimensional space {-n, ..., n} d at time zero, and one of the agents holds a piece of information to be disseminated.All the agents then perform independent random walks over the space, and the information is transmitted from one agent to another if the two agents are sufficiently close.We wish to bound the total time before all agents receive the information (with high probability).Our work extends Pettarin et al's work [10], which solved the problem for d ≤ 2. We present tight bounds up to polylogarithmic factors for the case d = 3. (While our results extend to higher dimensions, for space and readability considerations we provide only the case d = 3 here.)Our results show the behavior when d ≥ 3 is qualitatively different from the case d ≤ 2. In particular, as the ratio between the volume of the space and the number of agents varies, we show an interesting phase transition for three dimensions that does not occur in one or two dimensions.

Compact routing addresses the tradeoff between table sizes and stretch, which is the worst-case ratio between the length of the path a packet is routed through by the scheme and the length of an actual shortest path from source to destination. We adapt the compact routing scheme by Thorup and Zwick [2001] to optimize it for power-law graphs. We analyze our adapted routing scheme based on the theory of unweighted random power-law graphs with fixed expected degree sequence by Aiello et al. [2000]. Our result is the first analytical bound coupled to the parameter of the power-law graph model for a compact routing scheme. Let n denote the number of nodes in the network. We provide a labeled routing scheme that, after a stretch--5 handshaking step (similar to DNS lookup in TCP/IP), routes messages along stretch--3 paths. We prove that, instead of routing tables with Õ ( n 1/2 ) bits ( Õ suppresses factors logarithmic in n ) as in the general scheme by Thorup and Zwick, expected sizes of O ( n γ log n ) bits are sufficient, and that all the routing tables can be constructed at once in expected time O ( n 1+γ log n ), with γ = τ-22/τ-3 + ε, where τ∈(2,3) is the power-law exponent and ε 0 (which implies ε < γ < 1/3 + ε). Both bounds also hold with probability at least 1-1/ n (independent of ε). The routing scheme is a labeled scheme, requiring a stretch--5 handshaking step. The scheme uses addresses and message headers with O (log n log log n ) bits, with probability at least 1- o (1). We further demonstrate the effectiveness of our scheme by simulations on real-world graphs as well as synthetic power-law graphs. With the same techniques as for the compact routing scheme, we also adapt the approximate distance oracle by Thorup and Zwick [2001, 2005] for stretch-3 and we obtain a new upper bound of expected Õ ( n 1+γ ) for space and preprocessing for random power-law graphs. Our distance oracle is the first one optimized for power-law graphs. Furthermore, we provide a linear-space data structure that can answer 5--approximate distance queries in time at most Õ ( n 1/4+ε ) (similar to γ, the exponent actually depends on τ and lies between ε and 1/4 + ε).

Influence maximization, defined by Kempe, Kleinberg, and Tardos (2003), is the problem of finding a small set of seed nodes in a social network that maximizes the spread of influence under certain influence cascade models. In this paper, we propose an extension to the independent cascade model that incorporates the emergence and propagation of negative opinions. The new model has an explicit parameter called quality factor to model the natural behavior of people turning negative to a product due to product defects. Our model incorporates negativity bias (negative opinions usually dominate over positive opinions) commonly acknowledged in the social psychology literature. The model maintains some nice properties such as submodularity, which allows a greedy approximation algorithm for maximizing positive influence within a ratio of 1 – 1/e. We define a quality sensitivity ratio (qs-ratio) of influence graphs and show a tight bound of on the qs-ratio, where n is the number of nodes in the network and k is the number of seeds selected, which indicates that seed selection is sensitive to the quality factor for general graphs. We design an efficient algorithm to compute influence in tree structures, which is nontrivial due to the negativity bias in the model. We use this algorithm as the core to build a heuristic algorithm for influence maximization for general graphs. Through simulations, we show that our heuristic algorithm has matching influence with a standard greedy approximation algorithm while being orders of magnitude faster.

Processing the gathered information efficiently is a key functionality for wireless sensor networks. In this paper, we study the time complexity, message complexity (number of messages used by all nodes), and energy cost complexity (total energy used by all nodes for transmitting messages) of some tasks, such as data collection (collecting raw data of all nodes to a sink), data aggregation (computing the aggregated value of data of all nodes), and queries for a multihop wireless sensor network of n nodes. We first present a lower bound on the complexity for the optimal methods, and then, for most of the tasks studied in this paper, we provide an (asymptotically matching) upper bound on the complexity by presenting efficient distributed algorithms to solve these problems.

Influence maximization, defined by Kempe, Kleinberg, and Tardos (2003), is the problem of finding a small set of seed nodes in a social network that maximizes the spread of influence under certain influence cascade models. The scalability of influence maximization is a key factor for enabling prevalent viral marketing in large-scale online social networks. Prior solutions, such as the greedy algorithm of Kempe et al. (2003) and its improvements are slow and not scalable, while other heuristic algorithms do not provide consistently good performance on influence spreads. In this paper, we design a new heuristic algorithm that is easily scalable to millions of nodes and edges in our experiments. Our algorithm has a simple tunable parameter for users to control the balance between the running time and the influence spread of the algorithm. Our results from extensive simulations on several real-world and synthetic networks demonstrate that our algorithm is currently the best scalable solution to the influence maximization problem: (a) our algorithm scales beyond million-sized graphs where the greedy algorithm becomes infeasible, and (b) in all size ranges, our algorithm performs consistently well in influence spread --- it is always among the best algorithms, and in most cases it significantly outperforms all other scalable heuristics to as much as 100%--260% increase in influence spread.

We consider the problem of locating facilities in a metric space to serve a set of selfish agents. The cost of an agent is the distance between her own location and the nearest facility. The social cost is the total cost of the agents. We are interested in designing strategy-proof mechanisms without payment that have a small approximation ratio for social cost. A mechanism is a (possibly randomized) algorithm which maps the locations reported by the agents to the locations of the facilities. A mechanism is strategy-proof if no agent can benefit from misreporting her location in any configuration.

We present a data structure for answering approximate shortest path queries in a planar subdivision from a fixed source. Let $\rho\geqslant1$ be a real number. Distances in each face of this subdivision are measured by a possibly asymmetric convex distance function whose unit disk is contained in a concentric unit Euclidean disk and contains a concentric Euclidean disk with radius $1/\rho$. Different convex distance functions may be used for different faces, and obstacles are allowed. Let $\varepsilon$ be any number strictly between 0 and 1. Our data structure returns a $(1+\varepsilon)$ approximation of the shortest path cost from the fixed source to a query destination in $O(\log\frac{\rho n}{\varepsilon})$ time. Afterwards, a $(1+\varepsilon)$-approximate shortest path can be reported in $O(\log n)$ time plus the complexity of the path. The data structure uses $O(\frac{\rho^2n^3}{\varepsilon^2}\log\frac{\rho n}{\varepsilon})$ space and can be built in $O(\frac{\rho^2n^3}{\varepsilon^2}(\log\frac{\rho n}{\varepsilon})^2)$ time. Our time and space bounds do not depend on any other parameter; in particular, they do not depend on any geometric parameter of the subdivision such as the minimum angle.

Influence maximization is the problem of finding a small subset of nodes (seed nodes) in a social network that could maximize the spread of influence. In this paper, we study the efficient influence maximization from two complementary directions. One is to improve the original greedy algorithm of [5] and its improvement [7] to further reduce its running time, and the second is to propose new degree discount heuristics that improves influence spread. We evaluate our algorithms by experiments on two large academic collaboration graphs obtained from the online archival database arXiv.org. Our experimental results show that (a) our improved greedy algorithm achieves better running time comparing with the improvement of [7] with matching influence spread, (b) our degree discount heuristics achieve much better influence spread than classic degree and centrality-based heuristics, and when tuned for a specific influence cascade model, it achieves almost matching influence thread with the greedy algorithm, and more importantly (c) the degree discount heuristics run only in milliseconds while even the improved greedy algorithms run in hours in our experiment graphs with a few tens of thousands of nodes.

Our goal is to find an approximate shortest path for a point robot moving in a planar subdivision with n vertices. Let $\rho\geq 1$ be a real number. Distances in each face of this subdivision are measured by a convex distance function whose unit disk is contained in a concentric unit Euclidean disk and contains a concentric Euclidean disk with radius $1/\rho$. Different convex distance functions may be used for different faces, and obstacles are allowed. These convex distance functions may be asymmetric. For any $\varepsilon\in(0,1)$ and for any two points $v_s$ and $v_d$, we give an algorithm that finds a path from $v_s$ to $v_d$ whose cost is at most $(1+\varepsilon)$ times the optimal. Our algorithm runs in $O(\frac{\rho^2\log \rho}{\varepsilon^2}n^3 \log(\frac{\rho n}\varepsilon))$ time. This bound does not depend on any other parameters; in particular it does not depend on the minimum angle in the subdivision. We give applications to two special cases that have been considered before: the weighted region problem and motion planning in the presence of uniform flows. For the weighted region problem with weights in $[1,\rho]\cup \{\infty\}$, the time bound of our algorithm improves to $O(\frac{\rho\log \rho}{\varepsilon}n^3 \log(\frac{\rho n}\varepsilon))$.

We present a data structure for answering approximate shortest path queries ina planar subdivision from a fixed source. Let ρ ≥ 1 be a real number.Distances in each face of this subdivision are measured by a possiblyasymmetric convex distance function whose unit disk is contained in aconcentric unit Euclidean disk, and contains a concentric Euclidean disk withradius 1/ρ. Different convex distance functions may be used for differentfaces, and obstacles are allowed. Let ε be any number strictly between 0and 1. Our data structure returns a (1+ε)approximation of the shortest path cost from the fixed source to a querydestination in O(logρn/ε) time. Afterwards, a(1+ε)-approximate shortest path can be reported in time linear in itscomplexity. The data structure uses O(ρ2 n4/ε2 log ρn/ε) space and can be built in O((ρ2 n4)/(ε2)(log ρn/ε)2) time. Our time and space bounds do not depend onany geometric parameter of the subdivision such as the minimum angle.

We present simple algorithms for detecting the dimension k of a smooth manifold M ⊂ Rd from a set P of point samples, provided that P satisfies a standard sampling condition as in previous results. The best running time so far is O(d2O(k7 log k)) worst-case by Giesen and Wagner after the adaptive neighborhood graph is constructed in O(d|P|2) worst-case time. Given the adaptive neighborhood graph, for any l ≥ 1, our algorithm outputs the true dimension with probability at least 1-2-l in O(2O(k)kd(k + l log d)) expected time. Our experimental results validate the effectiveness of our approach in computing the dimension. A further advantage is that both the algorithm and its analysis can be generalized to the noisy case, in which outliers and a small perturbation of the samples are allowed.