4

TLDR: igraph の 2 つの頂点間のすべてのパスのエッジ タイプを抽出したいと思います。これを行うための比較的健全な方法はありますか？

私が最近勤務している診療所では、高校でかなり大規模な (1400 人) の結核接触者調査を実施しました。すべての生徒と教師 (!) のクラス スケジュールがあり、それらを (R の igraph を使用して) ネットワークに配置しました。各生徒と各部屋と期間の組み合わせを頂点として使用します (たとえば、期間の 123 号室のクラス)。 1 は、期間 2 の部屋 123 にあるクラスへの有向エッジを持つ頂点です)。私はまた、どの部屋が換気システムを共有しているかを知っています。グラフは唯一のソース ケースから出力されるため、ネットワーク上のすべてのパスには、可変数の部屋期間の頂点で区切られたソースと連絡先の 2 人だけが含まれます。概念的には、次の 4 種類のパスがあります。

  • 個人的な接触による暴露 (ソース -> 接触のみ)
  • 共有クラスの露出 (ソース -> ルーム期間 -> 連絡先)
  • 次の期間の露出 (ソース -> 123 号室期間 1 -> 123 号室期間 2 -> 連絡先)
  • 換気暴露 (ソース -> Room 123 Period 1 -> Room 125 Period 1 -> contact)

すべてのエッジには、それが人対人曝露、同室異期、換気エッジのいずれであるかを示す属性があります。

このネットワークで感染をモデル化するための中間ステップとして、学生がそれぞれのタイプの感染を何回経験したかを簡単に数えたいと思います。たとえば、学生が感染源とクラスを共有し、その後、感染源がいた部屋にいる可能性があります。その学生の指標は次のようになります。

personal.contact: 0
shared.class:     1
next.period:      1
vent:             1

ただし、この種の情報を取得する最善の方法はわかりません-個人的な連絡先リンクを簡単に特定できる最短パスを取得する関数がありますが、すべてのパスを評価する必要があると思います(これを尋ねるのはクレイジーなことのようです)典型的なソーシャルネットワークの場合、ソースとルーム期間のみがアウトエッジを持っている場合はそれほど怒っていません)。ソースから連絡先への各パスがエッジ タイプの順序付けられたベクトルによって表されるポイントにたどり着くことができれば、それらを自分の基準に簡単にサブセット化できると思います。そこにたどり着く方法がわかりません。igraph がこのための適切なフレームワークではなく、学生のスケジュールに大きな恐ろしいループを書く必要があるだけなら、それでいいのです! しかし、その穴に飛び込む前に、いくつかのガイダンスをいただければ幸いです。

以下は、3 つの間接パスのそれぞれとの連絡先のサンプル グラフです。

# Strings ain't factors
options(stringsAsFactors = FALSE)  
library(igraph)

# Create a sample case
edgelist <- data.frame(out.id = c("source", "source", 
                                  "source", "Rm 123 Period 1", 
                                  "Rm 125 Period 2", "Rm 125 Period 3", 
                                  "Rm 127 Period 4", "Rm 129 Period 4"),
                       in.id = c("Rm 123 Period 1", "Rm 125 Period 2", 
                                 "Rm 127 Period 4", "contact", 
                                 "Rm 125 Period 3", "contact", 
                                 "Rm 129 Period 4", "contact"),
                       edge.type = c("Source in class", "Source in class",
                                     "Source in class", "Student in class",
                                     "Class-to-class", 
                                     "Student in class", "Vent link",
                                     "Student in class"
                                     )
)

samp.graph <- graph.data.frame(edgelist, directed = TRUE)

# Label the vertices with meaningful names
V(samp.graph)$label <- V(samp.graph)$name

plot(samp.graph, layout = layout.fruchterman.reingold)
4

1 に答える 1

1

あなたのグラフモデルを理解しているかどうかは完全にはわかりませんが、質問が次の場合:

I have two vertices and I wish to extract every path between them,
then extract the edge attributes of those edges.

おそらくこれはうまくいくかもしれません。

幅優先検索を使用します。Igraph には 1 つ含まれていますが、自分で作成するのは簡単です。これにより、どの情報を取得するかについてより柔軟になります。グラフにサイクルがないと仮定します-そうしないと、無限の数のパスが得られます。私はあまり Python を知りません (ただし、R では igraph を使用します)。そこで、いくつかの疑似コードを示します。

list <- empty

allSimplePaths(u, v, thisPath)
  if (u == v) return
  for (n in neighborhood(u))
    if (n in thisPath)
      next
    if (u == v)
      list <- list + (thisPath + v)
  for (n in neighborhood(u))
    thisPath <- thisPath + n
    allSimplePaths(n, v, thisPath)
    thisPath <- thisPath - thisPath.end

基本的には、「各頂点から、すべての可能な展開パスを試して、最後に到達する」と書かれています。別の thisPathEdges を追加してエッジを挿入し、それを関数と頂点に渡すのは簡単なことです。もちろん、これは再帰的でない方がうまくいくでしょう。このアルゴリズムは、十分な数のノードでスタックを破壊する可能性があるため、注意してください。

@PaulG のモデルを使用して、学生のノード間に複数のエッジを配置することもできます。幅優先検索を実行して病気がどのように広がるかを確認したり、最小スパニング ツリーを見つけて時間の見積もりを取得したり、最小カットを見つけて進行中の感染などを隔離したりするなど、クールなことを行うことができます。

于 2012-07-31T07:18:19.733 に答える