《On the Shoulders of Giants: Incremental InfluenceMaximization in Evolving Social Networks》——解析

本文主要是介绍《On the Shoulders of Giants: Incremental InfluenceMaximization in Evolving Social Networks》——解析,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

中文翻译——动态社会网络的增量式影响最大化算法

1.什么是影响力最大化

        在2003年Kempe 等人就给出了准确的影响力最大化的定义,同时也证明了影响力最大化问题是一个NP难问题。影响力最大化问题可以定义如下:给定一个G=(V,E)的网络图,其中V表示图中的节点,E表示图中的边,同时给定一个正整数k,影响力最大化问题就是要在给定的传播模型下,找到一组数量为k的种子节点集,使得在网络中的影响力传播规模最大化。用数学语言来描述也就是:找到一个集合满足如下这些条件的集合,S∈V同时丨S'丨=k,使Φ(S') = max(Φ(S))。     

        上面所描述的影响力最大化问题其实就是在给定节点数量k的前提下,去寻找相应数量的节点使得所找到的给定数量的节点集合能影响最多的节点。而对影响力最大化问题的描述除此之外,还有一种,那就是给定所要达到的影响力大小,以此为前提,去寻找能够产生相应影响力的最小的节点集合。

2.文章背景

         社交网站规模的飞速发展导致大规模社会网络的底层拓扑结构不断变化。当社会网络结构变化时,其中用户的影响力和影响范围也会随之改变,从而导致最有影响力用户发生变化。然而,已有影响最大化问题研究大多针对静态社会网络。当社会网络结构改变时,现有算法仅能在变化后的网络图中重新计算来定位新的最有影响力节点。        

         社会网络会不断有新用户加入,另外旧用户可能放弃使用。同时,社交网络中每个用户的好友关系也在通过认识新朋友或者放弃对别人的关注等方式不断发生改变。而且,真实社会网络的变化速度十分惊人;据报道目前世界最大的社交网站Facebook 的用户数量正在以每天 60 万的速度不断增长;同样国外知名微博网站Twitter 平均每秒钟有 11 个新用户注册使用。社会网络拓扑结构如此大量的变化必然会导致网络结构重组,节点影响范围变化。原来的最有影响力用户影响值可能下降,而之前并非最有影响力的用户可能影响力迅速增长,成为有力的竞争者。因此,当社会网络结构发变化时,最有影响力用户也会随之发生变化,所以有必要对最有影响用户进行重新选择,才能保证最大的影响范围。

3.主要工作和创新

(1)社会网络的增长基本上满足优先连接原则(Preferential Attachment,PA),即新增加的边更加趋向于同网络中度数大的节点连接,这会导致著名的“富者更富”现象。

(2)社会网络中最有影响力节点基本上是从度数大的节点中选出。

(3)设计了一种增量式影响最大化算法 IncInf。IncInf 算法的增量式设计不需要在变化后的网络图中重新计算所有节点的影响值,从而大大提高了计算效率和可扩展性,因此可以处理大规模的动态社会网络。

4.什么是动态社交网络

    动态社会网络被定义为随着时间推移的一组社会网络图快照ζ=(G0,G1, · · · ,Gt),其中 Gt = (Vt, Et, Pt) 是社会网络 ζ 在时间 t 时的网络结构快照。本算法使用∆Gt = (∆Vt, ∆Et, ∆Pt) 来代表网络图 Gt 从时间 t 到 t + 1 发生的拓扑结构变化。很明显,等式 Gt+1 = Gt ∪∆Gt 成立。     

给定: 时间为 t 时的社会网络 Gt,社会网络 Gt 所对应的大小为 K 的最有影响力节点集合 St,社会网络 Gt 所对应的拓扑结构变化 ∆Gt。     

目标: 高效选择出时间 t + 1 时社会网络图 Gt+1 所对应的大小为 K 的最有影响力节点集合 St+1 ⊂ Vt+1,从而使得集合 St+1 的最终影响范围最大。

5.社会网络增长速度分析

        节点和边是社会网络拓扑的基本组成元素和重要组成部分。通过分析社会网络中节点和边的数量随时间的变化情况来挖掘社会网络的增长速度。

6.优先连接规则 

 7.节点影响力同度数关系

8.设计IncInf算法 

 

9.所提公式

        使用最大影响路径来近似从节点u到v的影响扩散。在这里,将图G中从节点u到v的最大影响路径MIP(u,v,G)定义为具有最大影响路径影响从节点u到v的所有路径之间的概率,可以正式描述如下

        其中prob(p)表示路径p的传播概率,P(u,v,G)表示图G中从节点u到v的所有路径。对于给定路径p = {u1,u2,...,um },路径p的传播概率定义如下:

 10.addNode伪代码

11.剪枝策略设计 

         (1)在第 i 轮迭代中,如果图 Gt 中的最有影响力节点集合 Sti 的影响值变化量 deltaInf[Sti] 为正(即 Sti 的影响值增加),则选择影响值变化量大于deltaInf[Sti] 的节点作为备选节点。这种剪枝方式可以剪枝大量节点,有效减少计算量。

        (2)在第 i 轮迭代中,如果图 Gt 中的最有影响力节点集合 Sti 的影响值变化量 deltaInf[Sti] 为负,则除了条件1之外,备选节点还需要在度数排名或者影响值增加量方面具备显著优势。上述条件可以形式化描述为满足下面两个条件之一:(1)节点的度数排名在图 Gt+1 所有节点中位于前 5%。(2)节点的度数增长率在图 Gt+1 所有节点中排名前 5%。节点 vj 的度数增长率被定义为degreet+1(j)/degreet(j)

 12.IncInf算法设计

 13.本文数据集

 14.实验结果

 

 

 

 文章引用:[1] X  Liu,  X  Liao,  Li S , et al. On the Shoulders of Giants: Incremental Influence Maximization in Evolving Social Networks[J].  2015.

这篇关于《On the Shoulders of Giants: Incremental InfluenceMaximization in Evolving Social Networks》——解析的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/415472

相关文章

Java的volatile和sychronized底层实现原理解析

《Java的volatile和sychronized底层实现原理解析》文章详细介绍了Java中的synchronized和volatile关键字的底层实现原理,包括字节码层面、JVM层面的实现细节,以... 目录1. 概览2. Synchronized2.1 字节码层面2.2 JVM层面2.2.1 ente

Redis 内存淘汰策略深度解析(最新推荐)

《Redis内存淘汰策略深度解析(最新推荐)》本文详细探讨了Redis的内存淘汰策略、实现原理、适用场景及最佳实践,介绍了八种内存淘汰策略,包括noeviction、LRU、LFU、TTL、Rand... 目录一、 内存淘汰策略概述二、内存淘汰策略详解2.1 ​noeviction(不淘汰)​2.2 ​LR

IDEA与JDK、Maven安装配置完整步骤解析

《IDEA与JDK、Maven安装配置完整步骤解析》:本文主要介绍如何安装和配置IDE(IntelliJIDEA),包括IDE的安装步骤、JDK的下载与配置、Maven的安装与配置,以及如何在I... 目录1. IDE安装步骤2.配置操作步骤3. JDK配置下载JDK配置JDK环境变量4. Maven配置下

Python中配置文件的全面解析与使用

《Python中配置文件的全面解析与使用》在Python开发中,配置文件扮演着举足轻重的角色,它们允许开发者在不修改代码的情况下调整应用程序的行为,下面我们就来看看常见Python配置文件格式的使用吧... 目录一、INI配置文件二、YAML配置文件三、jsON配置文件四、TOML配置文件五、XML配置文件

Spring中@Lazy注解的使用技巧与实例解析

《Spring中@Lazy注解的使用技巧与实例解析》@Lazy注解在Spring框架中用于延迟Bean的初始化,优化应用启动性能,它不仅适用于@Bean和@Component,还可以用于注入点,通过将... 目录一、@Lazy注解的作用(一)延迟Bean的初始化(二)与@Autowired结合使用二、实例解

C语言中自动与强制转换全解析

《C语言中自动与强制转换全解析》在编写C程序时,类型转换是确保数据正确性和一致性的关键环节,无论是隐式转换还是显式转换,都各有特点和应用场景,本文将详细探讨C语言中的类型转换机制,帮助您更好地理解并在... 目录类型转换的重要性自动类型转换(隐式转换)强制类型转换(显式转换)常见错误与注意事项总结与建议类型

MySQL 缓存机制与架构解析(最新推荐)

《MySQL缓存机制与架构解析(最新推荐)》本文详细介绍了MySQL的缓存机制和整体架构,包括一级缓存(InnoDBBufferPool)和二级缓存(QueryCache),文章还探讨了SQL... 目录一、mysql缓存机制概述二、MySQL整体架构三、SQL查询执行全流程四、MySQL 8.0为何移除查

在Rust中要用Struct和Enum组织数据的原因解析

《在Rust中要用Struct和Enum组织数据的原因解析》在Rust中,Struct和Enum是组织数据的核心工具,Struct用于将相关字段封装为单一实体,便于管理和扩展,Enum用于明确定义所有... 目录为什么在Rust中要用Struct和Enum组织数据?一、使用struct组织数据:将相关字段绑

使用Java实现一个解析CURL脚本小工具

《使用Java实现一个解析CURL脚本小工具》文章介绍了如何使用Java实现一个解析CURL脚本的工具,该工具可以将CURL脚本中的Header解析为KVMap结构,获取URL路径、请求类型,解析UR... 目录使用示例实现原理具体实现CurlParserUtilCurlEntityICurlHandler

深入解析Spring TransactionTemplate 高级用法(示例代码)

《深入解析SpringTransactionTemplate高级用法(示例代码)》TransactionTemplate是Spring框架中一个强大的工具,它允许开发者以编程方式控制事务,通过... 目录1. TransactionTemplate 的核心概念2. 核心接口和类3. TransactionT