Communities and community detection

A cluster algorithm for graphs means exactly the same as a community detection algorithm for networks, and community structure in networks means exactly the same as cluster structure in graphs. This is a severe and really unfortunate case of divergent terminology. My training as a mathematician has led me to use graph predominantly. This word has other meanings however, and is not always intuitive to people from other realms of science. Hence I have begun to appreciate and increasingly use network. On the other hand, the phrase community detection seems rather narrow and I strongly prefer the older idioms clustering and cluster analysis. Throughout these pages and the MCL documentation graph is used a lot, nowadays interspersed with usage of network. These should be understood to be entirely interchangeable — not just on these pages, but in a very broad sense. Similarly, communities are the same as clusters in the context of, well, graph clustering, also-known-as community detection in networks.

Partitions and graph partitioning

The concept of partition or partitioning means superficially the same as clustering, that is, a separation into mutually disjoint subsets that cover the entire set of interest.

The most important difference is that the problem of graph partitioning is universally defined as a problem where the number and sizes of the clusters are specified a priori. This is not the case in graph clustering or cluster analysis in general. The second, less important difference between these two terms is that clustering excludes the possibility of overlap by convention, so that it is still possible to speak of an overlapping clustering, whereas a partition or partitioning excludes the possibility of overlap by definition.