netANOVA algorithm for graph clustering

Studying heterogeneity between individuals lies at the core of precision medicine. Often, information about individuals can be represented as networks characterized by individual specific edge values. We developed an algorithm to identify networks that can be integrated in a cluster where the determination of the final clustering is based on notions of statistical significant differences between clusters. In particular, we first use an unsupervised hierarchical algorithm to identify latent classes of similar networks. Similarity between networks is computed via appropriate distance measures between graphs. To determine the optimal number of clusters, we recursively test for distances between two groups of networks, progressing from the root node to the end nodes of the clustering dendrogram. The test itself is based on computing pairwise distances between graphs and is inspired by distance-wise ANOVA algorithms, commonly used in ecology. Permutations are used to assess significance. The results of the strategy will pave the way towards deciding which networks can sensibly be aggregated. This is not only relevant in stratified medicine or for molecular reclassification of disease, but also in areas such as genetic epistasis detection in which conclusions need to be drawn from multiple statistical epistasis networks across different analysis protocols. The code is available on GitHub at https://github.com/DianeDuroux/netANOVA