13

ランダムに生成された形式グラフのセットがあり、それぞれのエントロピーを計算したいと思います。同じ質問を別の言葉で言います。私はいくつかのネットワークを持っており、それぞれの情報量を計算したいと考えています。

グラフ エントロピーの正式な定義を含む 2 つのソースを次に 示し ます
。

私が探しているコードは、グラフを入力として (エッジ リストまたは隣接行列として) 受け取り、ビット数またはその他の情報コンテンツの尺度を出力します。

これの実装がどこにも見つからないため、正式な定義に基づいてゼロからコードを作成しようとしています。誰かがすでにこの問題を解決していて、喜んでコードを共有してくれるなら、大歓迎です。

4

3 に答える 3

6

グラフ エントロピーの定義に別の論文を使用することになりました:
複雑なネットワークの情報理論: 進化とアーキテクチャの制約について
RV ソールと S. バルベルデ (2004)
および
トポロジ構成に基づくネットワーク エントロピーとランダム ネットワークへのその計算
BH Wang、WX WangとT.周

それぞれを計算するコードは以下のとおりです。このコードは、自己ループのない無向で重みのないグラフがあることを前提としています。隣接行列を入力として取り、エントロピーの量をビット単位で返します。R で実装され、sna パッケージを使用します。

graphEntropy <- function(adj, type="SoleValverde") {
  if (type == "SoleValverde") {
    return(graphEntropySoleValverde(adj))
  }
  else {
    return(graphEntropyWang(adj))
  }
}

graphEntropySoleValverde <- function(adj) {
  # Calculate Sole & Valverde, 2004 graph entropy
  # Uses Equations 1 and 4
  # First we need the denominator of q(k)
  # To get it we need the probability of each degree
  # First get the number of nodes with each degree
  existingDegrees = degree(adj)/2
  maxDegree = nrow(adj) - 1
  allDegrees = 0:maxDegree
  degreeDist = matrix(0, 3, length(allDegrees)+1) # Need an extra zero prob degree for later calculations
  degreeDist[1,] = 0:(maxDegree+1)
  for(aDegree in allDegrees) {
    degreeDist[2,aDegree+1] = sum(existingDegrees == aDegree)
  }
  # Calculate probability of each degree
  for(aDegree in allDegrees) {
    degreeDist[3,aDegree+1] = degreeDist[2,aDegree+1]/sum(degreeDist[2,])
  }
  # Sum of all degrees mult by their probability
  sumkPk = 0
  for(aDegree in allDegrees) {
    sumkPk = sumkPk + degreeDist[2,aDegree+1] * degreeDist[3,aDegree+1]
  }
  # Equivalent is sum(degreeDist[2,] * degreeDist[3,])
  # Now we have all the pieces we need to calculate graph entropy
  graphEntropy = 0
  for(aDegree in 1:maxDegree) {
    q.of.k = ((aDegree + 1)*degreeDist[3,aDegree+2])/sumkPk
    # 0 log2(0) is defined as zero
    if (q.of.k != 0) {
      graphEntropy = graphEntropy + -1 * q.of.k * log2(q.of.k)
    }
  }
  return(graphEntropy)
}

graphEntropyWang <- function(adj) {
  # Calculate Wang, 2008 graph entropy
  # Uses Equation 14
  # bigN is simply the number of nodes
  # littleP is the link probability.  That is the same as graph density calculated by sna with gden().
  bigN = nrow(adj)
  littleP = gden(adj)
  graphEntropy = 0
  if (littleP != 1 && littleP != 0) {
    graphEntropy = -1 * .5 * bigN * (bigN - 1) * (littleP * log2(littleP) + (1-littleP) * log2(1-littleP))
  }
  return(graphEntropy)
}
于 2011-08-10T02:39:13.483 に答える
1

重み付けされたグラフがある場合は、すべての重みを並べ替えてカウントすることから始めることをお勧めします。次に、式 -log(p)+log(2) (http://en.wikipedia.org/wiki/Binary_entropy_function) を使用して、コードに必要なビット数を決定できます。バイナリエントロピー関数なので、これは機能しないのでしょうか?

于 2011-08-05T02:49:06.757 に答える