如何计算图的熵？

Question

我有一组随机生成的形式图，我想计算每个图的熵。同样的问题，换句话说：我有几个网络，想计算每个网络的信息内容。

以下是包含图熵正式定义的两个来源：
http://www.cs.washington.edu/homes/anuprao/pubs/CSE533Autumn2010/讲座4.pdf (PDF) http://arxiv.org/abs/0711.4175v1

我正在寻找的代码将图表作为输入（作为边缘列表或邻接矩阵）并输出许多位或信息内容的一些其他度量。

因为我在任何地方都找不到它的实现，所以我开始根据正式定义从头开始编写代码。如果有人已经解决了这个问题并且愿意分享代码，我们将不胜感激。

Answer 1

我最终使用不同的论文来定义图熵：
复杂网络的信息论：论演化和架构约束
RV Sole 和 S. Valverde (2004)
和
基于拓扑配置的网络熵及其对随机网络的计算
BH Wang、WX Wang 和 T. Zhou

计算每个值的代码如下。该代码假设您有一个无向、未加权的图，没有自循环。它以邻接矩阵作为输入并返回以位为单位的熵量。它是在 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)
}

Answer 2

如果您有一个加权图，一个好的开始就是对所有权重进行排序和计数。然后，您可以使用公式 -log(p)+log(2) (http://en.wikipedia.org/wiki/Binary_entropy_function) 来确定代码所需的位数。也许这不起作用，因为它是二元熵函数？

Answer 3

您可以使用 Koerner 熵（= 应用于图表的香农熵）。一个很好的参考文献是此处。但请注意，计算通常是 NP 困难的（出于愚蠢的原因，您需要搜索顶点的所有子集）。