|Facebook friend Web|
Facebook friend Web
- Friend network of a particular Facebook account. The pink indicates a "mob" of tightly interconnected friends, such as high school or college friends.
- 1 Basic Description
- 2 A More Mathematical Explanation
- 3 Teaching Materials
- 4 References
The picture above may seem like an innocent model of someone's friend network on Facebook, but it reveals plenty about how modern society operates.
First, it indicates that people inherently have preferences for who they choose to associate with. Taken in the context of economic transactions, these preferences can determine whether or not a firm, state, or country prospers economically. Think about it: there are infinite possibilities of associations, but people sometimes prefer not to associate.
Second, the pink area (which probably represents high school friends, college friends, or coworkers) indicates something called clustering, which is kind of like grouping within a group. Given the context above, grouping can be thought of as a similar preference among certain individuals. Being in groups has allowed people to protest for their rights, start a new company, take over countries, etc. The odds are more in your favor in a group if you want to achieve something.
These kinds of preferences have undoubtedly shaped our world. Therefore, it is beneficial to analyze such powerful phenomenon. In other words, social networks, or the patterns of connections between people, are of enough importance to study through mathematics.
Social network analysis (SNA) can provide valuable information about a network by answering the following questions:
- "Who is most central to a network?"
- "Who has the greatest influence in a group?
- "How many different clusters can you find in a network?"
- "Which connections are pivotal for the functioning of a group?
- "Who is Mr./Ms. Popular?"
Most importantly, this analysis allows us to make more rational decisions based on data (rather than intuition) and to make predictions about the behavior of a group. For example, if we are able to determine that in the case of an epidemic, the virus is concentrated generally around a select few, there could be something done to prevent its spread. Conversely, if we wanted to make sure an important idea would spread quickly (a pitch for a school candidate, for example) we would first target the most influential and central people.
Perhaps the easiest and most fundamental answers to all of the the questions above revolve around the concept of centrality. The most frequently used measures of network structure, therefore, are centrality measures. These include Degree, Eigenvector, Closeness and Betweenness measures of centrality. More information about these measures is found below.
Keep in mind, however, that these measures quantify characteristics of people (or whatever objects pertain to the network) rather than the network as a whole.
For illustrative and simplification purposes, these explanations will be in the context of human interactions.
Degree centrality measures how well connected a person is to a network. It does this by simply counting how many people a person is directly connected to. It seeks to measure:
- The level of influence someone can establish in a community, organization, group, etc.
- The opportunity to be influenced by someone in a community, organization, group, etc
- How exposed someone is in a network, mostly known as the index of exposure
Example: The characters in the image to the right will probably seem familiar. It is a network analyzing the ties among characters of one of William Shakespeare's famous plays, Hamlet.If you are not familiar with the play, just know that Hamlet (a prince) is the protagonist and is next in line to inherit the throne of his father, King Hamlet. However, prince Hamlet's uncle, Claudius, inherits the throne. Hamlet later finds out that Claudius was responsible for killing his father. Because Hamlet is a prince, and the protagonist of the play, the story mostly revolves around Hamlet's quest to avenge the death of his father, which involves him talking to almost all the characters in the play. It seems like prince Hamlet is rather central, right? In the most simple sense, because the he has the most ties to any character in the play (as diagrammed by the image) he has the highest degree centrality, and thus it makes sense to conceive of him as the protagonist, or main character.
Eigenvector centrality is a more sophisticated version of degree centrality that measures not only the number of people someone is connected to, but also the quality of the connections. For a connection to have quality, in this context, it means that that connection leads to lots of other connections. It is necessary because, in an intuitive sense, connections with influential people will make you more influential than non-influential connections will. Eigenvector Centrality seeks to measure:
- Who the most popular person is in the group
- How well someone is connected to the well-connected, in other words, whether they know the "right people"
Closeness centrality, without a surprise, measures how close a person is within a network.Close in this context refers to how many "friends of friends" one would need to be related to another person. A not so close relationship, for example, would be someone in California being connected to some random person in North Dakota through 1 friend who knows another friend who knows another friend...(6 intermediate friends in total) between the person in California and the person in North Dakota. The 6 in the last example indicates the degrees of separation.
A person who is well connected has, on average, fewer degrees of separation to reach everyone on the network.
Betweenness centrality measures how "in between" someone is in the network. "In between" refers to how often the shortest route for information to get from one person to another in a network passes through a specific third person. A person with a high measure of betweenness usually "knows what's going on" and can act as a liaison to separate parts of the network.
A More Mathematical Explanation
From now on, we will add to our understanding of social networks by looking at them as graphs in the [...]
From now on, we will add to our understanding of social networks by looking at them as graphs in the context of interacting people. The people will now be thought of as vertices and the connections between people will be thought of as edges. For more information on the basics of graphs, which will be imperative to the mathematical understanding of social netoworks, look at the page Graph Theory.
The following graph of a hypothetical social network will serve as the example for the following sections, where its centrality measures will be determined:
If we are to do mathematical analyses, there must be one way to store information about the network as a whole. Luckily there is such a way! It is through the Adjacency Matrix. The adjacency matrix is defined as follows:
As an example, we will determine the adjacency matrix, A, of the graph above:
For a better visual and mathematical understanding of the adjacency matrix, you can look at the following chart:
Now with the graph and adjacency matrix at our disposal, we are ready to find certain measures of centrality. Typically, computers are used to measure centrality, but our graph is small enough that we can show most of the procedures to find certain measures of centrality.
Definition: The degree of a vertex i is
in other words, it means adding all of the edges adjacent to a given vertex. Having the adjacency matrix in mind, it is like counting all of the ones in a column or row for a specific vertex. We can use Chris's row in the adjacency matrix as an example:
As you can see, Chris's degree centrality is: 1+1+1+1=4
Let's calculate the degree centralities of the others:
Conveniently, they were displayed in a way that ranked them at the same time. We can now conclude that Chris has the highest degree centrality (he knows the most people!) and Donald, Bernie, Mark, David and Elissa are tied for the lowest degree centrality, each only knowing one person.
(Note: This section requires a knowledge of Linear Algebra)
If you can remember one thing about eigenvector centrality, it is that it's a more sophisticated version of degree centrality (counting edges from a vertex) that takes in account of the quality of the connections!
How can math store information regarding relative centralities (quality) and connections toward other vertices?
Let be the eigenvector centrality score of a vertex i and let be the adjacency matrix of the graph containing i. The use of the adjacency matrix is important because we want to consider everyone's data, and we don't want to include ones that aren't connected to us. The adjacency matrix tells us which vertices are connected to each other and how many vertices are connected. Let be the eigenvector centrality scores of the vertices adjacent to i.
The eigenvector centrality score for vertex i is proportional to the sums of the scores of all vertices that are connected to it:
where is a constant and N is the number of vertices in a graph. What this basically says that one person's eigenvector score depends on the eigenvector scores of it's neighbors.
Following the properties of matrix multiplication, the equation above can be written as:
Where is the vector containing all the vertices’ eigenvector centrality scores. This simplifies into the eigenvector equation:
Where is an eigenvector.
This is all nice and dandy. The eigenvector centrality score of one vertex relies on the eigenvector scores of the others. But how would we find the eigenvector centrality score of a particular vertex if it depends on the others??
Well the answer is that, strangely, we find them all at once! We just find the eigenvector associated with the highest eigenvalue, according to the Perron-Frobenious Theorem. The ith entry of that vector will correspond to the eigenvector centrality score of ith vertex.
We will now find the eigenvector associated with the highest eigenvalue, and thus the vector of eigenvector centralities, of our hypothetical network:
Let's test out one of the formulas, , to Jason.
, which matches Jason's eigenvector score.
We can clearly see here that even though Chris had higher degree centrality than Jason, Jason and Chris had the same eigenvector centrality. Eigenvector centrality was created for reasons like these, to determine someone's importance in a network by looking more than the amount of connections. In most settings,who you are connected to is more important than how many people you are connected to.
Closeness and Betweenness Centrality
- A path is a sequence of vertices that in which each vertex is adjacent to the next. We can think of this as a sequence of vertices that can be traversed by a vertex i. More information can be found in Graph Theory
- A geodesic path is the shortest path between a pair of vertices.
Closeness Centrality of a vertex is related to the mean geodesic path length between i and every other vertex in the graph. Intuitively, if mean geodesic path length is low, we say i is closely located to every other vertex. Be wary, however, that a low number in this case indicates a higher centrality score. This may be confusing for some. Therefore, closeness centrality of a vertex iis more easily understood as the reciprocal of the average geodesic path length between i and every other vertex in the graph, as follows:
Where n is the number of vertices in the graph and is the length of the geodesic path between vertex i to vertex j.
We will use our example graph once more to illustrate the shortest paths for certain individuals (the rest will be calculated and left to be verified by the reader):
Let's look at the shortest path from Donald to Elissa:
We can count the number of edges required to get to the other vertex (person). To get to Elissa, Donald's geodesic path has a length of 1+1+1+1=4. We hope that the shortest path seems is relatively easy to find given the simplicity of the model. For most real and complicated models, computers calculate these shortest paths with a specific algorithm, Dijksta's Algorithm, mentioned below.
Now to see an example in which someone may be "close" within a network, which is to have high closeness centrality. Let's look at some of Jason's geodesic paths to other people:
We see that to get to the two most distant people, Donald and Elissa, Jason only has to "walk" through two edges. In other words, Jason has 2 degrees of separation to Donald and to Elissa. Again, to have high closeness centrality, one have must the lowest mean degree of separation to everyone in the network. Things are looking good for Jason so far.
Let's now compute the closeness centralities for everyone. The entries of the following chart indicate the length of the geodesic path for each possible pairing:
You can check for your own answers for the geodesic path/closeness centrality. It looks like Jason came in first with a closeness centrality score of 0.63 and Donald, Bernie, David and Elissa tied for last with a closeness centrality score of 0.39. Jason's high score makes sense because visually, he is centrally located. The tie between Donald, Bernie, David and Elissa makes sense because they are directly connected to one other person in the system, and thus have to travel "farther" (meaning having to go through more "friends of friends") to reach someone in the network.
Betweenness Centrality of a vertex i is the fraction of geodesic paths within the graph that include i. In other words, it assembles every pair of vertices and computes the geodesic paths between them, then it determines the fraction of those paths that include i.
Where j, k and i are vertices in the graph such that , n is the total number of vertices in the graph, is the number of geodesic paths between j and k, and is the number of those paths that pass through i.
Again, we will use our example network to find betweenness. The following picture illustrates how betweenness is calculated (although not completely) for Chris and Austin in the context of paths between Jason and Elissa, Donald and Mark:
As you can see, shortest paths consisting of only one traversed edge (they are first degree friends), won't have any "middle men", or intermediaries. Therefore, in our matrix for closeness centrality, paths containing 0 can be ignored for the purposes of calculating betweenness centrality. Entries that were 1 will typically contribute a value of zero to betweenness centrality but will counted regardless because they still represent a geodesic path of length one. Notice that the formula has i, j, k not equal to each other. So when we calculate the betweenness centrality of i, we don't count any geodesic paths that start or end on i, but we count all the others. What matters most are the entries in the closeness centrality matrix that are greater than one, because those entries suggest that someone had to know an intermediary (or several) to be associated with a friend.
In the next image, the closeness centrality matrix will be modified in such a way that highlights the intermediaries for each possible geodesic path. For every path, the intermediary's (if any) initial will replace the numerical entry. If there are several intermediaries, then they will each have their own initial in the entry. The 0 entries of the former closeness centrality matrix in will be blank in the betweenness centrality matrix. The 1 entries in the former centrality matrix (the geodesic paths that were length 1) will have an asterisk because they are still counted, but are counted as zero. In addition, we will not count the geodesic path between vertex i and j twice. In other words, the geodesic path from i to j and the geodesic path from j to iwill only be recorded once, not twice. Therefore, we will only see the upper bound triangle of the matrix (above the diagonal). For our example, the total number of connections is , or 21. The two in the divisor comes from the fact that we are not counting pairs. This graph also gives an example for excluding the row and column of a person (Donald) when computing betweenness centrality.
With this image, we can now calculate everyone's betweenness centrality! All we do is add a person's "interruptions", or times they are on a geodesic path, and divide by the total amount of geodesic paths, 21.
This result makes intuitive sense. Jason has highest betweenness centrality because he is literally "in the middle" of everyone. Donald, Bernie, Mark, David and Elissa all have low betweenness centrality because they are located in the periphery of the network and don't bring people together.
Bernoulli Graph and Configuration Models
Previously, we were establishing measures concerning the properties of nodes, or people. We will now focus our attention to network properties. Our previous analyses consisted of taking measurements and analyzing them, now we are taking a step further to model real life situations knowing only very little of the network.
Before we begin, here are some definitions:
- Degree Sequence: The degree sequence for the graph is , where is the number of outbound links from j if i is connected to j, and 0 otherwise.
- There is a damping factor, d, empirically estimated to be 0.85, that is the probability of a random surfer to keep surfing. This is like the value of r in the reproduction number section.
- The PageRank value of a page is the chance that a random surfer will land on that page by clicking on a link.
The formula is as follows:
where is the PageRank of a page i, are the considered pages, is the set of pages that link to , is the number of outbound links on page , and N is the total number of pages.
The PageRank values are the entries in the dominant eigenvector of the adjacency matrix defined earlier.
You might be thinking, "how does this relate to the world?" Well it might not save millions of lives like preventing an epidemic can, but it facilitates the speed and relevance of finding information online! You also encounter this every time you make a Google search, and that is pretty interesting.
- There are currently no teaching materials for this page. Add teaching materials.
Image for Hamlet's Network is found here:http://magmods.wordpress.com/2011/08/18/how-to-do-things-with-networks-a-response-to-franco-moretti/
Leave a message on the discussion page by clicking the 'discussion' tab at the top of this image page.