基于加权转发关系的社交网络意见领袖识别算法
2018-09-26仇丽青范鑫
仇丽青 范鑫
摘要：在社交网络中进行意见领袖的识别对信息传播分析、舆情监测、网络营销等有着重要意义。目前，很多挖掘意见领袖的研究仅基于简单的粉丝关注或转发方式，而忽视了用户关系中的权重因素，不符合信息传播的实际情况。因此，提出加权网络下基于微博转发关系的FW-Rank（ForwardingWeightRank）算法。该算法使用新浪微博数据进行实验，相比于通过简单关注关系形成社交网络的方式，FW-Rank算法的最终结果更加合理准确。
关键词：社交网络；意见领袖；微博；FW-Rank
DOI：10.11907/rjdk.181151
中图分类号：TP312
文献标识码：A文章编号：1672-7800（2018）007-0111-05
Abstract：Identificationofopinionleadersinsocialnetworkshasgreatsignificanceontheanalysisofinformationdissemination，publicopinionmonitoring，networkmarketingandsoon.Atpresent，mostoftheresearchonopinionleadersinsocialnetworkisbasedonsimplefansorrewardconcernedaboutthelinkmerelyfocusedonfansattentionorforwardingmethod，andignorestheweightfactorsintheuserrelationship，whichmakesthefinalresultunreasonable.Therefore，thepaperproposesanovelalgorithmcalledFW-Rankwhichtakestheforwardingrelationshipofthenetworkintoaccount.AtlastweconducttheexperimentsonSinaMicroBlogdataset.Comparedtothebaselinealgorithms，thefinalresultsoftheproposedalgorithmismorereasonableandaccurate.
KeyWords：socialnetworks；opinionleader；micro-blog；FW-Rank
0引言
随着移动互联网的迅速发展，社交网络使用户之间可以随时随地进行交流和沟通，微博作为社交网络中的典型应用，已成为如今应用最广泛的信息传播媒介之一。微博作为一种分享和交流平台，更注重时效性和随意性，并具有便捷性、原创性和用户草根化等特点。在微博传播过程中，通常存在着一些很有影响力的用户，他们在网络口碑效应、突发事件传播、社会舆论等方面起着重要作用，这些用户被称为“意见领袖”。“意见领袖”最早由美国学者拉扎斯菲尔德提出，他认为信息是按照“媒体—意见领袖—受众”的模式传播[1]，后续学者研究结果表明，“意见领袖”具有“信息中间人”和“有影响力的人”两种角色特点[2]。在微博的信息网络中挖掘意見领袖，对微博营销、舆论引导、网络干预等都有着重大意义。
微博平台上的用户数量庞大，用户的任何一次“转发”行为都可看作信息的一次传播，用户的个人观点和影响力可沿着信息的“转发”网络进行传播。本文提出基于微博“转发”网络的新型排序算法，用于挖掘微博用户中的意见领袖，同时验证算法的有效性。
1相关研究
微博网络是社会网络的一种形式，属于复杂网络的范畴[3]。在微博网络中可以将用户的注册ID作为网络节点，进而在用户节点之间建立联系。目前用于挖掘意见领袖的方法主要分为两大类：指标聚类法和链接排序法。
（1）指标聚类法。指标聚类法是以节点基本特征为基础，通过对节点基本特征的分析，建立相应的评分指标体系，运用聚类算法进行意见领袖的挖掘。例如刘志明等[4]采用粗糙集理论，进行聚类并挖掘意见领袖；祝帅等[5]采用X-means迭代聚类算法挖掘意见领袖；尹衍腾等[6]建立领袖影响体系，提出D-means聚类算法；王钰等[7]采用EM期望最大化算法识别意见领袖。
以上采用指标聚类方法，通过获取符合条件的节点簇识别社交网络的意见领袖，但其数据的条目性过于清晰，破坏了用户之间的联系[6]。指标聚类法较为全面，同时也使用较多，但是属性指标选取很大程度上由个人主观决定，因此推广时具有一定难度。
（2）链接排序法。链接排序法通常是根据用户之间的相互关系构建社会网络，然后利用网络结构算法分析用户间的关系，进而进行重要性排名，识别意见领袖。自从Pagerank算法[8]被提出以来，不仅被谷歌成功应用于搜索引擎排序，还被广泛应用于社交网络分析中。Weng等[9]提出基于PageRank算法的TwitterRank算法实现某一特定主题下的意见领袖识别；肖宇等[10]在PageRank基础上加入感情权重，提出挖掘意见领袖的LeaderRank算法；熊涛等[11]构建基于微博转发关系的社交网络，通过改进后的HITS算法识别意见领袖；席运江等[12]综合考虑微博博主粉丝质量和微博用户的交互行为，提出MUR-IBM算法对微博用户进行影响力排名。
链接排序法与信息传播路径的关系密切，因此在客观性上占有很大优势。但是在传统的基于网络链接排序算法中，存在以下不足之处：①大量的基于网络链接排序算法通过用户“关注”关系建立社会网络。相关研究表明，由于意见领袖属于信息中间人的角色，相对于用户之间的关注关系，微博转发情况更能准确地衡量用户影响力[13]。即使转发者的观点与原文相反，也体现出该信息对转发者产生了一定影响。因此，研究基于微博转发关系的社会网络有重要意义；②在已有微博的意见领袖挖掘研究中，多数使用用户的注册ID作为网络节点，进而形成有向社会网络。但在使用排序算法处理网络结构时，很少提出节点之间信息传播流量对节点之间交互的影响。
基于以上研究，本文以微博中意见领袖的识别为目的，考虑到用户之间的交互活跃度，采用能够代表社交网络中信息流向的转发关系构建网络模型，提出一种基于转发关系的带权新型算法——FW-Rank算法。
2FW-Rank算法
现阶段大多数基于网络链接排序法识别微博网络意见领袖都采用用户之间“关注”关系形成的有向网络，且关系过于单一。因此，提出基于微博“转发”关系形成的带权有向社会网络，并利用FW-Rank算法进行意见领袖识别。
假设A、B、C、D为4个微博用户，用户A关注了用户B，用户B关注了用户C，用户C关注了用户A，用户D则没有关注其他人，同时也没有被其他人关注，如图1所示。
在图中，假设用户B发表原创微博，用户A对其进行了转发；用户B是用户C的粉丝，用户C却并未关注用户B，但用户C依旧可以转发用户B的微博；用户D虽然与其他用户没有关注关系，但其依旧可以转发相关微博。图1充分体现了信息传播路径和转发路径的密切关系，同时也能体现出网络中用户之间的影响力是沿信息传播路径逆向传播的。
根据图1可以得到用户之间基于转发关系的邻接关系矩阵：
Tr=0100000001000010
FW-Rank采用有向加权的人际网络模型，以便准确识别意见领袖。因此，将模型定义为G=（V，E，W）。V代表网络中的用户集合，E表示边集，
其中rj表示j用户发布帖子被转发的总次数之和，rij表示i转发j的总次数。其转发关系模型及其影响力关系模型如图2所示。
根据以上论述，定义FW-Rank算法公式为：
其中，FW（Vi）表示当前Vi节点权重，Vj为Vi指向节点的所有节点集合中第j个节点。S（Vi）表示指向Vi节点的所有节点集合，d为阻尼系数，一般取值为0.85；C（Vj）表示Vj节点的所有出链权重之和，wjk表示节点Vj指向节点Vk边的权重。
假设在图2中用户vi、vj和vk初始权值都为1，各自被转发的总次数分别为0次、3次和8次，其中vi转发过vj3次，vi转发过vk7次，vj转发过vk1次，由公式（1）可以得出wij=1，wik=0.875，wjk=0.125；由公式（3）得出C（Vi）=0.875+1=1.875，C（Vj）=0.125，C（Vk）=0；由公式（2）得出FW（vi）=1-0.85=0.15，FW（vj）=（1-0.85）+0.85*（1*1/1.875）=0.6033，FW（vk）=（1-0.85）+（1*0.875/1.875+1*0.125/0.125）=1.3967。
FW-Rank算法使用节点出链权重之和作为公式的分母，克服了PageRank算法平均分配权值的缺点；采用转发关系形成的影响力有向网络图，从而使社交网络中的网络指向符合信息传播轨迹，使用时更加符合现实情况。FW-Rank的伪代码如下：
算法：FW-Rank
INPUT：“边起点+终点+边的权值”格式的文件nodes.txt，迭代次数N，阻尼系数d
OUTPUT：排名+節点号+FW值
对所有节点设置初始值1，循环进行以下过程，直至收敛：
依次遍历所有节点，执行以下过程：
（1）获取当前节点所有链出边的数量n。
（2）循环n次{
计算每条边的权重wij=rijrj；
}
（3）计算与当前节点相连链出边的权值和C（Vj）=∑Vk∈S（Vj）wjk。
（4）计算并重新设置当前节点的权值FW（Vi）=（1-d）+d∑Vj∈S（Vi）FW（Vj）·wjiC（Vj）。
3实验分析
3.1实验数据准备
使用“中国爬盟”论坛提供的爬虫工具对新浪微博进行爬取，上传爬取结果后利用获得的积分下载微博数据。由于意见领袖大多是话题依赖的，因此针对“转基因”、“雾霾”、“小米”、“火箭”、“房价”和“公务员”6个较为具体的话题进行数据集下载。原始数据主要内容有：①用户信息：用户ID、用户昵称、省份城市、性别、粉丝数、状态数、创建时间；②微博信息：微博ID、发布时间、微博内容、被转发次数、被评论次数、源用户、话题类型；③用户关注关系：用户ID、关注ID；④微博关系：微博ID、来源微博ID。获得数据统计情况如表1所示。
经过对数据的去重、噪声数据识别等预处理，最终获得质量较高的6个主题微博数据，各主题的基本数据情况如表2所示。
将各个主题的数据集使用开源软件Gephi进行处理，可以得到各个主题的社会网络图，其中节点大小代表节点度数大小，如图3所示。
由图3可以看出，6个话题中的用户关系并不是非常密切，网络平均度较低，形成的邻接矩阵皆属于稀疏矩阵，与现实社会相似。其中“房价”、“小米”和“转基因”3个话题的节点数较多且图密度较大，更切合实际社交网络。
3.2实验及结果分析
在得到各个话题数据集的基本属性之后，对每个话题使用FW-Rank算法进行排序，得到的前10名用户如表3所示。
为了比较FW-Rank算法的实际效果，使用PageRank算法在基于关注关系形成的社会网络上进行实验，结果如表4所示。
由表3、表4的实验结果可以明显观察到，某些官方微博账号始终占有较为重要的社交地位，如“转基因”话题中的“崔永元”，“雾霾”话题中的“新周刊”和“学习粉丝团”，“小米”话题中的“小米公司”、“小米手机”等。但是相比于给予关注关系的PageRank算法，FW-Rank算法是按照信息传播路径进行意见领袖识别的，因此结果中的官方账号明显少于前者，即更容易挖掘普通用户中的潜在意见领袖，例如“转基因”话题中的“洞庭湖面风11”和“武汉陈国恩”，“雾霾”话题中的“五行属二”、“腐宅集中营”、“铁人唐吉柯德”等都是在基于关注关系的PageRank算法结果中不曾出现的。
以上两种算法平均运行时间随节点数变化折线图如图4所示。在运行时间方面，FW-Rank与PageRank运行时间相差无几，虽然FW-Rank属于基于PageRank算法的一种演变，但是该算法是基于转发网络进行计算的，更符合信息传播实际；此外，FW-Rank算法克服了PageRank平均分配权值的缺点，在加强重要节点地位的同时，弱化了普通节点作用，加快了计算速度。
中心性可以定义网络中的节点重要性，通过中心性度量方案，可以识别网络中的部分中心界定[14]。为了验证FW-Rank算法的有效性，选取社会网络研究领域较为熟知的度中心性、接近中心性和中介中心性3个典型的中心性度量指标，并将FW-Rank算法计算结果中排名前10位和前20位用户分别与3种中心性结果进行相关性计算，结果如表5所示。
由表5可以看出，在該测试数据集中，FW-Rank算法与度中心性的相关性非常强，相关系数均达到0.9以上；而FW-Rank算法接近中心性与中介中心性在不同话题中的相关系数有所不同，例如在“小米”话题中中介中心性达到0.86以上，相关性非常强，而在“雾霾”和“公务员”话题中的相关性较弱。
4结语
本文在分析社会网络意见领袖识别研究现状的同时，根据社会网络中的信息传播路径，提出基于微博转发关系的加权FW-Rank算法。实验结果表明，FW-Rank算法在识别意见领袖时得到的结果更加符合实际需求，且算法执行效率较高，有助于挖掘社会网络中的潜在意见领袖。然而，在执行FW-Rank算法之前对数据质量要求较高，原始数据预处理过程较为繁琐，后续研究将进一步寻找符合算法要求的更加高效便捷的数据预处理方法。
参考文献：
[1]LAZARSFELDPF，BERELSONB，GAUDETH.Thepeople′schoice[M].NewYork：ColumbiaUniversityPress，1948.
[2]ROGERSEM，SHOEMAKERFF.Communicationofinnovations：across-culturalapproach[M].NewYork：FreePress，1971.
[3]熊涛，何跃.微博转发网络中意见领袖的识别与分析[J].现代图书情报技术，2013（6）：55-62.
[4]DorogovtsevSN，MendesJFF.Evloutionofnetworks[J].AdvPhys，2002，51：1079-1187.
[5]刘志明，刘鲁.微博网络舆情中的意见领袖识别及分析[J].系统工程，2011（6）：8-16.
[6]祝帅，郑小林，陈德人.论坛中的意见领袖自动发现算法研究[J].系统工程理论与实践，2011（S2）：7-12.
[7]尹衍腾，李学明，蔡孟松.基于用户关系与属性的微博意见领袖挖掘方法[J].计算机工程，2013（4）：184-189.
[8]王珏，曾剑平，周葆华，等.基于聚类分析的网络论坛意见领袖发现方法[J].计算机工程，2011（5）：44-46，49.
[9]BRINS，PAGEL.Theanatomyofalarge-scalehypertextualWebsearchengine[J].ComputerNetworks&IsdnSystems;，1998，30：107-117.
[10]WENGJS，LINEP，JINGJ，etal.Twitterrank-findingtopic-sensitiveinfluentialtwitterers[C].Proceedingofthe3rdACMInternationalConferenceonWebSearchandDataMining，2010：261-270.
[11]肖宇，许炜，夏霖.一种基于情感倾向分析的网络团体意见领袖识别算法[J].计算机科学，2012（2）：34-37，46.
[12]席运江，吴柯，廖晓.改进PageRank算法对微博用户交互行为的影响[J].计算机仿真，2015（11）：437-440.
[13]KWAKH，LEEC，PARKH，etal.Whatistwitter，asocialnetworkoranewsmedia？[C].Proceedingofthe19thInternationalConferenceonWorldWildWeb，2010：591-600.
[14]LUJ，WANGW.Identificationofkeynodesinmicroblognetworks[J].EtriJournal，2016，38（1）：52-61.
（责任编辑：黄健）
