基于Hadoop云平台的新浪微博社交网络关键节点挖掘算法

陈红松 王 钢 张 鹏

(1北京科技大学计算机与通信工程学院, 北京 100083)(2材料领域知识工程北京市重点实验室， 北京 100083)(3铁道警察学院， 郑州 450053)

微博社交网络是一个不断发展并对社会产生巨大影响的传播平台，对微博社会网络中信息传播过程中关键节点的分析挖掘研究具有重要的理论意义和应用前景.作为一个新兴的信息传播平台，微博社交网络中的关键节点与传播规律研究在理论及应用方面都具有很高的价值，特别是在信息传播模型、关键节点挖掘、用户行为分析等方面[1].研究微博信息传播中关键节点挖掘算法的目的在于发现信息传播规律中的关键节点，以及关键节点对微博信息传播的作用.近年来，国内外已有许多算法用来对微博数据进行分析挖掘，例如基于社交网络特点对PageRank进行加权改进的研究[2]、基于随机网络的数据挖掘研究、启发式社交网络节点影响力计算方法[3]等.上述研究通过数据预处理和特征值竞争抑制机制较好地完成数据过滤，从而提高数据处理效率[4].这些研究的重点都是探索如何让算法更高效地对数据进行处理，提高算法的执行效率，但存在未能体现社交网络节点和网络连接的社会属性的缺陷.本文通过给社交网络中的节点和边赋予适当的社会属性权重，体现出节点的社会属性差异以及信息在社交网络中传播的特点和规律，从而在提高关键节点挖掘算法执行效率的同时，发现符合社交网络自身特点的关键节点及高价值分析结果.

本文首先针对热点微博的信息转发过程进行数据采集，根据微博转发过程构建一个信息转发传播网络，通过HITS算法挖掘信息传播过程中起关键作用的节点.本文的微博实验数据来自新浪微博API开放平台，整个数据处理流程在Hadoop云平台下进行，在大规模社会网络分析工具X-RIME开源框架基础上，采用分布式HITS算法对微博信息传播数据进行分析，并针对社交网络自身特点提出新的加权HITS算法用于挖掘关键节点，并通过实验进行分析验证.

1 X-RIME开源框架

X-RIME是一个基于Hadoop的大规模社会网络分析开源软件[5]，在Map/Reduce框架上对十几种社会网络分析算法进行并行化与分布式化处理，能够对大规模社会网络/复杂网络进行社会网络分析，具有良好的扩展性和通用性，研究人员可自由获得X-RIME的程序包和源代码.X-RIME算法库实现了许多社会网络分析常用算法，如最小生成树算法、节点度统计、弱连通算法、强连通算法、PageRank算法、高质量网页分析算法HITS (hyperlink-induced topic search)等.这些算法都支持分布式并行计算.PageRank算法对网络中所有节点给出全局重要性排序，有利于迅速响应用户主题检索请求，缺点在于检索主题的无关性.HITS算法是对网络中与主题相关的子集进行分析，它需要的迭代次数更少，收敛速度更快.本文研究的场景是社交网络信息传播过程中的关键节点挖掘，这些关键节点是与网络传播主题相关的网络节点子集，因此本文以HITS算法作为研究对象.

2 基于Hadoop平台的分布式HITS算法

在传统的社会网络关键节点分析中，节点中心度分析是较常用的方法，主要有点度中心度、加权点度中心度、中介中心度、接近中心度4种[6].但这几种中心度都有其局限性，难以反映在线社交网络中节点的社会属性及特征.本文基于HITS算法来挖掘微博社会网络中的关键节点.HITS算法基于节点之间的连接关系分析节点重要程度，通过计算节点的出入度及节点间连接关系分析挖掘社会网络信息传播过程中的关键节点.

2.1 HITS算法思想

HITS算法是链接分析中一种基础且重要的算法[7]，是IBM 公司阿尔马登研究中心“CLEVER”研究项目中的一部分，目前已被Teoma搜索引擎(www.teoma.com)作为链接分析算法在实际中使用.HITS算法中有2个重要概念：权威值(authority)和中介值(hub).网络中每个节点都有权威值和中介值，权威值表示一个节点在网络中的权威性，中介值表示一个节点在网络中传播信息的能力，中介值越高，说明这个节点在信息传播扩散中起的作用就越大.HITS算法的核心思想是分析计算权威值和中介值在网络系统中的相互作用、相互影响，可挖掘微博社会网络中信息传播过程中的关键节点.

2.2 HITS算法步骤

HITS算法包括值分配(delivery)、汇总(summer)、规范化(normalize)3个运算阶段[8].第1阶段是值分配阶段，对节点的权威值和中介值进行初始化和值分配.具体步骤如下：

① 为整个网络中的所有节点都赋予一个初始的非负中介值和权威值.通常将中介值和权威值分别初始化为1.

② 进行迭代运算得到节点p的权威值和中介值，运算公式为

(1)

(2)式中，n为指向p的某个节点；N为所有指向p的节点的集合；ap和hp分别为节点p的权威值和中介值.

式(1)表明，如果节点p被许多有较高中介值的节点所指，那么节点p的权威值会增加，而增加的值就是那些指向节点p的所有节点的中介值总和.式(2)表明，如果节点p指向许多权威值较高的节点，那么节点p的中介值会增加，而增加的值就是节点p指向的所有节点权威值的总和.经过值分配阶段后，由于多次迭代会导致结果数值增加速度过快，不利于算法的继续运行，因此要对数据进行汇总和规范化处理.

在汇总阶段，对整个网络中所有节点的权威值和中介值进行汇总，为下阶段的数据规范化做准备.

数据汇总之后就可进行规范化.在该阶段，利用汇总阶段的计算结果将值传递阶段得到的每个节点的权威值和中介值进行数据规范化，公式如下：

(3)

(4)

式中，P为网络拓扑结构中所有节点的集合.经过数据归一化阶段后，所有节点的中介值和权威值都映射为0～1范围的数值.然后循环迭代运行值传递、汇总、规范化3个步骤，直至运算结果的变化小于阈值，输出结果.

2.3 X-RIME框架中HITS算法的数据结构

HITS算法中每个节点需要有权威值和中介值2个属性，每个属性都有2个值，分别用来记录当前计算结果和上一轮运算结果.在X-RIME框架中，通过标签Label数据结构来记录节点的属性.本文通过HubLabel和AuthorityLabel两个数据结构模型来分别记录节点的中介值和权威值.由于HITS算法是针对有向图的，因此每个节点都有自己的前驱和后继.在X-RIME框架中，采用LabeledAdjBiSetVertex类来表示图中的节点，采用AdjVertexEdge类来表示图中的边.

3 HITS算法的分析与改进

3.1 HITS算法分析

本文所研究的微博转发网络属于社交网络范畴，社交网络的特点是每个用户(节点)之间社会属性差异明显[9-11].因此，在分析并挖掘微博信息传播中的关键用户时，区别每个用户的社会属性(粉丝数、活跃度等)显得尤为重要.传统HITS算法在值传递阶段进行节点初始化时，所有节点默认的权威值和中介值都是1，没有考虑不同节点中介值和权威值的社会属性差异.在新浪微博转发网络中，不同节点的初始影响力是有差异的，这就需要考虑节点的社会属性.因此，传统HITS算法值传递阶段节点初始化过程是可改进的.

传统HITS算法在值传递阶段计算节点接受到的权威值和中介值时，只考虑了节点间连接的数量，即节点的入度和出度值，而没有考虑节点间连接的社会属性差异，即使节点的入度、出度值相同，但所连接节点的粉丝数、活跃度等社会属性不同，需要综合考虑节点和边的社会属性.因此，传统HITS算法值传递阶段节点接受权威值和中介值的过程也是可改进的.本文将针对以上2个可改进点提出改进方案.

3.2 HITS算法改进

首先，本文提出的加权HITS算法根据节点的综合权值来确定节点的权威值和中介的初始值.在值传递阶段将节点的社会属性值进行初始分配，计算节点和边的社会属性值，利用加权HITS算法计算新的权威值与中介值.加权HITS算法在汇总阶段和规范化阶段的执行过程与传统HITS算法一致.

由以上分析可知，加权HITS算法的改进主要集中在值传递阶段的初始化过程与值分配过程，体现在节点和边的社会属性差异.由于HITS算法要求所有的边必须是有方向的，因此在计算过程中可通过A→B这样一个指向关系和A，B两个节点各自的社会属性来计算边的权值.

通过分析新浪微博提供的API发现，每个节点拥有可用来衡量自身社会属性权值的朋友数、粉丝数、状态数这3个属性，分别用来表示节点所拥有的朋友数、粉丝数、发布的微博数.对它们分别进行统计运算，用节点自身朋友数除以该传播过程中所有节点的朋友数总和，可得到该节点对应的朋友数权值，同理可求出每个节点对应的权值.

3.3 加权HITS算法改进与实现

3.3.1 加权HITS算法的改进

节点的朋友数是指该节点有多少关注的好友，例如A关注B表示A成为B的粉丝，B成为A的朋友.朋友数越多说明这个节点关注的微博用户越多，它能够看到的新微博也越多，能够对新微博作出回应的概率就越大.因此，朋友数越大的节点，其转发能力越强，转发微博的概率越大.

节点的粉丝数是指这个节点有多少人关注，粉丝越多，说明它发布的微博会被越多的人看到，微博被转发的概率就越大.因此，粉丝数越多的节点，其发布能力越强，它发布的微博被转发的概率就越大.

节点的状态数表示这个节点发布过的微博数，发布的微博数量越多，说明这个节点越活跃，越活跃的节点会有更大的概率对其他节点产生影响.因此，状态数越大的节点，它的活跃度越高，它发布的微博更容易被转发，而且它也更容易转发别人的微博.

在本文算法中，中介值和权威值分开考虑.中介值表示一个节点的中介度，如A→B，A转发了B的微博，A的中介度得到提高，因此A的朋友数和状态数影响到其中介值的计算，而B的粉丝数和状态数也能影响A的中介值.在实际计算过程中，朋友数权值、粉丝数权值、状态数权值的取值范围均为区间(0,1).

3.3.2 加权HITS算法的设计与实现

本文通过面向对象的Java程序设计语言来实现加权HITS算法，该算法程序实现的包结构如图1所示. 由图可知，在HITSLabel包中，包括AuthorityLabel, HubLabel, VertexWeightLabel三个类.AuthorityLabel类用来标记处理节点的权威值，HubLabel类用来标记处理节点的中介值，VertexWeightLabel类用来标记处理节点的权值属性.HITSAlgorithm类是整个算法的全局控制类.创建DeliveryStep，HITSSummer，NormalizeStep类的实例，分别对应值传递、汇总和规范化3个运算阶段.

图1 加权HITS算法程序实现的包结构

在weightedHITS包中，包括加权HITS算法具体实现的所有类.加权HITS算法相比于原算法最大的改动就是值传递阶段，对应DeliveryMapper类和DeliveryReducer类.Runner类是整个算法程序的入口，它通过创建一个HITSAlgorithm类的实例来开始算法的运行.HITSAlgorithm类是整个算法的全局控制类，通过创建DeliveryStep，HITSSummer，NormalizeStep类的实例，分别对应Delivery，Summer和Normalize三个运算阶段.HITSAlgorithm通过控制DeliveryStep，HITSSummer，NormalizeStep类的实例来控制整个算法的运行.在DeliveryMapper类的map方法中，依次处理社交网络中所有节点，直到所有节点的初始权威值和中介值都被分配完成.在DeliveryReducer类中有newhubScore，newauthorityScore，weightScore，friendScore，followerScore，statusScore六个参数记录节点的社会属性值.在DeliveryReducer类的reduce方法中，根据每个节点接收到的权威值、中介值、社会属性权值，按照加权HITS算法计算出本节点的权威值与中介值.

在数据预处理过程中，将Pajek格式的数据文件导入X-Rime框架.在数据后处理过程中，根据每个节点收到的权威值、中介值和节点的权值，由HITSResultCalc类进行节点数据的统计分析，当达到加权HITS算法的停止条件后，由加权HITS算法排序得出所有节点的权威值和中介值排名.

3.4 加权HITS算法执行结果的比较分析

本文选取4组微博信息传播实验数据来测试加权HITS算法相对传统HITS算法的优势，每组数据代表一条新浪微博的转发传播过程.表1是这4组数据对应微博的基本信息.

表1 实验数据信息表

3.4.1 实验结果区分度比较

通过加权HITS算法发现社交网络信息传播过程中权威值和中介值排名较高的节点，对于4组实验数据分别进行处理，各选取权威值和中介值排名前20的节点进行对比分析.图2是第1组数据的实验结果对比.

由图2可知，2种HITS算法得出的权威值前2名的结果是相同的，传统HITS算法的第3名“chrisxw_待业青年”在加权HITS算法中排第5，传统HITS算法中排第5名的“Joinin”在加权HITS算法中排第4名.加权HITS算法权威值计算结果与传统HITS算法相比变化不大.但对比权威值的具体数值可发现，传统HITS算法存在许多节点权威值相同的情况，如传统HITS算法中第13～15名的权威值都是0.000 001 78，第16～20名的权威值都是0.000 000 89.而在加权HITS算法的运算结果中，前20名的权威值没有重复，说明改进后的算法对节点权威值的区分度更高.改进前后HITS算法计算得到的中介度结果差距较大.采用传统HITS算法计算的第5～20名的中介值都是0.000 943 54.加权HITS算法的计算结果体现出区分度高的特点，前20名的中介值各不相同.而传统HITS算法结果中有15个节点的中介值相同，导致2种HITS算法的计算结果排名差异较大.

(a) 传统HITS算法

(b) 加权HITS算法

同理，通过分析中介值排名实验结果发现，加权HITS算法结果中用户“山东嘉华文化国旅青岛分社”排第7名，而在传统HITS算法中并未进入前20.对微博信息传播数据分析发现，该用户属于一个旅行社官方微博，有许多与其关系很紧密的用户，根据加权HITS算法计算公式，这些用户相互之间的社会关系属性权值较高.在计算中介值时，加权HITS算法考虑了用户间的社会关系权值，使该用户排名提高.

总之，加权HITS算法在结果区分度方面优于传统HITS算法，这是由于加权HITS算法考虑用户自身社会属性和用户间关系社会属性权值导致的.加权HITS算法相比于传统HITS算法更适合对社交网络中的关键节点进行分析挖掘.

3.4.2 算法执行效率比较

在验证程序执行效率时，4组实验数据的算法执行环境均为Hadoop云计算平台，硬件配置为：华为RH2288H V3 机架式服务器，32 GB DDR4内存，CPU型号Xeon E3-2609 ，采用Vmware虚拟机管理软件配置3台虚拟机，分别安装Unbuntu 16操作系统，其中1台虚拟机为Hadoop Namenode，其余2台虚拟机为Hadoop Datanode.为比较算法执行效率，2种HITS算法的运行环境均一致，具体运行效率情况如表2所示.

表2 加权HITS算法与传统HITS算法运行效率比较

由表2可知，在第1组、第2组和第4组实验中，传统的HITS算法执行了3次值传递、汇总和规范化过程，而加权HITS算法只执行了2次相应过程，加权HITS算法比传统HITS算法的执行效率提高了33.33%.第3组实验由于数据量较小，新旧算法的执行效率差距不大.第4组实验数据量最大，二者执行效率的差距也最大.传统HITS算法运行时间随数据量增大而显著增大，加权HITS算法在大数据量计算场景下具有相对优势，因此加权HITS算法更适合于大规模数据集的分析执行.

为了验证算法在通用数据集上的执行效果，本文在ego-Facebook数据集上分别执行传统HITS算法和加权HITS算法.ego-Facebook数据集来源于美国斯坦福大学的Stanford Network Analysis Project数据共享平台[12]，是国内外社交网络算法研究中通用性较强的数据集.在ego-Facebook数据集上分别运行传统HITS算法和加权HITS算法的实现程序，传统HITS算法执行了6次值传递、汇总和规范化过程，而加权HITS算法执行了4次值传递、汇总和规范化过程；传统HITS算法执行时间为758 s，加权HITS算法执行时间为492 s，实验结果表明加权HITS算法具有较高的执行效率.

因此，加权HITS算法在数据量较大情况下执行效率明显优于传统HITS算法.原因是加入了节点权值来描述节点间的社会关系，使得算法在初始化和运算过程中能更准确地计算节点的权威值中介值，从而减少算法迭代次数，提高执行效率.在加权HITS算法的迭代过程中，节点的初始权值和社会属性权值起到了加速迭代的作用，能让算法更快地到达收敛状态，减少了算法的迭代次数，提高了执行效率.

4 结语

传统HITS算法只考虑节点间连接关系，无法体现出微博社交网络中节点和连接的社会属性.加权HITS算法基于用户自身和用户间连接的社会属性，将节点初始权值和连接边权值引入HITS算法计算过程.本文在Hadoop云平台环境下，基于X-Rime开源框提出加权HITS算法及软件实现方案，并对算法的执行结果进行对比分析.实验结果表明，加权HITS算法由于充分考虑了社交网络信息传播过程中节点和边的社会属性，执行效率提高，执行结果具有更细的区分度.加权HITS算法在执行效率和结果区分度上均优于传统HITS算法.