社交网络中基于模块度最大化的标签传播算法的研究

社交网络影响力最大化研究综述社交网络影响力最大化研究综述摘要近年来，随着互联网的发展，社交网络得到飞速的发展并且得到人们越来越多的关注。

许多研究工作致力于社交网络的分析，社交网络中的影响力传播问题的研究具有很实际的现实意义，它在市场营销、广告发布、舆情预警以及社会安定等方面有十分重要的应用。

因此，本文对社交网络影响力最大化问题的定义、传播模型和算法的研究现状进行了调研分析，希望对社交网络影响力最大化问题有一个整体的认识。

关键词社交网络；影响力；传播模型；病毒式营销1引言近年来，随着互联网和个人电脑的普及，Facebook、Flikr、Twitter、人人网、新浪微博等社交网络得到迅速发展，社交网络也成为研究的热点。

社交网络分析从19世纪20年代早期开始发展，主要研究社会实体之间的关系，经过几十年多个学科领域的许多学者的努力，社交网络的相关研究也随着可获取的数据量的飞速增长及计算能力的大幅度提高取得了显著的成果，社交网络已经形成了比较完善的研究体系。

社交网络中的网络社区结构问题、重叠社区发现问题、影响力最大化问题、节点聚类问题等。

但社交网络中丰富的数据也给知识发现和数据挖掘领域带来前所未有的挑战和机会。

社交网络[1]是通过网络这一载体把人们连接起来，从而形成具有某一特点的团体，是指由个体及个体之间的关系所组成的一个复杂网络，这种复杂的社会结构对信息的传播和扩散起着至关重要的作用，当一个人采纳一个新的思想或接受一种产品时，他会向他的朋友或同事推荐，某些人可能会接受或采纳他的推荐，并进一步向他们自己的朋友或同事推荐，这个过程称为传播或扩散。

一个人的行为在很大程度上取决于周边的朋友或同事的决定。

社交网络是复杂网络的一种类型，文献[2]中详尽的介绍了复杂网络的相关理论和知识。

社交网络中的影响力最大化问题的研究有着十分重要的现实意义，它在市场营销、广告发布、舆情预警以及社会安定等方面有十分重要的应用。

影响力最大化问题[3, 4]的提出要追溯到对于“病毒式营销”[5-7]和“口碑效应”[8-10]的研究，社交网络影响力最大化问题首次由Domingos和Richardson提出的[3, 4]，影响力最大化问题可概括为：给定一个社交网络图和一种特定的影响力传播模型，给定初始的传播节点个数，如何在网络上确定这些初始的节点集合(这些集合中的节点初始时是被激活的)，然后遵循影响力节点的传播机制，从这些集合中的节点开始传播，使最终被影响的节点数目达到最多，其形式化的表述如下：给定一个社交网络G(V, E)，V为节点集合，E为边的集合，对于给定参数k，k是一个正整数，如何从网络G中选择k个初始节点结合A，满足|A|=k且A?V，按照某种传播策略，由这k个初始的节点开始影响其它节点，并使最终被影响的节点数目达到最大，用如下形式表示：σ=?max{(),||,}A A k A V为集合A最终影响的节点数目。

社交网络分析中的推荐系统算法研究随着互联网和社交媒体的迅速发展，人们的社交行为也从传统的线下活动转移到了线上社交网络平台。

这些社交网络平台积累了大量的用户信息和社交关系，为用户提供了许多新的交流和社交机会。

然而，随着用户数量的增加，社交网络中信息过载的问题也日益凸显。

这就需要推荐系统的帮助来解决用户在海量信息中获取感兴趣内容的问题。

社交网络分析中的推荐系统是指利用社交网络中的用户行为和社交关系信息来为用户推荐合适的内容和社交伙伴。

研究社交网络分析中的推荐系统算法，可以帮助我们更好地理解用户的兴趣以及社交网络中的群体结构和信息传播规律。

社交网络分析中的推荐系统算法可以分为基于内容的推荐和基于社交关系的推荐两种。

基于内容的推荐算法主要通过分析用户对内容的兴趣和评价来推荐相似的内容给用户。

这类算法可以利用文本挖掘和数据挖掘的技术来分析用户的文本历史记录和评价，从而更好地理解用户的兴趣和需求。

基于内容的推荐算法在社交网络分析中可以帮助用户发现新的有趣内容，并且可以通过提取用户兴趣的关键词或特征来进行个性化推荐。

而基于社交关系的推荐算法则主要通过分析用户在社交网络中的社交关系和交互行为来进行推荐。

这类算法可以通过挖掘用户之间的社交关系，比如好友关系、共同兴趣等来推荐适合用户的内容和社交伙伴。

基于社交关系的推荐算法在社交网络分析中可以帮助用户发现和扩大社交圈子，增强用户与其他用户之间的交流和合作。

除了基于内容和社交关系的推荐算法，还有一种常见的推荐算法是基于混合方法的推荐算法。

这类算法结合了基于内容和社交关系的推荐算法的优点，通过综合考虑用户的兴趣、社交关系和历史行为等信息来进行推荐。

基于混合方法的推荐算法在社交网络分析中可以帮助用户更全面地获取感兴趣的内容和社交伙伴。

在社交网络分析中，推荐系统算法研究的一个重要问题是如何准确地捕捉用户的兴趣和需求。

为了解决这个问题，研究者们提出了许多不同的推荐算法和技术。

2017 年软件2017,V〇1.38,No. 5第3 8 卷第 5 期COMPUTER ENGINEERING & SOFTWARE 国际IT 传媒品牌设讨研尧与启用基于用户聚类的社交网络影响力最大化传播模型曾燕清\陈志德2，李翔宇3(1.福建江夏学院，福建福州350108; 2.福建师范大学，福建福州350007)3.闽江师范高等专科学校，福建福州350007)摘要：本文针对的是社交网絡中的影响力最大化问题。

在经典线性阈值传播模型基础上，对社交网絡中的用户进行聚类分析，并在此基础上提出改善的K-L T传播模型。

在K-L T传播模型基础上，进一步提出K-K K影响力最大化算法。

通过采集真实社交网絡数据，进行试验仿真。

试验结果表明，改进的K-K K影响力最大化算法与未改进时相比，算法性能有较好提升。

关键词：社交网絡；传播模型；影响力最大化中图分类号：TP393.09 文献标识码：A D O I:10.3969/j.issn.l003-6970.2017.05.031本文著录格式：曾燕清，陈志德，李翔宇.基于用户聚类的社交网絡影响力最大化传播模型[J].软件，2017, 38 (5): 144-149User Clustering based Social Networks Influence Maximization Propagation ModelZENG Yan-q in g、CHEN Zhi-de2,LI Xiang-y u3Fujian Jiangxia University Fujian, Fuzhou350108; 2.Fujian Normal University Fujian, Fuzhou350007;3.Minjiang Normal College Fujian, Fuzhou350007)【A bstract】：This paper focuses on the problem o f influence Maximization in social networks.On the basis o f the classical Linear-threshold propagation model,we cluster and analyze the users in social networks.Then,we propose our improved K-LT propagation model.Based on K-LT model we further propose the K-K K influence maximization algorithm.The simulation is carried out by collecting the real social network data.The experimental results show that the improved K-K K algorithm is better than the other one when it is not improved.【Key w ords】：Social networks;Propagation model;Influence maximization0引言社交网络影响力是指用户受其他社交网络用户 信息传播的过程。

社交网络分析中的社区发现技巧总结社交网络分析是一种研究社交关系的分析方法，通过对社交网络中的节点和边进行深入研究，可以揭示出社会关系的模式、影响力的传播路径等。

其中，社区发现是社交网络分析中的一个重要方面，它能够帮助我们识别出网络中相互关联紧密、功能相似的节点群体。

社区发现技巧的总结如下：1.节点度中心性节点度中心性是指节点的度数，即其在网络中所连接的边的数量。

在社交网络中，节点度中心性可以反映出节点的重要性和连接的紧密程度。

通过计算节点的度中心性，我们可以发现网络中度数较高的节点，往往代表着社区的核心节点。

2.介数中心性介数中心性用于衡量节点在整个网络中的中介程度，即节点在网络中作为桥梁的能力。

在社交网络中，介数中心性可以帮助我们发现那些在社区之间有着重要桥梁作用的节点，即连接不同社区的节点。

3.聚类系数聚类系数反映了网络中节点之间的紧密程度，它可以衡量节点间连接的密集程度，并从而发现社区。

在社交网络分析中，如果节点的聚类系数较高，即节点与其邻居节点之间的连接较紧密，那么可以认为这些节点可能属于同一个社区。

4.模块化模块化是一种社区发现的度量方法，它通过计算网络中节点与社区的内部联系强度与节点与社区的外部联系强度的差别，来评估社区发现的效果。

模块化值在-1到1之间，当模块化值接近1时，表示社区发现效果好，节点在社区内部联系强，并且社区之间的联系较弱。

5.谱聚类谱聚类是一种常见的社区发现方法，它基于图谱理论，通过计算节点相似性矩阵的特征向量来划分社区。

谱聚类可以将节点分为一组个体相似的社区，并且保持社区内的紧密连接和社区间的松散连接。

6.标签传播标签传播算法是一种基于标签更新的社区发现方法，它通过不断的更新节点的标签信息，将具有相似标签的节点划分为同一个社区。

标签传播算法简单、高效，并且在一些实际应用中取得了较好的效果。

7.模块度最优化模块度最优化是一种基于网络结构的社区发现方法，它通过优化模块度函数，将网络划分成多个具有较高内部联系和较低外部联系的社区。

louvain算法例子Louvain算法（Louvain algorithm），也被称为Modularity Optimization算法，是一种用于社区发现的图算法。

它通过最大化网络中节点的模块度（modularity）来划分节点所属的社区，从而识别出图中的子群体。

下面将通过一个例子来介绍Louvain算法的原理和应用。

假设我们有一个社交网络，其中包含10个节点和15条边。

我们希望通过Louvain算法来识别出这个社交网络中的社区结构。

我们需要将这个社交网络表示为一个图。

为了方便起见，我们使用邻接矩阵来表示图的连接关系。

该邻接矩阵如下所示：```0 1 0 0 0 0 0 0 0 01 0 1 1 0 0 0 0 0 00 1 0 1 0 0 0 0 0 00 1 1 0 1 0 0 0 0 00 0 0 1 0 1 1 0 0 00 0 0 0 1 0 0 0 0 00 0 0 0 1 0 0 0 0 00 0 0 0 0 0 0 0 1 10 0 0 0 0 0 0 1 0 10 0 0 0 0 0 0 1 1 0```接下来，我们使用Louvain算法来划分社区。

Louvain算法的核心思想是不断地合并社区，直到无法继续提高模块度为止。

我们将每个节点视为一个社区，并计算每个节点的模块度增益。

模块度增益是指将某个节点从其当前社区移动到其他社区后，整个网络的模块度提高的程度。

然后，我们选择模块度增益最大的节点进行移动，并更新社区划分。

重复这个过程，直到无法再提高模块度为止。

在这个例子中，我们通过Louvain算法得到了以下的社区划分结果：```社区1：0 2 6社区2：1 3社区3：4社区4：5社区5：7 8 9```通过Louvain算法，我们成功地将这个社交网络划分成了5个社区，每个社区内的节点都有着紧密的连接，而不同社区之间的连接相对较少。

Louvain算法不仅可以用于社交网络的社区发现，还可以应用于其他领域，如生物信息学、交通网络分析等。

基于NVPA算法的社交网络影响力最大化算法徐浩;潘理【摘要】衡量与评估用户影响力是在线社交网络分析中的一个经典问题.现有的相关研究主要从个体角度出发,利用贪婪算法进行影响力分析,很少考虑网络中用户一般都会形成社区这样一个客观事实,而一般个体角度的影响力最大化算法都存在运行效率低的问题.因此,提出了一种基于社区的影响力最大化算法NVPA-IM(Neighborhood Vector Propagation Algorithm Influence Maximization).通过与经典影响力最大化算法的对比分析,证明了所提算法在保证算法精度的同时,显著提高了算法效率.【期刊名称】《通信技术》【年(卷),期】2018(051)004【总页数】6页(P924-929)【关键词】社交网络;社区发现;节点影响力评估;影响力最大化【作者】徐浩;潘理【作者单位】上海交通大学电子信息与电气工程学院,上海 200240;上海市信息安全综合管理技术研究重点实验室,上海 200240【正文语种】中文【中图分类】TP3930 引言随着在线社交网络分析在推荐系统、市场营销、信息检索等依据影响力对用户行为进行预测的领域的广泛应用，影响力分析问题在学术界和工业界引起了越来越多重视。

基于社交网络的市场营销，如何准确找到最具影响力的个体集合、获取最大的影响范围，是极其关键的问题。

对此，文献[1]给出了准确化定义，将影响力最大化问题转化为如何选择K个初始节点，通过激活这K个初始节点，在给定信息传播模型下，使网络中最终被激活的用户节点数最多。

已有的相关研究主要从个体的角度分析问题[2-4]，Kempe等人[2]首先使用贪婪爬山算法进行影响力分析，证明了这一问题是NP难问题，用贪婪算法求解可以达到(1-1/e)的精度。

但是，贪婪算法的时间复杂度太高。

后来研究人员主要解决的问题是提高算法的运行效率[5, 6]，但是这些算法都是基于网络全局进行算法模型设计。

社交网络分析算法的使用教程社交网络分析（Social Network Analysis，SNA）是一种研究人际关系的方法，通过分析个体之间的连接和关联，揭示社交网络中的模式和结构。

在社交媒体时代，社交网络分析算法成为了研究网络社会学、营销学以及信息传播的重要工具。

本文将介绍几种常用的社交网络分析算法及其使用教程。

一、度中心性算法（Degree Centrality）度中心性算法是最简单也是最常用的社交网络分析算法之一，用于计算每个节点在网络中有多少条边与之连接。

该算法可以用来评估一个节点的重要性和影响力。

具体计算方法如下：1. 首先，将网络数据导入社交网络分析工具（如Gephi、Cytoscape等）中。

2. 在工具中选择度中心性算法，并点击运行。

3. 程序会计算每个节点的度中心性，并将结果显示在节点上或作为节点的属性。

4. 分析结果，找出具有较高度中心性的节点，这些节点在网络中起到重要的枢纽作用。

二、介数中心性算法（Betweenness Centrality）介数中心性算法用于衡量节点在网络中的中介地位，即节点在连接其他节点之间的最短路径中扮演的角色。

该算法可以用来识别那些在信息传播、资源传输中起到关键作用的节点。

具体计算方法如下：1. 在社交网络分析工具中导入网络数据。

2. 在工具中选择介数中心性算法，并点击运行。

3. 工具会计算每个节点的介数中心性，并在节点上显示结果。

4. 根据分析结果，找出介数中心性较高的节点，这些节点在信息传播和资源传输中扮演着重要的桥梁角色。

三、聚集系数算法（Clustering Coefficient）聚集系数算法用于衡量节点邻居之间的相互连接程度，用来判断网络中的群组和社区结构。

该算法可以帮助我们理解社交网络中的小世界现象和群体行为。

具体计算方法如下：1. 将网络数据导入社交网络分析工具中。

2. 在工具中选择聚集系数算法，并运行。

3. 工具会计算每个节点的聚集系数，并在节点上显示结果。

大规模网络中的社区发现与网络推荐算法研究随着互联网的迅猛发展，人们在网络上的社交活动日益增多，网络中出现了众多复杂的社区结构。

社区发现和网络推荐算法成为了研究的热点，它们对于我们了解网络结构、挖掘用户特征以及提供个性化推荐服务具有重要意义。

本文将从大规模网络中的社区发现以及网络推荐算法两个方面进行研究，以探究如何有效地利用这些算法来改善网络用户的体验。

首先，我们将着眼于大规模网络中的社区发现。

社区是指连接度高、内部联系紧密的节点聚集。

通过发现社区结构，我们可以更好地理解网络的拓扑结构，探究用户之间的关联和信息传播的路径。

社区发现算法首先要解决的问题是如何定义社区。

常见的定义社区的准则包括节点之间的连接强度、节点之间的相似性以及节点之间的聚集性等。

在大规模网络中，基于连接强度的算法比较常见，如Louvain算法和模块度最大化算法。

Louvain算法是一种层次化的聚类算法，通过最大化模块度来划分社区。

模块度最大化算法则通过优化社区内部节点的连接度来划分社区。

随着大规模网络中社区的存在越来越复杂，传统的社区发现算法也逐渐暴露出一些问题。

例如，它们往往对社区大小、社区边界模糊性以及重叠社区的处理能力比较弱。

为了解决这些问题，研究者们提出了基于深度学习的社区发现算法。

这些算法通过构建网络的嵌入表示来发现社区结构，克服了传统算法的局限性。

基于深度学习的算法可以充分挖掘节点之间的隐藏关系，并提高社区发现的准确性和稳定性。

接下来，我们关注的是网络推荐算法。

随着信息爆炸和个性化需求的增加，网络推荐算法被广泛应用于个性化推荐、广告推送和搜索引擎等领域。

网络推荐算法的目标是根据用户的兴趣和行为数据，为其提供个性化的推荐服务。

常见的网络推荐算法包括基于内容的推荐算法和协同过滤算法。

基于内容的推荐算法通过分析用户的个人信息和内容特征，为用户推荐与其喜好相关的内容。

协同过滤算法则是基于用户行为数据，通过分析用户的行为模式和相似性推荐相似兴趣的用户喜欢的物品。

带权社交网络中的社区发现算法研究随着社交网络的普及，人们日常交流中的很多信息都通过网络传播。

社交网络已经成为了人们社交的重要渠道，同时也成为了研究人员分析社交关系的重要数据来源。

在社交网络中，人们可以相互联系、互相交流，形成各种社区。

而研究如何发现社区结构就成为了一个热门话题，因此带权社交网络中的社区发现算法也具备了很高的研究价值。

社区发现算法的主要目标是将网络中的节点和边划分为不同的群体，并且在同一群体中有很高的内部联系，在不同群体之间有较少的联系。

而在带权社交网络中，每个节点都有不同的重要性，也就是权重，包括节点之间的联系以及节点与其他因素之间的联系。

这种加权的情况要求我们在社区发现算法中进一步考虑权重的因素。

对于带权社交网络的社区发现算法研究，已经有了很多成果。

其中，不同的算法适用于不同的场合。

以下是几种常见的带权社交网络社区发现算法：Louvain算法：该算法目标是最大化modularity，是一种高效的本地优化算法。

这种方法的基本思想是：首先将所有节点划分为不同的社区，然后将各种边的权重加起来得到社区内的权重总和，再计算出模块度。

通过枚举每个节点并计算模块度增量，选择增量最大的节点调整其社区分配。

不断迭代直到社区的模块度达到最大。

Infomap算法：该算法是一个有效的最小描述长度（MDL）方法的离线版本，可以将节点放到纸牌的集合中，并以特定的方式遍历网格以获得最佳压缩网络表示。

该算法会遍历社区由基于模块排序的方法建立的社区层次结构，并在每个社区中使用概率模型，目标是最小化描述网络的概率分布所需的信息数量。

SLM算法：该算法是基于层次聚类的算法，目标是最大化模块度。

该算法将每个节点作为一个社区，然后将所有相邻的社区分配到单独的社区中。

从左到右遍历网络，在每个节点处尝试按照既定规则合并社区。

该算法是累积，因此较高的分辨率社区形成在较低分辨率社区之上，直到整个网络都被分层为止。

除了上述算法，我们在实际应用中还可以根据网络的特点选择其他算法。

大规模社交网络中的社区发现算法研究随着互联网的普及和社交媒体的兴起，大规模社交网络成为了人们日常生活的一部分。

在如此庞大的用户群体中，人们形成了各种各样的社区。

社区发现算法的研究就是为了能够有效地识别和理解这些社区的形成和演化。

社区发现算法有助于我们更好地理解和分析大规模社交网络中的用户行为和关系。

通过识别社区，我们可以了解用户的兴趣爱好、群体思维和传播模式等，这对于各类应用，如推荐系统、用户画像和舆情监测等都具有重要意义。

首先，我们需要了解社区发现算法的思想和方法。

其中，最著名的算法之一就是基于模块度的方法。

该方法基于社区内部节点的连接紧密度和社区间节点的连接稀疏度进行度量，通过不断优化模块度来划分社区。

该方法被广泛应用于社交网络中的社区发现中，可以有效地发现出社区结构。

其次，我们需要考虑到社交网络的特点以及挑战。

大规模社交网络通常具有节点数量庞大、连接复杂等特点，这给社区发现算法提出了挑战。

例如，社交网络存在稀疏性，即节点间连接并非是完全连通的，这意味着传统的聚类算法可能无法准确地发现社区。

另外，社交网络中的节点可能存在着多样性和异质性，这也增加了社区发现的难度。

因此，针对大规模社交网络中的社区发现，我们需要不断优化现有的算法，并结合社交网络的特点进行创新。

一种方法是基于图神经网络。

图神经网络是将节点和边作为输入网络的神经网络模型，可以捕捉到节点的局部结构和全局信息。

通过使用图神经网络，社区发现算法可以更好地利用社交网络的拓扑结构信息，提高社区发现的准确度和效率。

另外，社交网络中的社区发现也可以结合用户行为和兴趣。

社交网络中的用户行为和兴趣是识别社区的重要线索。

例如，用户在社交网络中的互动、评论和转发行为可以反映出用户的兴趣和关注点。

通过挖掘这些用户行为的模式和规律，我们可以更准确地划分社区。

因此，在社区发现算法中结合用户行为和兴趣是一种值得探索的方法。

在实际应用中，社交网络中的社区发现算法可以用于各个领域。

摘要社交网络承载着人与人间的信息交互，见证了影响力的传播扩散，社交关系是社交网络的基本要素，类似于朋友关系、同事关系、同学关系具有强烈的社交属性，可以在局部网络中实现影响力的迅速级联扩散，其关系的确定性和有序性亦有利于预先评估影响力的传播轨迹和影响范围。

在目前的社交网络建模中，绝大多数工作都着眼于正向信任关系的建模分析，而一定程度上忽略了负向信任关系，如忽视、敌对、厌恶等常见的社交关系，后者同样具有重大的研究价值。

本文面向社交网络影响力最大化问题，针对以下关键技术展开了研究：针对在线社交网络真实数据集，考虑社交网络中不同类型的信任关系，研究基于信任关系的影响力传播模型建模技术；针对社交网络的结构特征与传播特性，研究基于结构效益的影响力测度技术；面向新的社交网络模型，研究新型取种算法的设计及相关技术。

主要工作包括：1）结合真实社交网络数据集，提出了基于信任关系的模型假设；基于信任关系和消息扩散的特征，提出了基于信任关系的影响力传播模型；2）考察基于信任关系的影响力传播模型，讨论不同性质的信任关系和子结构及其对传播进程的影响；推导节点结构效益的相关理论计算公式和公式，提出基于结构效益的影响力评估策略；3）研究社交网络现有的典型影响力最大化问题的处理算法，总结了其设计思路与适用场景；基于社交网络的不同信任场景与前期研究的影响力评估策略，提出了三种基于不同思路的影响力最大化算法；4）基于真实数据集设计仿真试验，横向对比了既有经典影响力最大化算法与本论文所提出的算法，验证了其在运行时间、覆盖率等多维度性能表现，评估了其价值。

实验仿真证明本文提出的社交网络影响力扩散模型能够更好地仿真影响力在社交网络中受限制的传播场景，而基于结构效益的贪心式影响力最大化算法相对于经典启发式算法和贪心算法具有一定的综合性能优势，可以更好地应用于真实社交网络场景中。

关键词：社交网络，信任关系，线性阈值模型，影响力最大化AbstractSocial networks are the basis of communication and influence spread, Social relationship is the basic element of social network. Via strong social relationship such as friends, colleagues and classmates, rapid cascade spread of influence could be achieved in local network; on the other hand, the certainty and ordering property of these relationship are also conducive to pre-evaluating the trajectory and range of influence diffusion. In the current social network modeling, most of the work focuses on the modeling and analysis of positive trust relationship, while to some extent ignores negative trust relationship, such as neglect, hostility, aversion and other common social relationships, which are also of research value.Inspired by real datasets of online social networks and different types of trust relationships in social networks, we propose a new model of influence diffusion based on trust relationship. According to the structure and propagation characteristics of the model, we study the relevant strategies to measure the ability of influence propagation, designs and then validates effective solutions to the influence maximization program. Specifically as follows:1) Based on the analysis of typical scenarios, the hypothesis of trust-relationship-based model is put forward, and the characteristics of trust relationship and influence diffusion are qualitatively analyzed with real social network datasets. Based on the above work, the influence diffusion model based on trust relationship(LT-TR model) is proposed.2) According to the LT-TR model, different types of trust relationship and substructures and their impact on the diffusion process are discussed. Upon deducing the theoretical calculation formula and practical application formula of node structure benefit, the influence evaluation strategy based on structure benefit is put forward.3) We study the existing typical influence maximization algorithms of social networks, summarize their design ideas and application scenarios, and propose three influence maximization algorithms based on different scenarios and influence evaluation strategies of previous studies.4) Based on the real dataset, the simulation experiments are designed, and the existing classical influence maximization algorithm and the proposed algorithm are compared horizontally. The performance of the algorithm in running time, coverage and other dimensions is verified, and the application value of the algorithm is proved.Experiments show that the influence diffusion model can better simulate the restricted propagation scenarios in the symbolic network. Besides, the greedy algorithm based on structural benefit has some comprehensive performance advantages over the classical heuristic and greedy influence maximization algorithm, and could be better applied to real social network scenarios.Keywords: social networks, trust relationship, linear threshold model, influence maximization目录摘要 (I)Abstract (II)目录 (III)图目录 (V)表目录........................................................................................................................................................... V I 绪论 (1)1.1 社交网络与其影响力最大化问题 (1)1.2 研究背景及意义 (1)1.3 研究内容与主要工作 (2)1.4 论文组织结构 (2)研究现状 (4)2.1社交网络影响力传播模型 (4)2.1.1 独立级联模型 (4)2.1.2 线性阈值模型 (4)2.1.3 其他常用模型 (5)2.2影响力最大化算法 (6)2.2.1 基于贪心思想的算法 (6)2.2.2 基于启发式的算法 (6)2.2.3 其他常见算法 (7)2.3 本章小结 (8)基于信任关系的影响力传播模型 (9)3.1 引言 (9)3.2 信任关系与影响力传播 (9)3.2.1 基于节点对的信任关系 (9)3.2.2 精细化的激活类型 (10)3.2.3 正面影响力和负面影响力 (11)3.3 基于信任关系的影响力传播模型（LT-TR） (11)3.3.1 网络模型定义 (11)3.3.2 信任关系 (12)3.3.3 子结构 (14)3.3.4 模型传播过程 (17)3.4 模型仿真实验 (20)3.4.1 实验环境与数据集分析 (20)3.4.2 消息传播实验 (20)3.5 本章小结 (23)基于LT-TR模型的影响力评估策略 (24)4.1 引言 (24)4.2 局部结构与激活概率 (24)4.2.1 激活概率推导 (24)4.2.2 激活概率局部近似策略 (25)4.3 局部结构与结构效益 (28)4.3.1 结构效益推导 (28)4.3.2 结构效益局部近似策略 (30)4.4 全局结构效益评估策略 (31)4.4.1 PageRank算法 (31)4.4.2 结构效益全局近似策略 (32)4.5 本章小结 (34)基于结构效益的影响力最大算法 (35)5.1 引言 (35)5.2 基于结构效益的影响力最大化算法设计 (35)5.2.1 问题描述 (35)5.2.2 基于TOP-K效益的算法 (36)5.2.3 基于结构效益-距离的贪心（sd-greedy）算法 (36)5.2.4 基于结构效益的贪心（s-greedy）算法 (37)5.3 实验分析 (38)5.3.1 实验环境 (38)5.3.2 相关验证实验 (38)5.3.3 启发式算法传播实验 (39)5.3.4 基于结构效益的贪心算法传播实验 (41)5.4 本章小结 (44)论文总结与未来工作 (45)6.1 论文总结 (45)6.2 未来工作 (45)致谢 (47)参考文献 (48)作者简介 (50)图目录图3- 1负激活类型 (10)图3- 2信任关系 (13)图3- 3信任关系的主要子结构 (15)图3- 4涉及单行关系的子结构 (16)图3- 5转发阶段 (17)图3- 6接收阶段 (19)图3- 7随机取种传播结果 (21)图3- 8 纯C型传播过程 (22)图3- 9纯A类与LT正激活效果 (22)图3- 10不同型LT-TR激活效果 (23)图4- 1局部激活概率近似算法 (30)图4- 2局部结构效益近似算法 (31)图4- 3全局激活概率近似算法 (33)图4- 4全局结构效益近似算法 (34)图5- 1基于TOP-K效益的算法 (36)图5- 2基于结构效益-距离的贪心算法 (37)图5- 3基于结构效益的贪心算法 (38)图5- 4基于结构效益的启发式取种算法的激活数对比 (40)图5- 5基于结构效益启发式算法与基于度的启发式算法激活数对比 (41)图5- 6候选集合容量对s-greedy算法运行时间的影响 (42)图5- 7候选集合容量对s-greedy算法覆盖效果的影响 (42)图5- 8 s-greedy算法与其他算法的覆盖率对比 (43)图5- 9 s-greedy算法与其他算法的时间开支对比 (43)表目录表3- 1不同情况下下行节点接收的影响力 (18)表3- 2数据集统计 (20)表4- 1随机取种激活概率统计表 (25)第一章绪论绪论1.1社交网络与其影响力最大化问题进入21世纪以来，互联网领域的科技创新与应用模式日新月异，特别是以社交网络的迅速发展令人鼓舞。