Apologies for the triple posting now but this question was addressed for me today on stack overflow.
http://stackoverflow.com/questions/32878028/use-shortest-path-to-calculate-probability-of-connection On 1 October 2015 at 10:46, Ben Stewart-Koster < [email protected]> wrote: > Apologies for the double posting, I hit send by accident without finishing > my message. > > > Dear all, > > I'm wondering if there is a function within igraph way to calculate > connection probabilities among vertices in a weighted graph, where the > weights for the edges are probabilities of connection of the adjacent > vertices. > > I've built a graph based on such an adjacency matrix where adjacent > connection probabilities form the weights (this is for a river network so > each node of the graph is only connected to a single downstream node). > > I had hoped to use something like the shortest paths function in igraph > but that sums the weights rather than calculates the product of them and I > can't work out a way to change that. > > I have included an example below where I construct the adjacency matrix > from the data I have, which is the probability that the vertex is connected > to the downstream vertex and then the identity of the downstream vertex. > The most downstream vertex is the river mouth so it is connected to no > other (hence the downstream vector begins with NA). > > # vector of probability of connectivity to downstream node/vertice > 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 vertice 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) > > PIpath <- shortest.paths(PIgraph, mode="out") > > Matrix PIpath is then the shortest paths matrix based on summing the > distances of each step along each path. > Is it possible to calculate the product of the steps along each path? > > To extract an example from the graph, nodes 10 and 34 are connected via > node 15. > As calculated in PIpath, the path distance between nodes 10 and 34 > (PIpath[34,10]) is 1.708 which is the sum of the probability of connection > between nodes 34 and 15 (PIpath[34,15] = 1), > and nodes 15 and 10 (PIpath[15, 10] = 0.708) > I would like for that to be a product so the path "distance" between 10 > and 34 is 1*0.708. > Is it possible to calculate that for all possible paths to the river mouth > with a function in igraph or do I need to write some code separately to do > this? > > Any suggestions would be extremely helpful. Thank you. > > Ben > > -- > Dr Ben Stewart-Koster > Research Fellow > Australian Rivers Institute > Griffith University > Ph: +61 7 3735 9206 > Fax: +61 7 3735 7615 > > > > -- > Dr Ben Stewart-Koster > Research Fellow > Australian Rivers Institute > Griffith University > Ph: +61 7 3735 9206 > Fax: +61 7 3735 7615 > > _______________________________________________ > igraph-help mailing list > [email protected] > https://lists.nongnu.org/mailman/listinfo/igraph-help > > -- Dr Ben Stewart-Koster Research Fellow Australian Rivers Institute Griffith University Ph: +61 7 3735 9206 Fax: +61 7 3735 7615
_______________________________________________ igraph-help mailing list [email protected] https://lists.nongnu.org/mailman/listinfo/igraph-help
