﻿ 基于渗流模型的影响力最大化算法
«上一篇
 文章快速检索 高级检索

 智能系统学报  2019, Vol. 14 Issue (6): 1262-1270  DOI: 10.11992/tis.201906039 0

### 引用本文

HUA Yong, CHEN Bolun, ZHU Guochang, et al. An influence maximization algorithm based on percolation model[J]. CAAI Transactions on Intelligent Systems, 2019, 14(6): 1262-1270. DOI: 10.11992/tis.201906039.

### 文章历史

An influence maximization algorithm based on percolation model
HUA Yong , CHEN Bolun , ZHU Guochang , YUAN Yan , JIN Yin
School of Computer and Software Engineering, Huaiyin Institute of Technology, Huaian 223003, China
Abstract: Most of the influence maximization algorithms in social networks only focus on whether the influence of the seed node set selected is the optimal, and ignore the inherent ability of social network’s propagating influence. Using percolation simulation, we calculate the change trend of the giant component of the network generation after percolation with propagation probability, and derive the starting point at which the size of the giant component increases fastest, that is, the phase point. The phase value shows the inherent ability of the network propagating influence. The optimal seed set size of the network can be calculated through conversion of the phase value and the size of the seed set. We can obtain the optimal influence by limiting the size of the seed set to the optimal size. We performed experiments on karate club, football, high school, and soc-dolphins, verifying the effectiveness of the algorithm.
Key words: social network    influence maximization    seed set    percolation    propagation probability    giant component    phase point    phase value

1 问题描述 1.1 影响力最大化问题

1.2 独立级联模型

1.3 影响力函数

2 算法思想与步骤

1) For i=1:1:len(plist)

2) 　For j=1:1: R

3) 　　根据plist (i)对G'进行渗流模拟，形成　　　渗流后网络GP，并且获得GP的最大连通　　　子图GP'

4) 　　 C(j,i)=num(GP')；

End

End

5) C' =avg(C)；

6) 对plistC进行多项式拟合，求得拟合　　　函数F(x)；

7) 求F(x)的导函数dF(x)；

8) 通过函数dF(x)求得相变值pc

9) 最优种子集合大小 $k' = {p_c} \times n$

1)函数len(x)用来计算数组的长度，所以len(plist)的值等于1 000，此步骤具体是：在传播概率 $p \in {p_{list}}$ 的情况下，对网络G' 进行渗流；

2)采用当前传播概率p对网络G' 进行R次渗流；

3)渗流模型的定义如下：在网络G' 中，网络每条边具有统一的传播概率值p。我们对每条边产生独立的随机值pr，如果pr<p，那么此边处于占有状态，如果pr>p，那么此边处于非占有状态，也就是此边从网络中删除。通过改变统一的传播概率值p，那么存在一个值pc，当p>pc时，GP中的节点倾向于紧密的连接在一起，形成一个主团块。当p<pc时，GP中的节点倾向于形成多个零散的小团块。pc便称为网络G'的相变值。图1为渗流实验例图，图1(a)为2维晶格网络，网络中边的概率统一为p图1(b)图1(d)为渗流模拟后的网络，并且边的概率逐渐提高，我们发现当边的概率较低时，渗流模拟后的网络倾向于形成零散的团块，当边的概率较大时，渗流模拟后的网络倾向于形成一个主团块，其存在一个过度值，即网络由零散的团块到形成一个主团块的值，即相变值。图1(d)为2维晶格网络发生渗流时的状态，相变值pc=0.6。在3)中，通过对网络G' 进行渗流模拟，可以得到渗流后的网络GP并且计算求得GP的最大连通子图GP'

4)函数num(x)用于计算网络中节点的个数，所以此步骤是将GP'的节点个数存入到C中；

5)函数avg(x)用于计算矩阵每列的平均值，所以此步骤是对传播概率pR个num(GP')求平均值，并且存入到C' 中，也就是说，每个传播概率p，我们都会对G' 进行R次渗流模拟，从而产生R个num(GP')，最后将其求平均，即得到每个传播概率p所对应GP'的平均大小；

6)采用多项式拟合的方法对plistC' 进行拟合。多项式拟合是使用多项展开式去近似数据点的函数关系，并使用最小二乘法来得到多项展开式的系数，最终求得数据点函数关系的方法。多项式拟合公式为

 $F(x) = {a_0} + {a_1}x + {a_2}{x^2} + \cdots + {a_l}{x^l}，$ (1)

7)求函数F(x)的导函数dF(x)；

8)相变值pcpm的左邻域中，其中dF(pm)的值为函数dF(x)的最大值，dF(pc)的值为靠近dF(pm)最近的最小值，相变值pc为函数F(x)变化速率开始加快的起点位置；

9)求取最优种子集合大小。

3 实验结果及分析

3.1 渗流实验

3.2 相变值

 Download: 图 3 拟合函数变化速率 Fig. 3 The changing rate of fitting function

3.3 影响力模拟

3.4 平均影响力分析