Uncovering Latent Structure: Clustering and Community Detection

Kimmo Soramäki and Samantha Cook

Community detection for networks refers to grouping the nodes of a network in such a way that the nodes within a group are more similar to each other or more connected to each other than to nodes in other groups. We have already seen a few methods for grouping nodes: core–periphery classification and strong and weak components, in Chapter 2. Community detection aims to uncover other types of network structure and, unlike the methods previously presented, may depend on link properties as well as link structure. Community detection is useful in financial networks, such as in portfolio optimisation. This chapter will present many different algorithms for community detection, each with background on the methodology and examples with real data.

MAXIMUM CLIQUE

A clique is a subset of the nodes in a network such that the corresponding sub-graph is complete. For instance, any subset of the nodes in a complete network form a clique. A maximum clique is the largest clique in a network, and may represent an important community within the network. An example is that, in a perfect core–periphery network, the maximum clique corresponds exactly to the set of core nodes. Figure 4.1 shows a