独立级联(Independent Cascade)模型的原理及代码实现

1. 原理

独立级联模型在影响力最大化任务中属于比较经典的影响力传播模型。

具体来讲，针对某一具体传播的实体（谣言、绯闻、产品等），将图中的每个点描述为两种可能状态：不活跃（inactive）和活跃（active）。不活跃状态表示该个体还没有接受对应实体，而活跃状态表示该个体已经接受对应的实体。节点从不活跃状态变为活跃状态表示该节点接受了对应实体，也称之为被激活。

在社交网络间，如果存在边e=(u,v)，我们可以说节点u对节点v存在影响力，反之不一定。给定一个初始的激活节点集合(也称为种子节点集合)，集合中的节点将以一定概率去激活(影响)它们未被激活的邻居节点，被激活的邻居节点又继续去激活剩下的未被激活的邻居节点，如此往复，直至没有节点可激活。需要注意的是，每个被激活的节点只有一次机会去激活其未被激活的邻居节点，如果未激活就不再尝试。

独立级联模型的关键在于“独立”，对于一个未被激活的节点v来讲，在t时刻其邻居节点中可能存在多个在t-1时刻被激活的邻居节点，这些邻居节点都会尝试激活节点v，而这些激活动作间是相互独立的。

假设在t时刻节点v有n个在t-1时刻被激活的邻居节点$a_1,a_2,...,a_n$，这些节点激活节点v的概率分别为$p_{a_1,v},p_{a_2,v},...,p_{a_n,v}$，那么节点$v$被激活的概率为：
$$1-(1-p_{a_1,v})(1-p_{a_2,v})...(1-p_{a_n,v})$$

具体来讲，只要有一个节点将节点v激活那么节点v就被激活。

那么算法步骤可以被分解为：

1. 初始化种子节点，然后激活种子节点作为初始激活集合。
2. 寻找尚未被激活且有激活节点作为邻居节点的节点，放入备选节点集合。
3. 将激活集合清空。依次对备选节点集合中的节点计算激活概率，然后尝试激活，激活过程具体来讲为：随机初始化一个概率值，如果激活概率大于等于该值则进行激活。被激活的节点将被放进激活集合。
4. 重复23步骤，直至没有可激活的节点。

2. 代码实现

在本次代码实现中，每个节点激活邻居节点的概率都由采样得到，采样分布为01之间的均匀分布。

2.1 数据集

数据集采用PyG中已经处理好的GemsecDeezer数据集，具体来讲为：

data = GemsecDeezer('data', name='RO')
graph = data[0]
G = to_networkx(graph)
1
2
3

GemsecDeezer表示从一个音乐网站Deezer上收集到的用户及其关注者社交网络，一共包含三个欧洲国家的用户：
其中name=RO表示罗马尼亚用户数据集。

2.2 独立级联

首先为每条边(u,v)都初始化一个概率值，表示节点u激活节点v的概率：

# init probability
init_pro = uniform(size=G.number_of_edges())
for idx, e in enumerate(G.edges()):
    G[e[0]][e[1]]['p'] = init_pro[idx]
1
2
3
4

初始的种子节点设置：

init_seed = [4606]
1

然后是IC模型的定义：

def ic_model():
    activated = copy.deepcopy(init_seed)
    activated_status = np.zeros(G.number_of_nodes(), dtype=int)
    # initial activate
    for seed in init_seed:
        activated_status[seed] = 1

    while True:
        # 寻找未被激活且与激活节点相连的节点
        candidate_nodes = []
        candidate_nodes_pro = {}
        for v in G.nodes():
            candidate_nodes_pro[v] = []
            for u in activated:
                if G.has_edge(u, v) and activated_status[v] != 1:
                    if v not in candidate_nodes:
                        candidate_nodes.append(v)
                    # 添加概率
                    candidate_nodes_pro[v].append(G[u][v]['p'])

        print(candidate_nodes)
        if len(candidate_nodes) == 0:
            break

        # 计算概率
        probability = []
        for candidate_node in candidate_nodes:
            pro = 1.0
            for p in candidate_nodes_pro[candidate_node]:
                pro = pro * (1 - p)

            probability.append(1 - pro)

        # 尝试激活
        # 下一轮传播过程中的初始激活节点是本轮被激活的节点
        activated = []
        for candidate_node, pro in zip(candidate_nodes, probability):
            s = random.random()
            if pro >= s:
                activated_status[candidate_node] = 1
                activated.append(candidate_node)

    return activated_status
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

最后返回网络中所有节点的激活状态。