The idea behind the study of clusters is that if a connection exists between people, they often have a common set of ideas and goals. By finding clusters, you can determine these ideas by inspecting group membership. For instance, it’s common to try to find clusters of people in insurance fraud detection and tax inspection. Unexpected groups of people might raise suspicion that they’re part of a group of fraudsters or tax evaders because they lack the usual reasons for people to gather in such circumstances.
Friendship graphs can represent how people connect with each other. The vertexes represent individuals and the edges represent their connections, such as family relationships, business contacts, or friendship ties. Typically, friendship graphs are undirected because they represent mutual relationships, and sometimes they’re weighted to represent the strength of the bond between two persons.
Many studies focus on undirected graphs that concentrate solely on associations. You can also use directed graphs to show that Person A knows about Person B, but Person B doesn’t even know that Person A exists. In this case, you actually have 16 different kinds of triads to consider.
When looking for clusters in a friendship graph, the connections between nodes in these clusters depend on triads — essentially, special kinds of triangles. Connections between three people can fall into these categories:- Closed: All three people know each other. Think about a family setting in this case, in which everyone knows everyone else.
- Open: One person knows two other people, but the two other people don't know each other. Think about a person who knows an individual at work and another individual at home, but the individual at work doesn't know anything about the individual at home.
- Connected pair: One person knows one of the other people in a triad but doesn't know the third person. This situation involves two people who know something about each other meeting someone new — someone who potentially wants to be part of the group.
- Unconnected: The triad forms a group, but no one in the group knows each other. This last one might seem a bit odd, but think about a convention or seminar. The people at these events form a group, but they may not know anything about each other. However, because they have similar interests, you can use clustering to understand the behavior of the group.
The example here relies on the Zachary's Karate Club sample graph. It's a small graph that lets you see how networks work without spending a lot of time loading a large dataset. Fortunately, this dataset appears as part of the networkx package. The Zachary's Karate Club network represents the friendship relationships between 34 members of a karate club from 1970 to 1972. Sociologist Wayne W. Zachary used it as a topic of study. He wrote a paper on it titled "An Information Flow Model for Conflict and Fission in Small Groups." The interesting fact about this graph and its paper is that in those years, a conflict arose in the club between one of the karate instructors (node number 0) and the president of the club (node number 33). By clustering the graph, you can almost perfectly predict the split of the club into two groups shortly after the occurrence.
Because this example also draws a graph showing the groups (so that you can visualize them easier), you also need to use the matplotlib package. The following code shows how to graph the nodes and edges of the dataset.
import networkx as nx
import matplotlib.pyplot as plt
%matplotlib inline
graph = nx.karate_club_graph()
pos=nx.spring_layout(graph)
nx.draw(graph, pos, with_labels=True)
plt.show()
To display the graphic onscreen, you also need to provide a layout that determines how to position the nodes onscreen. This example uses the Fruchterman-Reingold force-directed algorithm (the call to nx.spring_layout). The figure shows the output from the example. (Your output may look slightly different.)
The Fruchterman-Reingold force-directed algorithm for generating automatic layouts of graphs creates understandable layouts with separated nodes and edges that tend not to cross by mimicking what happens in physics between electrically charged particles or magnets bearing the same sign. In looking at the graph output, you can see that some nodes have just one connection, some two, and some more than two. The edges form triads, as previously mentioned. However, the most important consideration is that the figure clearly shows the clustering that occurs in a social network.