Los autores probaron el enfoque SpringRank en conjuntos de datos sintéticos, donde se conocen las clasificaciones de verdad fundamental, y comparó los resultados con otros métodos de clasificación. Crédito:Caterina De Bacco, Daniel B. Larremore, y Cristopher Moore
Algunas veces, saber quién gana y quién pierde es más importante que cómo se juega el juego.
En un artículo publicado esta semana en Avances de la ciencia , Los investigadores del Instituto de Santa Fe describen un nuevo algoritmo llamado SpringRank que usa victorias y derrotas para encontrar rápidamente clasificaciones que acechan en grandes redes. Cuando se prueba en una amplia gama de conjuntos de datos sintéticos y del mundo real, que van desde equipos en un torneo de baloncesto universitario de la NCAA hasta el comportamiento social de los animales, SpringRank superó a otros algoritmos de clasificación en la predicción de resultados y en eficiencia.
Física Caterina De Bacco, ex becario postdoctoral en el Instituto Santa Fe, ahora en la Universidad de Columbia, dice que SpringRank usa información que ya está integrada en la red. Analiza los resultados de uno a uno, o por parejas, interacciones entre individuos. Para clasificar los equipos de baloncesto de la NCAA, por ejemplo, el algoritmo trataría a cada equipo como un nodo individual, y representar cada juego como una ventaja que lleva del ganador al perdedor. SpringRank analiza esos bordes, y en qué dirección viajan, para determinar una jerarquía. Pero es más complicado que simplemente asignar la clasificación más alta al equipo que ganó más partidos; después de todo, un equipo que juega exclusivamente con equipos de bajo ranking puede que no merezca estar en la cima.
Comparación de los métodos de clasificación SpringRank y Regularized Bradley-Terry-Luce (BTL) para predecir una variedad de conjuntos de datos. Crédito:Caterina De Bacco, Daniel B. Larremore, y Cristopher Moore
"No es solo una cuestión de victorias y derrotas, pero a qué equipos ganaste y contra cuáles perdiste, "dice el matemático Dan Larremore, ex becario postdoctoral del Instituto Santa Fe, ahora en la Universidad de Colorado Boulder. Larremore y De Bacco colaboraron con el científico informático Cris Moore, también en el Instituto Santa Fe, en el papel.
Como sugiere su nombre, SpringRank trata las conexiones entre nodos como resortes físicos que pueden contraerse y expandirse. Debido a que los físicos conocen desde hace mucho tiempo las ecuaciones que describen los movimientos de los resortes, dice De Bacco, el algoritmo es fácil de implementar. Y a diferencia de otros algoritmos de clasificación que asignan números ordinales a los nodos, primero, segundo, tercera, etc., —SpringRank asigna a cada nodo un número de valor real. Como resultado, los nodos pueden estar muy juntos, separar, o dispuestos en patrones más complicados y reveladores, como grupos de nodos clasificados de manera similar.
"Las ideas de la física a menudo nos brindan algoritmos elegantes y efectivos, ", dice Moore." Esta es otra victoria para ese enfoque ".
Las clasificaciones de baloncesto de la NCAA son solo un área en la que el nuevo algoritmo SpringRank supera a los competidores. En el diagrama de arriba, los puntos sobre la línea muestran ensayos en los que SpringRank predijo juegos con mayor precisión. Crédito:Caterina De Bacco, Dan Larremore, y Cris Moore
En el papel, los investigadores probaron el poder predictivo de SpringRank en una variedad de conjuntos de datos y situaciones, incluidos los torneos deportivos, Comportamientos de dominancia animal entre periquitos cautivos y elefantes asiáticos en libertad, y prácticas de contratación de profesores entre universidades.
Los investigadores cargaron el código de SpringRank en GitHub, un repositorio de código en línea, y dicen que esperan que otros investigadores, especialmente en las ciencias sociales, lo usará. "Se puede aplicar a cualquier conjunto de datos, "dice De Bacco.
El próximo conjunto de datos que ella y sus coautores planean analizar con SpringRank no se parece a ninguno de los presentados en el Avances de la ciencia papel. Trabajarán con Elizabeth Bruch, un profesor externo del Instituto Santa Fe, analizar patrones de mensajería en los mercados de citas online.
