基于社区与结构熵的异质网络影响力最大化

影响力最大化的目的是在网络中发现能够触发最大数量的剩余节点参与到信息传播过程的一小群节点.目前异质信息网络中影响力最大化的研究通常从网络中抽取同质子图、或基于节点局部结构的元路径进行节点影响力的评估,没有考虑节点的全局特征和网络中高影响力节点间的集群现象给种子集合最终扩散范围造成的影响损失.文中提出了一种基于社区与结构熵的异质信息网络影响力最大化算法,该算法能够有效地从局部和全局两个方面度量节点的影响.首先,通过构建元结构保留节点在网络中的局部结构信息和异质信息度量节点的局部影响;其次,利用节点所属社区在整个网络中的权重占比对节点的全局影响进行度量;最后,综合求出节点的最终影响并选出种子集合.在真实数据集上进行的大量实验结果表明所提算法有较好的有效性和效率.     

基于社区发现的社交网络影响力阻断最大化算法北大核心CSCD

随着社交网络的日益普及,社交网络已经成为信息传播的主要平台之一。由于对社交网络内容监管相对困难,导致一些负面信息容易快速扩散并产生较大的不良影响。影响力阻断最大化问题旨在寻找需要采用正影响的节点集,使信息传播过程中被负向消息影响的节点数量最小化。针对现有社交网络影响力阻断算法运行时间复杂度较高的问题,文章提出了基于社区发现的影响力阻断最大化算法,该算法首先使用社交网络节点的扩展h指数中心性来选择候选种子节点;然后以这些种子节点为起点,利用标签传播算法发现社交网络中的社区;接着通过计算社交网络社区的关系矩阵及当前关系矩阵的模块度对社区进行合并;最后,计算初始种子节点的标签度量等级,选取前k个节点作为具有最大阻断影响力的成员。实验结果表明,该算法阻断性能好,且时间复杂度低。     

融合节点覆盖范围和结构洞的影响力最大化算法

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

基于熵权TOPSIS的社会网络影响力最大化研究

在影响力最大化问题中,针对启发式方法精度不足和贪婪方法时间过载的问题,提出一种基于多属性决策方法的影响力最大化算法.首先,从社会网络节点的影响传播、节点之间的影响重叠和节点的信任度角度选取节点的重要性评价指标.然后,建立基于熵权TOPSIS的社会网络节点重要性评价模型,通过模型选择影响范围最广、与当前种子集的重叠最小且信任度最高的节点.最后,构建算法,并通过实验验证算法的性能.实验结果表明,与传统影响力最大化算法相比,所提算法在传播范围与时间效率上取得了较好的折中.     

社会网络中基于社群衰减的影响力最大化算法

针对现有网络传播模型忽略了信息传播过程中的信息衰减,传统影响力最大化算法无法有效利用社群结构提高影响力传播范围的问题,提出一种基于社群结构的影响力最大化算法--社群衰减的影响力最大化（IMID）算法。首先对整个社会网络进行社群结构划分,评估社群中节点影响力范围,并考虑社群之间关联点之间的关联概率,在信息传播过程中增加节点之间信息传播衰减度计算。通过实验与分析,该算法不仅降低了时间复杂度,还获得了接近贪心算法的影响力传播范围,影响覆盖率达到90%以上。因此,在核心种子节点集和连接社群之间纽带节点选取若干节点作为初始节点,会让信息以最小的代价在网络中获得广泛传播。     

基于微博网络的影响力最大化算法

由于影响范围的重叠效应,单纯的影响力度量算法并不能解决微博网络中的影响力最大化问题,针对这一研究现状,提出一种用于微博网络中Top-K节点挖掘的算法GABE。通过归纳决定微博用户影响力的关键因素,提出了节点间影响率的概念,进而建立了用于用户影响力度量的WIR算法;根据得到的WIR值提出了符合微博特性的影响力传播模型,运用贪婪算法挖掘出微博网络中的Top-K节点。以爬取到的新浪微博数据进行了模拟验证,结果发现GABE在影响范围上与传统的最大化算法和影响力度量算法相比分别提高了7.7%和20%。这表明通过引入微博特性和贪婪思想,GABE较好地解决了微博网络中的影响力最大化问题。     

基于渗流模型的影响力最大化算法

多数社交网络影响力最大化算法的研究只关注于所选种子节点集合的影响力是否最优,忽略网络自身传播影响力的固有能力。本文对网络进行渗流模拟,计算渗流后网络的主连通分量随着传播概率改变的趋势,并且求得主连通分量大小增加开始变快的相变点,从而计算网络自身传播影响力的固有能力。通过相变值与种子节点集合大小的换算,求得当前网络最佳的种子节点集合大小。将种子节点集合大小限制在最佳大小范围内即可获得最佳的影响力。在kareteclub、football、highschool和socdolphins社交网络数据集上进行实验,验证了该方法的有效性。     

基于种子候选的贪心策略影响力最大化算法

爬山贪心算法的时间复杂度较高,不易扩展至大规模社会网络.为了解决此问题,文中从理论上分析节点集影响力评估可转化为局部概率解计算,能够提高算法运行效率.将局部概率解函数拓展到贪心算法中,提出基于种子候选的贪心影响力最大化算法和基于种子候选的偷懒贪心影响力最大化算法.在4个真实数据集上实验表明,文中算法与具有成本效益的惰性前向选择算法(CELF)性能一致,但在运行时间上快于CELF.     

异质信息网络中基于有向无环图的影响力最大化算法

针对异质信息网络中的影响力最大化(IM)问题,提出了一种基于有向无环图(DAG)的影响力最大化算法(DAGIM).首先基于DAG结构度量节点的影响力,然后采用边际增益策略选择影响力最大的节点.DAG结构表达力强,不仅描述了不同类型节点之间的显性关系,也刻画了节点之间的隐性关系,较完整地保留了网络的异质信息.在三个真实数...     

基于Node2Vec的重叠社区发现算法

针对目前基于种子节点选择的社区发现算法在准确性和复杂度等方面存在的不足, 提出了一种基于Node2Vec的重叠社区发现算法. 首先, 使用Node2Vec算法学习到网络中每个节点的向量表示, 用以计算节点间的相似度, 其次, 利用节点影响力函数计算节点影响力并找出种子节点, 然后基于每个种子节点进行社区的扩展优化, 最终挖掘出高质量的重叠社区结构. 本文选取多个真实网络进行了对比实验, 结果表明, 本文所提出的算法能够在保证良好稳定性的前提下发现高质量的社区结构.     

基于计数排序的最小种子集贪心算法

网络最小种子集问题与网络影响最大化问题相关,研究的是对于具有节点阈值的网络,构造网络的最小节点子集,使得如果这个子集中的节点是活的,则在给定的影响传播模型下整个网络都受到影响。为此提出了新的贪心算法,以节点的度与阈值的差为关键值对网络节点进行计数排序,然后取值最小的节点进行处理。新算法在时间复杂度上改进了基于最小堆的种子点选取算法。在简单多数阈值模型上针对经典的无标度网络得到了所构造的种子集规模上界。实验在随机生成网络和一些实际网络数据集上进行,结果表明所提方法的有效性,特别在无标度网络上生成的种子集具有比相关算法更小的规模。     

成本控制下的快速影响最大化算法

针对成本控制下影响最大化时间复杂度高的问题,提出一种快速的最大化算法BCIM。首先提出对初始节点进行多次传播的传播模型;其次选择高影响力节点作为备用种子,并基于近距离影响减少计算节点影响范围的工作量;最后利用动态规划方法在每组备用种子中最多选择一个种子。仿真实验表明,与随机算法Random、每轮取影响力增量最大的节点的贪心算法Greedy_MII、每轮取影响力增量与成本比值最大的节点的贪心算法Greedy_MICR相比,在影响范围上,BICM接近或优于Greedy_MICR及Greedy_MII,远次于Random;在种子集合的质量上,BCIM、Greedy_MICR、Greedy_MII三者差距较小,但都远远好于Random;在运行时间上,BCIM是Random的几倍,而两个贪心算法都是BCIM的几百倍。BCIM算法能在较短时间内找到更有效的种子集合。     

移动社会网络中基于全局信任模型的用户影响力计算

针对现有算法和模型对于网络中用户影响力计算大多只考虑拓扑结构和贪心算法而较少考虑真实社会网络中信任度对于节点影响力的重要性这一问题, 该文提出一种全局信任模型(global trust model, GTM)用于评估节点的影响力. 首先计算节点与邻居节点间的信任关系作为局部信任度, 其次利用Beta信誉模型在节点局部信...     

异质信息网络中基于网络嵌入的影响力最大化

针对当前大部分影响力最大化算法忽略了异质信息网络包含多种节点类型和多种关系类型,且不同类型节点在原始空间无法直接度量的问题,提出了一种异质信息网络中基于网络嵌入的影响力最大化模型（influence maximization based on network embedding,IMNE）,用于选择初始扩散节点实现影响力最大化。该模型不仅可以在对异质信息网络进行编码的同时表征异质信息网络中潜在的信息,还可以捕获不同类型节点间影响力的不确定和复杂性。在3个真实数据集上的实验验证了IMNE算法的有效性。     

基于LT+模型的社交网络影响力最大化研究

影响力最大化问题的目标是寻找社交网络中一组种子结点集合,在给定的传播模型下,使得这些结点最终传播的影响范围最大。Kempe和Kleinberg提出的贪心算法可以获得很好的影响范围,但是因复杂度太高而并不适用于大型社交网络。Chen和Yuan等人基于线性阈值(LT)模型提出了构造局部有向无环图的启发式算法,但是LT模型只考虑了邻居结点的直接影响力,忽略了结点之间存在的间接影响力。因此,在LT模型的基础上,结合网络中结点之间存在的间接影响力,提出了LT⁺影响力模型,并利用构造局部有向无环图的启发式算法求解LT⁺模型的影响力最大化,称为LT⁺DAG算法。真实数据集上的对比实验表明,LT⁺DAG算法具有更好的影响范围以及较好的可扩展性。     

利用网络表征学习辨识复杂网络节点影响力

发现复杂网络中最具影响力的节点,有助于分析和控制网络中的信息传播,具有重要的理论意义和实用价值.传统的确定节点影响力的方法大多基于网络的邻接矩阵、拓扑结构等,普遍存在数据维度高和数据稀疏的问题,基于网络表征学习,本文提出了一种局部中心性指标来辨识网络中高影响节点(NLC),首先采用DeepWalk算法,把高维网络中的节点映射为一个低维空间的向量表示,并计算局部节点对之间的欧氏距离;接着根据网络的拓扑结构,计算每个节点在信息的传播过程中,对所在局部的影响力大小,用以识别高影响力节点.在八个真实网络中,以SIR和SI传播模型作为评价手段,将NLC算法和度中心性、接近中心性、介数中心性、邻居核中心性、半局部中心性做了对比,结果表明NLC算法具有良好的识别高影响力传播节点的性能.