Capítulo 23 Teoría de grafos
Algunos conceptos clave (Sabogal Sánchez and Ardila Romero 2015) en el análisis de redes son:
Los nodos también son llamados vértices. Los enlaces también son llamados conexiones o aristas -edges-.
Los enlaces que unen un nodo consigo mismo se denominan lazos o bucles.
Una sucesión de enlaces que unen cualquier par de nodos se denomina cadena. Una cadena que une un nodo consigo mismo se la denomina ciclo.
Un grafo se dice que es conexo si, dados dos nodos cualesquiera, existe por lo menos una cadena que los une.
Un grafo parcial o red parcial es aquella en donde se representan todos los nodos de un grafo original, pero se le han suprimido algunos enlaces. Si lo que se tiene es un subconjunto de nodos junto con todos los enlaces correspondientes, se llama subred.
Para representar la información de un grafo se utilizan dos estrategias básicas.
Una matriz, denominada de adyacencia. La matriz de adyacencia tiene tantas filas y tantas columnas como nodos (P). La fila (\(P_i\)) representan el nodo de salida y la columna (\(P_j\)) el nodo de llegada. El valor indica el número de enlaces entre el par \([P_i, P_j]\). En la diagonal sólo habrá un valor si hay un lazo o bucle. Si el grafo no es dirigido, será una matriz simétrica. La suma de los valores de una fila indica el número de enlaces de salida (grado de salida). La suma de los valores de una columna indica el número de enlaces de llegada (grado de llegada). Un nodo aislado tendrá cero tanto en su fila como en su columna.
Un vector de duplas de nodos. El primer valor de las duplas es el nodo de salida, denominado también source. El segundo valor de las duplas es el nodo de entrada, denominado también target.
Tamaño: Se refiere a la cantidad de nodos y enlaces que contiene. Cuanto mayor sea el número de nodos y conexiones, mayor será el tamaño de la red.
Densidad: La densidad de la red se refiere a la proporción de conexiones existentes en la red en relación al total posible de conexiones. Una red densa tiene una gran cantidad de conexiones, mientras que una red dispersa tiene pocas conexiones. La densidad se expresa como un valor entre 0 y 1, siendo 1 una red completamente densa.
Modularidad: La modularidad se refiere a la estructura interna de la red, es decir, cómo se agrupan los nodos en comunidades o módulos. La modularidad mide la fuerza de la división de una red en módulos o comunidades bien definidas. Una alta modularidad indica que los nodos están más conectados dentro de sus propios grupos que con otros grupos.
Centralidad: La centralidad mide la importancia relativa de un nodo en la red. Hay varios tipos de centralidad, como la centralidad de grado (que se refiere a cuántos enlaces de entrada y salida tiene un nodo), la centralidad de intermediación (que se refiere a cuánto un nodo actúa como intermediario entre otros nodos), y la centralidad de cercanía (que se refiere a cuán cerca está un nodo de todos los demás nodos).
Grado de separación: El grado de separación mide la distancia más corta entre dos nodos en la red. Si dos nodos están directamente conectados, su grado de separación es 1. Si no están conectados directamente, su grado de separación es el tamaño de la cadena. El grado de separación promedio en una red también puede ser un indicador de la conectividad general de la red.