COMS 4995-1: Networks & Crowds
Final
CS代考 For each question, you have to circle all the correct answer(s) (there may be one, several or even zero) cross all the incorrect answer(s).
Please indicate your uni:
- Thisexam should be answered in It is graded on a total of 350pt.
General Multiple Choice Review (18 × 8 = 144 pt) CS代考
For each question, you have to circle all the correct answer(s) (there may be one, several or even zero) cross all the incorrect answer(s). If you believe these answers are obvious you may not need to justify it, but for any question that may require justification, you can clarify your answer on the answer sheet! (Be brief, no more than a couple of sentences).
1.Which event lead to organizing the final on May 6? (This question is not graded, you’ll get all points.)
(a)Remembering the sack of Rome, often referred to as the end of the Renaissance, 495 years ago.
(b)The opening of the Eiffel tower 123 years ago.
(c)The anniversary of the death of Zhou Zuoren 55 years ago.
(d)The anniversary of the death of the celebrated modern sculptor Novera Ahmed 7 years ago. CS代考
Explanation:
2.Whichof the following properties is related to a form of homophily?
(a)Social networks have higher contagion threshold than uniform random graph.
(b)The probability to be friend with someone decreases as the geographical distance increases.
(c)Two persons very far away are more likely to be connected by a friendship edge.
(d)Social networks can exhibit small world navigation.
Explanation:
3.Milgram’s experiment hasshown
(a)that short chains of acquaintances can be found through a distributed search. CS代考
(b)that nodes on a grid where some edges are rewired to neighbors chosen uniformly at random can find a short path to any destination only with local information.
(c)that people become friends by copying friendship from their neighbor, which creates apower law distribution of degree.
(d)That information can be routed efficiently with greedy algorithm on social networks as long as the clustering coefficient remains sufficiently high.
Explanation:
4.What can you say about a graph with positive/negative edge that is made of three subsets A,B,C of nodes such that all nodes in A (resp. B and C) are mutual friends, and nodes in two different subsets are alwaysenemies? CS代考
(a)It is weakly structurally balanced.
(b)It is strongly structurally balanced.
(c)It contains only triangles with even number of friends
(d)If one only considers positive edge in this graph, its conductance is zero
Explanation:
5.Which of the following centrality measures does not account for distance in thegraph?
(a)Degre centrality.
(b)Closeness centrality.
(c)Betweenness centrality.
(d)k-shell decomposition.
Explanation:
6.The Hub and Authorityalgorithm
(a)is guaranteed to converge if and only if it is applied to an undirected graph (i.e.iff the adjacency matrix A is symmetric). CS代考
(b)converges only if the authority score is initially set up to be proportional to an eigenvector corresponding to the largest eigenvalue.
(c)converges,from any initial condition, to a limit that is also the eigenvector of a matrix related to the adjacency matrix.
(d)does not converge when a node has no outgoing edge or has only an outgoing edge that is a loop.
Explanation:
7.Thetail glass ceiling effect, which is distinct from a mere difference between average degrees among majority/minority groups …
(a)predicts that the fraction of members of a minority group vanishes when we progressively conditioned on higher and higher ”wealth/prominence” (e.g. measures of income, status, degree).
(b)wasshown to emerge when two sufficient conditions are satisfied in random networks: major- ity/minority groups, and homophily.
(c)is induced solely by a rich-get-richer dynamics such as preferential attachment.
(d)isalways reinforced (i.e., happens quickly) when recommendation algorithms based on common friends are in place.
Explanation:
8.Let us assume a model growing a graph by introducing a node one at a time.
Without loss ofgenerality we assume nodes are one of two colors Red, Blue, each new one is red with a probability Which of the following feature have been shown sufficient to create a simple model exhibiting tail glass ceiling, i.e., there exists a function k(n) such that we both have
(a)r < 1/2 and the distribution of degree in the network is heavy tailed.
(b)r < 1/2 and the network exhibits some homophily in the sense that the fraction of edges between red and blue nodes is significantly smaller than r ∗ (1 −r).
(c)Thetwo distribution of degrees are heavy tailed with two different coefficients satisfying βR > βB.
(d)The node decides who to connect to when joining the network by following preferrential at- tachment with a biased homophily: accepting an edge to a node of a different color with a different probability than with the same color. CS代考
Explanation:
9.Forwhich of these influence/epidemics models does the complete success of the epidemics (whether or not it has affected all nodes at least once) depends on the initial conditions? (NB: We assume that we always ignore the case where at time t = 0 no nodes is infected since it would trivially be different from other initial conditions).
(a)the continuous S → I model.
(b)the continuous SIS model
(c)Granovetter’s threshold model
(d)the fixed deterministic threshold model (i.e., Morris model) on an infinite graph
Explanation:
10.For which of these influence/epidemics models does the persistence of the epidemics (whether there is a positive fraction remaining infectious for large value of t, or whether it goes to 0) depends on the parameters? (NB: we remind the parameter(s) for each model in parenthesis. Again we ignore degeneratevalues such as infinite or zero threshold, zero probability, ). CS代考
(a)the continuous S → I model (infectionrate)
(b)the continuous SIS model (infection rate, recoveryrate)
(c)the continuous SIR model (infection rate, recoveryrate)
(d)the independent cascade model (infectionprobability)
Explanation:
11.For which of these influence/epidemics models does the complete success of the epidemics (whether or not it has affected all nodes at least once) depends on the parameters? (NB: we remind the parameter(s) for each model in parenthesis. Again we ignore degenerate values such as infinite or zero threshold, zero probability,).
(a)the continuous S → I model (infectionrate)
(b)the continuous SIS model (infection rate, recoveryrate)
(c)the discrete SIR model with single infection attempt (e., discrete independent cascade) (in- fectionprobability)
(d)the fixed deterministic threshold model (e., Morris model) on an infinite graph (threshold value).
Explanation:
12.Anadjacency matrix is any matrix that represents connections in a graph as matrix, in order to use linear algebra Which of the following problems can be directly analyzed from the spectral properties (eigenvector, eigenvalues) of the adjacency matrix
(a)Determine when is Milgram routing converging efficiently.
(b)Obtain a bound on the contagion threshold in a threshold model of influence.
(c)Findwho has more weight in iterated ranking algorithm (page ranks, hubs and authorities). CS代考
(d)Determine if the network is structurally balanced.
Explanation:
13.Whichof the following problem was shown to be equivalent to computing one centrality measure?
(a)Computing the eigenvector of a matrix related to a
(b)Ranking ads to assign to slots to maximize
(c)Finding clusters that define the contagion
(d)Determinethe optimal set of seeds to reach a maximum number of nodes in an influence model in the independent cascade
Explanation:
We consider a simple model of adoption in which each member of the population observes the total fraction x who already adopted a product before deciding to adopt or not.
where F (x) denotes how many people would adopt if a fraction x of the people adopts.
14.Assumingone chooses an initial fraction x(0) uniformly at random in [0; 1], the system would then evolve according to the natural adoption and eventually reaches and equilibrium x(∞). How many equilibrium exist that can be reached with a positive probability?
(a)5
(b)3
(c)2
(d)another value
Explanation:
- Which equilibrium point(s) has/have the largest probability to beoccur?
(a)x7
(b)x3
(c)x9
(d)another value of x
Explanation:
In the following we consider the three graphes below. The first Graph G1 is a finite graph containing 9 nodes, the two others G2, G3 contain an infinite number of nodes which follows a regular shape as shown on the Figure.
We define, for any p ∈ [0; 1] and S0 ⊆ V , the subset I(p, S0) as the ones containing all the nodes eventually adopting, when we assume that the adoption starts from the seed set S0, and each nodes adopt as soon as at least a fraction p of her neighbors adopted. CS代考
As a reminder, the contagion threshold of any graph tt = (V, E) as
sup{p such that there exists S0 ⊆ V , |S0| < ∞ , and I(p, S0) = V } .
16.What is the contagion threshold for G1
(a) 1/2
(b) 1/3
(c) 1/4
(d) another value
Explanation:
17.What is the contagion threshold for G2
(a) 1/2
(b) 1/3
(c) 1/4
(d) another value
Explanation:
18.What is the contagion threshold for G3
(a) 1/2
(b) 1/3
(c) 1/4
(d) another value
Explanation:
Exercise 1: It’s NOT Fair (50pt)
Your three friends ask to help them assign room in their communal apartments. They are willing to publicly disclosed their values for each room and describe it to you as follows:
You describe them the properties of a market clearing price and propose to implement it for them.
- Describethe prices you will construct and how it assigns those rooms? You may repeat either repeat the procedure learned in class or use another argument as long as you justify that your choice is a market clearing price?
- Afterthe assignment, one of your friends is upset by the That person claims, although as planned the room he/she chooses was the best given the price, you made a subjective choice. He/she claims that market clearing prices are not unique. She claims, as a consequence, that you picked a specific market clear price to make sure he/she receives that particular room. She also claims that you are friend with another of the three and could possibly choose prices that made that other person pay less. CS代考
What part of his/her concern are justified? What can you tell him/her to reassure that what you have done did not affect him/her?
- Your 3 friends graduated and move to the same neighborhood to buy 3 houses {a, b, c}, with values indicated below. Can you help solve the sameproblem?
Exercise 2: Sponsored Search Advertising (50 pt)
In your first day a Booble, a new search company, your manager asks you to implement a Generalized Second Price auctions to assign slots (with a fixed click-rate) among advertisers. When you mention to him that the ”pay-as-you-harm” (aka VCG) mechanism is incentive compatible and hence more stable, he answers ”Well, perhaps, but my friends told me that Generalized Second Price always brings more revenue and that’s all I care about”.
- Produce a small example to justify that Generalized Second Price auction may lead to stable bids that form a Nash Equilibrium but are not revenue optimal.Can the revenue be smaller than ”pay-as-you-harm” (aka VCG)?
- Doesthere exist such an example when advertisers compete for a single slot (or, equivalently, when nobody clicks on slots with index 2 and above)?
Exercise 3: Hub & Authorities algorithms on regular graphs (50pt)
Motivation: Intuitively, in a graph that is d regular (i.e., in which all nodes have the same degree d), no node should be more important than others. As a consequence, one expects the result from a ranking algorithm to be trivial. This exercices proposes a way to prove it.
Let tt = (V, E) an undirected and connected regular graph. We denote by A its adjacency matrix:
We assume that tt contains n nodes (i.e., |V | = n), hence A is a n × n matrix.
- By considering the vectore1 = (1, 1, . . . , 1) of size n, propose one eigenvalue for the matrix A.
Let us consider an eigenvalue λ of A, associated with an eigenvector x ∈ Rn (i.e., Ax = λ · x). We assume that x is different from e1. In other words, x and e1 are not linearly related, i.e., for any c ∈ R, x ̸= c · e1.
We wish to prove that λ is strictly smaller than d.
- Let xmax= maxi∈V xi and I = { i ∈ V | xi = xmax }. Show that ∅ ⊊ I ⊊ V .
- Deducefrom a property of tt that there exists an edge (i0, j0) such that i0 ∈ I and j0 ∈/ I.
- Deduce from the above result that λ <d.
To simplify the analyis of the hub and authorities algorithm, we will assume that each edge in E represents a “hub” and that this hub votes for both i and j, which are considered “authorities”. This makes a total of m = n×d hubs, and it is not hard to see that the m × n voting matrix M satisfies M T M = A. CS代考
- Using a result from the class (whose proof is admitted), justify why the hubs and authorities algorithm, which assigns a weight ai(k) to node i ∈ V after k steps will eventually assign the same weightto all What is the effect of the initial condition of these weights?
Exercise 4: Technology Adoption with Converters (50pt) CS代考
Motivation: As we have seen during our course, technologies can exhibit a local “network effect”; in other words the utility of a technology to a user depends on how many people she interacts with also possess it. In the case of competing products (i.e., “Google +” vs. “Facebook”, “Gowalla” vs. “FourSquare”), a natural solution is to offer converters, that allow users of one technology to interact with users choosing a different technology. This exercice proposes to study the impact of converters on technology adoption.
We assume a set of users that are connected through an undirected graph tt = (V, E). Every edge (u, v) (where u ̸= v are two users chosen in V ) corresponds to a “friendship” relation. We denote by N (u) ⊆ V the set of friends of u as defined by this graph.
Through the enjoyment of shared content and other applications, a user receives a utility for every of her friend, depending on which technology they adopt. If we denote by su ∈ { A, B } the strategy chosen by a user u ∈ V (whether to use technology A or B), then her utility is:
As an example: a user choosing A with three neighbors choosing respectively A, B and A, will in total receive a utility:
f (A, A) + f (A, B) + f (A, A) = a +a + b2 (1 − δ) + a .
We assume that a > b, so that technology A is intuitively “better”. Two users who follow a different strategies are still able to receive some benefits from their interaction (this value is proportional to the average benefits on each technology, a+b but it is also multiplied by a factor 1−δ (where δ > 0) represents a loss of utility related to the complexity of using a converter (or the loss of some features).
As before, we will assume that a user chooses her strategy in a myopic way according to the following slotted game. During time slot t, a user observes the strategies chosen by her neighbors (whether they use A or B). To choose her strategy during time slot t + 1, she assumes that each of her neighbors continues in the next time slot with her strategy at time t. She then chooses the strategy for herself that maximizes her own utility under these assumptions on others’ behaviors. CS代考
- Assuming first that δ = 1 (e.,the converter is essentially useless), what can you say about the behavior of this game?
- Assuming now that δ > 0, how would you describe, in the simplest possible form, the conditions under which a user will decide to play strategy A? Is that a tresholdstrategy?
- When δ <a−b , can you predict the result of the game for any graph?
- More generally, would you say that introducing a converter (with δ < 1) favors the adoption of superior technology? Are they always sufficient to achieve 100% adoption (provide either a proof or a counter example)?
THE FOLLOWING AND LAST EXERCISE IS MUCH HARDER AND GIVES VERY LITTLE POINT. IT IS ONLY INTENDED FOR THOSE OF YOU WHO COMPLETED ALL EXERCISE AND WONDER WHAT TO DO WIH SOME EXTRA TIME.
Exercise 5: Extension of the small world result to an inftnite lattice (6 pt, (↬)) CS代考
One of the limitation of small world navigation model seen in class is that as N goes to infinity, the probability for two chosen nodes at a given fixed distance to have an edge connecting them goes to zero. This is similar to random graphs and comes from a normalization constant. But, contrary to random graph, small world navigation model can be extended to be defined on an infinite graph, so the parameter N disappear! This exercise guides you to prove that advanced properties.
In an infinite lattice, one cannot hope to have any bound on the time to connect two arbitrarily far away nodes. On the other hand, one may hope that on an infinite lattice that starting from a node at a fixed distance D from the target, greedy routing finds a path whose length grows slowly with D.
- (↷) Assuming r > k, can you prove that the random biased augmented lattice (which we also called small world navigation, or Kleinberg’s model) can be defined without modification to an infinite lattice. Why is that impossible when r ≤k?
- (↷) Assuming r > k, can you quickly justify why there exists a constant C > 0 and η > 0 suchthat, in expectation, the path found by greedy routing requires at least CDη steps when starting from a node at distance D from the target. CS代考
We will now prove that Kleinberg model can be modified so that the proof of the critical case r = k applies to an infinite lattice.
- (↣)For an ε > 0 Let f : x ›→ 1 , what is f ′ the derivative of f ? what is the limit lim f ?
- Prove that for any ε > 0, one can naturally extend Kleinberg model to an infinite lattice for r = k, assuming that the probability to have a shortcut u ~ vis
- Prove that greedy routing in the above model uses at most O(ln2+ε(D)) steps when starting atdistance D from the target.
更多代写：经济学网课代修 台灣代考網 金融系网课代做考 金融paper代写 教育学文献综述代写 怎么写好一篇论文
合作平台：essay代写 论文代写 写手招聘 英国留学生代写
