Problem 4 In this problem, we are going to investigate how our neighbors in an information network differ from us. There are various network properties tiesbut to start we will begin with some of the simplest: the node degrees. that we could investigate centrality, tie strengths, structural proper To be concrete, let G V, E) be a graph representing a network of high schoolers, where each node v E V represents a high-school student, and an edge (u, v) E represents that students u and v are buddies. Let n = |V | and m = We let du denote the degree of node u. More specifically (a) How many buddies do students have on average in the arbitrary network G? If D is a random variable denoting the degree of a random student from the high school population, you can think of the answer as being the expectation E D Show your work and return the simplest expression as you can find in terms of the variables we have defined (b) Let us look at how many buddies your buddies have on average in the graph. Denote by B the randonm variable of buddies-of-buddies. Prove that TTL Hint: Count the impact of each single edge in the graph on the total number of buddies-of-buddies. Think of paths of length exactly 2. Be careful to quantify exactly what is being averaged over (c) Let us try to interpret the expression from (b) by simplifying it in terms of the degree distribution. Recall from probability theory that for a random variable X, the variance is defined as and is always non-negative Given D as above, prove that (d) What does the result from (c) actually imply in terms of your popularity compared to that of your buddies, on average? How does the interpretation differ if we instead look at a social network such as LinkedIn connections? What about a romantic liaison network, where edges denote that two partners have had sexual intercourse? What about a paper co-authorship graph, where edges denote that two people have collaborated on a publication? 3 Problem 4 In this problem, we are going to investigate how our neighbors in an information network differ from us. There are various network properties tiesbut to start we will begin with some of the simplest: the node degrees. that we could investigate centrality, tie strengths, structural proper To be concrete, let G V, E) be a graph representing a network of high schoolers, where each node v E V represents a high-school student, and an edge (u, v) E represents that students u and v are buddies. Let n = |V | and m = We let du denote the degree of node u. More specifically (a) How many buddies do students have on average in the arbitrary network G? If D is a random variable denoting the degree of a random student from the high school population, you can think of the answer as being the expectation E D Show your work and return the simplest expression as you can find in terms of the variables we have defined (b) Let us look at how many buddies your buddies have on average in the graph. Denote by B the randonm variable of buddies-of-buddies. Prove that TTL Hint: Count the impact of each single edge in the graph on the total number of buddies-of-buddies. Think of paths of length exactly 2. Be careful to quantify exactly what is being averaged over (c) Let us try to interpret the expression from (b) by simplifying it in terms of the degree distribution. Recall from probability theory that for a random variable X, the variance is defined as and is always non-negative Given D as above, prove that (d) What does the result from (c) actually imply in terms of your popularity compared to that of your buddies, on average? How does the interpretation differ if we instead look at a social network such as LinkedIn connections? What about a romantic liaison network, where edges denote that two partners have had sexual intercourse? What about a paper co-authorship graph, where edges denote that two people have collaborated on a publication? 3
