3

Q erdos.reyni グラフがあります。頂点に感染し、病気が頂点のどのシーケンスに従うかを確認したいですか? igraph には、get.adjacency()、neighbors() などの便利な関数があります。

詳細。これは、0,1 フラグの代わりに頂点名を使用した隣接行列であり、そこから伝染連鎖を取り出そうとしています。特定の頂点が感染した場合、グラフを介した伝染病の流れ/シーケンスのように。ここでは、感染確率について心配する必要はありません (ヒットしたすべての頂点が確率 1 で感染していると仮定します)。

頂点 1 (ここでは行 1) にヒットしたとします。頂点 4、5、18、22、23、24、25 への発信リンクがあることがわかります。したがって、次の頂点は 4,5,18...25 に接続された頂点になります。つまり、行 4、行 5、行 18、... 行 25 の値です。次に、モデルに従って、病気はこれらを通って移動します。

文字列を渡して行列の行を並べ替えることができることを理解しています。私の問題は、そのシーケンスを生成する方法がわからないことです。

マトリックスはこんな感じ。

    > channel
      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
 [1,]    4    5   18   22   23   24   25   NA
 [2,]    6   10   11   18   25   NA   NA   NA
 [3,]    7   11   18   20   NA   NA   NA   NA
 [4,]   24   NA   NA   NA   NA   NA   NA   NA
 [5,]    1    3    9   13   14   NA   NA   NA
 [6,]    3    8    9   14   19   23   NA   NA
 [7,]    3    4    8   15   20   22   NA   NA
 [8,]    2    3   25   NA   NA   NA   NA   NA
 [9,]    3    4   11   13   20   NA   NA   NA
[10,]    4    5    8   15   19   20   21   22
[11,]    3   13   15   18   19   23   NA   NA
[12,]   11   13   16   NA   NA   NA   NA   NA
[13,]    4    6   14   15   16   17   19   21
[14,]    2    6   13   NA   NA   NA   NA   NA
[15,]    3   17   20   NA   NA   NA   NA   NA
[16,]    6   15   18   23   NA   NA   NA   NA
[17,]    2   25   NA   NA   NA   NA   NA   NA
[18,]    2    5   NA   NA   NA   NA   NA   NA
[19,]    3   11   NA   NA   NA   NA   NA   NA
[20,]    1    4    7   10   12   21   22   25
[21,]    2    4    6   13   14   16   18   NA
[22,]    1    3    4   15   23   NA   NA   NA
[23,]    1   16   24   NA   NA   NA   NA   NA
[24,]    7    8   19   20   22   NA   NA   NA
[25,]    7   12   13   17   NA   NA   NA   NA

次のように、選択基準に基づいてこのマトリックスを並べ替えたいと思います。

R が最も役に立ちます (ただし、アルゴリズムに興味があるので、Python、Ruby などが最適です)。結果のベクトルの長さは 115 (8x25=200 - 85 NAs=115) になります。このようになります。これは基本的に、頂点 1 が感染した場合に病気が広がる方法です。

4,5,18,22,23,24,25,24,1,3,9,13,14,2,5,1,3,4,15,23,1,16,24,7,8,19,20,22,7,12,13,17,7,8,19,20,22, 4,5,18,22,23,24,25,7,11,18,20...

私がこれまでに知っていること: 1. R には、**igraph**隣人を計算できるパッケージがあります(graph, vertex, "out") 2. 同じパッケージで生成することもできますget.adjlist(graph...), get.adjacency

4

2 に答える 2

5

このような「感染連鎖」を見つけることは、グラフの幅優先検索と同等です。たとえば、次のようになります。

library(igraph)
set.seed(50)
g = erdos.renyi.game(20, 0.1)
plot(g)
order = graph.bfs(g, root=14, order=TRUE, unreachable=FALSE)$order

出力：

> order
 [1]  14   1   2  11  16  18   4  19  12  17  20   7   8  15   5  13   9 NaN NaN NaN

ここに画像の説明を入力

于 2013-03-27T23:58:00.973 に答える
1

行の順序をどのように定義するかは明確ではないため、いくつかのヒントを示します。

インデックス ベクトルを渡すことで、行の順列/組み合わせを選択できます。

> (m <- matrix(data=1:9, nrow=3))
     [,1] [,2] [,3]
[1,]    1    4    7
[2,]    2    5    8
[3,]    3    6    9
> m[c(2,3,1),]
     [,1] [,2] [,3]
[1,]    2    5    8
[2,]    3    6    9
[3,]    1    4    7

関数t()は行列を転置します。

行列は列優先 (または列優先) の順序で格納されます。

> as.vector(m)
[1] 1 2 3 4 5 6 7 8 9

NA値はサブセット化することで削除できます:

> qq <- c(1,2,NA,5,7,NA,3,NA,NA)
> qq[!is.na(qq)]
[1] 1 2 5 7 3

また、グラフ アルゴリズムは、Bioconductor のグラフまたは CRAN のigraph パ​​ッケージによって提供されます。

于 2013-03-27T22:57:46.420 に答える