Influence maximization in social networks based on TOPSIS(1)

今天发现了一个社交网络数据集网站：Network data
对于这篇文章Influence maximization in social networks based on TOPSIS，在早些时候，就看见了CSDN上的大佬实现了这个文章的代码。但是，在这里还是想自己来复现下，加入自己的一些粗浅的见解。就来再读一下，然后实现代码逻辑功能。

提出的原因

IM问题，常常都是考虑如何选择特定的有影响力的用户作为种子节点，而往往忽视了所选择用户之间的距离（distances），它可以用来确保对大规模社交网络的最小重叠与最大覆盖。同时满足这两个目标可能是矛盾的。本文提出了一种新的基于理想解相似度偏好排序技术(TOPSIS)的有影响力用户集合选择方法，该方法寻求在考虑上述两个目标的情况下给出一个解决方案。

在决策问题中，一些属性表示利润，一些表示成本。正理想解和负理想解是该方法中寻找最优解的两个主要概念。正理想使利润准则最大化，成本最小化;负理想使成本准则最大化，利润最小化。TOPSIS的目的是选择与理想正解距离最小、与理想负解距离最长的方案。
在该方法中，期望期望的目标节点具有更大的影响范围和更低的与当前种子集的重叠。
因此，以影响的扩散为利润标准，以重叠为成本标准。然后，使用TOPSIS对理想节点进行识别，并作为新成员添加到种子集，迭代k次，以获取最终的种子节点集合。

模型

看上面流程图，我们大致可以了解这篇论文中寻找种子节点的思路还是比较清晰，整个算法的创新点在于两点：
① 计算其他节点和种子节点集合之间的重叠；
② 用标题中的TOPSIS统计方法来找到最优的节点；

不妨来看看算法伪代码：

在上面的伪代码中出现了很多自定义的一些公式和字母表示，这里也贴在这里：
第5行的矩阵A由文中所定义的特征：
DS（Direct Spreding, 直接传播影响，即：节点V的度被认为是这个节点的直接影响）：

$d_v$是节点V的度。
IDS（Indirect Spreading, 不直接传播影响，用交叉熵来衡量节点V的邻居节点们之间的均匀度分布，以更加准确的确定其影响的扩散。用IDS来描述影响扩散如何影响节点V的邻居）：


$d_v^1$是节点V的一阶邻居，即V的直接邻居节点；$d_v^2$节点V的二阶邻居，即邻居的邻居，计算为：

相关系数${\lambda }_v$的计算如下：

DO（direct overlap， 直接重叠）, 和 IDO（indirect overlap， 非直接重叠 ）用来确定节点V和种子节点集的重叠范围。
在种子集中V的邻居的数目决定了节点V与种子节点的直接重叠程度，描述为：

$s_u$是一个指示函数，表述为：
$$s_u=\{\begin{array}{ll}1& \text{u is a seed set member.}\\ 0& \text{otherwise.}\end{array}$$
种子节点集和节点V之间的非直接重叠被定义为V与种子节点集所共享的邻居数目的总和，描述为：

$|N_u?N_v|$表示节点u和v之间所共享的邻居节点的数目；这个等式就确定了节点v与种子集和之间所共享的邻居的数量。

通过等式13和14就可以来计算节点v和种子节点之间的直接和间接的重叠，值得注意的是：较低的值也就是最优的节点v

综合以上所介绍的四个指标，这里就定义了一个最大化目标，即：

出于这个最大化的目的，MCIM算法在一开始就计算所有节点的这四个特征，组成下面的矩阵A，用一行来表示该节点：

以上介绍了MCIM算法理解所需的函数和变量，我们最终未知的就只有TOPSIS算法了，不妨来了解下：

TOPSIS 法是一种常用的组内综合评价方法，能充分利用原始数据的信息，其结果能精确地反映各评价方案之间的差距。基本过程为基于归一化后的原始数据矩阵，采用余弦法找出有限方案中的最优方案和最劣方案，然后分别计算各评价对象与最优方案和最劣方案间的距离，获得各评价对象与最优方案的相对接近程度，以此作为评价优劣的依据。该方法对数据分布及样本含量没有严格限制，数据计算简单易行。
来自知乎：https://zhuanlan.zhihu.com/p/37738503

OK，done!