Hierarchical Random Graph

  • 昨日、こんな論文を紹介していただいた(こちら)
  • データベースから取ってきた要素間のつながりの情報からグラフを作って
  • Hierarchical Random Graphを作成するというステップがあった
  • Hierarchical Random Graphに関する説明としていくつか挙げる
  • 意味的説明よりも作業的説明がわかりやすい、という人には「説明3(RのigraphパッケージのHRG用関数のヘルプ記事)」の記述が一番わかりやすいのでは、と思います。引用すると:
A hierarchical random graph is an ensemble of undirected graphs with n vertices. It is defined via a binary tree with n leaf and n-1 internal vertices, where the internal vertices are labeled with probabilities. The probability that two vertices are connected in the random graph is given by the probability label at their closest common ancestor.
HRGとは、n個のノードからなる無向グラフから作りだしたものであって、n個の葉ノード(leaf)とn-1個の節ノード(internal vertices)からなる2分岐木であり、節ノードには属性として確率が付与されている。HRG内の2つのノードが連結している確率は、当該2ノードのclosest common ancestor(2ノードから遡って(葉ノード側=末梢側)、最初に行きつくノード)に付与された値とする(HRGの推定にあたって、任意の2つの葉ノードに連結確率を求めておいて、それをうまく説明するようにHRGの2分岐木と節の属性数値とを決めるのがHRG構成のアルゴリズムらしい:和訳者注)
  • 以下に示す通り、グラフからHRGを推定すると、2分岐木と節について確率が出力される
library(igraph)
# 時間がかかる例だそうです
g <- erdos.renyi.game(10, p=1/2) + erdos.renyi.game(10, p=1/2)
hrg <- hrg.fit(g)
hrg

## The consensus tree for it
hrg.consensus(g, hrg=hrg, start=TRUE)

## Prediction of missing edges
g2 <- graph.full(4) + (graph.full(4) - path(1,2))
hrg.predict(g2)
> hrg
Hierarchical random graph, at level 3:
g1        p=   0  
'- g3     p=0.33  3 
   '- g14 p= 0.8  6  5  7  1  9  10 4  8  2 
'- g17    p=0.67  20
   '- g15 p=   0  15 11 17 19 16 18 13 12 14
> 
> ## The consensus tree for it
> hrg.consensus(g, hrg=hrg, start=TRUE)
$consensus
HRG consensus tree:
g1 -> 1  2  3  4  5  6  7  8  9  10
g2 -> 11 12 13 14 15 16 17 18 19 20
g3 -> g1 g2

$hrg
Hierarchical random graph, at level 3:
g1        p=   0  
'- g3     p=0.33  3 
   '- g14 p= 0.8  6  5  7  1  9  10 4  8  2 
'- g17    p=0.67  20
   '- g15 p=   0  15 11 17 19 16 18 13 12 14

> 
> ## Prediction of missing edges
> g2 <- graph.full(4) + (graph.full(4) - path(1,2))
> hrg.predict(g2)
$edges
      [,1] [,2]
 [1,]    5    6
 [2,]    1    6
 [3,]    3    6
 [4,]    2    6
 [5,]    4    6
 [6,]    1    5
 [7,]    2    5
 [8,]    3    5
 [9,]    4    5
[10,]    1    8
[11,]    2    8
[12,]    3    8
[13,]    4    8
[14,]    2    7
[15,]    1    7
[16,]    3    7
[17,]    4    7

$prob
 [1] 0.281802153 0.005028124 0.004929066 0.004920148 0.004813659
 [6] 0.004544067 0.004532028 0.004392293 0.004173190 0.003850587
[11] 0.003569339 0.003522883 0.003450740 0.003341852 0.003290939
[16] 0.003078743 0.003036602

$hrg
Hierarchical random graph, at level 3:
g1        p=0  
'- g6     p=1  1
   '- g3  p=1  3 2 4
'- g2     p=1  7
   '- g7  p=1  6 5 8