# Boosting Information Spread: An Algorithmic Approach

4m ago
19 Views
614.88 KB
12 Pages
Last View : 9d ago
Transcription

B. Potentially Reverse Reachable GraphsWe now describe how we estimate the boost of influence,which is our objective function in the k-boosting problem. Theestimation is based on the concept of the Potentially ReverseReachable Graph (PRR-graph), which is defined as follows.Definition 3 (Potentially Reverse Reachable Graph). Let r bea node in G. A Potentially Reverse Reachable Graph (PRRgraph) R for a node r is a random graph generated asfollows. We first sample a deterministic copy g of G. In thedeterministic graph g, each edge euv in graph G is “live”in g with probability puv , “live-upon-boost” with probabilityp0uv puv , and “blocked” with probability 1 p0uv . The PRRgraph R is the minimum subgraph of g containing all pathsfrom seed nodes to r through non-blocked edges in g. We referto r as the “root node”. When r is also selected from Vuniformly at random, we simply refer to the generated PRRgraph as a random PRR-graph (for a random root).Similarly, we have fR ({v3 }) fR ({v2 , v5 }) 1. Based onthe above definition of fR (·), we have the following lemma.Lemma 1. For any B V , we have n · E[fR (B)] S (B),where the expectation is taken over the randomness of R.Proof: For a random PRR-graph R whose root node israndomly selected, Pr[fR (B) 1] equals the differencebetween probabilities that a random node in G is activatedgiven that we boost B and we do not boost.Let R be a set of independent random PRR-graphs, defineXˆ R (B) n ·fR (B), B V.(2) R R Rˆ R (B) closely estimatesBased on the Chernoff bound, S (B) for any B V if R is sufficiently large.C. Sandwich Approximation StrategyPRR-graph Rrv0v1v2v3v4v5v6v7liveblockedlivev8v9v10upon boost Estimating the boost fR ( ) 0 fR ({v1 }) 1 fR ({v3 }) 1 fR ({v2 , v5 }) 1 Critical nodes CR {v1 , v3 } Estimating the lower bound µ(B) I(B CR 6 )Fig. 2: Example of a Potentially Reverse Reachable Graph.Figure 2 shows an example of a PRR-graph R. The directedgraph G contains 12 nodes and 16 edges. Node r is the rootnode. Shaded nodes are seed nodes. Solid, dashed and dottedarrows with crosses represent live, live-upon-boost and blockededges, respectively. The PRR-graph for r is the subgraph inthe dashed box. Nodes and edges outside the dashed box donot belong to the PRR-graph. It is easy to check that nodes andedges outside the dashed box are not on any paths from seednodes to r that only contain non-blocked edges. By definition,a PRR-graph may contain loops. For example, the PRR-graphin Figure 2 contains a loop among nodes v1 , v5 , and v2 .Estimating the boost of influence. Let R be a given PRRgraph with root r. By definition, every edge in R is either liveor live-upon-boost. Given a path in R, we say that it is live ifand only if it contains only live edges. Given a path in R and aset of boosted nodes B V , we say that the path is live uponboosting B if and only if the path is not a live one, but everyedge euv on it is either live or live-upon-boost with v B. Forexample, in Figure 2, the path from v3 to r is live, and thepath from v7 to r via v4 and v1 is live upon boosting {v1 }.Define fR (B) : 2V {0, 1} as: fR (B) 1 if and only if, inR, (1) there is no live path from seed nodes to r; and (2) a pathfrom a seed node to r is live upon boosting B. Intuitively, inthe deterministic graph R, fR (B) 1 if and only if the rootnode is inactive without boosting, and active upon boostingnodes in B. In Figure 2, if B , there is no live path fromthe seed node v7 to r upon boosting B. Therefore, we havefR ( ) 0. There is a live path from the seed node v7 to r thatis live upon boosting {v1 }, and thus we have fR ({v1 }) 1.To tackle the non-submodularity of function S (·), weapply the Sandwich Approximation (SA) strategy [22]. Usingnotations of our k-boosting problem, the SA strategy [22]works as follows. First, we find submodular lower and upperbound functions of S , denoted by µ and ν. Then, we selectnode sets B , Bµ and Bν by greedily maximizing S , µand ν under the cardinality constraint of k. Ideally, we returnBsa arg maxB {Bµ ,Bν ,B } S (B) as the final solution. Letthe optimal solution of the k-boosting problem be B and letOP T S (B ). Suppose Bµ and Bν are (1 1/e )approximate solutions for maximizing µ and ν, we haveµ(B )· (1 1/e ) · OP T, S (B ) S (Bν ) S (Bsa ) · (1 1/e ) · OP T.ν(Bν ) S (Bsa ) (3)(4)Therefore, to obtain a good approximation guarantee, at leastone of µ and ν should be close to S . In this work, wederive a submodular lower bound µ of S using the definitionof PRR-graphs. Because µ is significantly closer to S thanany submodular upper bound we have tested, we only use thelower bound function µ and the “lower-bound side” of the SAstrategy with approximation guarantee shown in Ineq. (3).Submodular lower bound. We now derive a submodularlower bound of S . Let R be a PRR-graph with the rootnode r. Let CR {v fR ({v}) 1}. We refer to nodes in CRas critical nodes of R. Intuitively, the root node r becomesactivated if we boost any node in CR . For any node set B V ,define fR (B) I(B CR 6 ). By definition of CR andfR (·), we have fR (B) fR (B) for all B V . Moreover,because the value of fR (B) is based on whether the node set Bintersects with a fixed set CR , fR (B) is a submodular functionon B. For any B V , define µ(B) n · E[fR (B)] wherethe expectation is taken over the randomness of R. Lemma 2shows the properties of the function µ.Lemma 2. We have µ(B) S (B) for all B V . Moreover,µ(B) is a submodular function of B.Proof: For all B V , we have µ(B) S (B) becausefR (B) fR (B) holds for any PRR-graph R. Moreover, µ(B)

is submodular on B because fR (B) is a submodular functionof B for any PRR-graph R.rOur experiments show that µ is close to S , especially forsmall values of k, say less than a thousand. Definen X µ̂R (B) ·fR (B), B V. R R RfR (B)Becauseis submodular on B for any PRR-graph R,µ̂R (B) is submodular on B. Moreover, by Chernoff bound,µ̂R (B) is close to µ(B) when R is sufficiently large.Remarks on function µ(B). Function µ(B) does correspondto some physical diffusion model. Roughly speaking, µ(B) isthe influence spread in a diffusion model with the boost setB, and the constraint that at most one edge on the influencepath from a seed node to an activated node can be boosted.Due to space limit, we omit the precise description of thecorresponding diffusion model here and include it in [26].Compared with the convoluted diffusion model correspondingto µ(B), the PRR-graph description of µ(B) is more directand is easier to analyze. Our insight is that by fixing therandomness in the original diffusion model, it may be easierto derive submodular lower-bound or upper-bound functions.A LGORITHM D ESIGNIn this section, we first present how we generate randomPRR-graphs. Then we obtain overall algorithms for the kboosting problem by integrating the general IMM algorithmwith PRR-graphs and the Sandwich Approximation strategy.We classify PRR-graphs into three categories. Let R be aPRR-graph with root node r. (1) Activated: If there is a livepath from a seed node to r; (2) Hopeless: If there is no seedsin R, or there is no path from seeds to r with at most k nonlive edges; (3) “Boostable”: not the above two categories. IfR is not boostable (i.e. case (1) or (2)), we have fR (B) fR (B) 0 for all B V . Therefore, for “non-boostable”PRR-graphs, we only count their occurrences and we terminatethe generation of them once we know they are not boostable.Algorithm 1 depicts how we generate a random PRR-graph.The generation contains two phases. The first phase (Lines 119) generates a PRR-graph R. If R is boostable, the secondphase compresses R to reduce its size. Figure 3 shows theresults of two phases, given that the status sampled for everyedge is same as that in Figure 2.Phase I: Generating a PRR-graph. Let r be a random node.In this phase, a backward Breadth-First Search (BFS) fromr makes sure that all non-blocked paths from seed nodes tor with at most k live-upon-boost edges are included in R.The status of each edge (i.e., live, live-upon-boost, blocked) issampled when we first process it. The detailed backward BFSis as follows. Define the distance of a path from u to v asthe number of live-upon-boost edges on it. Then, the shortestdistance from v to r is the minimum number of nodes wehave to boost so that at least a path from v to r becomes live.For example, in Figure 3a, the shortest distance from v7 to ris one. During the generation of R, we use dr [·] to maintainthe shortest distances from nodes to the root node r. Initially,v2v3v4v5Super-seedv6{v4 , v7 }v7(a) Results of phase Iv8v1v2v4v5Super-seed{v4 , v7 }v7v3(b) Results of phase IIAlgorithm 1: Generating a random PRR-graph (G, S, k)1234567810111213141516A. Generating PRR-graphsv1rFig. 3: Generation of a PRR-Graph. (Solid and dashed arrows represent live and live-upon-boost edges respectively.)9V.v0removedlater1718192021Select a random node r as the root nodeif r S then return R is activatedCreate a graph R with a singleton node rCreate a double-ended queue Q with (r, 0)Initialize dr [r] 0 and dr [v] , v 6 rwhile Q is not empty do(u, dur ) Q.dequeue front()if dur dr [u] then continue// we’ve processed ufor each non-blocked incoming edge evu of u dodvr I(evu is live-upon-boost) durif dvr k then continue// pruningAdd evu to Rif dvr dr [v] thendr [v] dvrif v S thenif dr [v] 0 then return R is activatedelse if dvr dur then Q.enqueue front((v, dvr ))else Q.enqueue back((v, dvr ))if there is no seed in R then return R is hopelessCompress the boostable R to reduce its sizereturn a compressed boostable Rwe have dr [r] 0 and we enqueue (r, 0) into a double-endedqueue Q. We repeatedly dequeue and process a node-distancepair (u, dur ) from the head of Q, until the queue is empty. Notethat the distance dur in a pair (u, dur ) is the shortest knowndistance from u to r when the pair was enqueued. Thus wemay find dur dr [u] in Line 8. Pairs (u, dur ) in Q are in theascending order of the distance dur and there are at most twodifferent values of distance in Q. Therefore, we process nodesin the ascending order of their shortest distances to r. When weprocess a node u, for each of its non-blocked incoming edgeevu , we let dvr be the shortest distance from v to r via u. Ifdvr k, all paths from v to r via u are impossible to becomelive upon boosting at most k nodes, therefore we ignore evusafely in Line 11. This is in fact a “pruning” strategy, becauseit may reduce unnecessary costs in the generation step. Thepruning strategy is effective for small values of k. For largevalues of k, only a small number of paths need to be pruneddue to the small-world property of real social networks. Ifdvr k, we insert evu into R, update dr [v] and enqueue(v, dvr ) if necessary. During the generation, if we visit a seednode s and its shortest distance to r is zero, we know R is

activated and we terminate the generation (Line 16). If wedo not visit any seed node during the backward BFS, R ishopeless and we terminate the generation (Line 19).Remarks on Phase I. At the end of phase I, R may includenodes and edges not belonging to it (e.g., non-blocked edgesnot on any non-blocked paths from seeds to the root). Theseextra nodes and edges will be removed in the compressionphase. For example, Figure 3a shows the results of the firstphase, given that we are constructing a PRR-graph R accordingto the root node r and sampled edge status shown in Figure 2.At the end of the first phase, we also i

Social media advertising: Companies could reach intended audiences via digital advertising. According to the Nielsen Global Trust in advertising survey [11], owned online chan-nels such as brand-managed sites are the second most trusted advertising formats (completely or somewhat trusted by 70% of global respondents), second only to recommendations

Related Documents:

Algorithmic Trading Table: Proportions of trading volume contributed by di erent category of algorithmic and non-algorithmic traders in the NSE spot and equity derivatives segment (for the period Jan-Dec 2015) Custodian Proprietary NCNP Total Spot Market Algo 21.34% 13.18% 7.76% 42.28% Non-

“algorithmic” from “software” has been also reflected in media studies. [2] “Drawing on contemporary media art practices and on studies of visual and algorithmic cultures, I would like to develop the idea of algorithmic superstructuring as a reading of aest

aforementioned model. Thus, the Triangulation Algorithmic Model is provided and defined to aid in understanding the process of measurement instrument construction and research design. The Triangulation Algorithmic Model for the Tri-Squared Test The Algorithmic Model of Triangulation is of the form (Figure 2). Where,

In these notes we focus on algorithmic game theory, a relatively new ﬁeld that lies in the intersection of game theory and computer science. The main objective of algorithmic game theory is to design eﬀective algorithms in strategic environments. In the ﬁrst part of these notes, we focus on algorithmic theory's earliest research goals—

The Effect of Algorithmic Trading on Liquidity in the Options Market Abstract Algorithmic trading consistently reduces the bid-ask spread in options markets, regardless of firm size, option strike price, call or put option, or volatility in the markets. Howeve

learning [12]. In this context, [21] presented a multi-class boosting-based classiﬁcation framework that jointly selects weak classiﬁers shared among different tasks. In contrast, here the interested is in boosting a single target classiﬁer by leveraging the (instance-based, or paramet

The Pendulum Charts: by Dale W. Olson Immune System Analysis Immune Boosting Supplements Immune Boosting Protocols If you are a beginner at using a pendulum or the Pendulum Charts, we would highly suggest reading: The Pendulum Bridge to Infinite Knowing, or The Pendulum Instruction Chart Book, or

Algorithmic Trading and Information Terrence Hendershott Haas School of Business University of California at Berkeley Ryan Riordan Department of Economics and Business Engineering Karlsruhe Institute of Technology August 18, 2009 Abstract We examine algorithmic trades (AT

was to construct a consistent algorithmic theory of proba- bility, the aim of this paper is to indicate how algorithmic . able function V: A* R with the following properties: V(A) 1, . rS1cx), where s,(x) denotes the number of occurrences of w E A* in the sequence x, and r,,, r, are computable positive reals with r0 r, 1. As a p .

Question Bank UNIT 1 - ALGORITHMIC PROBLEM SOLVING Part-A 1) Define Computer 2) Define algorithm 3) What are the two phases in algorithmic problem solving? 4) Why algorithmic phase is a difficult phase?Justify 5) What are the steps involved in algorithm development process? 6) Compare computer hardware and software.

Revised7 Report on the Algorithmic Language Scheme ALEX SHINN, JOHN COWAN, AND ARTHUR A. GLECKLER (Editors) STEVEN GANZ ALEXEY RADUL OLIN SHIVERS AARON W. HSU JEFFREY T. READ ALARIC SNELL-PYM BRADLEY LUCIER DAVID RUSH GERALD J. SUSSMAN EMMANUEL MEDERNACH BENJAMIN L. RUSSEL RICHARD KELSEY, WILLIAM CLINGER, AND JONATHAN REES (Editors, Revised5 Report on the Algorithmic Language Scheme) MICHAEL .

Revised6 Report on the Algorithmic Language Scheme MICHAEL SPERBER R. KENT DYBVIG, MATTHEW FLATT, ANTON VAN STRAATEN (Editors) RICHARD KELSEY, WILLIAM CLINGER, JONATHAN REES (Editors, Revised5 Report on the Algorithmic Language Scheme) ROBERT BRUCE FINDLER, JACOB MATTHEWS (Authors, formal semantics) 26 September 2007 SUMMARY The report gives a deﬁning description of the programming language .

understand fundamental algorithms and algorithmic techniques, analyze correctness, running time, and space complexity of a given algorithm, judge which algorithmic technique is best for a given problem, apply known algorithms and learned algorithmic techniques to new problems,

the algorithmic trading strategy’s design; typically, broker algorithmic trading systems seek to minimize the cost of trading by optimizing the execution strategy—that is, minimize market impact cost or time to execution, optimize the price, and so on—whereas proprietary algo - rithmic

2.2 ALGORITHMIC ART IS HARD This paper describes the goals of algorithmic art, not the way to achieve the goals. The latter requires intuition and, like with any other form of art, a sometimes rewarding but often .frustrating struggle for capturing "the essence". In the beginning

Mostly, algorithmic composition is a field that combines computer science and music. However, in general algorithmic composition is an example of generative art. Instead of music, one can create text, images, videos, anything using a similar approa

DIMACS Algorithmic Mathematical Art May 11 - 13, 2009 J-M Dendoncker 1. Projects : IT’S MATHEMAGIC - Van Maat tot Math 1.3.5 Surface of Scherk Dimacs Algorithmic Mathematical Art 34 The hyperbolic paraboloid shoul

Algorithmic Composition Lejaren Hiller (1924–1994) is widely recognized as the first composer to have applied computer programs to algorithmic composition. The use of specially designed, unique computer hardware was common at U.S.

Algorithmic problem solving is the art of formulating efﬁcient methods that solve problems of a mathematical nature. From the many numerical algo-rithms developed by the ancient Babylonians to the founding of graph theory by Euler, algorithmic problem solving has been a popular

Oct 10, 2007 · Algorithmic Modeling Interface (AMI), and is based on the concept that a model should be an algorithmic one which abstracts out the details of the circuit implementation. By abstracting out non-essential details, such a model c