Summary

In this paper, I present the data of a karate club social network that Zachary used in his study in 1997. I apply the Clauset, Newman, and Moore modularity optimization algorithm for community detection. I find that the result matches exactly the two factions that appeared in the club.

The Data

The data that I have selected for this assignment is the famous social network among members of a university karate club analyzed by Zachary (1997). I downloaded the data from the Nexus network data repository

President John A. and karate instructor Mr. Hi (pseudonyms) led the karate club. The edge weights are the number of common activities the club members (represented by numbers) took part. These activities, as stated in the Nexus network data repository, were:

  1. Association in and between academic classes at the university.
  2. Membership in Mr. Hi’s private karate studio on the east side of the city where Mr. Hi taught nights as a part-time instructor.
  3. Membership in Mr. Hi’s private karate studio on the east side of the city, where many of his supporters worked out on weekends.
  4. Student teaching at the east-side karate studio referred to in (2). This is different from (2) in that student teachers interacted with each other, but were prohibited from interacting with their students.
  5. Interaction at the university rathskeller, located in the same basement as the karate club’s workout area.
  6. Interaction at a student-oriented bar located across the street from the university campus.
  7. Attendance at open karate tournaments held through the area at private karate studios.
  8. Attendance at intercollegiate karate tournaments held at local universities. Since both open and intercollegiate tournaments were held on Saturdays, attendance at both was impossible.

Figure 1 shows a graph depicting this social network.

Figure 1. Graph of the social network between the members of the karate club. Edge width is proportional to the number of interactions between two members.

Community detection

Zachary (1997) studied conflict and fission in this network. After prolonged disputes between two factions of the club, one led by John A., the other by Mr. Hi., the karate club was split into two separate clubs.

Now we will predict the two factions of the club using the structure of the social network. For that, we will apply the fast greedy modularity optimization algorithm for finding community structure developed by Clauset, Newman and Moore (2004). The output of this algorithm is a hierarchical community structure that we can visualize as a dendrogram (Figure 2). In the dendrogram, we show the two communities resulting from a cut at the highest level into two communities.

Figure 2. Dendrogram resulting after community discovery using the Clauset, Newman and Moore modularity optimization algorithm. The colored rectangles show the two factions as the result of a cut of the hierarchy in two groups. The y axis represents modularity.

The graph in Figure 3 shows with different colors the two communities as predicted by the algorithm. The shape shows the actual factions that appeared in the karate school. As we can see, the algorithm detects both communities perfectly. Within-faction interactions are stronger than across-faction interactions, and we can observe that the karate club split across the weakest interactions. The only exception is member 09, who has a strong interaction with 03. It’s interesting to point that, although 09 was in John A. faction during the dispute, finally attended Mr. Hi classes after the club split.

Figure 3. Graph of the social network among the members of the karate club. Node color shows the two factions discovered using the Clauset, Newman, and Moore modularity optimization algorithm. The shape shows the actual factions in the club. Edge width is proportional to the number of interactions between two members.

Finally, we will display the social network as a bipartite graph with the members of each faction on each side (Figure 4). The arcs display the interactions between the two factions. As we can see, there are few and weak interactions between both factions, and they are focused on a few members.

Figure 4. Bipartite graph of the two factions of in a social network among the members of a karate club. Node color shows the two factions discovered using the Clauset, Newman, and Moore modularity optimization algorithm. The shape shows the actual factions in the club. Edge width is proportional to the number of interactions between two members.

References