The distribution of clusters in random graphs (Q2277493)

The authors investigate the occurrence of subgraphs of a given random graph G, which are rich in edges. Motivated by a molecular biology problem to discover a striking similarity between protein amino acid sequence and that of a previously sequenced protein of known function, they reason that more distant functional and evolutionary relationships would give rise to sets of proteins in which no pair displayed a dramatic similarity but in which many pairs showed mild similarities. In a graph whose vertices are all proteins and in which edges denote mild similarities, such sets would be clusters. They evaluate the statistical significance of such clusters of proteins before attempting to search for biological significance. They show, why the expected number of clusters which neighbor a given cluster tends to \(\infty\).