Algorithms For Dummies

Clustering networks in groups

People tend to form communities — clusters of other people who have like ideas 

and sentiments. By studying these clusters, attributing certain behaviors to the 

group as a whole becomes easier (although attributing the behavior to an indi-

vidual is both dangerous and unreliable). 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 insur-

ance 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. For the sake of simplicity, this chapter focuses 

solely on these four types: closed, open, connected pair, and unconnected.

When looking for clusters in a friendship graph, the connections between nodes in 

these clusters depend on triads — essentially, special kinds of triangles. Connec-

tions between three people can fall into these categories:

---

CHAPTER 10