Cluster evaluation on weighted networks

Abstract

(English) This thesis presents a systematic approach to validate the results of clustering methods on weighted networks, particularly for the cases where the existence of a community structure is unknown. Including edge weights has many applications in network science, as there are many situations in which the strength of the connections between nodes is an essential property that describes the network. This evaluation of clustering methods comprises a set of criteria for assessing their significance and stability. First, a well-established set of community scoring functions, which already existed for unweighted graphs, has been extended to the case where the edges have associated weights. There is consideration given to how in some cases many possible weighted extensions to the same function can be defined, and each of them can suit different types of weighted networks. Additionally, methods to randomize graphs but maintaining the original graph’s degree distribution have been defined in order to use these random graphs as baseline networks. This randomization together with the weighted community scoring functions are then used to evaluate cluster significance, since the random networks built from the original network with our methods provide reference values for each scoring function that will allow to actually determine whether a given cluster score for the original graph is better than a comparable graph with the same degree distribution but no community structure. As for the evaluation of stability, we define non parametric bootstrap methods with perturbations for weighted graphs where vertices are resampled multiple times, and the perturbations are applied to the edge weights. This, together with some fundamental similarity metrics for set partitions derived from information theory and combinatorics, constitutes our criteria for clustering stability. These criteria are based on the essential idea that meaningful clusters should capture an inherent structure in the data and not be overly sensitive to small or local variations, or the particularities of the clustering algorithm. A more in-depth study of the characteristics of cluster scoring functions and their potential bias towards clusters of a certain size has also been performed. This would render some of these functions unsuitable to compare results of clustering algorithms when the size of the partition differs considerably. For this analysis, we introduce parametrized multi-level ground truth models based on the stochastic block model and on preferential attachment that can showcase how the functions respond to varying the strength of each level of clusters in a hierarchical structure. Additionally, a scoring function that doesn't suffer from this kind of bias is proposed: the density ratio. This thesis also contributes with an efficient implementation of Newman's Reduced Mutual Information, a measure to compare set partitions based on information theory. Here it is used as a tool to compare network partitions, which is particularly useful for the evaluation of cluster stability, but it can have applications beyond the field of network clustering. Our algorithm uses an hybrid approach that combines analytical approximation with a Markov Chain Monte Carlo method for a good balance between accuracy and efficiency. Also an indispensable part of this thesis is the associated software that we developed, which includes the implementation of all the methods discussed in it. It all has all been included in our R package clustAnalytics. This package is designed to work together with igraph, the main R package dedicated to graphs, to make it easy and straightforward for other researchers to use. There are many useful applications for these tools: from the study and observation of new datasets, to the evaluation and benchmarking of clustering algorithms.

(Català) Aquesta tesi presenta un mètode sistemàtic per validar els resultats obtinguts per mètodes de clústering a xarxes amb pesos, especialment per als casos en què es desconeix l'existència d'una estructura de comunitats. La inclusió de pesos a les arestes té diverses aplicacions a l'estudi de xarxes, ja que hi ha moltes situacions on la força de les connexions entre nodes és una propietat essencial que descriu la xarxa. Aquesta avaluació de mètodes de clústering inclou una sèrie de criteris per quantificar la seva significació i estabilitat.

En primer lloc, hem estès un conjunt de funcions per avaluar comunitats, que ja existien per a grafs sense pesos, al cas on les arestes tenen pesos associats. S'ha tingut en compte com en alguns casos es poden definir diverses extensions de la mateixa funció, cada una per a diferents tipus de xarxes amb pesos. A més a més, s'han definit mètodes per aleatoritzar grafs mantenint la seqüència de graus original, per fer servir aquests grafs aleatoris de referència. Aquest procés, juntament amb les funcions definides, permet avaluar la significació dels clústers, ja que els grafs aleatoris donen valors de referència que serveixen per determinar si la puntuació del graf original és millor que la d'un de comparable però que no tingui una estructura de comunitats.

Pel que fa a l'avaluació de l'estabilitat, definim mètodes de bootstrap no paramètric amb pertorbacions per a grafs amb pesos on els vèrtexs es remostregen diverses vegades, i s'apliquen pertorbacions al pes de les arestes. Conjuntament amb mesures de similitud per a particions de conjunts basades en teoria de la informació i combinatòria, formen els criteris per avaluar l'estabilitat dels clústers. Aquests criteris es basen en la idea que els clústers rellevants haurien de captar l'estructura de les dades, però no ser excessivament sensibles a petites variacions locals o a les particularitats dels algoritmes de clústering.

També es fa un estudi més a fons de les característiques de les funcions avaluadores dels clústers i el seu possible biaix cap a clústers d'una certa mida. Això podria fer que algunes d'aquestes funcions fossin inadequades per comparar resultats d'algoritmes de clústering en cas que la mida de les particions fos prou diferent. Per aquesta anàlisi, introduïm models parametritzats de comunitats multinivell basats en el model de blocs estocàstics i en el model de connexió preferencial, que mostren com les funcions responen quan la força relativa dels diversos nivells de clusters varia. A més a més, proposem una funció avaluadora que no té aquesta mena de biaix, la ràtio de densitats.

Aquesta tesi també aporta una implementació eficient de la informació mútua reduïda ("reduced mutual information") de Newman, una mesura per comparar particions de conjunts basada en teoria de la informació. Aquí es fa servir per comparar particions de xarxes, que és especialment útil per mesurar l'estabilitat dels clusters, però pot tenir aplicacions més enllà del clústering de xarxes. El nostre algoritme té un funcionament híbrid que combina una aproximació analítica amb un mètode de Monte Carlo de cadena de Markov per trobar un bon equilibri entre exactitud i eficiència.

Una altra part essencial d'aquesta tesi és el software associat que s'ha desenvolupat, que inclou les implementacions de tots els mètodes que s'hi discuteixen. S'ha compilat tot al nou paquet clustAnalytics, que ja és al repositori de CRAN. Aquest paquet està fet per funcionar conjuntament amb igraph, el principal paquet d'R dedicat als grafs, per fer-lo fàcil i accessible d'utilitzar a altres investigadors. Hi ha moltes situacions on aquestes eines poden ser útils: des de l'estudi i observació de nous conjunts de dades, a l'avaluació d'algoritmes de clústering. A més a més, algunes parts del paquet, com ara la implementació de la informació mútua reduïda es poden fer servir per comparar particions de tota mena de conjunts, no només de xarxes.