基于重叠社团检测的社交影响力最大化多目标方法研究
发布时间：2021-11-08 02:38
近年来,社交网络分析成为人们研究的热点,通过社交网络分析,可以挖掘隐藏在网络中的重要信息,其中在社交网络分析中的一个研究热点就是社交影响力最大化问题。然而在这个研究领域中,大部分学者仅仅关注于影响力最大化,而忽视了被影响群体的多样性,而在实际营销中,商家更倾向于选择多样化的目标受众以推广新产品。除此之外,大部分学者在研究社交影响力最大化问题时忽视了节点成本的重要性,对于市场营销而言,在期望获得影响力最大化的同时营销的成本可以最小化。为了解决上述两个重要问题,本文将研究基于重叠社团检测的社交影响力最大化的多目标方法。之所以采用重叠社团检测技术,是因为重叠社团中的重叠点起着“桥梁”的作用,可以使得信息在不同的社团之间传播,因此被影响的节点的分布会更加多样化;同时,利用重叠社团结构信息可以挖掘网络中性价比（影响力/成本）高的节点,为用户提供影响力大成本小的种子节点。因此,本文在社交影响力最大化问题上分别考虑节点多样性和成本,提出了基于重叠社团检测的多样性影响力最大化进化算法和基于重叠社团检测的成本最小化影响力最大化进化算法。本文的主要研究工作如下:（1）本文提出了基于重叠社团检测的多样性影响...
【文章来源】：安徽大学安徽省 211工程院校
【文章页数】：61 页
【学位级别】：硕士
【部分图文】：
在线社交网络示例图
第二章相关工作与理论基础102.2.2线性阈值模型线性阈值模型（LinearThresholdModel）简称LT模型，它是基于随机扩散的一种模型，设定网络中每个节点都有一个激活的阈值∈[0,1]，表示节点被激活的临界值。节点的邻居节点()对该节点的影响力满足以下公式：∑≤1∈(),(2.2)与IC模型不同的是，线性阈值模型假定多个节点对同一个节点的影响力是可以累加的，当节点的影响力累加值大于它的阈值，即∑≥∈()此节点就会被激活，一直重复这个过程直到网络中没有新的激活节点产生。2.3重叠社团检测的相关理论社团结构，即将网络中的节点被划分为若干个不同的集合，同时每个集合内部节点之间的连边相对紧密，而不同集合节点之间的连边相对稀疏[40]。例如，在社交网络中，具有相似爱好的人形成一个社团；在蛋白质网络中，不同类别的蛋白质形成各个功能模块；在科学家合作网络中，不同的研究领域形成不同的社团。类似地，重叠社团中的节点可能属于一个社团，也可能属于多个社团，属于多个社团的节点被称为重叠点。下面给出重叠社团[41]的详细定义：定义2.2（重叠社团）：定义一个无向无权的网络(,)，把网络分成={1,2,...,}，共个社团，对于任意(1≤≤)满足≠且存在≠，(1≤≤,1≤≤,≠)，=1=。即网络中的节点可以属于多个社团。图2.1重叠社团结构示例Fig.2.1Exampleofoverlappingcommunitystructure图2.1中，可以看出有两个社团1={1,2,3,4}，2={4,5,6,7}，其中节点4属于在两个社团中。因此节点4是重叠点，则1和2是重叠社团。本文采用经典的重叠社团检测算法SLPA（Speaker-listenerLabelPropagation
第二章相关工作与理论基础12定义2.6（Pareto前沿面）：Pareto前沿面即PaS中所有Pareto最优解在目标空间上的映射，记为={F()|∈}。本文采用经典的多目标进化算法NSGA-II[49]为框架，下面将对该算法做出相关介绍。通常利用进化算法求解多目标优化问题，多目标进化算法是通过模拟生物在自然界的进化过程而形成的搜索方法，其中NSGA-II是多目标进化算法中经典的算法之一。NSGA-II算法是在NSGA算法[50]基础上的改进版本。NSGA采用非支配排序方法，可以使好的个体有更大的机会保留到下一代，同时提出适应度共享策略，使Pareto前沿面上的个体分布均匀，确保群体的多样性，防止过早收敛。但是NSGA算法中非支配排序时间复杂度较高，为（3）（m是目标数量，N是种群大小）。2002年Deb等人提出了NSGA-II，为了降低时间复杂度，首先提出了快速非支配排序方法，将时间复杂度降低到（2），大大地缩短了搜索时间。除此之外，NSGA-II引入精英保留策略，将父代和子代种群中非支配的个体保留下来，从而保证了种群的质量。最后，利用拥挤距离选择算子来保证种群的多样性。由于NSGA-II中巧妙的策略，该算法比NSGA有更高的计算效率，并且NSGA-II也已成为对比算法中的基准算法。多目标进化算法一般分为以下部分，如图2.2所示。首先，初始化种群，即产生一个初始的种群；然后，利用交叉变异操作产生子代。最后，利用环境选择机制，在父代和子代种群中选择生成下一代种群。图2.2多目标进化算法流程示例Fig.2.2Theflowchartofmulti-objectiveevolutionaryalgorithm
【参考文献】：
期刊论文
[1]交易型社区的病毒式营销策略:基于社会影响、同质性和网络拓扑结构的ABMS仿真研究[J]. 肖邦明,黄敏学. 营销科学学报. 2015(01)
[2]社交网络影响力研究综述[J]. 丁兆云,贾焰,周斌,唐府. 计算机科学. 2014(01)
[3]多目标进化算法综述[J]. 张福威,李军,孟品超,姜志侠,李延忠. 长春理工大学学报(自然科学版). 2012(03)
硕士论文
[1]群集智能优化算法的研究[D]. 王冬梅.武汉科技大学 2004
本文编号：3482837
【文章来源】：安徽大学安徽省 211工程院校
【文章页数】：61 页
【学位级别】：硕士
【部分图文】：
在线社交网络示例图
第二章相关工作与理论基础102.2.2线性阈值模型线性阈值模型（LinearThresholdModel）简称LT模型，它是基于随机扩散的一种模型，设定网络中每个节点都有一个激活的阈值∈[0,1]，表示节点被激活的临界值。节点的邻居节点()对该节点的影响力满足以下公式：∑≤1∈(),(2.2)与IC模型不同的是，线性阈值模型假定多个节点对同一个节点的影响力是可以累加的，当节点的影响力累加值大于它的阈值，即∑≥∈()此节点就会被激活，一直重复这个过程直到网络中没有新的激活节点产生。2.3重叠社团检测的相关理论社团结构，即将网络中的节点被划分为若干个不同的集合，同时每个集合内部节点之间的连边相对紧密，而不同集合节点之间的连边相对稀疏[40]。例如，在社交网络中，具有相似爱好的人形成一个社团；在蛋白质网络中，不同类别的蛋白质形成各个功能模块；在科学家合作网络中，不同的研究领域形成不同的社团。类似地，重叠社团中的节点可能属于一个社团，也可能属于多个社团，属于多个社团的节点被称为重叠点。下面给出重叠社团[41]的详细定义：定义2.2（重叠社团）：定义一个无向无权的网络(,)，把网络分成={1,2,...,}，共个社团，对于任意(1≤≤)满足≠且存在≠，(1≤≤,1≤≤,≠)，=1=。即网络中的节点可以属于多个社团。图2.1重叠社团结构示例Fig.2.1Exampleofoverlappingcommunitystructure图2.1中，可以看出有两个社团1={1,2,3,4}，2={4,5,6,7}，其中节点4属于在两个社团中。因此节点4是重叠点，则1和2是重叠社团。本文采用经典的重叠社团检测算法SLPA（Speaker-listenerLabelPropagation
第二章相关工作与理论基础12定义2.6（Pareto前沿面）：Pareto前沿面即PaS中所有Pareto最优解在目标空间上的映射，记为={F()|∈}。本文采用经典的多目标进化算法NSGA-II[49]为框架，下面将对该算法做出相关介绍。通常利用进化算法求解多目标优化问题，多目标进化算法是通过模拟生物在自然界的进化过程而形成的搜索方法，其中NSGA-II是多目标进化算法中经典的算法之一。NSGA-II算法是在NSGA算法[50]基础上的改进版本。NSGA采用非支配排序方法，可以使好的个体有更大的机会保留到下一代，同时提出适应度共享策略，使Pareto前沿面上的个体分布均匀，确保群体的多样性，防止过早收敛。但是NSGA算法中非支配排序时间复杂度较高，为（3）（m是目标数量，N是种群大小）。2002年Deb等人提出了NSGA-II，为了降低时间复杂度，首先提出了快速非支配排序方法，将时间复杂度降低到（2），大大地缩短了搜索时间。除此之外，NSGA-II引入精英保留策略，将父代和子代种群中非支配的个体保留下来，从而保证了种群的质量。最后，利用拥挤距离选择算子来保证种群的多样性。由于NSGA-II中巧妙的策略，该算法比NSGA有更高的计算效率，并且NSGA-II也已成为对比算法中的基准算法。多目标进化算法一般分为以下部分，如图2.2所示。首先，初始化种群，即产生一个初始的种群；然后，利用交叉变异操作产生子代。最后，利用环境选择机制，在父代和子代种群中选择生成下一代种群。图2.2多目标进化算法流程示例Fig.2.2Theflowchartofmulti-objectiveevolutionaryalgorithm
【参考文献】：
期刊论文
[1]交易型社区的病毒式营销策略:基于社会影响、同质性和网络拓扑结构的ABMS仿真研究[J]. 肖邦明,黄敏学. 营销科学学报. 2015(01)
[2]社交网络影响力研究综述[J]. 丁兆云,贾焰,周斌,唐府. 计算机科学. 2014(01)
[3]多目标进化算法综述[J]. 张福威,李军,孟品超,姜志侠,李延忠. 长春理工大学学报(自然科学版). 2012(03)
硕士论文
[1]群集智能优化算法的研究[D]. 王冬梅.武汉科技大学 2004
本文编号：3482837
本文链接：https://www.wllwen.com/shoufeilunwen/benkebiyelunwen/3482837.html
