文摘

排名的影响力的节点网络具有重要意义。有影响力的节点在进化过程中发挥巨大作用的信息传播,病毒式营销,和舆论控制。多个属性的排序方法是一种有效的方法来识别有影响力的节点。然而,这些方法提供了一个有限的改善算法性能,因为多样性不同属性之间没有很好地考虑。k层方法的基础上,我们提出一种改进的多属性k层方法通过迭代分解过程中的信息。我们的工作结合sigmod指数函数和迭代信息获取位置。位置属性是通过结合壳价值和位置索引。采用节点的本地信息获取邻居财产。最后,位置属性和邻居属性加权信息熵加权的方法。实验模拟在现实网络六先生结合模型和其他评价措施充分验证了该方法的正确性和有效性。

1。介绍

网络上的多维信息流动迅速,而对信息传输(不同的节点有不同的影响1),病毒式营销(2),公众舆论指导(3),和社会推荐(4,5)由于其不同的影响。从信息传播的角度,不同的社交网络有不同的信息传播模式,因为功能集中和用户结构的多样性。从市场营销的角度,通过提供有影响力的用户排名不同的爱好和组,它可以帮助新用户感兴趣的迅速和有效地获得相关信息来源,实现顺利冷启动。从舆论引导和控制的角度来看,热舆论的事件演化过程通常包括转发和评论的用户提供不同的影响在不同的平台上。这些简单的操作往往会导致一个巨大的公共意见不同的方向发展。

节点的影响评估从全球结构信息,如中间性中心(6),亲密中心(7],Katz中心(8]。这些方法在节点排序显示良好的性能。然而,由于甚至更高的计算复杂度,这些方法不适合大规模网络。节点是由本地信息量化的影响,如学位中心(9),半局部中心(10),混合度中心(11),平均最短路径中心(12),而h指数(13]。当地措施效率较低,因为他们只考虑本地邻居的信息。有很多启发式算法(14,15结合本地邻居的信息。研究基于随机游走的评估节点的影响通过与高昂计算多个迭代操作复杂性等特征向量中心(16),网页排名(17],LeaderRank [18),点击【19]。

Kitsak et al。20.)认为,最具影响力的是那些位于网络的核心节点。每个节点分配一个固定的k层分解后壳价值。然而,k层分解倾向于分配相同的壳价值很多节点,这些节点的影响相同壳价值不能进一步区分。在此基础上,提出了大量的方法来进一步提高k层的性能的方法。曾和张21)提出一个混合程度分解方法,它结合了残留程度和损耗程度更新节点。在分解的每一步,节点和基于混合程度的分解中移除。然而,参数优化是困难的。刘等人。22)提出了一种改进的排序方法来生成一个更差异化的排名。该方法实现了通过计算目标节点之间最短的距离和网络的核心节点。网络的核心节点的节点集壳价值最高的k层分解。该方法的计算成本相对昂贵的核心节点通过计算最短的距离。Bae和金23)提出一种新的测量社区coreness中心,计算扩散影响网络中节点的所有邻居壳值。节点具有相同的影响价值可以进一步区分通过移除节点的迭代信息来识别网络中节点的位置不同。基于迭代因子分解方法[程度24)是改善传统方法的性能通过使用迭代信息和节点度的分解。此外,一些其他node-sorting算法被引入提高分类的性能。

k层方法的基础上,我们的工作充分利用迭代分解过程中的信息,提出了一种改进的多属性k层方法。首先,迭代信息处理sigmod函数来获取位置指数。然后,位置属性被结合壳价值和地位指数。适应节点的本地信息获取邻居财产。最后,位置属性和邻居属性加权信息熵加权的方法。先生在实验中,模型,肯德尔系数,使用和不精确的功能,分别评估不同概率传播的传播能力,不精确的排名和相关系数不同的传播的可能性。此外,我们评估排名结果,该方法通过选择种子的影响力最大化问题和测量排名独特性和分布。实验结果证明该方法能有效区分不同属性的差异,明显促进识别性能的节点的影响。

以下部分组织如下。我们简要回顾相关算法用于比较的定义部分2。节3,我们提出了改进的多属性k层方法和有意义的例子说明提出的措施是如何工作的。节4,我们提出的细节数据,传播模型,评价测量用来评估我们测量的性能。并给出了实验结果5。最后,我们公开工作部分的结论6。

2。相关工作

Kitsak等人提出了k层法来确定网络中节点的影响。这种方法认为,越接近网络的中心节点,节点的影响将会越高。这个方法使用节点度对节点的重要性排名。下面的细节展示k层的分解原理的方法。

首先,我们需要删除的节点和边的中等程度1网络。这个时候,节点度为1仍然存在在剩余的网络。我们应该继续删除它们,直到没有节点度为1存在于网络。在这一点上,删除节点形成一层及其值赋给1。根据上述方法,继续删除网络中节点度值为2,重复此操作,直到没有网络中的节点。我们可以看到在图1,价值分配给节点8、9、10、11、12、13、14、15日和16日是1。的值分配给节点5、6和7是2。的价值分配给节点1、2、3和4是3。

k层分解方法适用于大型网络,因为很少的计算复杂性。当然,这种方法的缺点是显而易见的。首先,大多数节点被分配相同的值,这样这些节点的重要性不能被进一步区分。例如,从学位的角度来看,节点度8是3和节点11度是1。8节点的影响明显大于11,但是他们有相同的价值。其次,删除节点的过程中,已被移除的边缘是不被认为是和残留的影响仅仅是担心。通过这种方式,认为节点具有相同具有相同数量的外层边缘,这显然是不符合常识。例如,节点1和节点2有丰富的一阶和二阶的邻居在外层,而在外层节点1没有邻居。相同的价值分配给他们并不能反映它们之间的差异。第三,在常规网络大多数节点的值是1,这显然是不适合的背景。

传统的k层分解方法只更新节点根据剩余剩余的节点度和完全忽略的损耗程度删除节点。在混合程度分解方法,分解过程是基于剩余的其余节点和删除节点的损耗程度。为节点 ,其残留程度和损耗程度表示和 ,分别。每一步的混合程度分解方法,节点删除由混合程度决定 : 在哪里是在0和1之间的可调参数。当是0,混合程度分解方法k层分解方法是一致的。当是1,混合度分解方法相当于度中心的方法。有别于传统的k层分解方法,在混合程度分解方法,的价值所有节点的小数。的参数通常设置为0.7。

传统的k层分解方法提高了使用最短的距离从源节点到网络的核心节点。节点具有相同的传播能力价值可以进一步区分通过以下方法: 在哪里是最大的值k层分解,是值的节点 ,和组节点的吗值是最大的。尽管这种非参数方法可以识别相同的节点值,计算复杂度高,因为计算最短路径距离核心。更严重的是,如果没有完全连接网络,部分节点之间的最短路径距离对不能获得。

如果迭代信息是用来确定网络中节点的位置不同,节点具有相同的传播能力价值可以进一步区分。度分解方法的基础上,提出了迭代因子来改善传统方法的性能通过使用迭代信息和节点分解的学位。值得注意的是,学位是一个局部变量和迭代因子是一个全局变量。该方法充分结合当地和全球因素更有效地识别影响力的节点。迭代因子的节点是 在哪里是在k层分解和迭代的总数吗该节点的次数被移除的分解。节点的影响程度是基于迭代分解方法因素

节点的影响将是巨大的,如果一个节点有很多邻居的核心网络。基于这样的假设,你的邻居节点的核心 在哪里节点的邻居吗 。递归,扩展内核定义是邻居

3所示。材料和方法

实践证明,多个属性的结合可以进一步提高分类效果。近年来,研究人员不同的属性和策略结合节点的影响。这些方法证明了考虑多个属性的性能是一种有效的策略来评估节点性能的影响。目前,有许多属性权重的方法,如最小二乘加权法和主成分分析方法。在众多的属性节点,位置排序的过程中扮演重要角色的属性节点。同时,节点的影响能力在很大程度上取决于你的邻居的属性。结合这两个属性,这是一个有效的策略使用属性加权法来进一步识别节点的影响。

在k层分解过程中,迭代次数显示了非常重要的位置信息,它可以进一步区分删除节点的位置不同。一个节点具有更高的迭代次数更接近的核心网络,或是接近网络的边缘。这里的迭代次数是指全球的数量从k层迭代分解到结束。摘要sigmod函数用于进一步处理的迭代次数删除节点时,定义节点位置索引 :

地位指数和之间的关系如图的迭代次数2。随着迭代次数的增加,地位指数增加一个向下的斜坡0.75的临界值。

为代表的位置属性节点 ,的是哪一个节点和价值之和的邻居节点的位置指数: 在哪里是值的节点k层分解。

一个节点的位置属性不能有效区分节点在同一个位置的影响。例如,所有节点在网络的边缘有相同的位置信息,因此他们的影响力应该是相同的。事实上,由于局部结构的差别,边缘节点在同一个位置的影响会有很大区别。本地节点的属性应该进一步用来区分节点具有相同的位置属性的影响差异。如果一个节点拥有更多的邻居,它可以有一个更大的对网络的影响。此外,一个节点的邻居的影响也受到邻国的影响。考虑到二阶的邻居可以提高测量节点的影响的能力。

你的邻居节点的属性是由 ,所代表的是二阶的邻居节点的数量: 在哪里表示节点的程度 。

两个位置属性和本地属性发挥重要作用在识别节点的影响。结合这两个关键属性,可以精确的计算节点的影响和节点性能的影响可以进一步提高排名。许多传统多属性分类方法对所有属性权重是一致的。同时,权重的方法有很多,如层次分析法、多目标规划、主成分分析和加权最小二乘法。信息熵加权法是一个很好的权重方法,验证了许多例子。我们的方法适应信息熵加权的方法来避免传统的加权方法的缺陷: 在哪里代表的重量和位置属性代表你的邻居的重量属性。

信息熵加权法的计算过程如下。首先,每个属性的熵值计算: 在哪里代表的熵属性,代表的归一化值的属性节点。因为这种方法只有位置和邻居的属性,设置为1和2:

然后,结合信息熵计算的重量两个属性:

是否multiattribute-improved k层算法在本节中是可行的,可行性的帮助下可以解释图。图是一个无向图16 20节点和边缘。计算每个节点的PN价值根据算法。计算过程中的值如表所示1。从表中我们可以看到,所有节点的重要性可以排序根据PN值降序排列。的PN值节点节点11和12是一样的和不能区分它们的重要性。PN值的节点1、2、3、4的梯度,PN节点2的值是最大的。它的重要性可以看到在图1在网络。PN的节点值5,6,7,8位于第二梯度。这些节点不是外缘节点。

节点14的PN价值大于边缘节点9、11、12、13日和16。从图可以看出,因为它是直接连接到核心节点4,其影响力已经增强。从表中所示的计算结果1,它可以初步得出结论,基于多个属性的改进的k层方法在一定程度上是可行的。

4所示。实验装置

4.1。数据描述

我们六个不同的实际网络进行几个实验来评估我们的提议中心的性能的措施。真正的网络是来自不同的领域。CA-HepTh [25)是一种协作的网络Arxiv高能物理理论。Netscience [25)是网络的科学家们共同创作的网络理论和实验。Cond-Mat [25从预印本arXiv),涵盖了科学合作作者论文提交给浓缩物质类别。DNC邮件(26)的网络电子邮件在2016年的民主党全国委员会电子邮件泄漏。网络中的节点对应的数据集和用户之间的边缘是邮件交流。Ego-Twitter [27)包含Twitter user-user以下信息。一个节点代表一个用户和优势表明用户跟随其他用户。路线的观点(28是互联网的自治系统的网络互相连接。边缘节点自治系统(如),表示通信。简要概述的网络表所示2。

4.2。传播模型

评估排名列表的所有中心的措施,我们需要知道排名列表节点的实际传播过程。在传播过程中,从另一个用户接受消息的概率取决于用户的影响(31日]。节点的传播效率是用来测量有影响力的排名结果节点。有很多信息扩散模型,比如爵士模型,独立级联模型,线性阈值模型,一些信息扩散模型独立于网络拓扑结构(32,33]。在本文中,我们采用标准先生模型(34模拟扩散过程网络和记录每个节点的传播效率。在爵士模型中,每个节点属于敏感的国家之一,受感染的状态或恢复状态。在细节中,我们设置一个节点作为一个被感染的节点和其他节点易感节点。每一步,每一个受感染的节点,它可以感染易感邻居感染概率β然后可以删除概率 。一般来说,我们 。需要选择适当的传播概率,以防太小或太大传播概率使传播效果不理想,导致未能区分节点的影响。根据异构平均场方法,网络的流行阈值 。 和度和二阶程度的节点。传播的概率就比流行阈值设置。在实验中,这种动态的感染和恢复过程会重复,直到没有感染的节点。感染和恢复节点在时间的总和 ,用 ,可以被看作是一个指标来评估最初被感染节点的影响在时间吗 。很明显,增加而增加的并在时间将达到稳定状态 ,用 ,在哪里是最后的时间代表了最初被感染节点的最终影响。为了保证结果的可靠性,都是平均了大量的实现。

4.3。评价

为了评估中心的性能措施,我们使用肯德尔的系数τ(35)测量之间的关系产生的一个架构排名列表和一个爵士模型,由大量的接触模拟。让 和 是一个随机选择一双联合两个排名,和 ,分别。如果两个 和 或者,如果两个 和 ,据说他们正在整合。如果 和 或 和 ,他们是不和谐的。如果 或 ,这一对是一致的和不一致的。肯德尔的系数被定义为 在哪里和分别表示整合和不和谐的对的数量。的值隔和 。越高值表示,更精确的排名列表中心措施可能产生。最理想的情况 ,的排名列表生成的中心措施是一模一样的排名列表生成的实际传播过程。

测量不精确(17排名的方法有影响力的节点,我们比较有影响力的节点的传播能力获得的排名结果与节点的最大传播能力和传播能力的节点产生的爵士模型。肯德尔的相关系数之间的关系网络中所有节点的排名顺序和传播能力的所有节点的顺序。然而,不精确函数是用来评估不同比例累计顶级节点的传播能力。不精确的函数被定义为 在哪里是顶级节点的比例和表示节点的设置比例时在顶部 。 是传播能力的节点 。的价值隔和 。较低的值表示,更精确的中心措施是排名传播能力的节点。

5。结果与讨论

先生,在本章模型,肯德尔系数,和不精确函数用于验证该方法的性能。学位,k (k层),MDD(混合程度分解),ksIF (k层迭代因子方法),和数控+(扩展社区coreness中心测量)而提出的多属性PN的方法。

5.1。评估节点的传播能力

这部分验证不同传播概率选择传播渠道的固定比例下计算节点集传播能力的影响。通过比较不同算法在相同的传播能力传播概率,不同的方法可以比较的性能。仿真设置传播源比率为0.1。感染过程的最大时间步长设置为100,但是感染将停止在没有用户处于感染状态。结果是基于平均500个独立的实验。仿真结果如图所示3。传播概率是横坐标和纵坐标的传播能力,即表示为一个百分比。

首先,传播概率的增加,节点传播能力的六个方法改进。六个方法的性能比较接近时,传播概率很小,当传播概率很大明显不同。具体来说,CA-HepTh, DNC的邮件,和Cond-Mat PN的性能保持最好的在各种传播概率。Ego-Twitter数据集,PN的性能和数控+显著高于其他四种方法。此外,当传输概率为0.03,数控+的节点传输能力较高,而在其他情况下,节点传输PN方法更高的能力。Netscience和路由视图中的数据集,PN的性能相对优于其他方法,但数控+优于PN方法当Netscience传输概率小于0.1。PN在几个点路线的观点并不是最好的,但在大多数情况下,它有最高的传播能力,如图3 (f)。一般来说,本章提出的PN具有更好的性能。性能的差异与特定的网络结构。

5.2。评估排名的不精确

这部分验证不同比例的顶级节点选择下固定传播概率来计算节点的影响排名的不精确。通过比较不同算法的不精确的相同比例下顶级,不同方法的性能排名可以区分节点的影响。仿真设置传播节点的概率,如表所示2,顶级节点比例从0.01到0.2不等。感染过程的最大时间步长设置为100,平均结果是基于500个独立的实验。仿真结果在六个网络图所示4。横坐标是顶级节点的比例被认为是纵坐标是排名的不精确。

在图4(一),该方法PN, KsIF和数控+低时不精确高于0.02,他们在识别2%的顶级节点表现不佳。然而,不精确的PN远低于其他两个CA-HepTh数据集。的不精确程度排名前1%的节点比方法PN低约0.07。然而,程度最高当大于0.04。Netscience和Cond-Mat度、k层和MDD有更高的价值,和PN在大多数最低除了在0.02到0.04范围,KsIF优于PN Netscience。当大于0.04小于0.06,数控+优于PN Cond-Mat。在数据集,DNC电子邮件、k层和PN是更好的与其他方法相比,当k层有一个微小的优势0.04和0.1或0.13和0.15之间。然而,k层执行差在3%顶级节点。数据集,Ego-Twitter和路线的观点,很明显,我们提出的方法在所有情况下都表现良好和更稳定。从上述六个数据集的仿真结果,可以看出,该方法PN不仅可以精确识别最顶尖的1%到4%的节点也等级以下节点稳定的影响。

5.3。评估方法的相关系数

这部分验证之间的相关性影响价值和传播能力的节点在不同传播概率肯德尔的系数 。值范围的传播概率模拟数据集CA-HepTh 0.02到0.2,Cond-Mat, DNC邮件,Ego-Twitter和路由视图和扩展到0.3的数据集Netscience因为高流行阈值。在民主党全国委员会电子邮件和路线的观点,我们也把仿真结果当传播概率的值等于流行阈值。感染过程的最大时间步长是100。结果是基于平均500个独立的实验。仿真结果如图所示5。传播概率是横坐标和纵坐标是相关系数。每个网络的流行阈值也卷入图是一条垂直线。

排名结果的相关性不同的方法和真正的传播能力先生获得的模型在不同的数据集有不同的表现,但总的趋势是相同的。当传播概率很小,排名相关的学位,k层,与真正的MDD传播能力高于其他三种方法和流行阈值阈值大致相同的网络。图中可以看到5肯德尔高程度的系数当β小于0.06 CA-HepTh Netscience Cond-Mat和小于0.07,这是不明显的其他三个网络,因为小流行阈值。然而,在的情况下β高于 ,这些方法已经考虑学历和其他方面的影响等邻居节点的传播能力执行比主要考虑程度的方法。这是因为很小的传播概率感染行为将会在一个小范围在初始感染节点附近,无法在大区域,所以学位是决定性因素。随着传播的概率增加,感染的行为变得更容易,所以感染的程度不仅取决于邻居节点的数目也在邻国来繁殖的能力,甚至邻居的邻居。相反,当传播概率远远大于增加到一个点网络,感染变得太容易了,这样在网络的核心节点最大或与高度感染的范围。显然等小流行阈值显示在网络DNC电子邮件和图中路线的观点。当 ,PN肯德尔最高系数的方法t在CA-HepTh Netscience, Cond-Mat。我们建议的方法也执行最好的时候β是在0.06到0.14之间DNC电子邮件和在0.06到0.18之间的路线的观点。简而言之,与其他五个方法相比,PN在本章提出的方法具有良好的性能在适当的传播概率值范围。

5.4。评估的性能选择种子的影响力最大化问题

这部分验证的可靠性PN当它应用于影响力最大化问题。最大化的影响在现实生活中被广泛使用。例如,病毒式营销是一个典型的应用程序,它可以促进新产品或想法商人或宣传部门。它的目标是选择一组网络中的节点称为种子节点集作为初始传播节点,尽可能广泛地传播网络中根据一定的扩散模式。有许多相关的研究。我们使用选择的最高排名指定种子节点测量种子的传播范围节点选择几家排名方法。我们检查不同的种子节点集的传播效率有六个真实网络:CA-HepTh, Netscience, Cond-Mat, DNC邮件,Ego-Twitter,路线的观点。

在实验中,我们设置作为种子的比例节点在整个网络中,从0.01到0.05不等。我们也用爵士模型来模拟计算传播过程和影响范围使用的用户数量终于被感染。的传播概率仿真确定根据流行阈值和表所示2。感染过程的最大时间步长设置为100,结果是基于平均500个独立的实验。仿真结果如图所示6。横坐标是种子的比例在所有用户,纵坐标是初始种子的传播范围节点和表示为一个百分比。

结果清单,数据集Cond-Mat PN最好方法执行,DNC邮件,Ego-Twitter,路线的观点。CA-HepTh数据集,种子时PN组选择方法大于0.02可以感染比别人怀尔德。当0.02及以下,学位是最有效和PN比KsIF数控+。在Netscience网络KsIF最好的时候是0.03和0.04,受感染的种子选择PN KsIF在其他情况下几乎是一样。

5.5。测量排名独特性和分布

这部分验证新方法的单调性排序用Bae和金正日的排名单调性法(23]。自k层方法将计算k层许多节点相同的值的价值,很难区分他们的差异影响。在这方面,我们提出的方法可以做得更好。根据Bae的定义和金姆,单调性的排名结果表示如下:

在(16),R代表了排名n是它的大小,每一个元素的排名是一组节点有相同的排名值,然后呢节点的数量在吗具有相同的排名位置 。的价值之间波动和价值越高,独特性越强。在极端的情况下,意味着每个节点分配一个不同的值,而相反,所有节点在同一个等级。

我们检查不同的方法的单调性上面的六个数据集一样。计算结果如表所示3。从表中可以看出,PN的单调性的结果显然高于学历,MDD,近似KsIF和数控+。

为了澄清的排名分布不同的措施更清楚,一个互补累积分布函数(CCDF)绘制。根据CCDF原则,如果许多节点在同一等级,CCDF情节都将迅速减弱;否则,CCDF情节将慢下来。图7显示了排名分布在六个网络。

这条线代表学历, ,或MDD大幅下降,我们可以看到每个图的左边。特别是当节点数据集的数量很大。方法PN的排名分布略有改善与数控DNC +和KsIF数据集相比,电子邮件和路线的观点。KsIF和PN数据集的曲线Netscience基本上是重叠和下降速度比数控+。在数据集CA-HepTh Cond-Mat,数控+方法相比也不执行方法KsIF和PN。KsIF和PN同样擅长识别影响力的节点,而在后者排名的一部分,KsIF曲线的下降趋势比PN的曲线更加明显。暗示的能力方法PN区分节点的传播能力比数控+。可以看出在Ego-Twitter PN的性能比数控+方法。所以,我们可以说,在大多数网络PN表现良好。

6。结论

k层方法的基础上,我们提出了一种新的基于节点位置和附近的多属性的排名方法。我们充分利用迭代分解过程中的信息。首先,迭代信息处理sigmod函数来获取位置指数。位置属性是通过结合壳价值和地位指数。然后,采用节点的本地信息获取邻居财产。此外,位置属性和邻居属性加权信息熵加权的方法。最后,我们评估不同的传播功能传播概率,不同比例的不精确,不同传播的相关系数概率,选择种子的传播功能节点影响力最大化问题。与此同时,我们也验证了我们的方法的良好性能区分节点的影响。与其他k层分解和其改进算法相比,本文的方法更好的性能。通过仿真实验,发现PN方法可以充分利用迭代分解过程中的信息和邻居的影响,进一步区分节点具有相同的差异价值。先生实验模型,肯德尔的系数,不精确函数充分验证了该方法的正确性和有效性。总之,该方法的有效性在影响节点的识别是由各种形式的验证实验。

数据可用性

之前报道网络数据集被用来支持这项研究和可用http://networkrepository.com和http://konect.uni-koblenz.de。这些数据集是作为引用文本中引用在相关地方(22- - - - - -25]。

的利益冲突

作者宣称没有利益冲突有关的出版。

确认

这项工作得到了陕西省重点产业项目(批准号2019 zdlgy09-03),陕西省自然科学基金(批准号2018 jm6053和2018 jz6006),中国国家自然科学基金(批准号。61372076,61372076,61771296),和111年项目(批准号B08038)。