複体のグラフ表示

• 複体というのがある
• 単体の集合だ
• お絵かきしてみる
• 単体の隣接行列は、対角成分を０としそれ以外の成分はすべて１であるような行列である
• 複体は単体同士がより小さな単体を共有した形になっている
• したがって、次のようにランダムに作ることができる
  • ノード総数を定め
  • 複体を構成する「最大化した単体」に属するノード集合を、単体ごとに定め、そのノード集合について全ノードの隣接行列の要素を１にする
  • こうすると、結構、バラバラになった複体ができてしまうので、すべての単体が連結するようにして、「複体っぽさ」を図に表したいときには次のようにすることもできる
  • 第１の単体のノード集合を決め、複体に含ませる。以降は、新たな単体を追加するときに、それまでに複体に含まれることになったノードの集合から最低１個のノードは含むようにする
  • このようにすると、単体として登録していくときに「単体の最大化」を気にせずにどんどん登録しても、最終的に出来上がる複体の隣接行列には、影響が出ないし、グラフができたあとに、最大化したクリーク(これが複体を構成する最大化した単体に相当する)を抜き出せば、その情報も取れる
  • かと思ったが、(1,2),(2,3),(3,1)という３つの１単体の場合と(1,2,3)という１つの２単体の場合が、この処理だと混ざってしまう

• • 以下、その例
    • 関連する話題がこちらとこちら

library(igraph)
# ノードの最大数
N <- 500
# 個々の単体のノード集合を格納するリストを準備する
Bs <- list()
# 各単体の最大ノード数を与える
max.n <- 10
# 単体の数を指定する
k <- 10
# N個のノード候補のうち、複体に含まれることになったノードをチェックするベクトル
check <- rep(0,N)
# 単体を一つずつ作っていく
for(i in 1:k){
# 第一の単体とそれ以外の処理を分ける
	if(i ==1){
# ノード集合を適当に取る
		Bs[[i]] <- sample(1:N,sample(1:max.n,1))
	}else{
# 単体の追加に当たっては、２個以上のノードを持つ単体を追加する
		tmp.n <- sample(2:max.n,1)
# 必ず１個は、登録済みノードから取る
		a <- sample(which(check==1),1)
# それ以外は、採用の決まったa以外から取る
		b <- sample((1:N)[-a],tmp.n-1)
# 単体のノード集合を格納する
		Bs[[i]] <- sort(c(a,b))
	}
# 複体に含まれたノードを登録する	
	check[Bs[[i]]]<-1
}
# 複体の隣接行列を作る
M2 <- matrix(0,N,N)
for(i in 1:length(Bs)){
# 単体ごとに、隣接関係を登録する
	M2[Bs[[i]],Bs[[i]]] <- 1
}
# 対角成分は0に戻す
diag(M2) <- 0
# 複体に含まれることになったノードだけにする
M2 <- M2[which(check==1),which(check==1)]
# 無向グラフとしてグラフオブジェクト化する
g2 <- graph.adjacency(M2,mode="undirected")
plot(g2)
# 最大化クリークを出せば、それが複体を構成する最大化した単体に対応するノード集合
maximal.cliques(g2)

• おまけ

n <- 3
r <- c(2,3,4)
R <- prod(r)

m <- list()

m[[1]] <- 0
cnt <- 2
for(i in 1:n){
	for(j in 1:length(m)){
		for(k in 1:(r[i]-1)){
			m[[cnt]] <- c(m[[j]],i)
			cnt <- cnt +1
		}
	}
}
m