Lab 4: Distribution & Streaming; Social Networks
Lab 4: Distribution & Streaming; Social Networks
NetID: <Please fill in>
Part 1: Network Representation using Graphs
Part 1: Network Representation using Graphs
We will use circles to represent nodes, and lines between these circles (called "edges") to represent connections between nodes. These diagrams containing nodes and edges are called "graphs".
In a computer network the nodes (also called vertices) represent computers and the edges represent links between them.
In a social network the nodes (also called vertices) represent people and the edges represent relationships between them.
In a computer network the nodes (also called vertices) represent computers and the edges represent links between them.
In a social network the nodes (also called vertices) represent people and the edges represent relationships between them.
A generic network
A generic network
In[]:=
UndirectedGraph{s->a,a->d},
Out[]=
A computer network
A computer network
In[]:=
UndirectedGraph{laptop->router,router->server},
Out[]=
A friendship network (social network)
A friendship network (social network)
In[]:=
UndirectedGraph{harry->ron,ron->hermione,hermione->harry},
Out[]=
Part 2: Distribution of Content in a Computer Network
Part 2: Distribution of Content in a Computer Network
Link Bandwidth represented using Weighted Graphs
Link Bandwidth represented using Weighted Graphs
Let’s start this lab with computer networks. The nodes represent computers, and lines between the nodes or "edges" represent connections/links between computers.
We also have “weights” associated with each of the edges represented as a number along the edge.
The weight represents the network capacity of the connection (also called "bandwidth" of the link).
We also have “weights” associated with each of the edges represented as a number along the edge.
The weight represents the network capacity of the connection (also called "bandwidth" of the link).
In[]:=
Graph{sa,ad},EdgeWeight{30,10},
Out[]=
Bandwidth from s to a = 30 Mbps
Bandwidth from a to d = 10 Mbps
Bandwidth from a to d = 10 Mbps
Network Capacity for Simultaneous Network Usage
Network Capacity for Simultaneous Network Usage
Let’s look at how networks behave when two or more nodes are simultaneously using common links to communicate.
Here is a toy network. S1 and S2 are source nodes, and D1 and D2 are destination nodes . All network traffic has to share the link between P and .
In[]:=
Graph{s1p,s2p,pq,qd1,qd2},EdgeWeight{100,80,50,100,93.32},
Out[]=
Problem 1
Problem 1
Let's say that S1 is trying to send a large file to D1. What is the speed at which S1 can send the file to D1? Note: S2 is not using the link at all.
Answer
Answer
Problem 2
Problem 2
Now, let's say that S1 is sending a large file to D1, and S2 is also sending a large file to D2 simultaneously. At what speed can S1 send the file to D1? At what speed can S2 send its file to D2?
Answer
Answer
Problem 3
Problem 3
Now, let’s reduce the capacity of the link between Q and D1.
Out[]=
Let’s say that S1 is sending a large file to D1, and S2 is also sending a large file to D2 simultaneously. At what speed can S1 send the file to D1? At what speed can S2 send its file to D2?
Answer
Answer
Problem 4
Problem 4
Next, let’s look at a network where there are several internet customers in a neighborhood, that connect to the same ISP’s network.
Out[]=
The ISP has promised “up to 10 Mbps” for all customers in the neighborhood. Can the ISP keep up that promise at all times? If not, can it meet this promised speed sometimes? Does the ISP need to make changes to its network? Please explain your answer in one or two sentences.
Answer
Answer
Problem 5
Problem 5
Three new houses were built in the neighborhood, and everyone paid the same ISP for their home internet service. Let’s see what this looks like:
Out[]=
Again, the ISP has promised “up to 10 Mbps” for all customers in the neighborhood. Can the ISP keep up that promise at all times? If not, can it meet this promised speed sometimes? Does the ISP need to make changes to its network? Please explain your answer in one or two sentences.
Answer
Answer
Extra Credit
Extra Credit
If you are curious you can take a look at what real-world network performance looks like. You can use this website to take a quick internet speed test: speedtest.net.
◼
What was your download speed?
◼
What was your upload speed?
◼
Which server did you connect to?
◼
What was the University of Illinois IP address identified for your computer?
Answer
Answer
Part 3: Analyzing a Social Network
Part 3: Analyzing a Social Network
A Social Network Graph
A Social Network Graph
Evaluate the following code to see a simple graph representing a social network. The nodes represent people and the edges represent friendship between them.
Try to answer the following questions manually by observing the graph and then see if your answers match what the computer finds for you.
Problem 6
Problem 6
How many people are there on this network? How many distinct friendships are represented?
(You can represent friendships as “farhan and gloria”, “gloria and dave”, etc.)
(You can represent friendships as “farhan and gloria”, “gloria and dave”, etc.)
Answer
Answer
Problem 7
Problem 7
What is the maximum number of hops needed to get from one person to another i.e. what is the diameter of the graph?
Answer
Answer
Problem 8
Problem 8
What is the minimum number of hops you have to traverse to get from person farhan to alice? (i.e. what is the shortest distance between farhan and alice?)
Trace out this path (list all the nodes along the shortest path from node farhan to alice).
Trace out this path (list all the nodes along the shortest path from node farhan to alice).
Answer
Answer
Problem 9
Problem 9
Who is the person with the most friends (i.e. the node with the highest vertex degree - the hub of the graph) and who is the person with the least number of friends (the node with the lowest vertex degree) on this social network?
Answer
Answer
Try for other people in the graph:
Problem 10
Problem 10
Is it possible to find a path from every person to every other person in the friendsGraph? (i.e. is this graph connected?)
Answer
Answer
Evaluate the code below to see a different example of a graph. Is this graph connected?
Answer
Answer
Part 3: Social Networks as Small World Graphs
Part 3: Social Networks as Small World Graphs
Human relationships—the social connections—form what is called a small-world graph, named after the expression, “It’s a small world!”
Small world graphs have certain properties:
◼
small diameter and typical path length,
◼
local cliques,
◼
densely connected,
Social networks inherit properties of small world graphs and capture human relationship
◼
Small Diameter: Any two people in the network are separated by short paths. Most of the nodes in the graph are reachable in a small number of hops (everyone is pretty-well connected)
◼
Local Cliques: These graphs have lots of cliques around nodes (a person’s friends tend to know one another)
◼
Densely Connected: some nodes have high degree (the influencers!)
Here is an example of a social network graph from the Stanford Network Analysis Project. It represents one of the ten networks in this dataset consisting of ‘circles’ (or ‘friends lists’) from Facebook.
Evaluate the following code to visualize the graph.
Evaluate the following code to visualize the graph.
Problem 11
Problem 11
What is the maximum number of hops needed to get from one person to another i.e. what is the diameter of the graph? (Hint: Use GraphDiameter)
Answer
Answer
Problem 12
Problem 12
Answer
Answer
Answer
Answer
Can you find all the cliques with exactly 15 nodes (groups of exactly 15 Facebook friends where every member of the group is connected to every other member)? How many such groups are there?
Answer
Answer
Problem 13
Problem 13
Use the GraphHub function to find the node with the highest vertex degree ... possibly the “Influencer” in the network.
Answer
Answer
Evaluate the following piece of code to highlight the influencer in the graph.
Extra Credit
Extra Credit
The Wisdom and/or Madness of the Crowds
Here is a paper published in Nature that talks about social learning strategies that can regulate the tug-of-war between the collective “wisdom” of a group of individuals and their maladaptive “herding”.
Here is a paper published in Nature that talks about social learning strategies that can regulate the tug-of-war between the collective “wisdom” of a group of individuals and their maladaptive “herding”.
You will find an interactive online game called “The Wisdom and/or Madness of the Crowds” here: https://ncase.me/crowds/
Play the game and jot down three things you learned about human networks.
Answer
Answer
◼
◼
◼
Submitting your work
Submitting your work
1
.Ensure you have filled in your NetID at the top of the notebook
2
.Save the notebook as a PDF file (Alternately, "Print to PDF" but please ensure the PDF looks ok and is not garbled)
3
.Upload to Gradescope
4
.Just to be sure that your submission was received, maybe email your TA (sattwik2@illinois.edu) that you have submitted.