Exercise 1 Consider the fractional threshold model for the network on the left. The threshold is 1/2 for all nodes. 1. Suppose only one node can be chosen as an initial adopter. Which node should be chosen to obtain the largest cascade? 2. Find any set of initial adopters whose activation causes the complete cascade.

Exercise 1 Consider the fractional threshold model for the network on the left. The threshold is 1/2 for all nodes. 1. Suppose only one node can be chosen as an initial adopter. Which node should be chosen to obtain the largest cascade? 2. Find any set of initial adopters whose activation causes the complete cascade.

Operations Research : Applications and Algorithms

4th Edition

ISBN:9780534380588

Author:Wayne L. Winston

Publisher:Wayne L. Winston

Chapter17: Markov Chains

Section17.4: Classification Of States In A Markov Chain

Problem 3P

See similar textbooks

Similar questions

Given a Markov reward process with the attached graph: 1. If the values of the states A, B, and C are 2, 1, and 3 respectively, update the value of the state B in each of the 3 frameworks (TD(0), MC, and DP), given the following trace for MC and that the probability of moving right or left is 0.5 in each state. Trace for MC: B -> A -> B -> C -> T
In the Erdös-Rényi random network model, suppose N=101 and p=1/20, that is, there are 101 vertices, and every pair of vertices has a probability of 1/20 of being connected by an edge. For the network model given what is the probability that a network generated with those parameters has exactly 400 edges? No need to give the decimal value, the mathematical expression will suffice
Compute the gradient with respect to all parameters of f(w0 + w1a1 + w2a2) when w0 = 3, w1 = −2, a1 = 2, w2 = −1, a2 = 4, and β = 0.25 using backpropagation
defined a proper policy for an MDP as one that is guaranteed to reach a terminal state. Show that it is possible for a passive ADP agent to learn a transition model for which its policy is improper even if is proper for the true MDP; with such models, the value determination step may fail if y=1. Show that this problem cannot arise if value determination is applied to the learned model only at the end of a trial.
You are given three different Bayesian network structures (1, 2, 3), for three alarm system designs. Each system consists of 4 binary random variables (A, B, C, D). Each variable corresponds to an alarm condition in an assembly line in a factory, whose state can be either “ON” or “OFF”. Structures in image Using the chain rule of probability for Bayes Nets, factor P(A,B,C,D) according to the independencies specified in the three structures above. What is the minimum number of parameters required to fully specify the distribution (i.e. to calculate P(A,B,C,D))? Hint: The chain rule of probability P(A,B) = p(A|B) p(B) for three variables: P(A,B,C) = P(A| B,C) P(B,C) = P(A|B,C) P(B|C) P(C) and in general to n variables: P(A1, A2, ..., An) = P(A1| A2, ..., An) P(A2| A3, ..., An) P(An-1|An) P(An)
Use the Subset construction, as defined in the lecture notes, to construct DFA from the NFA produced by Thompson's construction on the regular expression x* ( y | € ) ( € | y) How many x-transitions (edges labelled x) does the DFA have? Choose... v How many accepting states does the DFA have? Choose... v How many states does the DFA have? Choose... How many y-transitions (edges labelled y) does the DFA have? Choose... v How many e-transitions (edges labelled € does the DFA have? Choose... v
Consider the following time series：Yt=Yt−1−0.25Yt−2+wt−0.5wt−1，wt is a white noise process with variance σw^2. Simulate a sample from the reduced model and calculate the sample ACF and PACF. Plot the sample ACF and theoretical ACF on one graph, and the sample PACF and the theoretical PACF on the other graph. Show the two graphs on one figure. (Please provide R codes).
1. Consider the network depicted in Figure 1; suppose that each node starts with the behavior B, and each node has a threshold of q = 1/2 for switching to behavior A. a. Now, let e and f form a two-node set S of initial adopters of behavior A. If other nodes follow the threshold rule for choosing behaviors, which nodes will eventually switch to A? b. Find a cluster of density greater than 1 – q = 1/2 in the part of the graph outside S that blocks behavior A from spreading to all nodes, starting from S, at threshold q. Figure 1: Starting from nodes e and f, the new behavior A fails to spread to the entire graph.
6. Let’s consider the operation of a learning switch in the context of a network in which 6 nodes labeled A through F are star connected into a switch. Suppose that (1) B sends a frame to E, (2) E replied with a frame to B, (3) A sends a frame to B and (4) B replied with a frame to A. The switch table is initially empty. Show the state of the switch table before and after each of these events. For each of these events, identify the link(s) on which the transmitted frame will be forwarded, and briefly justify your answers.
Given a DAG and two vertices v and w, find the shortestancestral path between v and w. An ancestral path between v and w is a common ancestorx along with a shortest path from v to x and a shortest path from w to x. The shortestancestral path is the ancestral path whose total length is minimized. Warmup: Find aDAG where the shortest ancestral path goes to a common ancestor x that is not an LCA.Hint: Run BFS twice, once from v and once from w.
The Barabasi and Albert model ´• A discrete time network evolution process,relating the graph G(t + 1) to G(t).• Start at t=0 with a single isolated node.• At each discrete time step, a new node arrives.• This new node makes m edges to already existing nodes.(Why m edges? i.e., what happens if m = 1?)• The likelihood of a new edge to connect to an existing node jis proportional to the degree of node j, denoted dj.• We are interested in the limit of large graph size, n → ∞.Visualizing a PA graph (m = 1) at n = 5000Probabilistic treatment (kinetic theory)• Start at t = 0 with one isolated node (or a small core set).– At time t the total number of nodes added n = t.– At time t the total number of edges added is mt.• Let dj(t) denote the degree of node j at time t.• Probability an edge added at t + 1 connects to node j:P r(t + 1 → j) = dj(t)/Pjdj(t).• Normalization constant easy (but time dependent):Pjdj(t) = 2mt(Each node 1 through t, contributes m edges.)(Each edge augments the degree of…
For a fixed integer C > 0, given a sequence of {rt}{_1, and {yt}E, with yt = (E-max{t-C,1} #s)°, construct a recurrent neural network (you can pick any activation functions and hidden weights as you like) which takes the sequence of {rt}{1 as inputs such that the output sequence {o}}i€[T] satisfies: OL = Y1