利用独立级联模型求解影响力最大的点

问题描述

给定750个点以及点与点之间的感染概率，并且感染过程符合独立级联（IC）模型以及一次感染的要求，求解在该点集中影响力最大的top5个点与top10个点

原理介绍

给定的数据其实可以归纳为一个有向有权图结构，而整个问题也就可以抽象为一个有向有权图中求影响力最大的问题，也就是“影响力最大化”问题，该问题在本题中可以归纳为给定节点个数k，选择出k个节点作为种子集使得种子集能影响的节点数最多。

而解决这类问题最主要的就是确定传播模型，传播模型中比较经典的有独立级联（IC）模型与线性阈值（LT）模型，由于本题直接指定了传播模型，因此解决问题的关键原理其实也就集中到了独立级联（IC）模型的介绍上。

独立级联模型是一种概率型的传播模型，英文全称为Independent Cascade Model，其基本原理的描述如下：

在有向有权图G（V，E）中，点集V中的节点具有两种状态，即激活状态与待激活状态。初始状态下，处于激活状态的节点会以一定概率（这种概率就是其边集E所带的权值决定）将与其相连的处于待激活状态状态下的节点激活。

整个过程可以归纳如下：

1、首先，在初始状态下，即t=0时，有且仅有种子集合S（也可以按照顺序将各个点作为种子集合）中的节点全部被设置为激活状态。

2、之后，当t=k时，所有在t=k-1时由待激活状态转变为激活状态态的全部节点，以一定的概率去尝试影响它们所有处于待激活态的邻节点。

3、不断重复过程2，直到整个网络中所剩余的具备激活其他节点能力的节点数为0（即待激活节点为0），传播过程结束。

实验思路与过程

1、读入数据，得到图的邻接矩阵

该步骤主要完成数据的加载以及图的邻接矩阵的初始化，使用numpy中的相应函数完成即可。

def generate_graph(data):
    """
    通过输入数据生成图的邻接矩阵（感染概率矩阵）
    :param data: 输入数据(父节点, 子节点, 感染概率)
    :return: 图的邻接矩阵
    """
    num_node = int(data.max())   # 节点个数
    num_line = data.shape[0]    # 数据条数
    graph = np.zeros((num_node, num_node))
    for i in range(num_line):
        x, y = int(data[i, 0] - 1), int(data[i, 1] - 1)
        graph[x, y] = data[i, 2]
    return graph

data = np.loadtxt("DUNF with Weights.txt")
graph = generate_graph(data)
print(graph)

2、构建独立级联模型（主要逻辑）

该步骤主要完成整个模型的逻辑编写。在实现中，我将整个过程封装成立一个类，而独立级联模型等等要用到的逻辑代码则作为类中的私有函数，其中逻辑上主要可以分为模拟爆发与增量计算两个过程。

模拟爆发则是在实现单个点的独立级联传播函数的基础上对所有点进行多次模拟，采用了一定蒙特卡洛算法的思想，假设感染概率为0.3，则生成一个0到1的随机数，若该随机数大于0.3则未能通过传播，若该随机数小于0.3，则通过了传播，以此进行多次模拟（本题我分别使用100000次实验了三次，使用500000次实验了一次），得到了一个到达概率矩阵（以矩阵坐标举例，即横坐标的点传播到纵坐标的点的概率）。

class ICModel:
    """
    独立级联模型类
    """
    def __init__(self, graph):
        """
        :param graph: 感染概率矩阵
        """
        # 邻接矩阵（感染概率矩阵）
        self.graph = graph
        # 节点的个数
        self.num_node = graph.shape[0]
        # 到达概率矩阵
        self.influence_matrix = np.zeros_like(graph)

    def _ic_process(self, actived_node):
        """
        实现独立级联过程
        :param actived_node: 初始激活点
        """
        self.influence_matrix[actived_node, actived_node] += 1
        actived_new = [actived_node]
        actived_set = [actived_node]
        # 进行类似于广度优先搜索的过程
        while actived_new:
            for node in actived_new:
                actived_new.remove(node)
                p = np.random.uniform(0, 1)     # 生成[0, 1)的随机数
                news = np.where(self.graph[node] > p)[0].tolist()   # 找到通过的节点
                for new in news:
                    # 防止多次感染
                    if new not in actived_set:
                        actived_new.append(new)
                        actived_set.append(new)
                        self.influence_matrix[actived_node, new] += 1

    def _caculate_increase_matrix(self, m1, m2):
        """
        计算增量矩阵
        :return: 增量矩阵
        """
        res = m1 - m2
        res[res < 0] = 0
        return res

    def _increase(self):
        """
        计算增量过程
        :return: 影响力最大的10个点
        """
        result = []
        # 按行求和找到影响力最大的点，并作为搜索起始点
        best_node = np.argmax(self.influence_matrix.sum(axis=1))
        best_row = self.influence_matrix[best_node]
        # 将影响力最大的点加入（不要忘了加1）
        result.append(best_node + 1)
        for i in range(9):
            increase_matrix = self._caculate_increase_matrix(self.influence_matrix, best_row)
            best_node = np.argmax(increase_matrix.sum(axis=1))
            best_row = np.maximum(self.influence_matrix[best_node], best_row)
            result.append(best_node + 1)
        return result

    def run(self, times):
        """
        向外的接口，用于运行整个搜索最大影响力点的过程
        :param times: 模拟爆发的次数
        :return: 到达概率矩阵, 影响力最大的十个点
        """
        for node in range(self.num_node):
            # 显示运行进度
            if node % 50 == 0:
                print('The node\'s number: {}'.format(node))    
            for time in range(times):
                self._ic_process(node)
        self.influence_matrix /= times
        result = self._increase()
        return self.influence_matrix, result

3、开始搜索

ic = ICModel(graph)
influence_matrix, result = ic.run(100000)

实验结果与分析

可视化分析

使用Python中的networkx包进行可视化分析，networkx包是一种专门用来处理图结构数据的包，因此能够很轻松的实现可视化等操作，相关代码及结果如下

import networkx as nx
import matplotlib.pyplot as plt

G = nx.DiGraph()
G.add_weighted_edges_from(data)
node_color_map = []
node_size_map = []
# 给节点赋颜色与大小
for node in G:
    if node in result:
        node_color_map.append('red')
        node_size_map.append(50)
    else:
        node_color_map.append('green')
        node_size_map.append(5)
nx.draw(G, node_size=node_size_map, node_color=node_color_map, width=0.5)
plt.show()

由上图可视化结果，其中绿色的点为普通的节点，而红色的节点为求出的影响力最大的十个点，从图中可以很明显的看出红色的节点基本处于整个网络中比较密集的区域（也就是其出度通常都较大），与“影响力”这个要求还是比较吻合的

Donate