Communities - Graph Analysis and Visualization - page 402

worthy of attention. The next section shows how you can use analytics,
visualization, and interaction to identify and analyze social groups.
Cliques and Other Groups
You may remember all too well what a clique is in common terms from
your days on the school playground—a tight-knit social group that tends
to speak and act as one, always together, and often to the exclusion of
others. Perhaps not surprisingly, then, clique detection is often used in
social network analysis. In the business world, for example, the presence
of a clique may indicate a group with a strong collective perspective that is
influenced by strategic direct marketing to key individuals in that group.
In graph terms, a clique is defined as a subgraph in which each node
connects to each of the other nodes. However, this definition alone is not
specific enough to identify a set of communities of interest. For example,
technically, two linked nodes form a clique, and one of those nodes and
another adjacent node form an overlapping clique. Clearly, identifying
trivial relationships of this nature adds little to your understanding.
Borrowing from the school playground example, describing each pairing of
kids in a group of five as a clique, as well as each combination of three, four,
and all five, is not a particularly helpful characterization.
A practical restriction for identifying cliques is that each be a maximal
clique . A maximal clique is not a subgraph of any other clique, though it
may overlap with others. This restriction limits identification to top-level
cliques only. Other simple strategies of focusing clique identification may be
to specify a minimum size as shown in Figure 11-16 , or the neighborhood
limits of a node of interest. No matter what the strategy, accurately
computing maximal cliques is expensive, so keep in mind that most
algorithms use some level of approximation.