Chapter 14 Project

How Connected are You?

Merriam-Webster defines social media as "forms of electronic communication through which users create online communities to share information, ideas, personal messages, and other content." It's hard to live in the modern world and not belong to some type of social media community (such as Facebook, Snapchat, Twitter, Instagram, Pinterest… the list is long).

In this project, you will use graphs to visualize and think about your community in social media. You are going to create a graph using a social media site where both parties agree to be connected, such as Facebook or LinkedIn. A different type of graph (that is, directed graphs, which are beyond the scope of this chapter) is created when you consider one-sided connections such as "following" someone on Instagram or Twitter.

As many people often have very large communities on social media, your graph will likely be a subgraph of your entire community. Using yourself as the first vertex, you will create a graph that consists of at least 15 people as the vertices, but the more you can include, the better! If two people are connected via your social media, their vertices will be joined with an edge.

  1. Before you begin, anticipate why it is important for you to use a social media where both parties agree to be connected when constructing your graph. Describe your predictions here.

On a separate piece of paper, create graph G of your social media community. Use a minimum of 15 people to whom you are "connected" and whom are also "connected" to you. The more connections you include, the better idea you will get of your community. Begin with yourself as the first vertex. Using the person's name, label each of the vertices. If any two people are connected via your social media, their vertices should be joined with an edge. If you don't have a social media account where connections are two-way, you will need to ask a friend who has one if you can create their graph of connections and answer the questions based on their graph.

Graph of social media connections

A graph with the following nodes, listed in order by the number of connections:

  • MG is connected to AR, AW, BS, DF, DJ, EA, ED, GI, GR, JA, JG, LD, PM, RA, and TG

  • RA is connected to DF, DJ, EA, GR, LD, MG, and PM

  • GR is connected to AR, JG, LD, MG, PM, and RA

  • PM is connected to AW, DF, DJ, EA, GR, and MG

  • LD is connected to AW, DF, GR, MG, and RA

  • AR is connected to ED, GR, JG, and MG

  • AW is connected to DF, LD, MG, and PM

  • DF is connected to AW, LD, MG, and RA

  • BS is connected to JA, MG, and TG

  • DJ is connected to MG, PM, and RA

  • EA is connected to MG, PM, and RA

  • JA is connected to BS, MG, and TG

  • JG is connected to AR, GR, and MG

  • TG is connected to BS, JA, and MG

  • ED is connected to AR and MG

  • GI is connected to MG

Answer the following questions about your graph G.

  1. What was the most difficult part of constructing G?

  2. How many vertices does G have?

  3. How many edges does G have?

  4. Is G connected? Why or why not?

  5. Is G connected if you remove your vertex from the graph?

  6. Suppose G becomes a disconnected graph upon removing your vertex, what does that mean in social terms about your groups of connections?

Now create a new graph on a separate piece of paper in which you remove your vertex from the graph G. Use this new graph F to answer the following questions.

  1. What can you say about the neighborhoods of the vertices in F?

  2. Which vertex in F has the largest degree? What is its degree?

  3. What can you say in terms of social media about the person with the largest vertex degree in F?

  4. Find the largest complete subgraph in F.

  5. What does this subgraph represent in terms of social media?

  6. Find the chromatic number χ of F.

  7. Find a vertex coloring of F with χ colors.

  8. What can you say about a group of people in F whose vertices all have the same color in your coloring?

  9. What would it mean in terms of the social media if F has a high chromatic number?

  10. What would it mean in terms of the social media if F has a low chromatic number?

  11. Find a minimum vertex cover of F.

  12. Why might a minimum vertex cover be useful to know if friends of yours were using social media to organize a surprise party for you?

  13. Find a spanning tree of F or, if F is not connected, find a spanning tree of the largest connected subgraph of F.

  14. How long is the longest path in your spanning tree?

  15. What does the longest path represent in terms of your social media connections?

  16. How many leaves are on your spanning tree?

  17. Does the number of leaves on your spanning tree indicate how many social media connections you have? Why or why not?

Consider the bipartite graph H formed by your social media connections on one side and the months of the year on the other side. A person is joined to their birthday month with an edge.

  1. When would this bipartite graph H have a matching from the months of the year into the people?

  2. When would H have a matching from the people into the months?

  3. Finally, think about what each of the graphs G, F, and H say about you and social media. Describe at least one practical way that you could use the information you've discovered in one of the the three graphs.