Numb3rs 318: Democracy

After several researchers die from 'accidents,' the team uses organizational theory to find other researchers working with the deceased. A conspiracy to defraud elections is uncovered, and Charlie publishes a paper to make the method of defraud common knowledge.

Social Networks

By analyzing how people are connected to each other in certain social contexts mathematicians have been able to study things as diverse as the spread of diseases and games like six degrees of Kevin Bacon. A social network is simply a collection of people and certain relationships between those people. To represent the network a graph is used. A graph consists of a set of vertices and edges (not necessarily straight lines) connecting vertices. Social networks represent people as vertices, relationships between people as edges. Below is a small example of a made up social network where two individuals are connected by an edge if they are friends. Real social networks are much more complicated; beside is a social network from a real high school where two individuals are connected if they are dating or have dated each other. You can read more about the dating network and see other networks here.

Social networks are common facets of our lives, and it is likely that you belong to some specific network that some scientist has studied. Many social networking sites like Facebook and Myspace have been the subject of scientific studies. Also, vertices are not just limited to people; the internet can be viewed as a network with edges representing links. Some scientists have even studied the interaction of proteins in your body as a network.

Many different network properties can be studied mathematically. A basic property is the distance between two vertices. If each edge has length 1, the distance between two vertices is the length of the shortest path connecting those vertices. Another property is the diameter of the network, which is the longest shortest path in the network. Another basic property is the degree of a vertex, i.e. the number of edges that touch a vertex. The distribution of the degrees of a network is another important property. Many networks such as social networks, protein interaction networks and the internet have been found to have power law distributions, that is the probability that a vertex is connected to n other nodes is proportional to n-a for positive a. Other properties of graphs can be found using advanced techniques. There are algorithms to find the most influential vertices in a network, and algorithms that can find closely related vertices in a network. In fact some algorithms can identify web pages which are about related topics without knowing the contents of the webpages just by analyzing links.

Identifying important vertices in a network is very useful. Search engine companies spend millions of dollars trying to find better ways to do this. One common strategy for finding important vertices is to take a random walk on the graph. This is done by starting at a vertex and then choosing at random an edge to use to walk to another vertex. If you randomly walk to a page very often it tends to mean that the page is important.
Activity 1
Make your friendship network. What is the diameter? What is the largest degree? You might also want to explore your network on any social networking sites you belong to.

Small Worlds and Scale Free Networks

Networks whose degree distributions obey power laws are often said to be scale free, which means that on average vertices are close to each other. This means that the diameter of a graph and the degree distribution are often related to each other. For social networks this relationship is particularly famous thanks to the game six degrees of Kevin Bacon which is a play on the idea of six degrees of separation, that you can find a string of at most six mutual acquaintances between any two people on the planet. It is unknown whether or not this idea is true, but it is based on an experiment conducted by the psychologist Stanley Milgram in the 1960's. The phenomenon of being able to get from one vertex to any other in a small number of steps is known as the small world phenomenon
Activity 2: To get an idea of how small the world might be we'll try a thought experiment. Let's take the world's population to be 6 billion, and suppose that each person knows 100 other people. We start with you, so at distance 0 we have 1 person. At distance 1 from you we have 100 people. At distance 2 we have 10,000 people. You'd be right to object that many of the people you know also know each other, so 1000 is too big. Let's say that each of your acquaintances only adds 20 people who weren't already distance 1 from you, and this property holds for all higher distances. So at distance 2 there are 2,000 people, at distance 3 there are 40,000 people, etc. How far away from you do you have to go to encompass everyone on the planet? Play around with the number of people each person knows and the number of new people added per person at each step; you might be surprised at how small you can make these numbers and still be able to reach everyone in the world in a small number of steps.