Red Pathfinder

Un método para podar redes densas para resaltar vínculos clave

Razón fundamental

Las relaciones entre un conjunto de elementos suelen representarse como una matriz cuadrada con entradas que representan las relaciones entre todos los pares de elementos. Relaciones como distancias, diferencias, similitudes, parentesco, correlaciones, coocurrencias, probabilidades condicionales, etc., pueden representarse mediante dichas matrices. Dichos datos también pueden representarse como redes con vínculos ponderados entre los elementos. Dichas matrices y redes son extremadamente densas y no se pueden comprender fácilmente sin alguna forma de reducción o poda de datos.

Una red Pathfinder resulta de aplicar un método de poda que elimina los enlaces más débiles de una red (generalmente densa) de acuerdo con las longitudes de las rutas alternativas (ver más abajo). ^{[1] [2] [3]} Se utiliza como un método de escala psicométrica basado en la teoría de grafos y se utiliza en el estudio de la experiencia, la educación, ^[4] la adquisición de conocimiento , los modelos mentales , ^[5] y la ingeniería del conocimiento . También se emplea en la generación de redes de comunicación, ^[6] la depuración de software, ^[7] la visualización de patrones de citas científicas , ^[8] la recuperación de información y otras formas de visualización de datos . ^[9] Las redes Pathfinder son potencialmente aplicables a cualquier problema abordado por la teoría de redes .

Descripción general

La poda de redes tiene como objetivo resaltar los vínculos más importantes entre los elementos representados en una red. Ayuda a simplificar la recopilación de conexiones involucradas, lo que resulta valioso para la visualización de datos y para comprender las relaciones esenciales entre los elementos representados en la red.

Varios métodos de escalamiento psicométrico parten de datos por pares y producen estructuras que revelan la organización subyacente de los datos. La agrupación de datos y el escalamiento multidimensional son dos de esos métodos. El escalamiento de redes representa otro método basado en la teoría de grafos . Las redes Pathfinder se derivan de matrices de datos para pares de entidades. Debido a que el algoritmo utiliza distancias, los datos de similitud se invierten para producir diferencias para los cálculos.

En la red Pathfinder, las entidades corresponden a los nodos de la red generada, y los enlaces en la red están determinados por los patrones de proximidades. Por ejemplo, si las proximidades son similitudes, los enlaces generalmente conectarán nodos de alta similitud. Cuando las proximidades son distancias o diferencias, los enlaces conectarán las distancias más cortas. Los enlaces en la red no estarán dirigidos si las proximidades son simétricas para cada par de entidades. Las proximidades simétricas significan que el orden de las entidades no es importante, por lo que la proximidad de i y j es la misma que la proximidad de j e i para todos los pares i,j . Si las proximidades no son simétricas para cada par, los enlaces estarán dirigidos.

Algoritmo

El algoritmo Pathfinder utiliza dos parámetros.

1. El parámetro restringe la cantidad de proximidades indirectas examinadas para generar la red. es un número entero entre y , ambos inclusive, donde es la cantidad de nodos o elementos. Las rutas más cortas no pueden tener más de enlaces. Cuando , se incluyen todas las rutas posibles. ${\displaystyle q}$ ${\displaystyle q}$ ${\displaystyle 2}$ ${\displaystyle n-1}$ ${\displaystyle n}$ ${\displaystyle q}$ ${\displaystyle q=n-1}$
2. El parámetro define la métrica utilizada para calcular la distancia de las rutas (cf. la distancia de Minkowski ). es un número real entre y , inclusive. ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle 1}$ ${\displaystyle \infty }$

La distancia de la ruta se calcula como: , donde es la distancia del enlace en la ruta y . Para , es simplemente la suma de las distancias de los enlaces en la ruta. Para , es el máximo de las distancias de los enlaces en la ruta porque . Un enlace se poda si su distancia es mayor que la distancia mínima de las rutas entre los nodos conectados por el enlace. Los métodos eficientes para encontrar distancias mínimas incluyen el algoritmo de Floyd-Warshall (para ) y el algoritmo de Dijkstra (para cualquier valor de ). ${\displaystyle d_{p}}$ ${\displaystyle d_{p}=(\sum _{i=1}^{k}l_{i}^{r})^{1/r}}$ ${\displaystyle l_{i}}$ ${\displaystyle ith}$ ${\displaystyle 2\leq k\leq q}$ ${\displaystyle r=1}$ ${\displaystyle d_{p}}$ ${\displaystyle r=\infty }$ ${\displaystyle d_{p}}$ ${\displaystyle \lim _{r\rightarrow \infty }d_{p}=\max _{i=1}^{k}l_{i}}$ ${\displaystyle q=n-1}$ ${\displaystyle q}$

Una red generada con valores particulares de y se denomina . Ambos parámetros tienen el efecto de disminuir el número de enlaces en la red a medida que aumentan sus valores. La red con el número mínimo de enlaces se obtiene cuando y , es decir, . ${\displaystyle q}$ ${\displaystyle r}$ ${\displaystyle PFNet(q,r)}$ ${\displaystyle q=n-1}$ ${\displaystyle r=\infty }$ ${\displaystyle PFNet(n-1,\infty )}$

Con datos de escala ordinal (ver nivel de medición ), el parámetro debería ser porque el mismo resultaría de cualquier transformación monótona positiva de los datos de proximidad. Otros valores de requieren datos medidos en una escala de proporción. El parámetro se puede variar para obtener el número deseado de enlaces en la red o para centrarse en relaciones más locales con valores más pequeños de . ${\displaystyle r}$ ${\displaystyle \infty }$ ${\displaystyle PFNet}$ ${\displaystyle r}$ ${\displaystyle q}$ ${\displaystyle q}$

Básicamente, las redes Pathfinder conservan las rutas más cortas posibles dados los datos. Por lo tanto, los enlaces se eliminan cuando no están en las rutas más cortas. El será el árbol de expansión mínimo para los enlaces definidos por los datos de proximidad si existe un árbol de expansión mínimo único. En general, el incluye todos los enlaces en cualquier árbol de expansión mínimo. ${\displaystyle PFNet(n-1,\infty )}$ ${\displaystyle PFNet(n-1,\infty )}$

Ejemplo

Aquí hay un ejemplo de una red de buscador de caminos no dirigida derivada de las calificaciones promedio de un grupo de estudiantes de posgrado en biología. Los estudiantes calificaron la relación de todos los pares de los términos mostrados y se calculó la calificación media para cada par. Los enlaces de color azul sólido son los (etiquetados como "ambos" en la figura). Los enlaces de color rojo punteados se agregan en el . Para los enlaces agregados, no hay rutas de 2 enlaces más cortas que la distancia del enlace, pero hay al menos una ruta más corta con más de dos enlaces en los datos. Un árbol de expansión mínimo tendría 24 enlaces, por lo que los 26 enlaces en implican que hay más de un árbol de expansión mínimo. Hay dos ciclos presentes, por lo que hay distancias vinculadas en el conjunto de enlaces en el ciclo. Romper cada ciclo requeriría eliminar uno de los enlaces vinculados en cada ciclo. ${\displaystyle PFNet(n-1,\infty )}$ ${\displaystyle PFNet(2,\infty )}$ ${\displaystyle PFNet(n-1,\infty )}$

Referencias

1. Schvaneveldt, RW , ed. (1990). Pathfinder associative networks: Studies in knowledge organization [Redes asociativas Pathfinder: estudios en organización del conocimiento]. Norwood, NJ: Ablex. ISBN 978-0893916244.
2. Schvaneveldt, RW ; Durso, FT; Dearholt, DW (1989). "Estructuras de red en datos de proximidad". En Bower, G. (ed.). La psicología del aprendizaje y la motivación: avances en la investigación y la teoría (PDF) . Vol. 24. Nueva York: Academic Press. págs. 249–284.
3. Schvaneveldt, RW ; Dearholt, DW; Durso, FT (1989). "Fundamentos teóricos de grafos de redes Pathfinder" (PDF) . Computadoras y matemáticas con aplicaciones . 15 (4): 337–345. doi :10.1016/0898-1221(88)90221-0.
4. Goldsmith, T.; Johnson, P.; Acton, W. (1991). "Evaluación del conocimiento estructural". Revista de Psicología Educativa . 83 (4): 88–96. doi :10.1037/0022-0663.83.1.88.
5. Kudikyala, Reino Unido; Vaughn, RB (2005). "Comprensión de los requisitos de software mediante redes Pathfinder: descubrimiento y evaluación de modelos mentales". Revista de sistemas y software . 74 (1): 101–108. doi :10.1016/j.jss.2003.09.028.
6. Shope, SM; DeJoode, JA; Cooke, NJ; Pedersen, H. (2004). "Uso de Pathfinder para generar redes de comunicación en un análisis de tareas cognitivas". Actas de la reunión anual de la Human Factors and Ergonomics Society . 48 (3): 678–682. doi :10.1177/154193120404800386.
7. Serrano, E.; Quinn, A.; Botia, JA; Cordón, O. (2010). "Depuración de sistemas software complejos mediante redes pathfinder". Ciencias de la Información . 180 (5): 561–583. doi :10.1016/j.ins.2009.11.007.
8. Chen, C.; Song (2017). "Herramientas y aplicaciones de mapeo científico". Representación del conocimiento científico . Springer. págs. 57–137.
9. Cribbin, T. (2010). "Visualización de la estructura de los resultados de búsqueda de documentos: una comparación de enfoques de teoría de grafos". Visualización de la información . 9 (2): 83–97. doi :10.1057/ivs.2009.3.

Otra información

Se puede encontrar más información sobre redes Pathfinder y varios ejemplos de la aplicación de PFnets a una variedad de problemas en las referencias.

• El libro de 1990 está agotado. Se puede descargar una copia comprimida de los capítulos en formato PDF.

• El capítulo de 1989 del libro de Bower es un artículo que resume las redes Pathfinder y algunas aplicaciones.

Tres artículos que describen implementaciones rápidas de redes Pathfinder:

• Guerrero-Bote, V.; Zapico-Alonso, F.; Esinosa-Calvo, M.; Gómez-Crisóstomo, R.; Moya-Anegón, F. (2006). "Binary Pathfinder: una mejora en el algoritmo Pathfinder". Procesamiento y Gestión de la Información . 42 (6): 1484-1490. CiteSeerX  10.1.1.378.5375 . doi :10.1016/j.ipm.2006.03.015.
• Quirin, A; Cordón, O; Santamaría, J; Vargas-Quesada, B; Moya-Anegón, F (2008). "Una nueva variante del algoritmo Pathfinder para generar grandes mapas científicos visuales en tiempo cúbico". Procesamiento y Gestión de la Información . 44 (4): 1611-1623. doi :10.1016/j.ipm.2007.09.005.
• Quirin, A.; Cordón, O.; Guerrero-Bote, VP; Vargas-Quesada, B.; Moya-Anegón, F. (2008). "Un algoritmo rápido basado en MST para obtener redes Pathfinder". Revista de la Sociedad Americana de Ciencias de la Información y Tecnología . 59 (12): 1912–1924. CiteSeerX  10.1.1.331.1548 . doi :10.1002/asi.20904.

(Las dos variantes de Quirin et al. son significativamente más rápidas. Mientras que la primera se puede aplicar con o y cualquier valor para , la última solo se puede aplicar en los casos donde y ). ${\displaystyle q=2}$ ${\displaystyle q=n-1}$ ${\displaystyle r}$ ${\displaystyle q=n-1}$ ${\displaystyle r=\infty }$

Enlaces externos

• Lista extensa de artículos que utilizan Pathfinder
• Sitio de descarga del software Pathfinder
• Implementación de las variantes original, binaria, rápida y MST del algoritmo en C
• Tabla comparativa entre las diferentes variantes