Palla, G. et al., 2005. Uncovering the overlapping community structure of complex networks in nature and society. Nature, 435(7043), p.814.
IntroductionThe 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
- a union of k-cliques (complete subgraphs of size k)
- accessible from each other through a series of neighbouring k-cliques.
AlgorithmThe following algorithm is used for finding k-clique communities:
- identify all cliques in the network
- identify communities by finding aggregating overlapping cliques
- ignoring any directionality, and
- only consider weights which exceed a threshold value w*
- 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.
- protein / function clustering
- Word associations: identify communities of word (= words with related senses), e.g. based on the South Florida Free Association norm list.