留学生作业代写推荐 COMS 4995代写 CS代写

COMS 4995: Intro Networks & Crowds

Homework #3 – Power Law & Matching Markets

留学生作业代写推荐 Now imagine that you create a new project page X. Creating outgoing links from X is notgoing to help you getting a higher authority score.

Why there is three parts in this assignment: Each part fulfills one of the objectives of the class:

Manipulateconcepts: Getting Familiar with the technical concepts used in class, by reproducing similar Being proficient by manipulating the object to answer some small-size problem. 留学生作业代写推荐

You are expected to answer this question rigorously, the answer can be quite short as long as it contains all the required argument to justify your answer.

Experience the concepts in real case: Being able to reproduce these concepts on real or synthetic data. Study their properties in real
Connect the concepts to real-life: Interpret a problem you find in light of the notions you have Develop somecritical eye to determine how the concepts introduced are useful in practice.

How to read this assignment : Exercise levels are indicated as follows 留学生作业代写推荐

(↣) “elementary”: the answer is not strictly speaking obvious, but it fits in a single sentence, and it is an immediate application of results covered in the lectures.

Use them as a checkpoint: it is strongly advised to go back to your notes if the answer to one of these questions does not come to you in a few minutes.

(↷) “intermediary”: The answer to this question is not an immediate translation of results covered in class, it can be deduced from them with a reasonable effort. 留学生作业代写推荐

Use them as a practice: how far are you from the answer? Do you still feel uncomfortable with some of the notions? which part could you complete quickly?

(↬) “tortuous”: this question either requires an advanced notion, a proof that is long or inventive, or it is still open.

Use them as an inspiration: can you answer any of them? does it bring you to another problem that you can answer or study further? It is recommended to work on this question only AFTER you are done with the rest!

Part A — Manipulating the Concepts 留学生作业代写推荐

Exercise 1: Manipulating Importance metrics (5pt)

Imagine you work in a small joint venture whose website contains only 6 webpages about various projects that points to each other as seen in Figure 1. You would like to create a new project and, assuming that Google follows the HITs algorithm, have it placed first whenever the name of your company is searched. We will neglect here the links from webpages of other website (which are longer to obtain, and are more difficult to control). We will also assume that, due to the competitive nature of projects in your company, you cannot ask any project to point to you.

1.(↣)Compute the score as obtained by the Hubs and Authorities after two complete iterations in the original network.

Figure 1: Elementary Network of Hubs and Authorities

2.(↷)Now imagine that you create a new project page X. Creating outgoing links from X is notgoing to help you getting a higher authority score. So you another fake project Y and points to X, as a way to provide some authority to X. You can also decide what project(s) Y links to. 留学生作业代写推荐

Compare the score you will obtain after two iterations in the HITs algorithm if Y points only to X or if Y points to A, B and X. Which one will you choose.

(↷)Imagine you can now create two fake projects Y and Z. Find a configuration that will place yourproject X as second in the order of Again you will stop after two iterations.

Exercise 2: Issues with Basic Pagerank on undirected graphs (1pt and challenging! (↬)) 留学生作业代写推荐

Basic pagerank is the first version of pagerank, without a restart or, equivalently, with no “dumping factor”. The importance metric of a node is hence the probability that a random walk in steady state is currently visiting this node. We have seen that this can create black hole whenever a node (or a small group of nodes) only receives links from other, but this does not seem to be the case if the graph is undirected.

(↬)Prove that basic pagerank on an undirected graph is not intrinsically better since it is equivalent to another metric we have seen.
(no credit, just for fun) Can you imagine a situation in which this algorithm is stilluseful?

Exercise 3: The advantages of ftnding a dominant strategy (5pt, no point for (↬))

Motivation: In game theory, a dominant strategy for player i denotes a strategy that, if played by i, always returns the largest reward. This property holds without assuming anything on how other players behave. It is convenient because i does not need to assume that other players are playing rationally; they may have bad information, or bugs in their code, but i can nevertheless determine what’s best. In contrast, a best response for player i is one that, given that i correctly predicts what other players are doing, returns the largest reward. 留学生作业代写推荐

In our study of matching market and advertising auctions, we learn that when the ad network imple- ments the pay-for-what-you-harm mechanism (often called VCG), the system is incentive compatible in the following sense: For a given advertiser/buyer i, it is i’s best strategy to bid the true value he/she has for all items/ad-slots, and this result holds no matter how all other players behave. In other words, for player i, being truthful is a dominant strategy

Unfortunately, most ad-networks do not implement the scheme above but used Generalized Second Price auction (GSP). In GSP, it is not guaranteed for i that being truthful is a dominant strategy.

(↣) Does GSP at least guarantee that, for i, being truthful is always a best response when othersare truthful? Justify your answer with a proof or a counter-example.
(↷) Does GSP at least guarantee that a dominant strategy always exist (even if that strategy may not necessarily be truthful)? We remind you that when GSP is used, there always exists a Nash Again, justify your answer with a proof or a counter-example.
(↬)(no pt, just for fun) Same question when you assume, in addition, that the Nash Equilibrium is unique.

Part B — Experiencing the Concepts 留学生作业代写推荐

Exercise 4: Measuring the glass ceiling in Instagram (15 pt)

Motivation: As we saw in lecture, many networks exhibit an inherent bias in their structure, whether it has to do with gender, class, ethnicity and so on. More specifically, it has been shown that minorities often experience inequality in opportunity in acceding to positions of influence or visibility. This phenomenon has been referred to as the “glass ceiling effect”, defined by the US Federal Commission¹ as follows:

The glass ceiling”… is the unseen, yet unbreakable barrier that keeps minorities and women from rising to the upper rungs of the corporate ladder, regardless of their qualifications or achievements.”

This effect has been observed in academia, industry, and social networks, such as Twitter, where for example women experience less visibility than men². The goal of this exercise is to explore the existence (or non-existence) of a glass ceiling effect of gender in a social network based on Instagram activity.

Description:

The graph is the product of a crawl performed on Instagram’s public profiles over multiple months of 2014 and 2015 starting from the founder of Instagram, Kevin Systrom.

For each profile, the following data were collected: 留学生作业代写推荐

(a)a unique userid,

(b)name (used to infer the gender of eachuser),

(c)the meta-data for each photo posted, including a random subset of 3-5 likes and comments withtheir authors. An edge was created between the authors of the pictures and each one of the authors ofthe likes or comments.

1See, e.g., Federal Glass Ceiling Commission. ”Solid investments: Making full use of the nation’s human capital. US Government, Department of Labor. Washington, DC: US Government Printing Office. Retrieved February 2013.” (1995).

2Nilizadeh, Shirin, et al. ”Twitter’s Glass Ceiling: The Effect of Perceived Gender on Online Visibility.” Tenth Interna-tional AAAI Conference on Web and Social Media. 2016.

For this homework, you will be using a subgraph of 3323 nodes and 15374 edges, where everyone has a labeled gender. The graph is undirected, thus a user’s degree indicates how many distinct comments or likes he/she either received from or gave to other users. You can access the graph edge list and associated gender dataset at the following link: http://bit.ly/Data4HW3 (or, if you love to type long URL, https://www.dropbox.com/sh/4jqjs975a6el4js/AAB3wWZFqv-cTTxQLOicTc4oa?dl=0).

Tail Glass Ceiling: 留学生作业代写推荐

Remember from class the following definition of tail glass ceiling inequality:

Assume G(n) is a bi-populated network consisting of m edges and n nodes of two types, the groups R and B of red and blue nodes. The graph sequence G(n) exhibits a tail glass ceiling effect for some red nodes if there exists an increasing function k(n) such that

(↣)We start by defining successful members of the social network to be high degree vertices; namely, usersthat receive and give a large number of likes and comments, corresponding to high influence.

Compute the tail glass ceiling plot (fraction of female with degree > k) in the Instagram dataset (an example³ is shown for illustration in Figure 2). Does the fraction of females among the verticesof degree k or higher decrease continuously as k increases? Do you notice any significant decreases (e.g. moving from degree 1 to degree 2 to higher)? Briefly discuss your results.

Figure 2: Example of Tail glass ceiling plot. 留学生作业代写推荐

2.(↷)Movingforward, we define success in the social network as membership to large, densely con- nected groups. For this exercise, create a tail glass ceiling plot similar to the one you created in Exercise 4.1., but this time define wealth as k-shell value instead of degree centrality.

For that, you will need to compute the k shell decomposition. Start by removing all nodes with only one connection (with their links), until no more such nodes remain, and assign them to the

3from Avin, Chen, et al. ”Homophily and the glass ceiling effect in social networks.” Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science. ACM, 2015.

1-shell. In the same manner, recursively remove all nodes with degree 2 (or less), creating the 2-shell.

Continue, increasing k until all nodes in the graph have been assigned to one of the shells. Do you observe a tail glass-ceiling effect? As above, briefly discuss your results. You will also have to submit the k-shell decomposition for each node with your results.

(↬)Finally, we define success in a social network as power over flow of information. In thismea- surement of centrality (betweenness), powerful nodes (those that have high betweenness scores) occupy critical roles in the network by controlling the flow of information. In other words, they occupy high brokerage positions at the interface of tightly-knit communities that, without them, would not be connected. 留学生作业代写推荐

Defining betweenness centrality of a node v as the sum of the fraction of all-pairs shortest paths that pass through v, compute the betweenness values of all nodes in the Instagram graph. Then, check whether the graph exhibits a glass-ceiling effect when we define “wealth” as control over flow of information. Does the proportion of women with a betweenness score equal to k or higher decrease continuously as k increases? Again, plot and discuss your results. You will also have to submit the betweenness centrality values of each node with your results.

(↣)You have had the chance to explore the existence of gender inequality in a social media network employing a variety of measurements of “wealth”, from degree, to k-shell centrality, and between- ness. Did you notice any trends (or lack of)? Is the glass ceiling stronger for any of these measures? Considering the nature of the dataset you have analyzed, how generalizable do you think your resultsare? You can use statistical methods to support your argument, but it is not

What you need to submit? 留学生作业代写推荐

3 plots representing the tail glass ceiling effect when we measure wealth as degree, k-shell, and betweenness.
Interpretation of your results.
Value per node ofk-shell.
Value per node of betweenness centrality.
Your code.

Part C — Concepts at large 留学生作业代写推荐

Exercise 5: Big old stars in mathematics (5 pt)

Pick 10 mathematicians arbitrarily who graduated in 2012, using the interface of the Math genealogy project: http://genealogy.math.ndsu.nodak.edu/search.php For diversity we recommend you pick ten starting with the same initial as your lastname, and try to avoid picking all of them from institutions in the same country.

Follow their ancestors, by clicking on their advisor (if you see two advisor, pick the first one), and note for each step: (1) Their name, (2) affiliation country (3) their number of students, (4) their number of descendants. 留学生作业代写推荐

Are all ancestor chains disjoint?If not draw the tree on a piece of paper and comment on its topology? Are there important names or countries of affiliations that you observe?
Commenton the number of students and ancestors that you observe during this process? Does this seem to correspond to a preferential attachment scheme?

Exercise 6: Exercice 11-(a),(b) and (c) p.306 in Chapter 10 of Easley-Kleinber book (10 pt)

合作平台：essay代写论文代写写手招聘英国留学生代写