Supervised data mining in networks: link prediction and aplications

Abstract

La predicción de enlaces consiste en predecir la existencia de enlaces no observados actualmente o enlaces que aparecerán en el futuro entre pares de nodos en redes complejas. Este problema ha atraído la atención de investigadores en diversas disciplinas debido a su utilidad en una amplia gama de aplicaciones, entre las que se encuentran la identificación de genes asociados a determinadas enfermedades o la mejora de las sugerencias realizadas por los sistemas de recomendación. Esta tesis doctoral comprende diferentes líneas de trabajo, todas ellas estrechamente relacionadas con el problema de la predicción de enlaces. Por un lado, después de un estudio exhaustivo del estado del arte en predicción de enlaces, se identificaron las principales limitaciones de los enfoques actualmente propuestos. Estas limitaciones se relacionaban con las dificultades asociadas al equilibrio entre la escalabilidad y el rendimiento de las técnicas de predicción de enlaces. Se han propuesto dos técnicas escalables de predicción de enlaces que siguen diferentes enfoques para explotar características locales de la red. Por otro lado, se han abordado diferentes aplicaciones para las técnicas de predicción de enlaces. Se ha propuesto un nuevo algoritmo para priorización genérica, como la priorización de genes asociados a una determinada enfermedad, que logró mejores resultados que otras técnicas gracias a su capacidad para integrar fuentes de datos heterogéneas. También se ha desarrollado un algoritmo para la desambiguación de los sentidos de las palabras en relaciones semánticas entre conceptos, basado en la predicción de enlaces y que no requiere datos anotados. En este trabajo, mostramos cómo nuestro algoritmo logró una mayor precisión que otras técnicas del estado del arte en diferentes tareas de evaluación y cómo las relaciones extraídas pueden usarse para mejorar el rendimiento de las técnicas de última generación para la desambiguación del sentido de las palabras. Además, dado que la función de los nodos influye en cómo se forman los enlaces en redes complejas, hemos desarrollado una nueva métrica de distancia basada en el concepto de equivalencia automórfica con aplicación al descubrimiento de los roles de los nodos. Finalmente, hemos desarrollado una herramienta de minería de datos para redes complejas. Esta herramienta, llamada NOESIS, contiene implementaciones eficientes de una extensa lista de algoritmos relacionados con redes, incluyendo una biblioteca completa de técnicas de predicción de enlaces.

Link prediction is the problem of predicting the existence of currently-unobserved links or links that will appear in the future between pairs of nodes in complex networks. This problem has attracted a great deal of attention from researchers in diverse disciplines due to its applicability in a wide range of tasks, such as the identification of disease-associated candidate genes or the improvement of recommendations suggested by recommender systems. This PhD dissertation comprises different lines of work, all of them closely related to the link prediction problem. On the one hand, after an exhaustive study of the state of the art in link prediction, the main limitations of currently proposed approaches were identified. These limitations were related to the difficulties associated to the trade-o_ between scalability and performance in link prediction techniques. Two scalable link prediction techniques were proposed that follow different approaches to exploit local network features. On the other hand, different applications of link prediction techniques were addressed. We proposed a novel algorithm for generic prioritization, such as disease-gene prioritization, which achieved better results than other state-of-the-art techniques due to its capacity for integrating heterogeneous data sources. We also developed a novel algorithm for word sense disambiguation of semantic relations between concepts, based on link prediction and without the requirement of annotated data. We showed how our algorithm achieved better accuracy than other state-of-the-art techniques in different evaluation tasks and how relations extracted using our approach could improve the performance of state-of-the-art general-purpose word sense disambiguation techniques. In addition, since node role influences how links are formed in complex networks, we developed a novel distance metric based on the concept of automorphic equivalence with application to node role discovery. Finally, we developed a software framework for network data mining. This framework, called NOESIS, contains efficient implementations of an extensive list of network-related algorithms, including a complete library of link prediction techniques.