나는 그래프 엔트로피의 정의에 대해 서로 다른 용지를 사용하여 종료 토폴로지 구성 및 임의의 네트워크에 그것의 계산을 바탕으로 단독 및 S. 발 베르데 (2004)
및
네트워크 엔트로피
[B. 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)
}
그런데 일단이 함수를 구현하고 실제 그래프에 대한 엔트로피를 계산하면 이러한 측정에 실망했습니다. Wang 측정 값은 그래프의 크기와 밀도에만 의존하며 그래프 구조를 전혀 고려하지 않습니다. 그것은 주로 밀도의 척도입니다. Sole 측정 값은 노드 사이에 남아있는 정도의 다양성을 반영합니다. 그것은 다른 어떤 것보다 더 많은 희열의 척도입니다. 나는 그래프가 얼마나 복잡한 지 아닌지를 수량화하는 데 여전히 실패하고 있습니다. –