影响力最大化

摘要： 影响力最大化是社交网络分析中的一个重要问题,旨在挖掘可以使得信息在网络中传播范围最大化的一小组节点(通常称为种子节点)。基于网络拓扑结构的启发式影响力最大化算法通常仅考虑某单一的网络中心性,没有综合考虑节点特性和网络拓扑结构,导致其效果受网络结构的影响较大。为了解决上述问题,提出了一种融合覆盖范围和结构洞的影响力最大化算法NCSH。该算法首先计算所有节点的覆盖范围和网格约束系数;然后通过覆盖范围增益最大原则选择种子节点;其次,若存在多个节点增益相同,则按照网格约束系数最小原则选取;最后,重复上述步骤直至选出所有种子节点。NCSH在不同种子数量和不同传播概率条件下,在六个真实网络数据集上均保持着优异的效果,在影响力传播范围方面,比同类的基于节点覆盖范围的算法(NCA)平均提高了3.8%;在时间消耗方面,比同类的基于结构洞和度折扣的最大化算法(SHDD)减少了43%。实验结果表明,NCSH能有效解决影响力最大化问题。

摘要： 影响力最大化IM问题旨在查找社交网络中的一组用户,通过这些用户,使信息在网络中传播的范围最大化。现有研究主要关注静态网络中的IM问题,然而在现实生活中,社交网络是不断演化的,基于静态网络的传播模型(如独立级联模型、线性阈值模型)无法适用于演化网络中的信息传播过程。同时,现有研究忽略了用户行为对信息传播的影响。因此,针对该问题,提出了一种用户行为驱动的独立级联BDIC传播模型,该模型主要根据用户行为对信息的传播过程进行建模,可有效刻画演化社交网络中的信息传播过程。在该模型的基础上,提出了用户行为驱动的影响力最大化算法,主要包括3个步骤:首先,建模消息传播过程,计算演化社交网络中的信息传播概率;然后,提出一种用户行为驱动的反向影响力采样方法,有效查询单个时间点下的种子用户;最后,设计一种不同时间节点(时间序列)下的种子节点查询方法,有效反映演化社交网络中种子节点动态变化的特性。为了评估所提算法的有效性,设计了种子节点与受影响节点的相似度对比方法。通过大量真实数据集上的实验,验证了信息传播概率算法的高效性和扩展性,证明了相比普通的独立级联模型,BDIC模型能更好地建模演化社交网络中的信息传播过程。

摘要： 在社交网络的发展过程中,影响力最大化问题得到学术界和产业界的普遍关注,在政务发布、信息扩散、市场营销等场景中得到了广泛应用,在理论研究和实际应用中得到了系统探讨.研究者们最初从拓扑结构入手,随后在计算最优解的贪心算法的逐渐优化中取得了一系列的研究成果;还有研究者从启发式算法入手,不断在提升算法可扩展性和维持传播稳定性之间进行改进.通过对相关研究方法进行分类梳理,对影响力最大化问题的未来深化领域进行了展望.

摘要： 针对异质信息网络中的影响力最大化(IM)问题,提出了一种基于有向无环图(DAG)的影响力最大化算法(DAGIM)。首先基于DAG结构度量节点的影响力,然后采用边际增益策略选择影响力最大的节点。DAG结构表达力强,不仅描述了不同类型节点之间的显性关系,也刻画了节点之间的隐性关系,较完整地保留了网络的异质信息。在三个真实数据集上的实验结果验证所提DAGIM的性能优于Degree、PageRank、局部有向无环图(LDAG)以及基于元路径的信息熵(MPIE)算法。

摘要： 随着5G的发展,网络传播以前所未有的速度向各领域渗透.其中,影响力分析是研究网络信息传播机制的关键技术.传统的影响力分析算法主要通过选取具有最大传播特性的种子节点用于网络传播.但在种子节点选取上,其度量算法没有反映社交网络中的潜在信息.这将对影响力传播分析造成影响,同时一旦社交网络结构遭到破坏,网络的传播能力将会受到影响.针对这一问题,本文首先定义了一种基于属性的朋友亲密度度量关系,量化网络中各用户的影响力;其次,提出了一种属性和亲密度兼顾的影响力算法,该算法综合考虑了网络的结构、属性和亲密度三者之间的关系,选择出具有高影响力及抗攻击性的种子节点,提高网络传播能力及抗攻击能力;最后,通过真实网络环境下的实验,验证出相比现有的度量算法,本文提出的算法在种子节点数目较大时具有更好的传播特性,并且在隐私高风险状态下的社交网络中,该算法的受攻击影响程度稳定在5%-10%左右,影响程度最低,具有较好的抗攻击性.

摘要： 传统的影响力最大化算法忽视了病毒式营销过程中的商业收益问题.现实营销中,商家更加关注如何使用一个固定预算,在合理的时间内选出种子集,最大化营销收益.为了解决这个问题,提出一种高效的启发式算法.首先,定义边际性价比衡量用户节点的重要性;其次,分析出贪心算法的节点选取结果为一个自洽序列,提出MCPR(Marginal Cost Performance Ranking)算法,迭代逼近一个近似自洽排序,以追求贪心算法的效果;最后,采用性价比向前分配策略估计节点边际性价比,加速算法迭代.在3个真实社会网络上进行大量实验,结果表明MCPR能够取得与贪心算法近似的结果,但算法效率远高于贪心算法.

摘要： 影响力最大化问题是信息网络挖掘中的热门研究问题之一,大多数信息网络包含了多种不同类型的节点和连接边,其本质属于异质信息网络,然而以前关于影响力最大化问题的研究大多停留在同质信息网络,它们考虑的节点和连接边类型单一,这与现实的信息网络有所差别。异质信息网络的影响力最大化问题其关键在于如何识别异质信息网络中最有影响力的节点。为了能融合网络中的异质信息并衡量节点影响力,提出了一种基于加权PageRank的异质信息网络影响力最大化算法。该算法保留了网络中所有类型节点和连接边的信息,通过考虑异质信息网络中不同类型节点之间的影响关系来得到节点的最终影响力,从而实现异质信息网络的影响力最大化。该算法能更好地描述节点和连接边的异质性,并在两个真实的数据集上验证了算法的有效性。

摘要： 影响力最大化问题旨在从社交网络中寻找若干具有高影响力的用户节点(种子),以触发最大化的信息传播规模.目前绝大多数工作认为社交网络中所有用户都拥有相同的影响力推广价值.然而,在基于位置的营销活动中,影响力推广的主体通常为带有位置标签的空间对象,考虑到用户在物理世界中的移动受限问题,空间对象仅能吸引其邻近范围内的潜在用户.因此,为了最大化市场营销潜力,商家通常需要同时拥有多个营销目标,譬如,连锁店企业对旗下的多家门店进行联合推广.不同的推广内容以及不同的影响力种子选择都将对营销推广的效益产生切实的影响.鉴于此,综合考虑商家在营销过程中对推广门店位置的选择以及在线上部署影响力传播种子的策略,在地理社交网络中研究基于多目标组合优化的空间感知影响力联合推广问题.首先分析了问题的理论难度,阐明了其与传统影响力最大化问题的区别.为支持高效且准确的问题求解,根据用户推广权重的差异,拓展了现有反向影响力采样(reverse influence sampling,RIS)技术,对不同位置和种子组合下的影响力传播收益进行理论保证下的上下界评估,并基于此提出了迭代处理算法框架,在多个轮次下实现高置信度保障的近似最优求解.最后,通过多组真实数据集上的实验,证明了所研究问题能在多目标组合下有效地提升空间感知的影响力推广效果,并验证了所提出算法的良好性能.

摘要： 现有影响力最大化算法多数因时间复杂度较高或影响力传播范围有限,不适用于大规模社交网络。基于独立级联模型,结合反向可达集采样提出一种改进的影响力最大化算法D-RIS。在影响力传播函数满足单调性和子模性的前提下,通过自动调试确定反向可达集生成数量的临界值。在Slashdot和Epinions真实数据集上的实验结果表明,D-RIS算法在影响力传播范围上接近CELF算法且优于RIS、HighDegree、LIR和pBmH启发式算法,同时在运行时间上相比CELF算法减少近百倍,具有更好的通用性与稳定性,适用于拓扑结构变化和规模较大的社交网络。

摘要： 用户影响力度量是影响力最大化问题的核心,与网络拓扑结构相关的影响力度量指标主要分为全局性指标和局部性指标,其中全局性指标需要依靠网络完整拓扑结构计算节点影响力且时间复杂度较高,局部性指标通常忽略或弱化了网络中的自环和多边现象,导致对节点影响力的度量不全面,限制信息最终传播范围。结合三度分隔原理,提出基于局部域的影响力最大化算法。考虑网络中的自环和多边现象,根据网络拓扑结构构建生成图。依据生成图划分每个节点对应的局部域,使用节点在局部域内的影响力近似其在全局范围内的影响力,并据此选择候选种子节点。计算候选种子加入种子集合后的重叠比因子,根据重叠比因子决定是否将此候选种子节点选作种子节点,控制种子集合的影响力重叠程度。在真实数据集上的实验结果表明,与MaxDegree、PageRank等算法相比,该算法能有效识别高影响力节点群体,扩大信息传播范围,且具有较低的时间复杂度。

摘要： 影响力最大化是社会化营销的热点研究内容.目前关于影响力最大化的研究通常基于网络拓扑结构的视角,忽视了消费者兴趣、企业成本等因素.本文基于多目标优化的视角,考虑结构影响力、用户兴趣和企业成本等因素,构建影响力最大化的多目标优化模型.为了提高优化效果,本文用经典的影响力最大化算法获得有影响力的节点作为候选种子集,基于改进的线性阈值模型计算种子集合的结构影响力、所影响用户的兴趣度和企业成本,并利用多目标演化算法NSGA-Ⅱ获得多目标影响力最大化的不可支配解集.基于真实社交网络数据的实验表明,所提方法可以为企业提供更加柔性的决策建议.

摘要： 对于社交网络影响力最大化问题,Kemple和Kleinberg提出了有较好影响范围的贪心算法,但是KK算法的复杂度非常高,并不实用.利用线性阈值模型提出了一种基于节点激活阈值的启发式算法.它综合考虑了节点之间的影响力和节点的激活阈值,根据每个节点在激活过程中动态变化的阈值来计算PIN值,启发过程中,每一次都选取PIN最大的节点作为种子节点进行激活,贪心阶段中再贪心地挑选那些具有最大影响范围增量的节点作为种子节点.通过实验表明,即使在完全不采用贪心阶段,该算法的激活范围与KK算法都非常接近,而算法的复杂度则相对非常小.实验还表明该算法相对于HPG算法在相同启发因子c的情况下具有更大的激活范围.

摘要： 当前社交网络平台的发展,吸引了大量的用户群,进而带动了社会化营销的研究工作.影响力最大化是其一个重点研究方向.本文通过考虑扩散规模,用户兴趣值和扩散预算等因素,将影响力最大化模型作为多目标优化问题.多目标影响最大化(MOIM)模型的目的是最大化信息传播规模,尽可能多地传播对信息感兴趣的用户,并以预算约束最小化传播成本.考虑到社交网络的特性,本文利用蒙特卡洛抽样方法获得高影响力用户候选子集,并提出了一种基于分解策略的多目标进化算法(MOEA/D)的优化方法获得满足多目标约束的不可支配解集.利用真实社交网络数据的实验表明,提出的MOIM模型可以生成适当的种子集,为社会化营销提供了灵活高效的决策支持.

摘要： 本发明提供了一种基于局部影响力计算的影响力阻断最大化方法，包括如下步骤：确定负影响范围；构造节点局部影响区域；计算节点局部负激活概率；计算节点阻断负影响；迭代选择阻断负影响最大的节点作为正种子；更新节点的阻断负影响。本发明针对社交网络规模大的特点，提出局部负激活概率近似计算动态规划方法，基于计算的局部负激活概率计算节点阻断负影响，基于阻断负影响选择正面种子，适合于快速选择使负影响阻断最大的正种子群。

摘要： 本发明提供了一种基于局部影响力计算的影响力阻断最大化方法，包括如下步骤：确定负影响范围；构造节点局部影响区域；计算节点局部负激活概率；计算节点阻断负影响；迭代选择阻断负影响最大的节点作为正种子；更新节点的阻断负影响。本发明针对社交网络规模大的特点，提出局部负激活概率近似计算动态规划方法，基于计算的局部负激活概率计算节点阻断负影响，基于阻断负影响选择正面种子，适合于快速选择使负影响阻断最大的正种子群。

摘要： 本申请提供一种考虑群体共识的竞争影响力传播最大化方法及相关设备，可以为社交网络实现更好的影响力传播效果。该方法包括：将从社交网络中选取的K个初始节点进行激活，得到正向节点集合；若目标群体满足群体激活条件，则通过正向影响或竞争影响对目标群体进行激活；若社交网络中存在未激活且不处于已激活群体中的目标节点，且目标节点满足节点激活条件，则通过正向影响或竞争影响对目标节点进行激活；将被正向影响所激活的节点添加至正向节点集合以及被竞争影响所激活的节点添加至竞争节点集合；基于添加节点后的正向节点集合和竞争节点集合对社交网络中未激活的节点进行激活，直至达到终止条件得到正向最终集合。

摘要： 本发明涉及一种网络信息传播影响力度量方法、系统，包括：根据社交网络中消息传播的历史传播数据，构建节点和传播源的激活对；将社交网络中的用户作为节点，将给定消息的传播数据中参与时间为0的节点作为给定消息的传播源，通过聚合函数将传播源对节点的影响力进行聚合后通过影响力边际递减函数，得到节点在传播源下被激活的概率；以历史传播数据为训练数据，以概率的对数似然最大作为目标，对所有激活对使用随机梯度下降进行参数学习，得到节点间影响力，以得到传播源集合的影响力度量。本发明提出的基于数据驱动的影响力最大化方法直接基于本发明学习得到的影响力度量，对节点的边际效应进行估计，以高效地进行影响力最大化的节点集合选择。

摘要： 基于从众心理的超图影响力传播方法及影响力最大化方法，本发明属于用户行为挖掘技术领域，解决图的节点之间只存在二元关系，不能很好的模拟真实世界的特性且会丢失重要信息以及超图上的影响力最大化的问题，本发明使用表达能力更强的超图来建模社会关系网络，在此基础上，提出一种在超图上的影响力传播模型并对现实生活中人们普遍存在的从众心理现象进行建模，使得该传播模型更加符合实际，基于提出的超图上传播模型，解决了图的节点之间只存在二元关系，不能很好的去模拟真实世界的特性，并且会丢失一些重要信息的缺点；采用超度的算法来解决影响力最大化问题，为超图上的影响力最大化问题提供了一种可行的解决方案。

摘要： 基于三度影响力原则的社会网络影响力最大化的方法，涉及社会网络科学领域，尤其涉及一种基于三度影响力原则的社会网络影响力最大化的方法。本发明要解决社会网络影响力实现最大化时，现有方法运行时间短时存在运算精度低的问题，而在保证运算精度时，又存在运行时间超长的问题。本发明按以下步骤进行：一、输入社会网络的节点集合以及节点间的关系集合；二、针对社会网络里的每个节点，计算出节点的一度节点集合；三、针对社会网络里的每个节点，计算出节点的二度节点集合；四、针对社会网络里的每个节点，计算出节点的三度节点集合；五、针对社会网络里的每个节点，计算出节点的线性衰减度中心性值。本发明应用于社会网络科学领域。

摘要： 本发明涉及一种网络信息传播影响力度量方法、系统，包括：根据社交网络中消息传播的历史传播数据，构建节点和传播源的激活对；将社交网络中的用户作为节点，将给定消息的传播数据中参与时间为0的节点作为给定消息的传播源，通过聚合函数将传播源对节点的影响力进行聚合后通过影响力边际递减函数，得到节点在传播源下被激活的概率；以历史传播数据为训练数据，以概率的对数似然最大作为目标，对所有激活对使用随机梯度下降进行参数学习，得到节点间影响力，以得到传播源集合的影响力度量。本发明提出的基于数据驱动的影响力最大化方法直接基于本发明学习得到的影响力度量，对节点的边际效应进行估计，以高效地进行影响力最大化的节点集合选择。

摘要： 本发明涉及独立级联模型下基于最大似然的影响力最大化方法。本发明在复杂网络中确定种子节点，构造基于抽样的缩略图以及顶点分层，计算构造的缩略图中所有顶点的最大似然概率值，对所有的最大似然概率值进行排序，筛选出k个节点。本发明克服了Degree方法在识别有影响力节点方面缺乏准确性，CascadeDiscount方法计算复杂，内存消耗大且运行时间也比较长等缺陷。本发明提出一种构造缩略图的方法从而将复杂网络进行分解，按照条件筛选出包含k个节点的种子节点集合S，避免之前算法中寻找最短路径等其他条件，从而减少了许多不必要的计算，使得预测结果更加的准确，可靠性更高。

摘要： 本发明公开了一种基于局部和全局影响的社交网络影响力最大化方法，属于社交网络领域，本发明提出了一种候选顶点的两阶段过滤策略，此策略首先根据顶点的局部影响力选择一定数目源顶点；然后，寻找源顶点的祖先顶点，并根据祖先顶点对源顶点的预期影响筛选一定数目候选顶点；最后，本发明利用候选顶点对源顶点的预期影响的边际收益从两阶段过滤策略选择出的候选顶点中选择种子顶点。通过本发明方法，不仅克服了时间效率低的问题，而且提高了影响范围的准确性，有效地解决了社交网络影响力最大化问题。

摘要： 本发明提供一种社交网络影响力最大化节点识别方法及系统，包括：对于给定的社交网络，根据每个节点的三元闭包结构数量，计算每个节点的三元闭包加权度值；根据每个节点的所有邻居节点的所述三元闭包加权度值，计算每个节点的加权影响力期望值；基于每个节点的所述加权影响力期望值降序排列所有节点；根据降序排列的加权影响力期望值，进行影响力最大化节点识别。本发明解决了在社交网络影响力最大化节点识别过程中，更新节点影响力期望值的现有方法时间复杂度过高，以及影响力最大化节点选取方法过于局部化，识别结果不够准确的问题。