基于澳大利亚火灾有向网络节点属性的链路预测研究

李 莉，田 甜，刘 闯

(1. 山西大学计算机与信息技术学院，山西 太原 030006；2. 杭州师范大学阿里巴巴商学院，浙江 杭州 311121)

0 引言

图1 澳大利亚的气候、降雨量以及植被示意图Fig.1 A diagram of Australia’s climate, rainfall and vegetation

从2019年9月开始澳大利亚大火持续不断，截至12月底，澳大利亚已经有超过1 200万英亩的土地被烧毁，1 600多座房屋被摧毁，至少18人死亡.悉尼连续几周被浓烟笼罩，墨尔本等城市甚至是远在2 000 km之外的新西兰都深受影响.

根据澳大利亚地理形势的研究[1-2]，我们从气候、温度、降水量、地形、风向、风速、植被方面对澳大利亚山火不断蔓延的原因进行分析：南部、西南部形成地中海气候，温度大约在21—24℃；东南沿海较湿润，形成亚热带湿润气候，温度大约在24—33℃;东北部形成热带雨林气候，温度大约在27—33℃；最南端形成温带海洋性气候，温度大约在18—24℃；西部沿海形成热带草原气候，温度大约在33—39℃;中部形成干燥少雨的热带沙漠气候，温度大约在30—39℃.澳大利亚的气候、降雨量以及植被情况如图1所示.

复杂网络是由数量巨大的节点与节点之间复杂的关系构成的网络结构.链路预测作为复杂网络分析中的一个重要研究领域，它是指根据已知的网络结构等信息去预测网络中尚未产生连边的两个节点之间产生连边的可能性，主要包括预测已经存在但尚未被发现的链接，以及预测现在尚未存在但未来可能存在的链接的两类问题[3].

链路预测问题的研究在很多领域都有着极其重要的应用价值，比如：将链路预测应用到蛋白质-蛋白质相互作用网络[4]、食物网和代谢网络中可以指导科研人员进行有针对性的实验，从而提高实验效率、降低实验成本[5-6]；应用到电子商务网站上进行商品推荐[7-8];应用到社交网络中进行朋友推荐[9-10]以及对敌友关系进行预测[11]；链路预测还可以对股票指数[12]和疾病信号[13]进行预测等.

针对有向网络的链路预测是极具挑战性的[14]，我们不仅要考虑任意两节点之间链接的存在性，还要考虑链接的方向性.我们可以从两方面着手研究有向网络：

一是可以将无向网络中的方法应用到有向网络中；二是研究出专门针对有向网络的方法.

在真实的网络中，个体与个体之间的关系是非常复杂的，有时很难精确地刻画出简单的无向图.比如需要引入加权、有向等更加复杂的网络来描述微博关注网络、社交关系演化网络和食物链网络等.这类型的复杂网络的链路预测往往与实际应用紧密结合，因此越来越多的研究者开始对其进行关注.张千明等人系统地介绍了有向网络的“势理论”预测[15]，认为如果一条边的出现可以生成更多的可定义势的子图，那么该边出现的概率就越大.除了基于局部子图的预测方法，还有一些基于有向网络中局部随机游走过程的方法，同样链路预测效果很好[16-17].

本论文对澳大利亚火灾网络的有向链接从两方面确定.一方面是根据任意两个节点的经纬度计算两个节点的距离，再根据每个月某个节点的风速计算出从某一个节点的火灾传播到另一个节点所需的时间，根据时间来判断有向边的存在性.另一方面根据风向考虑两个节点之间产生联系的可能性.

如何准确地对澳大利亚的山火进行链路预测，就要考虑到澳大利亚火灾网络中节点的属性.利用Jaccard系数算法，对节点的气候、温度等属性计算节点的属性相似度，然后根据澳大利亚网络中节点的风向属性来建立火灾的有向网络的拓扑结构，将节点的属性相似度与真实存在的有向边进行对比，从而更好地对未来火灾发展趋势进行预测.

1 数据预处理

表1 24 h内的有向边数量Tab.1 Number of directed edges

澳大利亚火灾网络中拥有165个节点，针对边的确定，本文考虑如果从A节点的火灾蔓延到B节点的时间在24 h之内以及在48 h之内，则有一条从A到B的有向边.从2019年9月到2020年2月，按照每月的数据构建的具体网络边数如表1所示.

有向边的确定主要从两方面进行：

(1)根据已知的A,B两节点的经纬度计算A,B之间的距离，从而得到从A节点火灾蔓延到B节点所需的时间，来判断A节点的大火能否蔓延到B节点.本文分别考虑在24 h和48 h，对节点间边的确定进行讨论.

(2)考虑风向问题，首先根据A,B两节点之间的经纬度得到两节点的方位角，若两节点的方位角区间在(180,360)范围内，则认为风向与东风方向一致；若两节点的方位角区间在(0，180)范围内，则认为风向与西风方向一致；若两节点的方位角区间在(0，90)或(270,360)范围内，则认为风向与南风方向一致；若两节点的方位角区间在(90,270)范围内，则认为风向与北风方向一致；若两节点的方位角区间在(135,315)范围内，则认为风向与东北风方向一致；若两节点的方位角区间在(0,45)或(225,315)范围内，则认为风向与东南风方向一致；若两节点的方位角区间在(0,135)或(315,360)范围内，则认为风向与西南风方向一致；若两节点的方位角区间在(45,225)范围内，则认为风向与西北风方向一致；在与风向一致基础上，则认为A节点的大火可以蔓延到B节点，从而确定了A,B两节点的有向边.

2 链路预测方法

2.1 基于节点属性相似性的链路预测

两个节点的属性越相似，就越容易产生联系.目前基于节点属性相似性的链路预测的研究主要应用在社交网络上.在社交网络中，任意两个节点之间属性相似度的计算，最基本的解决方法是使用标签.例如，利用任意两个节点的年龄、性别、兴趣爱好、地理位置等属性的相似程度，来预测节点对之间产生的联系或者节点对之间关系的演化.也可以通过分析节点属性的文本相似性[18-20]进行预测.例如，用网络上用户关注、发表的内容以及参与的话题等信息，来计算用户之间的话题相似性，从而进行好友预测[21].可以将在线社交网络中的预测方法应用到其他网络的链路预测当中.

Jaccard系数对网络中任意两节点之间进行相似度计算.是将网络中每个节点的属性看作为一个集合，并且对任意节点之间的连接可能性进行预测.其计算公式如下：

(1)

2.2 基于节点属性的澳大利亚火灾有向网络的链路预测算法实现

计算任意两个节点之间的相似度是链路预测最基本的解决方法.如果两个节点的属性越相似，他们之间产生连边的可能性越大，反之亦然.在澳大利亚火灾网络中，每个节点都有气候、温度、降水量、风向、风速、植被、地形等属性，任意两个节点之间，若他们的属性越相似，则证明从一个节点的火灾蔓延到另一个节点可能性越大.

根据澳大利亚火灾中节点的属性，本文使用Jaccard系数对节点之间的属性进行相似度计算，然后与真实存在的有向边进行比对，从而验证预测效果.基于节点属性的澳大利亚大火有向网络的链路预测算法，下面给出具体的算法描述：

(1)Jaccard系数计算节点对的相似度：

输入：节点部分属性列表

输出：节点对的相似度

1)fori

2)forj

3)ifrecord.get(i).get Climate()).equals

4) (record.get(j).get Climate())then

5) num++;

6)ifrecord.get(i).get Weather().equals

7) (record.get(j).get Weather())then

8) num++;

9)ifrecord.get(i).get Precipitation().equals

10) (record.get(j).get Precipitation())then

11) num++;

12)ifrecord.get(i).get Vegetation().equals

13) (record.get(j).get Vegetation())then

14) num++;

15)ifrecord.get(i).get Terrain().equals

16) (record.get(j).get Terrain())then

17) num++;

18)ifrecord.get(i).get Ave_speed().equals

19) (record.get(j).get Ave_speed())then

20) num++;

(2)有向边的确定：

输入：节点经纬度列表以及风向

输出：网络中两节点之间的连边

1)ift<24then

2) System.out.println(i+","+j);

3)else if(record.get(i).get Wind_direction().equals("东风"))

4)if(180.0

5)if(t<24)then

6) System.out.println(i+","+j);

(3)有向网络的链路预测：

输入：相似度矩阵和有向网络矩阵

输出：ACC

1)fori in range(165)do

2)forj in range(165)

3)ifnew_round(a[i][j],0)==1 and b[i][j]==1then

4) TP=TP+1

5)ifnew_round(a[i][j],0)==0 and b[i][j]==0then

6) TN=TN+1

7)ifnew_round(a[i][j],0)==0 and b[i][j]==1then

8) FN=FN+1

9)ifnew_round(a[i][j],0)==1 and b[i][j]==0then

10) FP=FP+1

11) acc=(TP+TN)/(TP+TN+FN+FP)

3 实验结果和分析

3.1 精确度指标ACC

(2)

TP(True positives):正样本被正确识别为正样本的个数.TN(True negatives):负样本被正确识别为负样本的个数.

FP(False positives):负样本被错误识别为正样本的个数.FN(False negatives):正样本被错误识别为负样本的个数.

3.2 预测结果与分析

澳大利亚火灾网络中共有165个节点，任意两节点进行对比来计算相似度，共比较27 225次.根据表2可知，以2 019.09为例，当时间在24 h之内时，节点的属性相似度与澳大利亚火灾的有向网络中，真实存在的有向边进行对比，预测存在的边被正确识别为存在的边有114条；预测不存在的边被正确识别为不存在的边有25 578条；预测存在的边被错误识别为不存在的边有111条；预测不存在的边被错误识别为存在的边有1 422条.

根据ACC指标对9月份，10月份，11月份，12月份，1月份和2月份进行预测.根据表3中的ACC结果可知，每个月通过48 h确定的有向边比24 h确定的边略小，主要原因是48 h之内确定的有向边被预测正确的边数TP虽然比24 h之内确定的有向边被预测正确的边数TP多，但48 h之内确定的有向边被预测正确的边数TP与不存在的边被预测正确的边数TN的和却比24 h之内的多，所以，通过24 h确定的边的预测效果要比48 h之内确定的边的预测效果好.

表2 混淆矩阵Tab.2 Confusion matrix

表3 预测准确率Tab.3 Forecast accuracy

4 结束语

本文利用Jaccard系数计算节点对之间属性相似度，并与通过经纬度和方向得到网络的有向边进行对比，从而对澳大利亚火灾趋势进行预测，实验结果证明基于此算法预测的澳大利亚火灾蔓延趋势效果很好.通过预测的结果可以有效阻断火灾的继续蔓延，对火灾的控制起到了一定的作用.同时，该论文也可以应用到对其他火灾[22]以及自然灾害[23]等的预测，对预防火灾等自然灾害有一定的借鉴意义.