基于D-S证据理论和聚集系数的重要节点挖掘算法-论文.pdf

《基于D-S证据理论和聚集系数的重要节点挖掘算法-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、ACADEMICRESEARCH学术研究基于D—S证据理论和聚集系数的重要节点挖掘算法◆徐晓东摘要：本文采用Ds证据理论，基于节点的度及局部集聚系数，提出了一种新的节点重要性挖掘算法，该算法的计算复杂度较低，且挖掘的结果更为理想。关键词：社会网络；聚集系数；D—s证据理论；重要节点一通常，在一个社会网络中fm≠fM，lcm≠lcM。、引言近几年来，根据研究的具体问题，学者们提出了多种多定义一个识别框架0=(high，low)。样的节点重要性排序方法。如基于节点的度(Degree)、接(【1)：)=(1)=近度(Closeness)、介数(betweefl

2、ness)、信息(Infomation)、，的值定义如下：特征向量(Eigenvector)的度量方法，以及Kitsak等人提：fM一+20"P=lcM—lcm+26出的k一壳分解法(k-shelldecomposition)，Chen等人提出其中0<．<1，fi为节点v的自身度及其邻居度之和，的基于节点的多级邻居信息指标的半局部信息法等。l。为节点v。的局部集聚系数。则节点v基于度和局部集聚系二、基于度、集聚系数、DS证据理论的重要数的基本概率分配函数(BPA)如下：节点挖掘方法Mi)=(mn(h)，H(1)，m())Ml(i)=(m·(h)，m①，m

3、·())对于网络中某一个节点vi，它的局部集聚系数LC(i)表其中，(0)=1-(h)一(1)，mj()=1一mj(h)一mj。(1)。示与它相连的节点抱成团(完全子图)的程度，其值等于所基于Ds证据理论合成公式，有M(i)=(m；(h)，mj(1)，m；())，m()有与节点v；相连的节点之间所连的边的数量除以这些节点表示节点v；重要度高或低的概率。这里把mi(O1的值均分给之间可以连出的最大边数，对于无向图，这个最大边数等于m，(h)，m(1)，则有：2。其中，。为节点；的邻居节点数。则无向图中节点M(h)=m．(h)+l／2m(0)v。的局部聚集系

4、数LC(i)可定义为：M，(1)=m，(1)+1／2m．(0)LC(i)=显然，M(h)的值越高，节点v。的重要性越高，M。(1)的值其中r(O为节点vi的邻居节点的集合。越低，节点v的重要性越高。D—s证据理论的辨识框架FrameOfDiscernment)是由三、结束语一些互斥且穷举的元素构成。设D为识别框架，领域内的命我们通过爬虫软件在网络上抓取了一个社交网站的真实题都用D的子集表示，则概率分配函数定义如下：数据集，并编制程序验证该算法。我们发现与使用简单的度设函数M：2。一f0，11，且满足属性的挖掘算法相比，该算法的准确度有显著的提高，尤其M(

5、)：0，A∑GDM(A)=l在网络中存在大量的星形节点的时候，更凸显出了该方法的则称M是2。上的基本概率分配函数，M(A)表示证据对优越性，在与基于平均最短路径的挖掘算法相比时，该算法A的支持程度。如果有两个证据源M，M则根据文献中的合在时间复杂度上有这明显的优势，但是在准确率上稍微差一成公式进行融合。其定义如下：些，这也表明该算法更适合于大型社会网络中的重要节点挖设M。，M为两个基本概率分配函数，其正交和M=MtM2掘，尤其是在网络节点达到上亿甚至更多时，算法的优越性M(A)=∑Mt(毋c)则更为凸显。今后我们将进一步改进算法，使其在准确率上。flC=

6、X有所提高。∞其中。(B)M2(C)，其大小反映了证据的冲突程度，系数1／(1一K)称为归一化因子。A，B，c均为D的子集。参考文献基于度和集聚系数的基本概率分配[1]WattsDJ，StrogatzSH．Collectivedynamicsofsmall首先定义f(i)为节点v的度及其邻居节点的度之和，表worldnetworks．Nature，1998(393)：440—442．示为：[2]赫南，李德毅，淦文燕，朱熙．复杂网络中重要性节点ffi1_ki+己发掘综述计算机科学，2007．(作者单位：山东工商学院、山东师范大学)其中k表示节点W的度，rl

7、表示节点v的邻居节点集。fm=min{fl，f2，．．．，fN}fM=max{fl，f2．，fN}lcm=min{lcl，lc2，．．．，lcN}lcM=max{lcl，lc2，．．，lcN}126信息系统工程I2015．420