What networks can tell us about the world - A lecture (2 of 3) by Mark Newman

For those willing to get introduced to the world of complex networks, the three lectures given by Mark Newman, a British physicist, at the Santa Fe Institute on 14,15 and 16 September 2010 are a great way to get to know a little bit about this field.

In his first lecture, Mark Newman introduced what a network was. Let's continue with the second lecture, in which he explains what we can do with complex networks. You can find it here.

In this post I summarise (certainly in a very personal fashion, although some points are directly extracted from his slides) the learning points I extracted from the lecture.

Positioning of nodes within a social network. Centrality
- The idea of distances in networks.
- The most famous experiment in networks is the one by Stanley Milgram in 1967. The same Milgram who, some years afterwards made the famous experiment on obedience to an authority.
- The network-related experiment that Milgram made relates to the concept of a "small-world".
- He explains the mathematical basis of the six-step relationship concept. Everybody is connected with everyone is even less than six steps.
- If each person knows 100 people, then the number of people 1 step away from you is 100. The number of people 2 steps away from you is 100x100 = 10000. Actually people 5 steps away is 10 billion (more than the current world population).
- A way to pinpoint important people in a social network. Closeness centrality: Average distance to everyone in the network. Those nodes with the shortest distance are well connected. The most connected node is the one with the highest closeness centrality. However, this calculation is not very useful. Its calculation is complex and centrality numbers are very very similar to each other in a social network.

Degree centrality
- Can we do better? Yes, the degree centrality. The degree is the number of nodes a node is connected to. Degree centrality is just the degree number.
- Hubs in the network play a really important role in the function of the network.
- He presents a very important graph in network science. The degree graph. The x axis represents the degree i.e. the number of connections that a node has. The y axis represent the number of nodes that have that degree.
- They are well spaced values.

PageRank
- "Degree is like a score where you get one point per person you know. But not all people are equally important".
- How can we signal whether a node is connected to a very important node? One algorithm is PageRank. The rank associated to any node is an eigenvector. "Each node in the network has a score that is the sum of the score of its neighbours.

Transitivity
- What does a triangle means in a social network? A friend of my friend is my friend. Or, probably two of my friends know each other.
- However if my friends don't know each other, I am more central, I have more influence in the network.
- Predicting future friendships: Look for pairs who have one or more mutual friends.

Homophily
- Probably not a big surprise but...
- People tend to be friends with people in the same school grade.
- People tend to get married with people with a similar age.
- Liberal blogs like to be connected to liberal blogs.
- Conservative blogs like to be connected to conservative blogs.
- We can use homophily to make predictions.
- For example, on average about 70% of your friends vote like you do.
- Probably people change opinions to match their friends' and people change friends to match their opinions (both things happen).
- "83% of friends had the same ethnicity.
- However if those links are randomly chosen there is already a specific chance.
- Modularity helps us identifying when there is a lot of homophily in the network. The difference between the homophily case and the random case.

Modules, groups or communities
- Are there communities in a network?
- This helps understanding how networks will split up.
- A computer can calculate the definition of modularity for all nodes in the network.
- Understanding these network characteristics would enable us to solve real problems.

 Sunset networking