最近看了这篇发表在EPL上的有关影响力最大的论文
论文代码根据文章中对于算法的介绍进行了复现，希望大家批评指正
import networkx as nx
import matplotlib.pyplot as plt
def welsh_powell(graph):
# 将图中结点按度的递减顺序进行排列
degree_graph = dict(nx.degree(graph))
trans_degree = list(zip(degree_graph.values(), degree_graph.keys()))
trans_degree.sort(reverse=True)
nodes = [item[1] for item in trans_degree]
signs = [0 for _ in trans_degree]
# print(nodes)
# print(len(nodes))
# print(signs)
# print(len(signs))
# 着色
# 按排列顺序对与前面着色结点不邻接的结点着上同样的颜色
# 直到所有的结点全部着上色为止
colors = []
for i in range(len(nodes)):
if signs[i] == 0:
signs[i] = 1
tmp = [nodes[i]]
cache = list(graph.neighbors(nodes[i]))
for j in range(i+1, len(nodes)):
if signs[j] == 0 and nodes[j] not in cache:
signs[j] = 1
tmp.append(nodes[j])
cache_ = list(graph.neighbors(nodes[j]))
cache.extend(cache_)
cache = list(set(cache))
colors.append(tmp)
print(colors)
print(len(colors))
return colors
def pick_spreaders(colors, num):
max_size = 0
max_set = []
for item in colors:
if len(item) > max_size:
max_size = len(item)
max_set = item
return max_set[:num]
if __name__ == '__main__':
# G = nx.read_edgelist(r"F:\OpenNE\data\karate\karate.edgelist")
G = nx.read_edgelist(r"E:\NE_DATA\email\email-Eu-core.edgelist")
# nx.draw_networkx(G)
# plt.show()
independent_set = welsh_powell(G)
spreaders = pick_spreaders(independent_set, 42)
print(spreaders)