xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

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

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

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

微信客服：xiaoxionga100

微信客服：ITCS521

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

学霸联盟