基于Hurst指数的在线社交网络影响力最大化方法

沙特国王大学学报基于Hurst指数的社交网络影响力最大化方法Bhawna Saxena，Vikas Saxena印度北方邦Noida 201309，A- 10，Sector - 62， Jaypee Institute of Information Technology，Department of Computer Science Engineering IT阿提奇莱因福奥文章历史记录：收到2019年2019年12月16日修订2019年12月18日接受在线发售2019年保留字：在线社交网络影响力最大化自相似Hurst指数A B S T R A C T在线社交网络中的影响力最大化由于其在许多现实世界领域的应用而成为一个趋势研究领域。影响最大化解决了识别社交网络中的k在本文中，影响力最大化已经提出了一个节点的连接和它的实际过去的活动模式相结合。分析节点的活动与相互作用的频率和自相似性的趋势，提供了一个更现实的视图的节点的影响力的潜力。受这一概念的启发，提出了基于连接和过去行为识别初始采用者的HAC-Rank算法。此外，还提出了用于扩散的基于Hurst的影响最大化（HBIM）模型，其中节点的激活取决于其连接和其过去活动所表现出的自相似性趋势。为了评估节点活动模式的自相似性趋势基于所取得的结果，该算法已被发现比其他国家的最先进的算法，初始adop-ter识别。©2019作者由爱思唯尔公司出版代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍在线社交网络（OSN）是为社交互动而创建的相互连接的用户的结构。社交网络（数学类比中的图）是代表用户的节点（顶点）和代表用户之间连接的链接（边）的集合。在当今世界，OSN在信息、观点、想法、创新等的传播中发挥着至关重要的作用。由于OSN在教育、金融、政治、医药和医疗保健、娱乐等多个领域的使用，OSN已经变得非常流行。政治运动经常利用OSN来传播/散布信息（Chen等人，2009，Sun和Tang 2011，Peng等人，2017，Li等人，2018年，Peng等人，2018，Han and Li 2018）。*通讯作者。电 子 邮 件 地 址 ： bhawna161@yahoo.co.in （ B.Saxena ） ， vikas. jiit.ac.in（V.Saxena）。沙特国王大学负责同行审查制作和主办：Elsevier社会网络分析（SNA）是一个受欢迎的研究领域，旨在通过使用社会，统计，图论和计算机科学领域来分析社会结构在SNA下进行的各种工作可以分为三类，即结构分析-基于网络的结构和功能的分析，社会数据分析-基于网络中产生的数据的分析，以及社会交互分析-使用社会网络用户交互进行的分析（Kurka等人， 2015年）。社会互动分析下的一个新兴研究领域是社会影响分析，其研究社交网络中的信息传播过程以及有影响力的用户的识别（Li et al.，2018年）。社交影响是指由于另一个用户的行为或意见而导致的用户的行为、情感或意见的变化。社会影响力的强度可能取决于关系的强度，用户之间的距离，时间效应，用户和网络特征（Sun和Tang，2011）。在社会影响的作用下，人们倾向于采取他们的邻居所表现出的行为。社会影响力分析在各种现实世界的应用中找到用途，用于产品/服务的在线促销的影响力最大化这里的想法是在利用最少资源的同时最大限度地扩大活动的范围。考虑一个假设的场景，其中公司希望使用社交网络来推广其产品它将https://doi.org/10.1016/j.jksuci.2019.12.0101319-1578/©2019作者。由爱思唯尔公司出版代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comB. 萨克塞纳河谷Saxena/沙特国王大学学报2219Dv我肯定希望它的营销活动能接触到尽可能多的潜在客户。开发潜在客户的最好方法是发放免费样品。但每次营销活动都有预先确定的预算，因此只能提供有限数量的免费样品。该公司肯定会想把这些免费样品给一些有影响力的人，这些人反过来可以把他们的产品推销给很多人。因此，这里的目标是让一小部分有影响力的用户采用该产品，这些用户反过来可以引发大量的进一步采用。因此，这个问题减少到一小部分有影响力的初始采用者的识别。这个问题被称为影响最大化问题，它涉及识别一小组初始采用者，这些初始采用者在最大化整个网络中的信息传播方面最有影响力（Kempe等人，2003; Chen等人， 2009年）。为了从网络中的各个节点（用户）中选择初始采用者，需要量化节点的影响潜力。 这可以通过在一段时间内利用节点特性或节点行为来完成（Kempe等人，2003; Chen等人，2009; Heidemann等人，2010;Goyal等人，2011; Deng等人，2015年; Liu等人，2017; Tong等人，2017年）。用于评估节点的影响潜力的广泛流行的度量是其程度（Kempe等人， 2003; Chen 等 人 ， 2009; Wang 等 人 ， 2014 年 ; Liu 等 人 ，2017;Alshahrani等人，2018年）。一般认为，连接数越多，节点的影响潜力就越大一旦确定了最初的采用者，就需要一个扩散模型来衡量这些最初的采用者所预期达到的影响力扩散。（Kempe等人，2003）提出了独立级联（IC）和线性阈值（LT）两种扩散模型，在影响最大化领域得到了广泛的应用。在IC模型中，网络中的每条边都有一个分配给它的传播概率，这表明了该边上激活的机会。在LT模型中，每个边被赋予预定义的权重，并且节点考虑一个情况其中节点u和v之间具有m条平行边，并且du和dv分别表示u和v的度数。然后，边（u，v）被分配权重（m）（Kempe等人， 2003年）。所以在这两个模型的扩散都与分配给节点连接的概率值或权重有关营销活动通常是时间紧迫的。组织总是希望他们的营销活动在预定的时间范围内达到尽可能多的人。在这种情况下，节点（社交网络中的用户）的连接数量与这些连接上的通信频率一样重要。‘‘A node mightbe having a large number of connections, butif it is notcommunicating with its neighbours, then it is more like a dormantnode (必须相应调整这些节点因此，节点节点之间的交互类型、节点之间的通信频率和节点的活力是影响影响力传播的一些用户行为特征（ Heidemann 等 人 ， 2010; Goyal 等 人 ， 2011; Deng 等 人 ， 2015年）。虽然人类行为通常被认为是随机的，但它确实倾向于重复自己并显示统计自相似性。（Fan等人，2010）已经观察到，对应于人类行为生成的时间序列显示出具有长程相关性的自相似性。因此，除了相互作用的量之外，可以考虑的另一个方面是自相似性质，即，重复趋势，由用户的交互模式显示。用户交互是一个时代发展的现象，可以考察其是否存在某种趋势。 与现实世界网络中的人类行为类似，OSN中的用户行为也可以被期望显示自相似性。不过，研究人员已经研究了自相似性在OSN中的边缘生成中的作用（Liu等人，2016），但是用户交互时间序列中自相似性的存在，是一个关于OSN还没有被探索的领域。拟议的工作从这样一种信念中汲取动力，即由节点实时执行的交互给出了其行为的更真实的图片，因为它们表明节点使用其连接来传播信息的程度和频率。此外，反映在节点的活动模式中的自相似性趋势基于这两个概念，已经提出了用于选择初始采用者的算法，即HAC_Rank，其基于节点具有的连接数量、其活动水平（即，由节点发起的交互的数量此外，还提出了一种扩散模型，即基于Hurst的影响最大化（HBIM）模型，该模型计算由一组种子节点实现的影响的传播。在所提出的HBIM模型中，边缘上的传播取决于接收节点过去行为中显示的自相似性趋势及其程度。在IC和建议的HBIM扩散模型下评估了建议的HAC-Rank算法的性能与其他最先进的算法相比，在IC模型下运行时，HAC-Rank的平均影响力扩展为20.3%。在提出的HBIM模型下，与其他最先进的算法相比，HAC-Rank实现了49.8%的平均文件的其余部分组织如下。第2提出了一个简短的讨论有关的影响最大化和自相似性的一些现有的工作。 在第三节中，讨论了影响最大化和自相似性的概念。此外，本节还讨论了一些现有的影响最大化的扩散模型。第4节简要介绍了拟议的工作，并详细说明了所进行的实验。第5节对所得结果进行了分析。最后，第6节结束了工作。2. 现有技术影响最大化（Influence Maximization，IM）包括两个主要活动：种子节点（初始采用者）的识别和信息扩散模型的建立.如上所述，量化节点影响力潜力的最直观方法是它所具有的连接/链接的数量，即它的度。中心性度量是用于识别网络中的影响节点的最常用的度量之一（Freeman 1979; Sun和Tang 2011;Zafarani等人，2014年）。在一些工作中，节点活动水平也被认为是对该节点的影响潜力评估的重要贡献者（Heidemann等人，2010; Goyal等人，2011; Deng等人，2015年; Saxena和Kumar，2019年）。通过文献调研发现，现有的种子选择算法大多是双向工作的。 第一个是增强贪婪算法以减少它们的执行时间，第二个是开发利用节点的结构和时间属性的新算法，用于种子选择，而不需要多次重复（Leskovec等人，2007; Chen等人，2009; Heidemann等人，2010;Goyal等人，2011; Wang等人，2014; Deng等人，2015; Bucur和Iacca，2016;Liu等人，2017; Wang等人，2017; Tong等人，2017; Zhu等人，2017; Agarwal 和 Mehta ， 2018; Alshahrani 等 人 ， 2018; Sheng 和Zhang，2018）。根据用于种子选择的方法，各种现有的种子选择算法可以在很大程度上分为两组-基于贪婪的和基于启发式的（Peng等人，2018年; Li等人，2018年）。在基于贪婪的方法下，基于种子的边际增益来选择种子2220B. 萨克塞纳河谷Saxena/沙特国王大学学报值及其预期的传播几乎是有保证的，但是该过程是非常耗时的。在启发式方法下，使用启发式方法选择种子，该方法不保证是最优的，但其执行时间更少。2.1. 贪婪的做法IM问题的算法方法首先由Domingos和Richardson提出（2001年）。从那时起，许多算法的种子集识别，和各种扩散模型已经开发的IM在OSN。（Kempe等人，2003）开发了一种用于种子集识别的基于贪婪的算法，其中，导致朝向影响扩散的最大边际增益的节点被选择为种子节点。他们还讨论了三种扩散模型，用于研究通过确定的种子节点在网络中实现的影响传播，即（Leskovec等人，2007）提出了用于种子集识别的成本有效的惰性转发（CELF）算法，该算法是对原有贪婪算法的优化。在CELF中，每次迭代的计算数量减少，因为它基于当前迭代中节点的边际增益值不能优于其先前迭代的值的概念（Deng等人，2015）提出了具有节点特征的贪婪算法（GNF）用于初始种子集识别。GNF是一种贪婪算法，它使用边际增益的概念进行种子选择。此外，他们还提出了一种扩散模型，即具有节点特征的信用分布（CD-NF），其灵感来自Goyal等人提出的信用分布（CD）模型，2011年）的报告。在CD-NF模型中，信息在网络中的传播依赖于节点的信息传播轨迹。根据每个节点过去执行的活动，为每个节点计算信用评分。信用评分既考虑了信用节点（Tong等人，2017）提出了两种自适应种子选择方法，A-Greedy和H-Greedy。在这些方法中，种子选择机制本质上是自适应的，并且迭代中的选择取决于先前迭代的结果。此外，他们还提出了动态独立级联（DIC）扩散模型，其中边缘上的传播概率不是静态的，而是从预定义的分布中选取的（Zhu等人，2017）提出了一种基于贪婪的算法，基于结构洞的影响最大化（SHIM），用于有影响力的种子识别，该算法的灵感来自于结构洞节点在社区之间传播信息时更有效的想法。通过测量结构孔洞节点的影响潜力，生成候选节点集，并从中选取种子节点由Sheng和Zhang，2018提出的用于种子选择的LPIMA算法基于标签传播社区的概念种子节点是从一个候选集，这是通过评估社区节点的影响力产生的。2.2. 启发式方法除了提出对CELF算法的进一步改进之外，（Chen等人， 2009）也 提 出 了 两 种 启 发 式 种 子 选 择 算 法 SingleDiscount 和DegreeDiscountIC，其影响范围与贪婪算法相当接近。由于是启发式的，它们的运行时间大大少于贪婪算法。在这两种算法中，种子是根据节点的度来选择的。在每次迭代中，对于每个选定的种子节点，其本身不是种子的邻居的度被打折。（Chen和Ying，2013）已经提出了用于种子识别的CI方法，其中各种群落的影响值首先对网络中的节点进行评估，然后从具有较高影响力值的社区中挑选种子节点。（Wang等人， 2014）提出了用于种子选择的PRDiscount算法。这是一种启发式方案，其从PageRank算法（Page等人， 1999），其中网页的排名是基于其前身的排名来计算的。类似地，在PRDiscount中，每个节点的影响力是基于其前任的影响力计算节点的影响力被用作种子选择标准。影响力越大，被选入种子集的机会就越大用于识别最不可能退出使用网络的前k个可靠用户的基于PageRank的新算法已经由（Heidemann等人，2010年）。它使用用户的连接和通信活动的概念。首先，生成加权活动图，其指示在每条边上发生的交互的数量。此后，该图已被用于确定用户中心性分数。该方法的灵感来自PageRank算法。（Jung等人，2012）提出了一种用于即时通信的IRIE算法，该算法综合了影响力排名（IR）和影响力估计（IE）两种方法。IR首先生成网络中所有节点的全局影响力排名节点的影响扩散可以彼此重叠。为了减轻这种重叠效应，一旦选择了种子，就重新估计所选种子对网络中每个节点的影响。此后，重新计算剩余节点的排名。基于GA的影响最大化算法已由（Bucur和Iacca，2016）提出，其中遗传算法的交叉和变异操作已用于减少候选解的大小并选择最合适的节点作为种子节点（Bucur和Iacca，2016）。（Liu等人，2017）提出了用于识别顶级k种子节点的局部索引排名（LIR）算法。LIR利用“富俱乐部现象”，这表明具有高度的节点的邻居也具有高度。计算每个节点的LI得分，并将其用作种子选择的标准。通过计算节点的度与其邻居的度之间的差来计算节点的LI得分。具有LI得分为0的节点被认为是其相应邻域中的领导者，并且被选择为种子节点。（Alshahrani等人，2018年）提出了PrKatz算法，用于识别前k个有影响力的节点。该算法利用Katz中心性和传播概率（使用节点的度计算）。（Agarwal和Mehta，2018）提出了一种种子集选择算法，该算法使用具有动态边缘概率的遗传算法。动态边缘概率的计算已经使用局部亲和传播机制完成。（Adineh和Nouri Baygi，2018）提出了两种基于度中心的算法来识别种子节点，即NeighborsRemove和DegreeDecrease。在这两种算法 中 ， 具 有 最 大 度 的 节 点 被 选 择 为 种 子 节 点 在 每 一 个 迭 代 。 在NeighborsRemove中，一旦一个节点被选为种子，它的所有邻居都将从有资格选择种子的候选者列表中删除。在DegreeDecrease中，所选种子节点的所有邻居的度都会降低，以降低它们的优先级。附录中的表A1对当前最先进的种子节点识别算法的特点、优点和缺点进行了综述2.3. 合成对现有种子选择算法的研究表明，种子识别算法大多利用节点B. 萨克塞纳河谷Saxena/沙特国王大学学报2221在网络中的位置，以评估其影响潜力。然而，一些研究表明，节点其影响潜力（Heidemann等人，2010; Goyal等人，2011; Deng等人，2015年）。具有较少连接但较高交互的用户可能与具有大量连接但很少交互的用户具有同等影响力。除了交互频率之外，另一个值得考虑的方面是关于活动水平的统计自相似性的用户活动模式如果高度活跃的用户的活动模式显示持续的自相似性趋势（暗示行为的重复），则可以预期用户将在未来继续显示高活动水平。这样的节点因此可以被认为是用于充当初始采用者的潜在候选者（Fan等人，2010年）研究了人类行为的分形特征，使用的时间序列产生的金额的图书馆借阅的用户，并已发现所产生的时间序列是分形与长程相关。此外，他们认为人类行为不是随机的，在一段时间内往往会表现出一些相似性在他们的工作中，（刘等人，2016）已经研究了自相似性缩放在社交网络边缘创建过程中的作用。他们分析了时间标记的痕迹，这些痕迹表明用户的到达时间和用户之间的链接创建时间。他们发现，在他们考虑的两个真实世界社交网络数据集中，边的创建过程都显示出自相似特性。比特币加密货币汇率时间序列和比特币相关OSN中的社群活动的分形分析已经由（Lyudmyla等人，2017年）。他们发现比特币时间序列和社群活动具有自相似特性。此外，他们还研究了与比特币相关的OSN中比特币汇率与社群活动基于对现有工作的回顾，已经观察到，在影响最大化领域所做的大部分工作，利用节点的直接和扩展连接来量化其影响能力或在扩散过程中激活它（中心性是用于量化节点影响的广泛使用的度量）。各种中心性度量利用节点然而，单靠节点连接可能不足以判断节点的影响潜力。人们通常认为，节点将利用其所有连接来传播信息。这个假设是基于节点的预期影响能力的静态视图，以及节点是否实际在做是或不是，我们无法得知。为了得到更真实的画面，节点实际上是如何利用其连接的，应当检查其动态行为。虽然分析节点的活动水平是一个重要方面，因为它可以更真实地了解节点连接的实际使用情况，但研究人员在评估节点的影响潜力方面还没有进行太多探索。如前所述，可以假设OSN用户的行为类似于现实世界中的人类行为。因此，可以预期OSN中的用户行为在一段时间内显示自相似性。评估节点行为中的自相似性水平可以给出关于节点行为所描绘的趋势的想法。在OSN中，探索节点活动时间序列中自相似性的存在节点关于节点如何真正使用其连接的陈述。节点的交互频率指示在给定时间段期间节点使用其连接进行信息传播的次数。基于频率，可以知道节点是否活动。此外，通过检查节点的过去活动时间序列，可以识别活动模式所表现出的趋势。如果趋势表现出持续的行为，那么可以预期节点的未来行为将与其过去的行为相似。结合这两个因素，即，互动频率和趋势在活动模式中，可以帮助识别更活跃的节点（与网络中的其他节点相比）并显示持久行为。此后，将节点的度、其实际交互频率以及其活动模式中显示的趋势的概念合并起来，将比单独考虑其度更好地评估其影响潜力。所提出的工作旨在解决IM的问题，通过开发种子识别算法和扩散模型，实现更高的影响力传播，相比其他一些现有的方法。在这种思想的驱动下，在所提出的工作中，一个启发式算法的种子节点识别使用节点的连接，互动频率和自相似性的性质表现在其活动模式已经开发。此外，还提出了信息扩散模型，其中，在边/链路上的扩散依赖于在接收节点的过去行为中显示的自相似性的程度和性质。3. 预赛本节简要讨论自相似性、赫斯特指数和影响最大化的概念。3.1. 自相似性和Hurst指数在数学中，一个物体被认为是自相似的，如果整个物体具有与它的一个或多个部分完全或近似相似的形状。沿着时间或空间维度的尺度不变性指示自相似性的精确形式，其中在任何放大水平下，对象的较小部分与整个对象精确相似。还存在另一种形式的自相似性，称为统计自相似性，其中模式以跨尺度保持相同统计特性的方式随机重复。表现出自相似性的随机过程被称为自相似过程。在时间序列的情况下，自相似性表 明 时 间 序 列 的 相 关 结 构 在 不 同 尺 度 下 保 持 不 变 （ Crovella 和Bestavros，1997）。换句话说，对于时间过程，自相似性是指不变性行为，其中某些统计特性在过程的适当重新缩放版本下是相似的（Liu等人， 2016年）”。随着时间发展的现象可以用时间序列来描述。时间序列是对一个变量在一段时间内所取值的一组定量观察的时间顺序排列。换句话说，时间序列是按时间排序的数字数据点的序列。量化时间序列中自相似性程度的流行度量是赫斯特指数（H），其测量时间序列的自相关性（Fan等人，2010，Resta，2012，Lyudmyla等人，2017年）。H测量时间序列的相对倾向，要么强烈回归到平均值，要么向一个方向聚集（Kleinow，2002）。H的值在0到1的范围内，并表示不同的趋势：2222B. 萨克塞纳河谷Saxena/沙特国王大学学报⊂0 - 0.5范围内的H 这样的时间序列也称为均值回复时间序列，因为这些值表现出回复到均值的趋势H= 0.5表示随机且不相关的时间序列。在这样一个系列中，由于现值和未来值之间不存在相关性，因此很难确定任何趋势。0.5 - 1范围内的H为了评估H，使用了重标极差（R/S）分析技术。R/S分析是一种用于对时间序列进行分类的统计方法（Qian and Rasheed，2004）。它有助于测量一段时间内时间序列数据的可变性（Hurst，1951）。它的基本目的是评估时间序列中的可变性如何随不同的时间跨度而变化。 为了计算时间序列的H，完整的时间序列首先被分成多个具有不同长度的较短时间序列。然后计算所有时间序列的平均重标度范围，即，为对于所有较短长度的时间序列。时间序列的重缩放范围值通过将其范围（R）除以其标准差（S）来计算。然后，通过在log（R/S）与log（n）（其中n是时间序列的长度）的不同值的图中拟合直线来估计H。拟合直线的斜率给出了H的值（Hurst，1951，Qian和Rasheed，2004）。3.2. OSN中的影响最大化社会影响力分析是一个趋势研究领域，因为它在各种现实世界的应用中找到了用途，如在线营销、政治活动、有针对性的营销、增加为社会事业运行的程序的范围、推荐系统等。社会影响力分析的一个受欢迎的子领域是影响力最大化。影响最大化（IM）主要包括两个步骤：1. 种子识别：评估节点的影响潜力，然后识别可以在网络中产生最大传播的种子节点;以及2. 扩散模型：选择一种模型在网络中扩散信息。OSN可以被概念化为图G（V，E），其中V是用户（节点）的集合，并且E是描绘用户之间的连接的边的集合对于给定的网络G，IM的目标是识别一个k-节点集S（SV），该节点集可能最大化在G上传播的影响。S表示初始种子集，k表示S中的节点数。如果d（S）表示期望的扩散，则目标是识别d（S）是最大的集合S种子选择算法旨在识别种子用户的初始集合，这些种子用户可以充当初始采用者，并且可以触发进一步的采用，从而在整个网络中传播最大的影响力。如前所述，在他们的开创性工作中，（Kempe等人，2003）提出了两种流行的扩散模型：IC模型和LT模型。在这两种模型中，节点可以处于活动状态（表示采用信息）或非活动状态。这两种模型下的扩散都是以离散的时间步长进行的。IC和LT都是渐进模型，这意味着一旦节点的状态从非活动变为活动，它就会在整个扩散过程中保持其状态。这些模型的前提是节点变为活动的机会随着其活动的前趋节点的数量的增加而增加在IC模型中，扩散开始于一组活跃节点，称为种子节点，比如在时间t处的S。在每个随后的时间步t+ 1，所有活动节点都有一次机会以某个预定义的边传播概率激活它们的后继节点。因此，如果一个节点在激活任何后继节点时失败，那么它不能再次尝试这样做。指示在边缘上激活的机会的边缘传播概率对于网络中的所有边缘是相同的。扩散过程继续进行，直到不能进行进一步的激活。在LT模型中，每个节点都有一个与之相关的预定义阈值h，描述了其激活所阈值对于网络中的所有节点都是相同的为网络中的每条边分配权重。该边权重描述了对该边施加的影响在LT中，扩散过程也从一组活跃的种子节点开始，并且随着活跃节点对其不活跃的后继节点施加影响而进行当来自其活跃前辈的影响之和等于或超过其阈值时，节点变为活跃的扩散继续进行，直到不能进行进一步的4. 拟议工作对于病毒式营销应用程序，节点传播信息的速度与其链接的数量一样重要。因此，节点的时间行为与它可以传播信息的路径数量同样重要。对于时间关键型应用，偶尔使用其连接的高度连接节点的影响能力应被认为小于具有较少连接但频繁使用那些连接的节点。研究还表明，人类倾向于重复他们的行为（Fan等人，2010年），因此可以说人类行为是一个自相似的过程。因此，如果一个节点如前所述，持续的时间序列表明高值之后可能会有更高的值，并且在未来很长一段时间内都将遵循相同的模式在这些概念的驱动下，并结合它们，种子选择机制，HAC-Rank，已经提出了在这项工作中，利用节点的连接，其活动频率，其活动模式的自相似性。研究了节点行为模式中的自相似性，以了解其遵循的趋势。此外，还提出了一种称为基于Hurst的IM（HBIM）模型的信息扩散模型，其中，网络中的边缘上的扩散取决于接收节点的度和其过去活动模式的H值。第4.1节简要描述了提出的HAC-Rank算法，第4.2节简要描述了提出的HBIM模型。4.1. HAC-Rank机制与许多现有的工作不同，所提出的用于种子识别的HAC-Rank算法通过结合用户（节点）的连接性、活动性和对应于其过去活动模式的H（Hurst指数）来解决该问题该方法包括以下四个步骤：1. 计算活动分数：计算网络中每个节点在预定义时间范围内的活动分数;●●●B. 萨克塞纳河谷Saxena/沙特国王大学学报2223Imax2. 计算H：根据给定时间跨度内生成的活动时间序列，计算每个节点的H3. 节点排名标准：通过组合其对应的出度值、活动得分和H来计算每个节点的排名;以及4. 识别初始采用者：最后，为给定网络识别初始采用者的k节点种子集[k表示初始种子集中的种子.4.1.1. 计算活动评分对于给定社交网络中的每个节点，分配一个活动分数，该分数对应于该节点在所考虑的时间跨度内开始的交互次数。如果一个节点还没有启动任何通信，那么它的活动得分为0。活动-已经按照（1）计算了ity score，其中N（v）表示v的后继者的集合（参见等式（1））。 ① ①）。 （时间跨度是一个前提，影响它就失去了意义。设节点v是节点u的前代节点之一。如果节点u被v以外的任何一个节点激活，那么v就失去了激活u的机会，因此，从v到u的边不应该计入v（Chen等人， 2009年）。因此，所有这些不活跃的前代的出度在目前的工作中，已经按照度折扣启发式（Chen et al.， 2009年）。重复选择具有最高秩的节点并调整其不受影响的前代节点的度的过程，直到已经识别出k个4.2. 提出的HAC-Rank算法算法1提出了用于种子节点选择的建议的HAC-Rank算法。决定的时间段，在该时间段内，由节点被记录和调查。在比较不同的网络时，应考虑相同的时间跨度。在独立分析网络的情况下，则可以针对不同的网络考虑不同的时间跨度）。算法1：HAC-Rank（G，k）输入参数：图G =（V，E），初始种子集的大小k输出参数：initial_seeds[ ]：k-大小的选定种子节点开始行为能力评分Pu2Nuvp其中：总交互量v;u表示从v到u发起的总交互量Imax表示网络中任何节点发起的最高交互次数4.1.2. 计算Hð1Þ1：对于每个节点，使用等式2计算其Activity_score。（1）和Out_degree值;2：对于每个节点，生成其针对所考虑的时间跨度的活动时间序列，并基于所生成的时间序列计算H3：对于每个节点，使用等式2计算其HAC-Rank。（2）;4：初始化seed_counter：= 1;5：WHILE种子计数器 =k第六章：chosen_node=MAX（HAC-Rank（v i）），其中i=1至N，N = G中的节点总数;第七章：initial_seed_nodes[seed_counter]：=chosen_node;8：识别chosen_node的前置节点，并存储它们对于网络中的每个节点，在完整的时间跨度（每单位时间是预先确定的值，并且可以是每小时、每天、每周、每月等）期间，生成由该节点每单位时间发起的交互的时间序列。）.此后，基于其生成的时间序列为每个节点计算H。在所提出的工作中，H已使用重新标度范围（R/S）分析方法（如第3.1节所述）计算。4.1.3. 节点排序标准节点排名标准主要结合了节点的两个主要特征-其连通性和其活动性，对这两个方面给予相等的权重。活动方面进一步细化为活动频率和活动自相似性趋势，并赋予这两个子方面相等的权重。网络中的每个节点根据等式中指定的排名标准被分配一个排名。（二）、HAC排名排名aωOut degree排名bωActivityscore排名þðcωHðvÞÞð2Þ其中v表示节点，H（v）表示对应于节点v的过去活动的赫斯特指数，并且a、b和c表示分配给连接性、活动分数及其H值的方面的权重。在建议的工作中，a= 0.5，b=c= 0.25。4.1.4. 识别初始种子一旦所有节点都被排序，则选择具有最高排序的节点为了减少重叠效应（Chen等人，2009; Wang等人，2014），则所选种子节点的不活动（仍然未受影响的）前驱节点的出度被打折。这样做的原因是，一旦节点被激活，其尚未激活的前任节点变为活动节点的机会neighbors_of_chosen_node;9：FORneighbors_of_chosen_node中的邻居10：如果邻居不在initial_seed_nodes11：折扣出度（邻居）12：根据等式12重新计算HAC-秩（邻居）（2）; 13：如果结束第14章：一夜情15：seed_counter=seed_counter+1;第16章：一夜情计算每个节点的Activity_score和Out_degree（步骤1）需要O（n）时间，其中n是网络中的节点数Cal-culatingH（步骤2）为每个节点需要O（nbL）的时间，其中b是不同长度的完整的时间序列被划分成的数量，和L是在全长时间序列的数据点的数量。计算每个节点的HAC-Rank（步骤3）需要O（n）时间。从n个节点中选择具有最高HAC-Rank搜索一个节点的邻居是否已经被选为种子，需要O（n）时间。步骤11-12，执行一些常量操作，需要O（1）时间。对于所有节点，重复步骤10此外，步骤5-16所需的计算时间因此，该算法需要O（kn2）时间才能完成，其中k是初始种子集的大小，n是节点（用户）的数量。在下面的部分中，提出了一个信息扩散模型，该模型基于节点的度和H值来激活节点。2224B. 萨克塞纳河谷Saxena/沙特国王大学学报1234.3. 基于Hurst的影响力最大化模型（HBIM）IC和LT模型（Kempe等人，2003）是用于研究由种子节点实现的影响传播的两个最广泛使用的模型。如前所述，在IC模型下，信息从一个节点到另一个节点的传播与预定义的传播概率相关联，该传播概率对于网络上的所有边都是相同的，并且在LT模型下，当来自其活动的前趋节点的组合影响超过其预定义的阈值时，节点被激活。这两个模型的工作原理都是基于这样一个概念，即非活动节点转变为活动状态的机会随着其活动前辈数量的增加而增加。除了其连接之外，分析节点的实际行为，即，计算节点实际使用其连接的程度以及节点的活动趋势是什么，将给出对节点的影响能力的更好和更现实的理解。受此启发，本文提出了一种研究种子节点影响力传播的HBIM模型，其中节点的激活依赖于其连接和过去活动所显示的自相似性趋势在所提出的HBIM模型下，首先计算网络中每个节点的H值，对应于其过去的活动时间序列。此后，扩散过程以初始k大小的种子集开始。在每次迭代中，每个活动节点激活出度值大于或等于整个网络的平均出度值并且H> 0.5的那些非活动后继节点H> 0.5的选择是基于H> 0.5指定持久时间序列的上述事实扩散过程不断重复，直到不再可能激活。5. 实验已经通过将其性能与三种现有的种子选择算法进行比较来评估所提出的HAC-Rank算法，即度（Kempe等人，2003）、SingleDiscount（Chen等人，2009）和DegreeDiscountIC（Chen等人，2009年）。并将HBIM模型与IC模型的性能进行了比较。这些评估是在三个公开的真实世界网络数据集上进行的。下节描述了所用数据集。所有实验都是在Windows环境下使用Python软件进行的机器设置为英特尔（R）酷睿（TM）i5- 8250 U CPU@1.6 GHz，具有8 GBRAM。5.1. 数据集使用三个真实世界的社交网络数据集进行了实验所有正在考虑的数据集都是有向时间网络，其中包含交互的方向以及指示交互时间的时间戳。关于节点的数量和边的数量，已经使用了具有不同大小（大的和小的）的所用数据集的详情如下：UC Irvine消息-包括在加州大学欧文分校的OSN上的学生之间交换的消息的它有1，899个节点，20，296条静态边和59，835条时间边。每条边表示两个节点之间的交互。它包含从2004年4月15日到2004年 10 月 26 日 的 193 天 期 间 交 换 的 信 息 。 数 据 以 文 本 格 式提 供（Panzarasa等人， 2009年）。Math Overflow数据集包含24，818个节点，2，39，978个静态边和5，06，550个时间边。该数据集包含2009年9月29日至2016年3月6日的2350天数据。数据以文本格式提供（Paranjape等人， 2017年）。Linux内核邮件列表--一个数据集中共有63，399个节点，具有242，976条静态边和1，096，440条已存储2922天的数据，从2006年1月1日至2014年1月1日。数据可以TSV格式获得（Kunegis等人，2017年）。上述数据集具有不同的时间跨度，因为已经在每个数据集上独立地比较了所提出的工作的性能。然而，当比较所提出的HAC-Rank与其他三种现有的种子选择算法的性能时，已经考虑了相同的时间跨度进行比较。此外，当比较所提出的HBIM模型与IC模型时，再次使用相同的时间跨度来比较两个模型的性能。每个数据集被分为两部分，第一部分用于生成活动时间序列和计算第二部分是种子节点的识别和影响力传播的研究。在UC Irvine数据集的情况下，最初的100天用于生成用户的活动时间序列，剩余的天数用于研究影响最大化。对于数学溢出数据集，使用初始4年数据，对于Linux内核数据集，使用初始5年数据生成活动时间序列为用户5.2. HAC-Rank算法所提出的HAC-Rank算法的性能已经通过与以下三种种子选择算法的比较进行了评估：度-一种启发式方案，选择具有最高度的k个节点作为种子节点（Kempe等人， 2003年）。SingleDiscount-一种简单的度折扣启发式方案，其中所选节点的每个非活动邻居的度被折扣1（Chen等人， 2009年）。DegreeDiscountIC-一种启发式方案，其中种子节点的不活动邻居的程度基于邻居节点的程度以及已经被选择为种子节点的其邻居的数量来打折（Chen等人， 2009年）。利用IC模型研究了HAC-Rank算法识别的种子节点的影响扩散，以及利用上述现有算法识别的种子节点的