グラフのエントロピーを計算するにはどうすればよいですか？

Question

私はランダムに生成された正式なグラフのセットを持っており、それぞれのエントロピーを計算したいと思います。異なる言葉で同じ質問：私はいくつかのネットワークを持っており、それぞれの情報内容を計算したい。
http://www.cs.washington.edu/homes/anuprao/pubs/CSE533Autumn2010/lecture4.pdf私が探していたコードは、（エッジリスト又は隣接行列のいずれかとして）入力としてグラフをとり http://arxiv.org/abs/0711.4175v1

（PDF）と：ここ

グラフエントロピーの正式な定義を含む二つの源でありますいくつかの他の情報量の測定値を出力する。

私はどこでもこの実装を見つけることができないので、正式な定義に基づいてこれをゼロからコード化するように設定しています。誰もがすでにこの問題を解決してコードを共有しようとするならば、それは大いに感謝しています。

Answer 1

私はグラフのエントロピーの定義については、別の論文を使用して終了しましたTopologyの設定とランダムネットワークへの計算に基づいソールとS.バルベルデ（2004）
と
ネットワークエントロピー
B。H. Wang、W.X。 Wang and T. Zhou

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

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) 
} 

Answer 2

グラフを重み付けした場合は、すべての重みをソートしてカウントするのがよいでしょう。次に、式に-log（p）+ log（2）（http://en.wikipedia.org/wiki/Binary_entropy_function）を使用して、コードに必要なビット数を決定することができます。おそらく、バイナリエントロピー関数なので、これはうまくいかないでしょうか？複雑ネットワークの
情報理論：進化にと建築制約
R.V.

Answer 3

Koerner's entropy（=グラフに適用されるシャノンエントロピー）を使用できます。文献の良い参考文献はhereです。ただし、計算は一般的にはNP困難です（頂点のすべてのサブセットを検索する必要があるという愚かな理由のため）。