最近看了这篇发表在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)