May-29-2017

Chapter 4-1: Strong and weak ties

In 1973, Mark Granovetter published: The Strength of Weak Ties. This paper is now recognized as one of the most influential sociology papers ever written.

Granovetter found that most jobs were found through "weak" acquaintances. This pattern reminded Granovetter of his freshman chemistry lesson that demonstrated how "weak" hydrogen bonds hold huge water molecules together, which are themselves held together by "strong" covalent bonds.

In Granovetter's view, a similar combination of strong and weak bonds holds the members of society together.

Weak ties play a crucial role in our ability to communicate with the outside world. Often our close friends can offer us little help in finding a job. They move in the same circles we do and are inevitably exposed to the same information. To get new information, we have to activate our weak ties. The weak ties, or acquaintances, are our bridge to the outside world since by frequenting different places they obtain their information from different sources than our immediate friends.

Chapter 4-2: Clustering Coefficient

Page 46: Duncan Watts Introduce the clustering coefficient:

Divide the number of actual links between your neighbor nodes (e.g., friends) by the number of links that they could have if they are connected with each other (e.g., they were all friends of each other).

The clustering coefficient tells you how closely knit your circle of friends is.

Chapter 3-3: Small-World Networks (en.wikipedia.org/wiki/Small-world_network)

A small-world network is a type of mathematical graph in which most nodes are not neighbors of one another, but the neighbors of any given node are likely to be neighbors of each other and most nodes can be reached from every other node by a small number of hops or steps.

Specifically, a small-world network is defined to be a network where the typical distance L between two randomly chosen nodes (the number of steps required) grows proportionally to the logarithm of the number of nodes N in the network, that is:

L∝log⁡N

While the clustering coefficient is not small. In the context of a social network, this results in the small world phenomenon of strangers being linked by a short chain of acquaintances. Many empirical graphs show the small-world effect, e.g., social networks, the underlying architecture of the Internet, wikis such as Wikipedia, and gene networks.

A certain category of small-world networks were identified as a class of random graphs by Duncan Watts and Steven Strogatz in 1998. They noted that graphs could be classified according to two independent structural features, namely the clustering coefficient, and average node-to-node distance (also known as average shortest path length). Purely random graphs, built according to the Erdős–Rényi (ER) model, exhibit a small average shortest path length (varying typically as the logarithm of the number of nodes) along with a small clustering coefficient. Watts and Strogatz measured that in fact many real-world networks have a small average shortest path length, but also a clustering coefficient significantly higher than expected by random chance. Watts and Strogatz then proposed a novel graph model, currently named the Watts and Strogatz model, with (i) a small average shortest path length, and (ii) a large clustering coefficient.