D

o you have a social media account? Facebook, Twitter, Instagram or even LinkedIn? Have you ever noticed that these companies make recommendations about people whom you should "friend"? How do they know who would be best? Well, the answer to that is an area of mathematics known as graph theory.

Graph theory is the study of vertices (dots) and edges (lines between nodes). For example, consider Graph 1.

In this graph you will notice that there are five vertices and six edges. Now it is important to understand that the position of the vertices is not important, only which vertices have an edge connecting them. Now imagine these vertices are people (see Graph 2) in a social network.

We can ask some questions to understand how the math of social media works. First, we can ask, Who is the most popular? Looking at this graph we notice that B and D are connected to three edges each, so each has three friends. On the other hand, A and E have two edges connected to each, or only two friends.

Next, we can ask who we should recommend as friends for E. Again we can notice that E is already friends with both C and D, eliminating them as recommendations. Both A and B are friends of D, but only B is a friend of C. So the best person to suggest as a friend would be B since they have the most friends in common with E. But suggesting A as a second alternative would be good, especially since we don't know if E is closer friends with D than C. And that is how social networks determine whom to suggest for you.

But the math for social networks does not end there. We can now think about this in terms of advertising. Suppose that you want to sell something and you want to ask people in this network to share on the social network about your product. If you as the business have to pay the individuals to share, you would want to choose as few people as you could. So what is the fewest people we can choose so that everyone is friends with at least one of our sharers? From before, we can remember that B and D were the most popular. Yet if we choose only one of them, then there will be one person who does not get shared with. So we need to choose at least two people. We could choose both B and D and would cover everyone. But is that the best choice?

There are a few more factors to consider to know if this is "best." One might be how much we have to pay B and D to share. They might require more payment than the other people since they are the most popular. Secondly, we can notice that if we choose B and D, then both C and E only get shared with once. If we were to choose B and E on the other hand, then only A gets shared with once. So that would seem a better choice. Can you now see how businesses utilize this math to determine how to advertise most effectively using social networks?

Allow me to end with a final example of how this same social network analysis can be used during our current pandemic. I will again use the same graph as in the previous business example, except we can change the edges to represent who they interact with at least once per week. In this scenario, if A is infected, how long will it take for everyone else to have been exposed? This question is a little more complicated since there are some statistics involved because each contact may not result in an infection. So to simplify, let's just suppose that half of those exposed to an infected person each week become infected themselves. Then A would infect either B or D in the first week. If B is infected, then either D or C would be infected the next week. And then everyone else would be infected by the third week. In this scenario, it only took three weeks for everyone to be infected. Similar models are among the tools scientists are trying to use to examine the spread and determine the optimal measures to limit spread.

These examples are a little simple, since we only used a small graph. But the concepts are the future of social networks, especially as we become more and more connected as a society. And hopefully this has helped you begin to see how your dots are connected.