According to Heider’s social balance theoryⁱ, individuals (nodes) in a social network tend to form relationships (+ or - edges between nodes) as follows: “for every set of three nodes, if we consider the three edges connecting them, either all three of these edges are labeled + (triadic closure), or else exactly one of them is labeled +.”ⁱⁱ One can prove mathematically that a social network with this property requires it to have “either all nodes are friends, or, more commonly, the nodes are divided into two groups” where the people within a group all like each other and everyone in a group dislikes everyone in the other group. This type of dichotomy in a network can be seen in real life, one famous example being the college karate club observed by W.W. Zachery, where a dispute broke out between the club’s administrator and its teacher, eventually resulting in the club splitting into two clubs. The drawback of social balance theory is that it requires everyone to know and have a relationship (+ or -) with everyone in the network, and that triadic closure is strictly enforced. In a large social network, it is common to find two people who, despite having mutual friends, simply don’t know each other. It is also not uncommon for a person to have two friends who don’t like each other, or for three people to all dislike each other, despite the social dissonance in these situations. An intuition notion that social balance theory does not provide a good model for large networks is that they tend to be composed of many sub-communities, not just one or two.

If it is indeed true that a social network consists of communities, then it is natural to try to identify them. This allows us to have a better understanding of the structure of a network on a global scale. Finding clusters in a collaboration network between physicists, for example, allows us to see the level of research activity of different branches of physics.ⁱⁱⁱ Another use of finding communities is to extract smaller networks from a large one, where the smaller networks might be much easier to analyze and their interactions might actually behave more accordingly to social balance theory. Consider the Zachery’s karate club example: if the researchers were collecting social network data on the entire university instead, then the dynamics of the club would have been lost the in complexity and global dynamics of the entire network. A good clustering algorithm would enable them to isolate the club and study the effects of the dispute in the club. Thus, finding communities allows us to gather data on a large network on a global scale while still be able to look at its sub-clusters and study the local dynamics of individual clusters.

iFritz Heider. Attitudes and cognitive organization. Journal of Psychology, 21:107–112, 1946.

iiStructural Balance. ECON 204 handout. http://www.infosci.cornell.edu/courses/info204/2007sp/balance.pdf

iiiM.E.J. Newman and M. Girvan. Finding and evaluating community structure in networks.