para - poligono en r

Use la ruta más corta para calcular la probabilidad de conexión

Question

Me pregunto si hay una función dentro de igraph para calcular las probabilidades de conexión entre vértices en un gráfico ponderado, donde los pesos para los bordes son probabilidades de conexión de los vértices adyacentes.

Construí un gráfico basado en una matriz de adyacencia en la que las probabilidades de conexión adyacentes forman los pesos (esto es para una red fluvial, por lo que cada nodo del gráfico solo está conectado a un único nodo descendente).

Tenía la esperanza de usar algo como la función short.paths en igraph, pero eso suma los pesos en lugar de calcular el producto de ellos y no puedo encontrar la manera de cambiar eso.

El siguiente ejemplo muestra cómo construyo la matriz de adyacencia a partir de los datos que tengo, que es la probabilidad de que el vértice esté conectado a su vértice descendente (ProbConn) y luego la identidad del vértice descendente (descendente). El vértice más corriente abajo es la boca del río, por lo que no está conectado a ningún otro (de ahí que el vector llamado aguas abajo comience con NA).

library(igraph)

# vector of probability of connectivity to downstream vertex
ProbConn <- c(0, 1, 0.945881098491627, 0.997349787519144, 0.891475447373691,
0.993221681072185, 0.48071450525165, 0.0292543433507856, 0.0248645581575872,
1, 0.00540807765075205, 0.661465657844344, 0.108524549747512,
0.383311676351655, 0.708853495942148, 0.00150109592270933, 0.463859846404347,
0.0011491165581467, 2.87879700370202e-09, 0.536140153595653,
0.00831752330277812, 0.00185182893416988, 0.0186237313262708,
0.398961560996748, 0.582414707676981, 0.338534342155656, 1, 0.00137024127706289,
0.291146504057852, 1, 0.0743301054564134, 0.0514743607033332,
1, 1)

# the downstream vertex of each node
downstream <- c(NA, 1, 2, 3, 4, 5, 6, 2, 2, 7, 5, 8, 4, 6, 10, 3, 11, 3, 4,
11, 6, 6, 9, 9, 9, 8, 12, 5, 10, 13, 6, 6, 14, 15)

# Create the adjacency matrix from these vectors
adjacPI <- matrix(0, nrow=length(downstream), ncol=length(downstream)) # Set up the adjacency matrix to build the distance matrix

for (i in 1:length(downstream)) {
  adjacPI[i, downstream[i]] <- ProbConn[i]  # Fill the adjacency matrix
}

# create the graph reflecting the downstream connectivity
PIgraph <- graph.adjacency(adjacPI, weighted=T)
plot(PIgraph) # visualise the graph 

PIpath <- shortest.paths(PIgraph, mode="out") 
# creates  the shortest paths matrix based on summing the distances of each step along each path   

Para extraer un ejemplo de la ruta de acceso más corta PIpath, los vértices 10 y 34 se conectan a través del vértice 15. Como se calcula en PIpath, la distancia de trayecto entre los vértices 10 y 34 (PIpath [34,10]) es 1.708, que es la suma del probabilidad de conexión entre los vértices 34 y 15 (PIpath [34,15] = 1), y los vértices 15 y 10 (PIpath [15, 10] = 0,708) Me gustaría que sea un producto para que la ruta "distancia" entre 10 y 34 es 1 * 0.708.

No estoy completamente seguro de la nomenclatura, pero los elementos de la matriz que estoy buscando serían el producto de las probabilidades de transición de cada paso entre los vértices conectados. Esencialmente reemplazando la función suma en shortest.paths con un producto.

¿Es posible calcular eso con una función en igraph o debo escribir algún código por separado para hacer esto?

Answer 1

Si los enlaces de una ruta tienen probabilidades p_1, p_2, ..., p_n de tener éxito, entonces (asumiendo independencia de las probabilidades de éxito de enlace, lo cual haré a lo largo de esta respuesta), la probabilidad de que toda la ruta tenga éxito es p_1 * p_2 * ... * p_n . Como nota, este es un producto, pero el camino más corto minimiza las sumas; un truco común para convertir productos en sumas es tomar el logaritmo. El log de la probabilidad de que la ruta tenga éxito es log(p_1) + log(p_2) + ... + log(p_n) . Maximizar eso (nuestro objetivo) es equivalente a minimizar (-log(p_1)) + (-log(p_2)) + ... (-log(p_n)) . Como todas las probabilidades se encuentran entre 0 y 1, sus registros no son positivos y, por lo tanto, los negativos de sus registros no son negativos.

En conclusión, puede establecer todos sus pesos en -log(p_i) , donde p_i es la probabilidad de que la conexión tenga éxito, y la ruta más corta entre un par de nodos (según lo calculado por la función igraph en igraph ) será la ruta que maximiza la probabilidad de conexión. Podrías construir tu gráfica como una línea dado tus vectores ProbConn y downstream cambiando a graph.data.frame :

PIgraph <- graph.data.frame(na.omit(cbind(from=seq_along(downstream), to=downstream,
                                          weight=-log(ProbConn))),
                            vertices=seq_along(downstream))