线性阈值(Linear Threshold)模型的原理及代码实现

1. 原理

线性阈值模型和独立级联模型一样，在影响力最大化任务中属于比较经典的影响力传播模型。

有关独立级联模型的相关原理和代码可以参考我的上一篇文章：独立级联(Independent Cascade)模型的原理及代码实现

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

在线性阈值模型中，每条边e=(u,v)上都存在一个权重$w_{u,v}$，$w_{u,v}$量化了节点u在节点v的所有入邻居中的影响力占比，权重越大说明节点u对节点v影响就更大。需要注意的是，节点v的所有入边上的权重之和要小于等于1。除此之外，节点v还有一个影响力阈值${\theta }_v$，这个阈值在01之间均匀随机选取，一旦确定就不再改变。节点v的阈值越高，表明节点v越不容易被影响，反之阈值越低越容易被影响。

激活过程具体来讲：初始时同样只有种子节点被激活，随后每个时间步所有未被激活的节点都根据其已被激活的入邻居到它的线性加权和是否达到阈值来决定是否激活该节点。与独立级联不同的是，每个被激活都节点都有多次机会去激活自己尚未被激活的邻居节点。

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

1. 初始化种子节点，然后激活种子节点作为初始激活集合。
2. 寻找尚未被激活且有激活节点作为邻居节点的节点，放入备选节点集合。
3. 依次对备选节点集合中的节点计算激活概率，然后尝试激活，被激活的节点将被放进激活集合。
4. 重复23步骤，直至没有可激活的节点。

2. 代码实现

在本次代码实现中，$w_{u,v}$的计算方法为：
$$w_{u,v}=\frac{1}{d_v^{in}}$$
其中$d_v^{in}$表示节点$v$的入度。从计算方法来看，如果一个节点v的入邻居很多，那么每条入边上的权重会相应降低，这保证了它们的和不会超过1。

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)计算$w_{u,v}$：

in_degree = G.in_degree()
# init influence
for e in G.edges():
    G[e[0]][e[1]]['influence'] = 1 / in_degree[e[1]]
1
2
3
4

为了简单起见，每个节点的阈值都被设置为0.5，当然也可以进行均匀随机采样：

# init threshold
threshold = uniform(size=G.number_of_nodes())
for n in G.nodes():
    # G.nodes[n]['threshold'] = threshold[0][n]
    G.nodes[n]['threshold'] = 0.5
1
2
3
4
5

初始的种子节点设置：

init_seed = [1, 15, 149, 785, 1542, 1958, 2008, 2784, 3025, 7845, 9584, 10025]
1

然后是LT模型的定义：

def linear_threshold():
    final_activated = copy.deepcopy(init_seed)
    activated = []
    while True:
        flag = False
        for v in G.nodes():
            if v in final_activated:
                continue
            activated_u = list(set(G.predecessors(v)).intersection(set(final_activated)))
            total_threshold = 0.0
            for u in activated_u:
                total_threshold += G[u][v]['influence']
            if total_threshold >= G.nodes[v]['threshold']:
                activated.append(v)
                final_activated.append(v)
                flag = True

        if flag:
            continue
        else:
            break

    return activated, final_activated
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

代码比较简单，不再解释。