Influence maximization in social networks based on TOPSIS(2)

按照上一篇中所描述的算法逻辑和相关的伪代码，可以得到在文中所定义的初始决策矩阵A，即：

同样的，所用数据集是karate_club_graph数据集，其图形之前绘制过，如下图：

在jupyter notebook中运行，可以比较方便的看到这个矩阵的结构：

注意这个矩阵的名称，叫做（decision matrix）决策矩阵，结合TOPSIS法(优劣解距离法)介绍及 python3 实现一文中的详细解释TOPSIS算法，我们知道，可以直接将我们得到的初始决策矩阵用来作为判别的四个指标。
但有点不想写topsis决策函数了，就直接使用知乎大佬的实现：

import numpy as npdef topsis(data1, weight=None, n=0):# 二维数组的矩阵转换成pandas中的数据类型dataframe# data2 = pd.DataFrame(data1, index=[i for i in range(1, n+1)], columns=['DS', 'IDS', 'DO', 'IDO'])# 归一化data = data1 / np.sqrt((data1 ** 2).sum())# 最优最劣方案# Z是正理想解和负理想解矩阵Z = pd.DataFrame([data.min(), data.max()], index=['负理想解', '正理想解'])# 距离#weight = entropyWeight(data) if weight is None else np.array(weight)Result = data1.copy()Result['正理想解'] = np.sqrt(((data - Z.loc['正理想解']) ** 2 * weight).sum(axis=1))Result['负理想解'] = np.sqrt(((data - Z.loc['负理想解']) ** 2 * weight).sum(axis=1))# 综合得分Result['综合得分'] = Result['负理想解'] / (Result['负理想解'] + Result['正理想解'])Result['排序'] = Result.rank(ascending=False, method='first')['综合得分']print(Result)return Result[(Result['排序'] == 1.0)].index.tolist()

调用后，的输出为：

if __name__ == '__main__':G = nx.karate_club_graph()print(MCIM(G, 5).calc())

运行结果：[33, 32, 2, 0, 1, 3]
也即是，对应的图中的节点是：34、33、3、1、2、4。

全部代码如下：

# Influence maximization in social networks based on TOPSIS
import networkx as nx
import math
import numpy as np
import pandas as pdclass MCIM(object):def __init__(self, G, k):""":param G: networkx:param k: 种子节点大小"""self.G = G  # 图self.k = kself.SS = []  # 种子节点集合self.SS.append(self.getMaxDegreeNode())  # 初始加入最大度节点self.weight = [0.3, 0.2, 0.3, 0.2]  # topsis判别计算权重# 得到图中度最大的节点def getMaxDegreeNode(self):dic = self.G.degree()return sorted(dict(dic).items(), key=lambda x: x[1], reverse=True)[:1][0][0]def calcNodeIDS_E1(self, v):result = 0for u in list(self.G.neighbors(v)):result += self.G.degree(u) / self.G.degree(v) * math.log(self.G.degree(u) / self.G.degree(v))return -1 * resultdef calcNodeIDS_E2_dv2(self, node):resu = 0for u in list(self.G.neighbors(node)):resu += self.G.degree(u)return resudef findMaxCalcNodeIDS_E2_dv2(self):max = 0for i in range(len(self.G)):val = self.calcNodeIDS_E2_dv2(i)if val > max:max = valreturn maxdef calcNodeIDS_Coefficient(self, v):return self.calcNodeIDS_E2_dv2(v) / self.findMaxCalcNodeIDS_E2_dv2()def calcNodeIDS_E2(self, v):result = 0for u in list(self.G.neighbors(v)):result += self.G.degree(u) / self.calcNodeIDS_E2_dv2(v) * math.log(self.G.degree(u) / self.calcNodeIDS_E2_dv2(v))return -1 * resultdef calcNodeDS(self, node):# calculate node v's degreereturn self.G.degree(node)def calcNodeIDS(self, node):return self.calcNodeIDS_E1(node) + self.calcNodeIDS_Coefficient(node) * self.calcNodeIDS_E2(node)def calcNodeDO(self, node):resu = 0for u in list(self.G.neighbors(node)):if u in self.SS:resu += 1return resudef calcNodeIDO(self, v):Nv = self.G.neighbors(v)resu = 0for seed in self.SS:Nu = self.G.neighbors(seed)com = [val for val in Nv if val in Nu]temp_resu = 0for node in com:if node in self.SS:temp_resu += 1resu += temp_resureturn resu# 生成矩阵Adef generateMatrixA(self):A = []for i in range(len(self.G)):# 依次计算每个节点的四个特征A.append([self.calcNodeIDS(i), self.calcNodeIDS(i), -1 * self.calcNodeDO(i), -1 * self.calcNodeIDO(i)])return np.array(A)# 决策函数def topsis(self, matrixa, weight, n):# 二维数组的矩阵转换成pandas中的数据类型dataframedata1 = pd.DataFrame(matrixa, index=[i for i in range(n)], columns=['DS', 'IDS', 'DO', 'IDO'])# 归一化data = data1 / np.sqrt((data1 ** 2).sum())# 最优最劣方案# Z是正理想解和负理想解矩阵Z = pd.DataFrame([data.min(), data.max()], index=['负理想解', '正理想解'])# 距离# weight = entropyWeight(data) if weight is None else np.array(weight)Result = data1.copy()Result['正理想解'] = np.sqrt(((data - Z.loc['正理想解']) ** 2 * weight).sum(axis=1))Result['负理想解'] = np.sqrt(((data - Z.loc['负理想解']) ** 2 * weight).sum(axis=1))# 综合得分Result['综合得分'] = Result['负理想解'] / (Result['负理想解'] + Result['正理想解'])Result['排序'] = Result.rank(ascending=False, method='first')['综合得分']return Result[(Result['排序'] == 1.0)].index.tolist()def calc(self):MatrixA = self.generateMatrixA()removed_node_list = []for i in range(self.k):# remove u from matrix ， 即：删除所在行 np.delete(MatrixA, i, 0)node_i = self.SS[len(self.SS) - 1]removed_node_list.append(node_i)for node in list(self.G.neighbors(node_i)):if node not in removed_node_list:MatrixA[node][2] += 1for i_node in list(self.G.neighbors(node)):if i_node not in removed_node_list:com = [val for val in list(self.G.neighbors(node_i)) if val in list(self.G.neighbors(node))]MatrixA[i_node][3] += len(com)# find the optimal solution by topsis(A)u = self.topsis(MatrixA, self.weight, len(MatrixA))[0]self.SS.append(u)# endreturn self.SSif __name__ == '__main__':G = nx.karate_club_graph()print(MCIM(G, 5).calc())