一种基于历史交互行为的关键节点选取算法

刘元晖

摘要：在包含大量不对等关系的实体网络中，通常存在一个或多个在交互行为中起主导作用的节点，即“关键节点”。本算法参考了衡量网络中节点重要性的PageRank经典算法，提出了一种基于历史交互行为的改进算法，并对相关的参数和公式做了定义和论述，同时对算法流程做了详细的说明。该算法采用节点交互覆盖率作为评估指标，计算节点社会影响力值，从而获得实体网络中的关键节点。与传统PageRank算法进行对比，该算法具有更高的准确性。

关键词：关键节点； 交互行为

中图分类号：TP302 文献标识码：A 文章编号：1009-3044（2018）30-0198-03

1 引言

物联网的核心在于实现物与物之间主观能动的信息交换和数据通信，将物体的信息通过网络传输到某个信息处理中心，实现各种信息服务和应用，即物物互联。确定物联实体间的信息交互关系，同时根据参与的交互对象的关系，自主确定信息交互的方式，进而确定需要交互的信息，有助于提升物联实体间的信息交互的智慧性，实现物联网的智慧互联。

在物联网的交互关系网络中，根据交互关系的方向性和信息反馈差可将交互关系分为对等关系和不对等关系。

在实体交互网络中，不对等关系通常占据明显地位，且存在于众多设备间[1-2]。因此，不对等关系是智慧物联网交互关系网络研究的重点，而在包含大量不对等关系的实体网络中，通常存在一个或多个在交互行为中起主导作用的节点，即“关键节点”[3]。在分析物联交互关系网络时，找到其中的“关键节点”，可迅速通过该节点找到与之相关联的全部节点，继而掌握整个网络的交互关系组成。因此，研究提取关键节点的算法对于识别不对等关系有明显的研究意义。

本文参考衡量网络中节点重要性的PageRank算法[4]，提出一种针对不对等关系中关键节点的选取算法，该算法通过对实体间交互历史数据的分析，选取不对等关系中的关键节点。

2 相关定义

交互度是交互关系中控制节点与被控制节点间的交互程度，基于节点间的交互信息量，节点间的交互度定义如下：

节点p进入网络时，会选择与自己拥有相同连接关系的多个节点，如p1，p2，p3并与之有进一步的交互，当节点p1与节点p进行单向交互时，就说明p与p1之间存在不对等交互关系，即p将自己的交互度以一定的比例分配给了p1节点。节点间的交互度分配比例定义如下：

定义4：节点间的交互度分配比例

定义5：时间函数

在t时刻，完成交互请求的累计函数为[yt]，单位时间内完成交互请求的函数为[y，t]。

当[t=0]时，[yt=0]，代表此时无交互行为进行；当[t>0]时，[yt]会随着时间的增大而逐渐增大，为单调递增函数，[y，t>0]。

SNRank算法通过节点对网络的影响程度来判断关键节点，因此，定义节点的社会影响力如下：

定义6：节点的社会影响力

其中，SNR（q）、SNR（p）分别表示实体节点q、p的影响力值；E表示所有与节点q进行交互的节点的集合；[p]表示节点p进行单向交互的所有节点总和；[y，t]为t时刻时，单位时间完成交互请求的数量；C为用于函数收敛的阻尼系数，是一个常数，表示节点q收到请求信息并响应后，继续与它的下级节点进行交互的概率，本文参考PageRank算法中的阻尼系数取值，在所提出的SNRank算法中，C的取值同样为0.85。

3算法流程

算法的目的是计算出节点的社会影响力值，对所有节点的社会影响力值进行排序，社会影响力值排序靠前的一个或多个节点即为所要找的“关键节点”。

算法的主要流程如下：

首先对所用到的数据集进行初处理，将各个节点对应的不同交互行为进行分类、累加，从而求得节点的全部信息量[Sq]和节点间的交互信息量[Np，q]，继而求出节点间的交互度[Ip，q]。通过分析目标节点与其他与之有交互关系的节点间的交互情况，可以计算该节点与其他节点间的交互度分配比例。最后，利用SNRank算法进行不断迭代计算，由于阻尼系数的存在，每个实体的SNRank值最终会趋于一个稳定值，当前后两次计算的SNRank值的偏差足够小时，可以认为该值已经保持稳定；当每个节点的SNRank值均处于稳定时，计算结束。

该算法的流程图如图1所示：

4 实验验证

本文选取麻省理工学院人体动力学实验室采集的Reality Mining项目中所收集的数据作为测试用例，来构建实体间信息交互原始关系网络。该数据集中包含了100名志愿者在一年内彼此之间的全部通信行为记录，包括通话记录、短信记录、邮件记录、手机蓝牙连接记录、WIFI热点连接记录等物联网中常见的数据类型。

本文采用的准确率评估指标为交互覆盖率（Coverage）[5]和节点突出率（Highlight）。

交互覆盖率分析如图2（上）所示，从图中可发现，SNRank算法在交互覆盖率的结果上，与PageRank算法的结果近似，说明找到的“关键节点”都是能够起到作为“关键节点”作用的，表明所得结果是正确的，且SNRank算法与PageRank算法的结果中的差异体现在交互覆盖率上，说明SNRank算法所提取的“关键节点”准确性更高。

节点突出率分析如图2（下）所示：从图中可发现，SNRank算法在节点突出率的结果上，优于PageRank算法，说明了SNRank算法能够从“非关键节点”中高效地识别出所需的“关键节点”，且提取出的“关键节点”更加突出、更有识别度。

5 总结

本文提出了一种基于历史交互数据分析的关系识别算法。该算法结合物联网内交互数据的特性，针对数据的时空相关性进行了分析和处理，使用了麻省理工学院人体动力学实验室的Social Evolution数据集进行了实验，并与PageRank算法进行了对比实验，根据实验结果，利用准确性评估指标，验证了所提出算法的准确性和有效性。

参考文献：

[1] 房旋，陈升波，宫婧，孙知信.基于社交影响力的推荐算法[J].计算机技术与发展，2016，26（06）：31-36.

[2] Sergey Brin，Lawrence Page. Reprint of： The anatomy of a large-scale hypertextual web search engine[J]. Computer Networks，2012，56（18）.

[3]Feng Li，Timon C. Du. Who is talking？ An ontology-based opinion leader identification framework for word-of-mouth marketing in online social blogs[J]. Decision Support Systems，2010，51（1）.

[4]Pavel Zakharov. Diffusion approach for community discovering within the complex networks： LiveJournal study[J]. Physica A： Statistical Mechanics and its Applications，2006，378（2）.

[5]吳渝，马璐璐，林茂，刘洪涛.基于用户影响力的意见领袖发现算法[J].小型微型计算机系统，2015，36（03）：561-565.

【通联编辑：代影】