¿Cómo calculo la entropía de un gráfico?

Question

Tengo un conjunto de gráficos formales generados al azar, y me gustaría calcular la entropía de cada uno. La misma pregunta en palabras diferentes: tengo varias redes y quiero calcular el contenido de información de cada una.

Aquí hay dos fuentes que contienen definiciones formales de gráfico de entropía:
http://www.cs.washington.edu/homes/anuprao/pubs/CSE533Autumn2010/lecture4.pdf (PDF) http://arxiv.org/abs/0711.4175v1

El código Busco toma un gráfico como entrada (ya sea como una lista borde o una matriz de adyacencia) y genera una cantidad de bits o alguna otra medida de contenido de información.

Como no puedo encontrar una implementación de esto en ninguna parte, me estoy preparando para codificar esto desde cero en función de las definiciones formales. Si alguien ya ha resuelto este problema y está dispuesto a compartir el código, sería muy apreciado.

Answer 1

Terminé usando diferentes tipos de papel para las definiciones de entropía gráfico:
Teoría de la información de las redes complejas: sobre la evolución y Restricciones de arquitecturas
R.V. Sole y S. Valverde (2004)
y
Red de entropía basado en la configuración de topología y su cálculo al azar Redes
B.H. Wang, W.X. Wang y T. Zhou

El código para calcular cada uno está por debajo. El código supone que tiene un gráfico no ponderado no dirigido sin bucles automáticos. Toma una matriz de adyacencia como entrada y devuelve la cantidad de entropía en bits. Se implementa en R y hace uso del 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

Si tiene un gráfico ponderado, un buen comienzo sería ordenar y contar todos los pesos. Luego puede usar la fórmula -log (p) + log (2) (http://en.wikipedia.org/wiki/Binary_entropy_function) para determinar la cantidad de bits que se necesitarán para el código. Tal vez esto no funciona porque es la función de entropía binaria?

Answer 3

Puede utilizar Koerner's entropy (= entropía de Shannon se aplica a un gráfico). Una buena referencia para la literatura es here. Sin embargo, tenga en cuenta que el cálculo es en general NP-hard (por la estúpida razón de que necesita buscar todos los subconjuntos de vértices).