Uncovering the overlapping community structure of complex networks in nature and society

Palla, G. et al., 2005. Uncovering the overlapping community structure of complex networks in nature and society. Nature, 435(7043), p.814.

Introduction

The article introduces an approach for identifying overlapping (rather than separate) cohesive groups of nodes, since most real networks typically contain parts in which some nodes are more highly connected to each other than to the rest of the network.

They define a k-clique community as

1. a union of k-cliques (complete subgraphs of size k)
2. accessible from each other through a series of neighbouring k-cliques.

Algorithm

The following algorithm is used for finding k-clique communities:

1. identify all cliques in the network
2. identify communities by finding aggregating overlapping cliques

The algorithm is applied to binary networks (undirected and unweighted links). A network can be transformed into a binary network by

1. ignoring any directionality, and
2. only consider weights which exceed a threshold value w*

Applications

1. Identification of publication topics (by identifying cliques in co-authorship networks) - each clique represents such a topic; author weight: w=1/(n-1) with for every publication with n authors.
2. protein / function clustering
3. Word associations: identify communities of word (= words with related senses), e.g. based on the South Florida Free Association norm list.