在线社交网络中面向目标用户的最小节点问题
发布时间：2021-10-08 23:04
随着在线社交网络的蓬勃发展,通过大数据分析用户的行为属性,面向目标用户建立相应标签的精准营销和个性化推荐越来越具有应用价值。本文主要围绕面向目标用户的最小节点问题进行研究。本文采用用户画像区分目标用户与非目标用户,首先针对单一传播环境下面向目标用户的最小节点问题（NLC-TU）展开研究。NLC-TU问题旨在寻求最小的初始种子节点集,使得初始种子节点集的信息传播范围可以覆盖目标用户群体中预期数量的用户。考虑社交网络中节点传播能力的不同,本文提出了受限传播模型（LD-IC）,证明了在该模型下NLC-TU问题是NP-hard问题,并且NLC-TU问题的信息传播函数在LD-IC模型下具有单调性和子模性。本文提出贪心算法来解决这个问题并且分析了贪心算法的精度保证。然而贪心算法耗时长,难以应用于大型社交网络。考虑到在LD-IC模型下节点的局部影响力可以近似表示全局影响力,面向目标节点的局部影响力启发式算法（TU-LIH）被提出。在四个真实社交网络上的实验证明了我们提出的算法高效且具有可拓展性。随后,考虑现实网络中信息传播的复杂性,本文在NLC-TU问题的基础上针对竞争环境下面向目标用户的最小节点问...
【文章来源】：上海交通大学上海市 211工程院校 985工程院校 教育部直属院校
【文章页数】：69 页
【学位级别】：硕士
【部分图文】：
在线社交网络抽象成拓扑图
上海交通大学硕士学位论文-10-图2-2用户画像来源Fig.2-2userprofile2.3单一传播环境下最小节点问题的研究病毒式营销中的影响力最大化问题最先受到研究者的关注。Kempe等人[7]总结了影响力传播的经典模型独立级联模型，在这种模型下影响力最大化问题是NP-hard问题可用贪心算法求解，并且贪心算法可提供(11e)的精度保证。此后在影响力最大化问题的基础上，又衍生了最小节点问题。Long,Cheng[4]首次提出了J-MIN-Seed问题，并证明它在IC传播模型下是NP-hard问题，可用贪心算法求解。最小节点问题本质上是影响力最大化的对偶问题，因此很多影响力最小化问题的性质得以在最小节点的问题中沿用。此后，一部分研究者致力于研究更普遍场景下的最小节点问题，Goyal[5]提出了影响力传播的最小时间和最小预算问题，针对不同的传播时间限制和预算限制控制变量分别进行了研究。Zhang,Peng[6]引入了概率P，研究了以概率P覆盖一定范围的最小节点问题，更加贴近现实情况。Kai等人[32]研究了在线社交网络中的最小成本种子选择问题，其目标是选择一组总成本最小的种子节点，使网络中受影响节点的预期数量超过预定义的阈值，根据传染模型提出了双准则近似算法。上述研究从初始用户选择出发研究了最小的代价问题，将所有用户无差别的看待。近年来随着大数据的兴起，研究者开始
上海交通大学硕士学位论文-15-速传播，而粉丝数不多的普通账号发布的信息往往没有获得关注[41]。因此我们考虑信息在社交网络中用户传播能力的不同，提出受限传播模型（limited-diffusion-IC，LD-IC）。在LD-IC模型中，信息不会无限的传播下去，种子节点的影响只能传播有限的深度。给定社交网络G，其中每一条边(,)∈E都有个激活概率(,)，此时是的入度邻居，是的出度邻居。信息从节点1出发传递到节点可能存在多种传播路径。对于一个信息传播路径P=(1→2→→1→)，我们定义这条信息传播路径的传播概率是Pa()：Pa(P)=∏p(ui,ui+1)m1i=1(3-1)式中(ui,ui+1)——节点ui被激活后，节点ui通过边(ui,ui+1)激活ui+1的概率。路径越长，节点越多，则信息从u1传递到um的概率Pa(P)越小，因此我们引入阈值θ，θ代表了路径最小传播概率，一旦Pa(P)<θ时信息传播终止，即Pa(P)=∏p(ui,ui+1)m1i=1≥θ时信息才会从节点u1沿路径P传播到节点um。图3-1IC模型和LD-IC模型的不同Fig.3-1DifferenceofinformationpropagationbetweentheICandtheLD-IC如图3-1所示。图中黑色的点代表被激活后处于活跃状态，白色的点代表还没有被激活处于非活跃态，每条边都有一个激活概率。在IC模型中信息传播不受
【参考文献】：
期刊论文
[1]社交网络影响力传播研究[J]. 陈卫. 大数据. 2015(03)
本文编号：3425144
【文章来源】：上海交通大学上海市 211工程院校 985工程院校 教育部直属院校
【文章页数】：69 页
【学位级别】：硕士
【部分图文】：
在线社交网络抽象成拓扑图
上海交通大学硕士学位论文-10-图2-2用户画像来源Fig.2-2userprofile2.3单一传播环境下最小节点问题的研究病毒式营销中的影响力最大化问题最先受到研究者的关注。Kempe等人[7]总结了影响力传播的经典模型独立级联模型，在这种模型下影响力最大化问题是NP-hard问题可用贪心算法求解，并且贪心算法可提供(11e)的精度保证。此后在影响力最大化问题的基础上，又衍生了最小节点问题。Long,Cheng[4]首次提出了J-MIN-Seed问题，并证明它在IC传播模型下是NP-hard问题，可用贪心算法求解。最小节点问题本质上是影响力最大化的对偶问题，因此很多影响力最小化问题的性质得以在最小节点的问题中沿用。此后，一部分研究者致力于研究更普遍场景下的最小节点问题，Goyal[5]提出了影响力传播的最小时间和最小预算问题，针对不同的传播时间限制和预算限制控制变量分别进行了研究。Zhang,Peng[6]引入了概率P，研究了以概率P覆盖一定范围的最小节点问题，更加贴近现实情况。Kai等人[32]研究了在线社交网络中的最小成本种子选择问题，其目标是选择一组总成本最小的种子节点，使网络中受影响节点的预期数量超过预定义的阈值，根据传染模型提出了双准则近似算法。上述研究从初始用户选择出发研究了最小的代价问题，将所有用户无差别的看待。近年来随着大数据的兴起，研究者开始
上海交通大学硕士学位论文-15-速传播，而粉丝数不多的普通账号发布的信息往往没有获得关注[41]。因此我们考虑信息在社交网络中用户传播能力的不同，提出受限传播模型（limited-diffusion-IC，LD-IC）。在LD-IC模型中，信息不会无限的传播下去，种子节点的影响只能传播有限的深度。给定社交网络G，其中每一条边(,)∈E都有个激活概率(,)，此时是的入度邻居，是的出度邻居。信息从节点1出发传递到节点可能存在多种传播路径。对于一个信息传播路径P=(1→2→→1→)，我们定义这条信息传播路径的传播概率是Pa()：Pa(P)=∏p(ui,ui+1)m1i=1(3-1)式中(ui,ui+1)——节点ui被激活后，节点ui通过边(ui,ui+1)激活ui+1的概率。路径越长，节点越多，则信息从u1传递到um的概率Pa(P)越小，因此我们引入阈值θ，θ代表了路径最小传播概率，一旦Pa(P)<θ时信息传播终止，即Pa(P)=∏p(ui,ui+1)m1i=1≥θ时信息才会从节点u1沿路径P传播到节点um。图3-1IC模型和LD-IC模型的不同Fig.3-1DifferenceofinformationpropagationbetweentheICandtheLD-IC如图3-1所示。图中黑色的点代表被激活后处于活跃状态，白色的点代表还没有被激活处于非活跃态，每条边都有一个激活概率。在IC模型中信息传播不受
【参考文献】：
期刊论文
[1]社交网络影响力传播研究[J]. 陈卫. 大数据. 2015(03)
本文编号：3425144
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/3425144.html
