xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

扫码添加客服微信

扫描添加客服微信

python代写-CS 5854

时间：2021-03-01

CS 5854 : Networks, Crowds, and Markets

Homework 1

Instructor: Rafael Pass TAs: Cody Freitag, Benjamin Chan

Due: March 3, 2021, 11:59 pm Eastern Time

Homework Policies and Guidelines:

Submission: Your written homework solutions must be typed and submitted as a single .pdf file on Gradescope.

You must additionally submit all relevant files specified in the assignment for all coding problems, in the appropriate

format. The format is important because your code will be partially graded by an autograder. Template .tex and

.py files will be provided containing an outline for your submission.

Late Days: Each student may use four “late days” in total for the first three assignments in the semester, each

of which grants a 24-hour extension to an assignment’s due date. Late work beyond this limit will still be accepted

and graded until grades have been released for that assignment, but (unless discussed in advance with the TA and/or

instructor) will have a negative impact on final grades.

Collaborations: You may work in groups of up to 3 students. Every member of the group must list all other

collaborators at the top of their assignment. (Note: the maximum size of a connected component of groups must be

3. If A,B, and C work together, it must not be the case that A and D work together.)

Your submitted answers, explanations, and discussion for all written questions in the pdf must be your

own, individual, unique solutions. You will receive ZERO points for written explanations which are copied

verbatim or copied with minor changes (up to the discretion of the TAs)—either from another group member or from

a cited online source. You will also receive ZERO points for submitting code which is copied verbatim or with minor

changes (up to the discretion of the TAs) from an online source. You may share and even submit the same code,

examples, figures, and graphs with your collaborators, but ALL explanations must be your own. Additionally, you

may make use of published material (papers, Github, Wikipedia, etc.), provided that you acknowledge and specifically

cite all sources used. Still, this does not give you permission to copy code/ explanations from an online source. It is

considered a violation of academic integrity to submit a problem solution that you are unable to explain orally to a

member of the course staff.

How to receive credit: You must justify all answers to receive credit unless specified otherwise. We will

do our best to make clear the level of justification we expect for each problem. For coding questions, please turn in

complete, executable code for each part of the question that asks for an implementation. All coding questions will

also include a written component which you will include in the main .pdf file. Using Python is required. We will not

grade code based on style, but we may mark down code if we are unable to understand what it is doing. You may

use standard libraries to implement data structures such as graphs, but, unless otherwise specified, you may not use

pre-existing implementations of any algorithms without express permission from the TAs. (If a problem asks you to

implement X and you use a package that implements X for you, you will not get credit.)

Grading: There will be four homeworks throughout the semester. Each homework (and each problem within

each homework) will receive an associated weight specified by a number of points. Your raw score at the end of the

semester will be the sum of points earned divided by the total number of available points. If your raw score is greater

than 94%, you are guaranteed to get at least an A, 90% for A-, 87% for B+, 84% for B, and so on. We reserve the

right to lower the cutoffs (but we will not raise them).

There will additionally be optional bonus problems on some assignments. These will not be factored into your

raw point totals, but will be factored in after computing your raw score to determine your final grade (for getting an

A+, or possibly bumping up 1 or 2 letter grades).

1

Part 0: Logistics

Slack: Join the slack channel for the course, via the following link: SLACK

Collaborators: If you need help finding a group to collaborate on the assignments with, you can

use Slack and/ or fill out THIS GOOGLE FORM. Cody will periodically match people who fill out

this form before HW1 is due.

Policies: Read the full homework policies and guidelines above. If there are any questions, please

ask them on slack before this first homework is due.

Submitting on Gradescope: All homeworks will be released on Canvas, and submitted on

Gradescope. In the process of submitting on Gradescope, please be sure to match your submission

pages to problem numbers. (This makes grading much easier; otherwise we have to do it for you).

When submitting code on Gradescope, please make sure the preliminary autograder correctly eval-

uates your submission; otherwise you will receive an incorrect grade. Finally, when submitting code

on Gradescope, you have the option of submitting individually, or as a group; take your pick.

Part 1: Game Theory

1. For each of the following three two-player games, find (i) all strictly dominant strategies, (ii)

the action profiles which survive iterative removal of strictly dominated strategies, and (iii)

all pure-strategy Nash equilibria. Give a brief justification for each part.

(a)

(∗, L) (∗, R)

(U, ∗) (5, 4) (4, 5)

(D, ∗) (4, 4) (0, 0)

(b)

(∗, L) (∗, R)

(U, ∗) (2, 2) (2, 1)

(D, ∗) (3, 2) (0, 3)

(c)

(∗, L) (∗, R)

(U, ∗) (6, 5) (4, 5)

(D, ∗) (5, 4) (2, 2)

2. Consider the two-player game given by the following payoff matrix:

(∗, L) (∗,M) (∗, R)

(t, ∗) (-1, 2) (5, 1) (0, 0)

(m, ∗) (1, 2) (-1, 0) (6, 2)

(b, ∗) (4, 1) (3, 1) (2, 0)

(a) Does either player have a strictly dominant strategy? If so, which player, what strategy,

and why? If not, what is the smallest number of entries in the payoff matrix which would

need to be changed so that some player did have a strictly dominant strategy? Justify

why this is the minimum, i.e. there is no smaller value that works.

2

(b) What are player 1’s and player 2’s best-response sets given the action profile (m,L)?

Explain in words why these are the best responses.

(c) Find all pure-strategy Nash equilibria for this game. (Argue why all that you wrote

are PNEs and why there are no others.) Describe how best-response dynamics might

converge to each pure-strategy Nash equilibria.

3. (a) Prove the following: If player 1 in a two-person game has a dominant strategy s1, then

there is a pure-strategy Nash equilibrium in which player 1 plays s1 and player 2 plays

a best response to s1. (Your proof should be near the level of formality used in the

book. Part of the point of this problem is to get familiar with formally arguing about

the definitions provided.)

(b) Is the equilibrium from part (a) necessarily a unique pure-strategy Nash equilibrium?

Justify your answer.

(c) In particular, can there also exist a pure-strategy Nash equilibrium where player 1 does

not play s1? Justify your answer.

(d) If s1 is instead a strictly dominant strategy for player 1, how do the answers to (a)-(c)

change? Provide proper justifications for each part.

4. Formulate a normal-form game (as a payoff matrix) that has a unique pure-strategy Nash

equilibrium, but for which best-response dynamics does not always converge (i.e. there are

possible starting states for which BRD will not converge). Justify your answer. (Hint: Try

modifying a game where BRD does not converge to give it a unique PNE.)

5. Consider the following two-person game between a kicker (row player) and a goalie (column

player). Before the penalty kick, the kicker can decide to either kick to the left, middle, or

right, and the goalie can decide to either guard left, middle, or right. Based on what each

player decides, they have the following payoffs:

GL GM GR

KL (-1, 1) (-0.5, 0.5) (1,-1)

KM (0.5, -0.5) (-1,1) (0.5, -0.5)

KR (1,-1) (-0.5, 0.5) (-1,1)

Intuitively, this says that the goalie blocks the kick if they both choose the same direction.

The kicker scores a goal if they choose opposite directions. The goalie has a slight advantage

to guard the middle (it can better react if the kicker chooses left or right). And the kicker

has a slight advantage if it kicks middle and the goalie commits to left or right.

(a) Prove that there is no pure-strategy Nash equilibrium in this game.

(b) Suppose each player chooses each action uniformly at random (so 1/3 probability for

each available choice). Compute the expected utility for each player.

(c) The kicker notices that kicking to the middle is not working out very well for her, so

she decides to randomly kick to the left or right instead (each with probability 1/2).

Compute the goalie’s strategy that maximizes its expected utility. Specifically, provide

3

probabilities xL, xM , xR (such that xL + xM + xR = 1) where xL is the probability the

goalie chooses GL, xM for GM, and xR for GR. Then compute the expected utility for

the goalie under those probabilities. Justify why the value you computed is maximal,

i.e. is a best response.

(d) Bonus (and a hint for the previous question): Prove there will always exist a “pure”

best response to any mixed strategy above, where the goalie plays one of the actions

with probability 1.

(e) Prove that the mixed action profile from part (c) is a Nash equilibria. Namely, neither

player has a (strictly) profitable deviation.

Part 2: Graph Theory

Note: Unless stated otherwise, please assume for any problem involving graphs that we refer to

undirected and unweighted graphs.

6. Given a graph, we call a node x in this graph pivotal for some pair of nodes y and z if x (not

equal to y or z) lies on every shortest path between y and z.

(a) Give an example of a graph in which every node is pivotal for at least one pair of nodes.

Explain your answer.

(b) For any integer c ≥ 1, construct a graph where every node is pivotal for at least c

different pairs of nodes. That is, if I give you any value for c ≥ 1, your explanation

should tell me how to construct such a graph for that c. Explain your answer.

(c) Give an example of a graph having at least four nodes in which there is a single node x

which is pivotal for every pair of nodes not including x. Explain your answer.

7. Given some connected graph, let the diameter of a graph be the maximum distance (i.e.

shortest path length) between any two nodes. Let the average distance be the expected

shortest path length between a randomly selected pair of distinct nodes.

(a) Let G be a graph with average distance A. What is the smallest diameter possible for

such a graph? Provide a graph G that attains this minimum and prove that any smaller

is impossible.

(b) Give a graph G with average distance A and diameter at least 3 ·A.

(c) Repeat (b) for a diameter of at least 100 · A. (You don’t need to draw the graph, just

describe it and briefly justify why the diameter is at least 100 times larger than than

the average distance.) Describe how you could extend this to an arbitrarily large factor

C ·A.

(d) Discuss what the diameter and average distance of a social network (given as a graph)

might represent. What might it mean if the diameter is very similar to the average

distance? What might it mean if the diameter is much greater?

8. Consider a graph G on n nodes.

(a) What is the fewest number of edges such that G is connected? Give an example with

that many edges, and argue why any fewer edges must result in a graph G which is

disconnected.

4

(b) What is the fewest number of edges such that any two nodes in G have a shortest path

length of 1? Again, prove that this is the minimum by arguing that no fewer is possible

and that the number you give is attainable.

(c) Repeat part (b) for a shortest path length of at most 2.

Part 3: Coding: Shortest Paths

9. For this problem you will submit both hw1.py, as well as written/graphical answers in your

main pdf submission. Please follow instructions carefully. Please don’t hesitate to contact us

with any questions.

(a) In hw1.py, implement the UndirectedGraph class, and implement a function create graph(n,

p) that produces an UndirectedGraph with n nodes where each pair of nodes is con-

nected by an edge with probability p.

(b) Implement a general shortest-path algorithm for graphs, as described in lecture, that

works on your graph. In hw1.py, include a function shortest path(G, i, j) that

outputs the length of the shortest path from node i to j in your graph G. Make sure

to handle the case where the graph is disconnected (i.e. no shortest path exists) by

outputting −1.

(c) In hw1.py, implement avg shortest path(G, num samples=1000), to estimate the av-

erage shortest path between a random pair of two (connected) nodes in the graph, by

taking the average over num samples random pairs of (connected) nodes.

Next, construct a graph for n = 1000 and p = 0.1. Run avg shortest path on your

graph, taking num samples=1000, and include your estimate (a number) in your written

pdf submission. Does it seem reasonable? Briefly justify your answer.

(d) For n = 1000, run your average shortest-path algorithm for many values of p. Specifically,

choose p from p = 0.01 to p = 0.04 using .01 increments, and then p = 0.05 to p = 0.5

using .05 increments). Plot the average shortest path as a function of p and include the

graph or image in your main .pdf file.

Note: For p = 0.01 there is actually a small but reasonable chance (around 4%) to

produce a disconnected graph. If this occurs, resample and produce a connected graph

for the purposes of gathering data.

(e) Intuitively explain the behavior of the data you found; specifically, as p increases (in

particular, look at the larger values, e.g. 0.3 and above), what function f(p) does the

average shortest path length asymptotically approach? Justify why it behaves this way.

10. Now run your code on the Facebook social network data available at:

http://snap.stanford.edu/ data/egonets-Facebook.html

(a) In hw1.py, implement create fb graph. In particular, you should refer to the file

“facebook combined.txt.gz”; the data is formatted as a list of undirected edges between

4,039 nodes, numbered 0 through 4038. You will need to parse this data as part of your

code; knowing how to do this will be useful for subsequent assignments!

You do not need to submit ‘facebook combined.txt’ on Gradescope; the autograder has

a copy. (Submit hw1.py and any dependencies only.)

5

(b) Repeat the same analysis as in part 9(c) (i.e. run your algorithm on 1000 random

pairs of nodes and determine the average shortest path length). Include your code in

hw1.py. Include your estimate (a number) in your written pdf submission. Does it seem

reasonable? Briefly justify your answer.

(c) For the Facebook data, estimate the probability p that two random nodes are connected

by an edge. Explain how you computed p.

(d) Is the average shortest path length of the Facebook data greater than, equal to, or less

than you would expect it to be if it were a random graph with the same number of nodes

and value of p? (To answer this, you may wish to run your code from question (8c) using

the p you determined in part (9b) and 4039 nodes.) Explain why you think this is the

case.

6

学霸联盟

Homework 1

Instructor: Rafael Pass TAs: Cody Freitag, Benjamin Chan

Due: March 3, 2021, 11:59 pm Eastern Time

Homework Policies and Guidelines:

Submission: Your written homework solutions must be typed and submitted as a single .pdf file on Gradescope.

You must additionally submit all relevant files specified in the assignment for all coding problems, in the appropriate

format. The format is important because your code will be partially graded by an autograder. Template .tex and

.py files will be provided containing an outline for your submission.

Late Days: Each student may use four “late days” in total for the first three assignments in the semester, each

of which grants a 24-hour extension to an assignment’s due date. Late work beyond this limit will still be accepted

and graded until grades have been released for that assignment, but (unless discussed in advance with the TA and/or

instructor) will have a negative impact on final grades.

Collaborations: You may work in groups of up to 3 students. Every member of the group must list all other

collaborators at the top of their assignment. (Note: the maximum size of a connected component of groups must be

3. If A,B, and C work together, it must not be the case that A and D work together.)

Your submitted answers, explanations, and discussion for all written questions in the pdf must be your

own, individual, unique solutions. You will receive ZERO points for written explanations which are copied

verbatim or copied with minor changes (up to the discretion of the TAs)—either from another group member or from

a cited online source. You will also receive ZERO points for submitting code which is copied verbatim or with minor

changes (up to the discretion of the TAs) from an online source. You may share and even submit the same code,

examples, figures, and graphs with your collaborators, but ALL explanations must be your own. Additionally, you

may make use of published material (papers, Github, Wikipedia, etc.), provided that you acknowledge and specifically

cite all sources used. Still, this does not give you permission to copy code/ explanations from an online source. It is

considered a violation of academic integrity to submit a problem solution that you are unable to explain orally to a

member of the course staff.

How to receive credit: You must justify all answers to receive credit unless specified otherwise. We will

do our best to make clear the level of justification we expect for each problem. For coding questions, please turn in

complete, executable code for each part of the question that asks for an implementation. All coding questions will

also include a written component which you will include in the main .pdf file. Using Python is required. We will not

grade code based on style, but we may mark down code if we are unable to understand what it is doing. You may

use standard libraries to implement data structures such as graphs, but, unless otherwise specified, you may not use

pre-existing implementations of any algorithms without express permission from the TAs. (If a problem asks you to

implement X and you use a package that implements X for you, you will not get credit.)

Grading: There will be four homeworks throughout the semester. Each homework (and each problem within

each homework) will receive an associated weight specified by a number of points. Your raw score at the end of the

semester will be the sum of points earned divided by the total number of available points. If your raw score is greater

than 94%, you are guaranteed to get at least an A, 90% for A-, 87% for B+, 84% for B, and so on. We reserve the

right to lower the cutoffs (but we will not raise them).

There will additionally be optional bonus problems on some assignments. These will not be factored into your

raw point totals, but will be factored in after computing your raw score to determine your final grade (for getting an

A+, or possibly bumping up 1 or 2 letter grades).

1

Part 0: Logistics

Slack: Join the slack channel for the course, via the following link: SLACK

Collaborators: If you need help finding a group to collaborate on the assignments with, you can

use Slack and/ or fill out THIS GOOGLE FORM. Cody will periodically match people who fill out

this form before HW1 is due.

Policies: Read the full homework policies and guidelines above. If there are any questions, please

ask them on slack before this first homework is due.

Submitting on Gradescope: All homeworks will be released on Canvas, and submitted on

Gradescope. In the process of submitting on Gradescope, please be sure to match your submission

pages to problem numbers. (This makes grading much easier; otherwise we have to do it for you).

When submitting code on Gradescope, please make sure the preliminary autograder correctly eval-

uates your submission; otherwise you will receive an incorrect grade. Finally, when submitting code

on Gradescope, you have the option of submitting individually, or as a group; take your pick.

Part 1: Game Theory

1. For each of the following three two-player games, find (i) all strictly dominant strategies, (ii)

the action profiles which survive iterative removal of strictly dominated strategies, and (iii)

all pure-strategy Nash equilibria. Give a brief justification for each part.

(a)

(∗, L) (∗, R)

(U, ∗) (5, 4) (4, 5)

(D, ∗) (4, 4) (0, 0)

(b)

(∗, L) (∗, R)

(U, ∗) (2, 2) (2, 1)

(D, ∗) (3, 2) (0, 3)

(c)

(∗, L) (∗, R)

(U, ∗) (6, 5) (4, 5)

(D, ∗) (5, 4) (2, 2)

2. Consider the two-player game given by the following payoff matrix:

(∗, L) (∗,M) (∗, R)

(t, ∗) (-1, 2) (5, 1) (0, 0)

(m, ∗) (1, 2) (-1, 0) (6, 2)

(b, ∗) (4, 1) (3, 1) (2, 0)

(a) Does either player have a strictly dominant strategy? If so, which player, what strategy,

and why? If not, what is the smallest number of entries in the payoff matrix which would

need to be changed so that some player did have a strictly dominant strategy? Justify

why this is the minimum, i.e. there is no smaller value that works.

2

(b) What are player 1’s and player 2’s best-response sets given the action profile (m,L)?

Explain in words why these are the best responses.

(c) Find all pure-strategy Nash equilibria for this game. (Argue why all that you wrote

are PNEs and why there are no others.) Describe how best-response dynamics might

converge to each pure-strategy Nash equilibria.

3. (a) Prove the following: If player 1 in a two-person game has a dominant strategy s1, then

there is a pure-strategy Nash equilibrium in which player 1 plays s1 and player 2 plays

a best response to s1. (Your proof should be near the level of formality used in the

book. Part of the point of this problem is to get familiar with formally arguing about

the definitions provided.)

(b) Is the equilibrium from part (a) necessarily a unique pure-strategy Nash equilibrium?

Justify your answer.

(c) In particular, can there also exist a pure-strategy Nash equilibrium where player 1 does

not play s1? Justify your answer.

(d) If s1 is instead a strictly dominant strategy for player 1, how do the answers to (a)-(c)

change? Provide proper justifications for each part.

4. Formulate a normal-form game (as a payoff matrix) that has a unique pure-strategy Nash

equilibrium, but for which best-response dynamics does not always converge (i.e. there are

possible starting states for which BRD will not converge). Justify your answer. (Hint: Try

modifying a game where BRD does not converge to give it a unique PNE.)

5. Consider the following two-person game between a kicker (row player) and a goalie (column

player). Before the penalty kick, the kicker can decide to either kick to the left, middle, or

right, and the goalie can decide to either guard left, middle, or right. Based on what each

player decides, they have the following payoffs:

GL GM GR

KL (-1, 1) (-0.5, 0.5) (1,-1)

KM (0.5, -0.5) (-1,1) (0.5, -0.5)

KR (1,-1) (-0.5, 0.5) (-1,1)

Intuitively, this says that the goalie blocks the kick if they both choose the same direction.

The kicker scores a goal if they choose opposite directions. The goalie has a slight advantage

to guard the middle (it can better react if the kicker chooses left or right). And the kicker

has a slight advantage if it kicks middle and the goalie commits to left or right.

(a) Prove that there is no pure-strategy Nash equilibrium in this game.

(b) Suppose each player chooses each action uniformly at random (so 1/3 probability for

each available choice). Compute the expected utility for each player.

(c) The kicker notices that kicking to the middle is not working out very well for her, so

she decides to randomly kick to the left or right instead (each with probability 1/2).

Compute the goalie’s strategy that maximizes its expected utility. Specifically, provide

3

probabilities xL, xM , xR (such that xL + xM + xR = 1) where xL is the probability the

goalie chooses GL, xM for GM, and xR for GR. Then compute the expected utility for

the goalie under those probabilities. Justify why the value you computed is maximal,

i.e. is a best response.

(d) Bonus (and a hint for the previous question): Prove there will always exist a “pure”

best response to any mixed strategy above, where the goalie plays one of the actions

with probability 1.

(e) Prove that the mixed action profile from part (c) is a Nash equilibria. Namely, neither

player has a (strictly) profitable deviation.

Part 2: Graph Theory

Note: Unless stated otherwise, please assume for any problem involving graphs that we refer to

undirected and unweighted graphs.

6. Given a graph, we call a node x in this graph pivotal for some pair of nodes y and z if x (not

equal to y or z) lies on every shortest path between y and z.

(a) Give an example of a graph in which every node is pivotal for at least one pair of nodes.

Explain your answer.

(b) For any integer c ≥ 1, construct a graph where every node is pivotal for at least c

different pairs of nodes. That is, if I give you any value for c ≥ 1, your explanation

should tell me how to construct such a graph for that c. Explain your answer.

(c) Give an example of a graph having at least four nodes in which there is a single node x

which is pivotal for every pair of nodes not including x. Explain your answer.

7. Given some connected graph, let the diameter of a graph be the maximum distance (i.e.

shortest path length) between any two nodes. Let the average distance be the expected

shortest path length between a randomly selected pair of distinct nodes.

(a) Let G be a graph with average distance A. What is the smallest diameter possible for

such a graph? Provide a graph G that attains this minimum and prove that any smaller

is impossible.

(b) Give a graph G with average distance A and diameter at least 3 ·A.

(c) Repeat (b) for a diameter of at least 100 · A. (You don’t need to draw the graph, just

describe it and briefly justify why the diameter is at least 100 times larger than than

the average distance.) Describe how you could extend this to an arbitrarily large factor

C ·A.

(d) Discuss what the diameter and average distance of a social network (given as a graph)

might represent. What might it mean if the diameter is very similar to the average

distance? What might it mean if the diameter is much greater?

8. Consider a graph G on n nodes.

(a) What is the fewest number of edges such that G is connected? Give an example with

that many edges, and argue why any fewer edges must result in a graph G which is

disconnected.

4

(b) What is the fewest number of edges such that any two nodes in G have a shortest path

length of 1? Again, prove that this is the minimum by arguing that no fewer is possible

and that the number you give is attainable.

(c) Repeat part (b) for a shortest path length of at most 2.

Part 3: Coding: Shortest Paths

9. For this problem you will submit both hw1.py, as well as written/graphical answers in your

main pdf submission. Please follow instructions carefully. Please don’t hesitate to contact us

with any questions.

(a) In hw1.py, implement the UndirectedGraph class, and implement a function create graph(n,

p) that produces an UndirectedGraph with n nodes where each pair of nodes is con-

nected by an edge with probability p.

(b) Implement a general shortest-path algorithm for graphs, as described in lecture, that

works on your graph. In hw1.py, include a function shortest path(G, i, j) that

outputs the length of the shortest path from node i to j in your graph G. Make sure

to handle the case where the graph is disconnected (i.e. no shortest path exists) by

outputting −1.

(c) In hw1.py, implement avg shortest path(G, num samples=1000), to estimate the av-

erage shortest path between a random pair of two (connected) nodes in the graph, by

taking the average over num samples random pairs of (connected) nodes.

Next, construct a graph for n = 1000 and p = 0.1. Run avg shortest path on your

graph, taking num samples=1000, and include your estimate (a number) in your written

pdf submission. Does it seem reasonable? Briefly justify your answer.

(d) For n = 1000, run your average shortest-path algorithm for many values of p. Specifically,

choose p from p = 0.01 to p = 0.04 using .01 increments, and then p = 0.05 to p = 0.5

using .05 increments). Plot the average shortest path as a function of p and include the

graph or image in your main .pdf file.

Note: For p = 0.01 there is actually a small but reasonable chance (around 4%) to

produce a disconnected graph. If this occurs, resample and produce a connected graph

for the purposes of gathering data.

(e) Intuitively explain the behavior of the data you found; specifically, as p increases (in

particular, look at the larger values, e.g. 0.3 and above), what function f(p) does the

average shortest path length asymptotically approach? Justify why it behaves this way.

10. Now run your code on the Facebook social network data available at:

http://snap.stanford.edu/ data/egonets-Facebook.html

(a) In hw1.py, implement create fb graph. In particular, you should refer to the file

“facebook combined.txt.gz”; the data is formatted as a list of undirected edges between

4,039 nodes, numbered 0 through 4038. You will need to parse this data as part of your

code; knowing how to do this will be useful for subsequent assignments!

You do not need to submit ‘facebook combined.txt’ on Gradescope; the autograder has

a copy. (Submit hw1.py and any dependencies only.)

5

(b) Repeat the same analysis as in part 9(c) (i.e. run your algorithm on 1000 random

pairs of nodes and determine the average shortest path length). Include your code in

hw1.py. Include your estimate (a number) in your written pdf submission. Does it seem

reasonable? Briefly justify your answer.

(c) For the Facebook data, estimate the probability p that two random nodes are connected

by an edge. Explain how you computed p.

(d) Is the average shortest path length of the Facebook data greater than, equal to, or less

than you would expect it to be if it were a random graph with the same number of nodes

and value of p? (To answer this, you may wish to run your code from question (8c) using

the p you determined in part (9b) and 4039 nodes.) Explain why you think this is the

case.

6

学霸联盟

- 留学生代写
- Python代写
- Java代写
- c/c++代写
- 数据库代写
- 算法代写
- 机器学习代写
- 数据挖掘代写
- 数据分析代写
- Android代写
- html代写
- 计算机网络代写
- 操作系统代写
- 计算机体系结构代写
- R代写
- 数学代写
- 金融作业代写
- 微观经济学代写
- 会计代写
- 统计代写
- 生物代写
- 物理代写
- 机械代写
- Assignment代写
- sql数据库代写
- analysis代写
- Haskell代写
- Linux代写
- Shell代写
- Diode Ideality Factor代写
- 宏观经济学代写
- 经济代写
- 计量经济代写
- math代写
- 金融统计代写
- 经济统计代写
- 概率论代写
- 代数代写
- 工程作业代写
- Databases代写
- 逻辑代写
- JavaScript代写
- Matlab代写
- Unity代写
- BigDate大数据代写
- 汇编代写
- stat代写
- scala代写
- OpenGL代写
- CS代写
- 程序代写
- 简答代写
- Excel代写
- Logisim代写
- 代码代写
- 手写题代写
- 电子工程代写
- 判断代写
- 论文代写
- stata代写
- witness代写
- statscloud代写
- 证明代写
- 非欧几何代写
- 理论代写
- http代写
- MySQL代写
- PHP代写
- 计算代写
- 考试代写
- 博弈论代写
- 英语代写
- essay代写
- 不限代写
- lingo代写
- 线性代数代写
- 文本处理代写
- 商科代写
- visual studio代写
- 光谱分析代写
- report代写
- GCP代写
- 无代写
- 电力系统代写
- refinitiv eikon代写
- 运筹学代写
- simulink代写
- 单片机代写
- GAMS代写
- 人力资源代写
- 报告代写
- SQLAlchemy代写
- Stufio代写
- sklearn代写
- 计算机架构代写
- 贝叶斯代写
- 以太坊代写
- 计算证明代写
- prolog代写
- 交互设计代写
- mips代写
- css代写
- 云计算代写
- dafny代写
- quiz考试代写
- js代写
- 密码学代写
- ml代写
- 水利工程基础代写
- 经济管理代写
- Rmarkdown代写
- 电路代写
- 质量管理画图代写
- sas代写
- 金融数学代写
- processing代写
- 预测分析代写
- 机械力学代写
- vhdl代写
- solidworks代写
- 不涉及代写
- 计算分析代写
- Netlogo代写
- openbugs代写
- 土木代写
- 国际金融专题代写
- 离散数学代写
- openssl代写
- 化学材料代写
- eview代写
- nlp代写
- Assembly language代写
- gproms代写
- studio代写
- robot analyse代写
- pytorch代写
- 证明题代写
- latex代写
- coq代写
- 市场营销论文代写
- 人力资论文代写
- weka代写
- 英文代写
- Minitab代写
- 航空代写
- webots代写
- Advanced Management Accounting代写
- Lunix代写
- 云基础代写
- 有限状态过程代写
- aws代写
- AI代写
- 图灵机代写
- Sociology代写
- 分析代写
- 经济开发代写
- Data代写
- jupyter代写
- 通信考试代写
- 网络安全代写
- 固体力学代写
- spss代写
- 无编程代写
- react代写
- Ocaml代写
- 期货期权代写
- Scheme代写
- 数学统计代写
- 信息安全代写
- Bloomberg代写
- 残疾与创新设计代写
- 历史代写
- 理论题代写
- cpu代写
- 计量代写
- Xpress-IVE代写
- 微积分代写
- 材料学代写
- 代写
- 会计信息系统代写
- 凸优化代写
- 投资代写
- F#代写
- C#代写
- arm代写
- 伪代码代写
- 白话代写
- IC集成电路代写
- reasoning代写
- agents代写
- 精算代写
- opencl代写
- Perl代写
- 图像处理代写
- 工程电磁场代写
- 时间序列代写
- 数据结构算法代写
- 网络基础代写
- 画图代写
- Marie代写
- ASP代写
- EViews代写
- Interval Temporal Logic代写
- ccgarch代写
- rmgarch代写
- jmp代写
- 选择填空代写
- mathematics代写
- winbugs代写
- maya代写
- Directx代写
- PPT代写
- 可视化代写
- 工程材料代写
- 环境代写
- abaqus代写
- 投资组合代写
- 选择题代写
- openmp.c代写
- cuda.cu代写
- 传感器基础代写
- 区块链比特币代写
- 土壤固结代写
- 电气代写
- 电子设计代写
- 主观题代写
- 金融微积代写
- ajax代写
- Risk theory代写
- tcp代写
- tableau代写
- mylab代写
- research paper代写
- 手写代写
- 管理代写
- paper代写
- 毕设代写
- 衍生品代写
- 学术论文代写
- 计算画图代写
- SPIM汇编代写
- 演讲稿代写
- 金融实证代写
- 环境化学代写
- 通信代写
- 股权市场代写
- 计算机逻辑代写
- Microsoft Visio代写
- 业务流程管理代写
- Spark代写
- USYD代写
- 数值分析代写
- 有限元代写
- 抽代代写
- 不限定代写
- IOS代写
- scikit-learn代写
- ts angular代写
- sml代写
- 管理决策分析代写
- vba代写
- 墨大代写
- erlang代写
- Azure代写
- 粒子物理代写
- 编译器代写
- socket代写
- 商业分析代写
- 财务报表分析代写
- Machine Learning代写
- 国际贸易代写
- code代写
- 流体力学代写
- 辅导代写
- 设计代写
- marketing代写
- web代写
- 计算机代写
- verilog代写
- 心理学代写
- 线性回归代写
- 高级数据分析代写
- clingo代写
- Mplab代写
- coventorware代写
- creo代写
- nosql代写
- 供应链代写
- uml代写
- 数字业务技术代写
- 数字业务管理代写
- 结构分析代写
- tf-idf代写
- 地理代写
- financial modeling代写
- quantlib代写
- 电力电子元件代写
- atenda 2D代写
- 宏观代写
- 媒体代写
- 政治代写
- 化学代写
- 随机过程代写
- self attension算法代写
- arm assembly代写
- wireshark代写
- openCV代写
- Uncertainty Quantificatio代写
- prolong代写
- IPYthon代写
- Digital system design 代写
- julia代写
- Advanced Geotechnical Engineering代写
- 回答问题代写
- junit代写
- solidty代写
- maple代写
- 光电技术代写
- 网页代写
- 网络分析代写
- ENVI代写
- gimp代写
- sfml代写
- 社会学代写
- simulationX solidwork代写
- unity 3D代写
- ansys代写
- react native代写
- Alloy代写
- Applied Matrix代写
- JMP PRO代写
- 微观代写
- 人类健康代写
- 市场代写
- proposal代写
- 软件代写
- 信息检索代写
- 商法代写
- 信号代写
- pycharm代写
- 金融风险管理代写
- 数据可视化代写
- fashion代写
- 加拿大代写
- 经济学代写
- Behavioural Finance代写
- cytoscape代写
- 推荐代写
- 金融经济代写
- optimization代写
- alteryxy代写
- tabluea代写
- sas viya代写
- ads代写
- 实时系统代写
- 药剂学代写
- os代写
- Mathematica代写
- Xcode代写
- Swift代写
- rattle代写
- 人工智能代写
- 流体代写
- 结构力学代写
- Communications代写
- 动物学代写
- 问答代写
- MiKTEX代写
- 图论代写
- 数据科学代写
- 计算机安全代写
- 日本历史代写
- gis代写
- rs代写
- 语言代写
- 电学代写
- flutter代写
- drat代写
- 澳洲代写
- 医药代写
- ox代写
- 营销代写
- pddl代写
- 工程项目代写
- archi代写
- Propositional Logic代写
- 国际财务管理代写
- 高宏代写
- 模型代写
- 润色代写
- 营养学论文代写
- 热力学代写
- Acct代写
- Data Synthesis代写