（python ）改进的k-shell 算法来识别关键节点Theimprovedk-shell 。。。⼀.介绍
k-shell算法中很多节点的kshell值相同，⽆法区分它们的重要性，因此对k-shell算法进⾏了改进，提出了IKS算法
⼆.算法思路
1. 熵是⽤来表⽰信息的不确定性，熵越⼤表⽰信息的不确定性越⼤。
2. 这篇⽂章将熵扩展到了复杂⽹络中，称为节点信息熵。节点信息熵越⼤，节点影响⼒越⼤。
3. 是对每个shell中的节点⽤信息熵排序，再重复从每个shell中取熵最⼤的节点。
shell代码三.公式
令节点的度为，节点的重要性 :
这⾥N为图G的节点数。节点的信息熵为：
其中j∈Γ (i)是节点vi的邻居集合。节点的信息熵考虑了邻居节点的传播效应，节点信息熵越⼤，影响⼒就越⼤。
四.算法步骤
1. 根据k-shell分解算法将⽹络分解为k壳
2. 根据上式计算节点的信息熵ei
3. 根据节点的信息熵将每个壳内的节点由⼤到⼩进⾏排序
4. 对于k-shell值最⼤的节点，选择节点信息熵最⼤的结点，然后选择节点信息熵最⼤的壳层下⼀层的节点。这个过程继续进⾏，直到在1-shell中选中节点为⽌，第⼀次迭代完成。
5. 重复步骤4，选中剩余的节点，直到选中所有的节点。忽略选中所有节点的shell。在特定壳层中，当节点信息熵值相等时，随机选择节点。
五.代码：稳定（熵值相同时，每次只选第⼀个)
import networkx as nx
import matplotlib .pyplot as plt
import math
#抽取txt 中的数据
def read_txt (data ):
g = nx .read_weighted_edgelist (data )
print (g .edges ())
return g
def gDegree (G ):
"""
将G.degree()的返回值变为字典
"""
node_degrees_dict = {}
for i in G .degree ():
node_degrees_dict [i [0]]=i [1]
v i k i v i I i I =i k ∑j =1N j
k i e =i −I ⋅j ∈Γ(i )∑
j ln I j
return node_py()
def kshell(G):
"""
kshell(G)计算k-shell值
"""
graph = G.copy()
importance_dict ={}
ks =1
des():
temp =[]
node_degrees_dict = gDegree(graph)
kks =min(node_degrees_dict.values())
while True:
for k, v in node_degrees_dict.items():
if v == kks:
temp.append(k)
node_degrees_dict = gDegree(graph) if kks not in node_degrees_dict.values():
break
importance_dict[ks]= temp
ks +=1
return importance_dict
def sumD(G):
"""
计算G中度的和
"""
G_degrees = gDegree(G)
sum=0
for v in G_degrees.values():
sum+= v
return sum
def getNodeImportIndex(G):
"""
计算节点的重要性指数
"""
sum= sumD(G)
I ={}
G_degrees = gDegree(G)
for k,v in G_degrees.items():
I[k]= v/sum
return I
def Entropy(G):
"""
Entropy(G) 计算出G中所有节点的熵
I 为重要性
e 为节点的熵sum += I[i]*math.log(I[i])
"""
I = getNodeImportIndex(G)
e ={}
for k,v in I.items():
sum=0
for i ighbors(k):
sum+= I[i]*math.log(I[i])
sum=-sum
e[k]=sum
return e
def kshellEntropy(G):
"""
kshellEntropy(G) 是计算所有壳层下，所有节点的熵值例：
{28: {'1430': 0.3787255719932099,
'646': 0.3754626894107377,
'646': 0.3754626894107377,
'1431': 0.3787255719932099,
'1432': 0.3787255719932099,
'1433': 0.3754626894107377
....
ks is a dict 显⽰每个壳中的节点
e 计算了算有节点的熵
"""
ks = kshell(G)
e = Entropy(G)
ksES ={}
ksI =max(ks.keys())
while ksI >0:
ksE ={}
for i in ks[ksI]:
ksE[i]= e[i]
ksES[ksI]= ksE
ksI -=1
return ksES
def kshellEntropySort(G):
ksE = kshellEntropy(G)
ksES =[]
ksI =max(ksE.keys())
while ksI >0:
t =sorted([(v, k)for k, v in ksE[ksI].items()],reverse=True)
ksES.append(list(i[1]for i in t))
ksI -=1
return ksES
def getRank(G):
rank =[]
rankEntropy = kshellEntropySort(G)
while(len(rankEntropy)!=0):
for i in range(len(rankEntropy)):
rank.append(rankEntropy[i].pop(0))
while True:
if[]in rankEntropy:
else:
break
return rank
G1 = nx.read_gml("l",label="id")
getRank(G1)
六.同⼀个熵下的节点应该随机选取还没有实现
======================================
七.2021.10.24更新：实现了随机选择熵相同的节点（排序结果不稳定）
import networkx as nx
import matplotlib.pyplot as plt
import math
from numpy import*
#抽取txt中的数据
def read_txt(data):
g = nx.read_weighted_edgelist(data)
print(g.edges())
return g
def gDegree(G):
"""
将G.degree()的返回值变为字典
"""
node_degrees_dict ={}
for i in G.degree():
for i in G.degree():
node_degrees_dict[i[0]]=i[1]
return node_py()
def kshell(G):
"""
kshell(G)计算k-shell值
"""
graph = G.copy()
importance_dict ={}
ks =1
des():
temp =[]
node_degrees_dict = gDegree(graph)
kks =min(node_degrees_dict.values())
while True:
for k, v in node_degrees_dict.items():
if v == kks:
temp.append(k)
node_degrees_dict = gDegree(graph) if kks not in node_degrees_dict.values():
break
importance_dict[ks]= temp
ks +=1
return importance_dict
def sumD(G):
"""
计算G中度的和
"""
G_degrees = gDegree(G)
sum=0
for v in G_degrees.values():
sum+= v
return sum
def getNodeImportIndex(G):
"""
计算节点的重要性指数
"""
sum= sumD(G)
I ={}
G_degrees = gDegree(G)
for k,v in G_degrees.items():
I[k]= v/sum
return I
def Entropy(G):
"""
Entropy(G) 计算出G中所有节点的熵
I 为重要性
e 为节点的熵sum += I[i]*math.log(I[i])
"""
I = getNodeImportIndex(G)
e ={}
for k,v in I.items():
sum=0
for i ighbors(k):
sum+= I[i]*math.log(I[i])
sum=-sum
e[k]=sum
return e
def kshellEntropy(G):
"""
kshellEntropy(G) 是计算所有壳层下，所有节点的熵值例：
{28: {'1430': 0.3787255719932099,
{28: {'1430': 0.3787255719932099,
'646': 0.3754626894107377,
'1431': 0.3787255719932099,
'1432': 0.3787255719932099,
'1433': 0.3754626894107377
....
ks is a dict 显⽰每个壳中的节点
e 计算了算有节点的熵
"""
ks = kshell(G)
e = Entropy(G)
ksES ={}
ksI =max(ks.keys())
while ksI >0:
ksE ={}
for i in ks[ksI]:
ksE[i]= e[i]
ksES[ksI]= ksE
ksI -=1
return ksES
def kshellEntropySort(G):
ksE = kshellEntropy(G)
ksES =[]
ksI =max(ksE.keys())
while ksI >0:
t =sorted([(v, k)for k, v in ksE[ksI].items()],reverse=True)
#把熵值⼀样的节点放在⼀个集合中
t_new ={}
for i in t:
t_new.setdefault(i[0],list()).append(i[1])
#按熵值排序变成列表
t =sorted([(k, v)for k, v in t_new.items()],reverse=True)
#把相同熵值的节点列表打乱顺序，相当于随机选择
sub_ksES =[]
for i in t:
if len(i[1])==1:
sub_ksES += i[1]
else:
random.shuffle(i[1])
sub_ksES += i[1]
ksES.append(sub_ksES)
# ksES.append(list(i[1] for i in t))
ksI -=1
return ksES
def getRank(G):
rank =[]
rankEntropy = kshellEntropySort(G)
while(len(rankEntropy)!=0):
for i in range(len(rankEntropy)):
rank.append(rankEntropy[i].pop(0))
while True:
if[]in rankEntropy:
else:
break
return rank
G1 = nx.read_gml("l",label="id")
getRank(G1)
======================================
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论