COMS 4995: Intro to Networks & Crowds
Midterm
cs exam代考 For each question, you have to circle all the correct answer(s) (there may be one, several or even zero) and cross all the incorrect answer(s).
Please indicate your uni:————————–
- This exam should be answered in 75mn.
- It is graded on a total of 128pt.
- Note that it is long and we do not expect students to complete it entirely. Receiving 100pt would already be near the maximum point (but if you have more point, we will continue to count them not to disadvantage you if you are having a good day).
- Good luck
General Multiple Choice Review (16 × 8 = 128 pt) cs exam代考
For each question, you have to circle all the correct answer(s) (there may be one, several or even zero) and 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).
The first question is just to practice the format and lighten the mood. Don’t worry about getting it right.
1.How many minutes are needed to setup the hybrid class teaching setting each week?
(a) 1 in theory, but the professor is unable to use any device that was designed after the 1990s.
(b) I don’t know I could never force myself to stay awake past the first 2mn of each lecture
(c) An infinity since at least one thing is wrongly configured everytime.
(d) What?!? There was a recording. You mean I could have skipped all those boring classes to watch them at 1.5x speed later, and you are only telling me now!
(a) probably true, (b) in my dream, (c) unfortunately true, (d) I’ll try to speak faster next time.
2.What is the average number of sets of three nodes that are open triads in a uniform random graph with N nodes and edge probability p = 1/N? For this answer, we are ignoring constant factors that are independent of N, so don’t worry about those.
(d) none of the above, even with a different constant.
3.A large network with a small clustering coefficient …
(NB: here clustering coefficient denotes the average number of closed triangle among friends. We say it is small if when n becomes large it gets smaller and smaller and approaches zero).
(a) … could be a large uniform random graph.
(b) … contains a large majority of weak ties.
(c) … resembles a structured graph like a grid where a very small infinitesimal fraction of edged are rewired independently.
(d) … contains many edges that are local bridges. cs exam代考
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 always enemies?
(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 negative edges in this graph, it contains no cycle.
5.Privacy is often defined as preventing individuals from harm implied by information pertaining to them used in new contexts, especially those outside of their control.
When it comes to social networks, this often implies recognizing the same node in two different graphs which is what we consider here. Here we assume that a small set of nodes decided to publicly connect their accounts,and we are examining the privacy implications for other individuals. If the graph are publicly released, which of the following statements hold:
(a) This privacy is ensured for all remaining nodes when graphs released contain only profile number or names that are not in anyway associated with real identifiers, and all remaining nodes have all same degree.
(b) This privacy is ensured for all nodes when graphs released contain only profile number or names that are not in anyway associated with real identifiers, and we also assume that the two graphs follow two independent random graphs.
(c) Not all individuals will be recognized exactly if one of the graph admits an auto-morphism (i.e. a 1-to-1 mapping between nodes that preserve the existence of an edge between pairs, and is not the identity).
(d) If we assume in addition that all nodes have the same degree, if one graph admits an automor-phism (i.e. a 1-to-1 mapping between nodes that preserve the existence of an edge between pairs, and it not the identity), then all individuals privacy is guaranteed.
6.Assume that G is a Uniform random graph with N nodes and edge probability p = 1/N. cs exam代考
Assume G1 is obtained from G by retaining each edge of G independently with probability s1. Assume G2 obtained in the same way from the same graph G, also with probability s2. Let i, j be two nodes chosen in G. What is the probability that i and j are connected both in G1 and G2?
(a) p × s1 × s2.
(b) p 2 × s1 × s2
(c) 1 − (1 − p)(1 − s1)s2 − (1 − p)(1 − s2)s1
(d) 1 − (1 − p)(1 − s1)ps2 − (1 − p)(1 − s2)ps1
7.Assume that G is a Uniform random graph with N nodes and edge probability p = 1/N.
Assume G1 is obtained from G by retaining each edge of G independently with probability s1. Assume G2 obtained in the same way from the same graph G, also with probability s2. Let first choose two nodes i, j and chose k, l so that k ≠i. What is the probability that i and j are connected in G1 and k and l are connected in G2?
(a) This is p 2 × s1 × s2 but only if we assume that j ≠l, otherwise it is different.
(b) p 2 × s1 × s2 for any choice of j, l.
(c) 1 − (1 − p)(1 − s1)ps2 − (1 − p)(1 − s2)ps1.
(d) This probability is smaller than the answer to question 10.
8.The current diagram represents a node A and 4 neighbors in a weakly structurally balanced networks.
(a) The sign of the edge (B, C) is entirely determined.
(b) The sign of the edge (B, D) is entirely determined.
(c) The sign of the edge (D, E) is entirely determined.
(d) All the above answers remain identical if we assume that the graph is strongly structurally balanced.
9.The following graph is incomplete and contains positive and negative edges as shown.
As a reminder,an incomplete graph is said strongly structurally balanced if it’s possible to complete all missing edges (fill all the blank) with a sign so that the complete graph is itself strongly structurally balanced.
(a) This graph is strongly structurally balanced.
(b) This graph is weakly structurally balanced.
(c) In order for the graph to be weakly structurally balanced, the sign of the missing edge (4,6) can only take one value. cs exam代考
(d) All the results above remain the same when we remove edge (13,15) and (4,2).
10.We consider the following network, composed of strong and weak ties. We assume that triadic closure holds. In addition we assume each node who has at least 4 friends has at least 2 strong ties among them.
(a) A-B is necessarily a weak tie.
(b) H-B is necessarily a weak tie.
(c) A-C can either be a weak tie or a strong tie
(d) None of those statements are changing if we replace the last assumption with ”All nodes with at least 3 friends or more in the graph have at least 2 strong ties each, with only one exception in the entire graph who may have less than 2”.
11.The fact that a network exhibits a degree distribution that is a power law systematically implies:
(a) That the distribution or density function of degree in linear when plotted in log-log plot.
(b) That the network has been created following a preferential attachment, or reinforcement pro-cess.
(c) That very large degree nodes are rare but still not unlikely to occur in a large graph.
(d) That P[degree ≥ x] decreases exponentially fast in x.
12.Which ones of the following distribution appears to be a power law? cs exam代考
13. In a matching market with N > 2 sellers and N buyers with valuations for each of the goods, a setof market clearing prices …
(a) is constructed as the results of a second price auctions.
(b) is uniquely defined.
c) always exist.
(d) never assigns the same price to different goods.
We consider the following bipartite graph with rooms and students listed a room that they are willing tostay in.
14.The following statement holds
(a) The bipartite graph has no perfect matching.
(b) The bipartite graph has no constricted set.
(c) This graph is a preferred-seller graph for a set of market clearing prices.
(d) There is one assignment following this preferred-seller graph that maximizes the total valuation of sellers to buyers.
15.Sponsored search advertising markets
(a) are a specialized case of a matching market.
(b) Are typically not implementing the pay-for-what-you-harm mechanism (aka VCG) because that mechanisms may lead to suboptimal total valuation of slot assignments.
(c) Often uses Generalized Second Price Auction because that mechanism always guarantees a maximum total valuation of slot assignments.
(d) uses Generalized Second Price Auction because, as opposed to a First Price Auc-tions, that mechanism always guarantees that a Nash Equilibrium exists for ad-vertisers bids. cs exam代考
16.The Hub and Authority algorithm
(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).
(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.