Re: [igraph] Fwd:

[Ben Stewart-Koster]

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 <address@hidden> 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
address@hidden
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