《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

相关文章

SQL 外键Foreign Key全解析

《SQL外键ForeignKey全解析》外键是数据库表中的一列(或一组列),用于​​建立两个表之间的关联关系​​,外键的值必须匹配另一个表的主键(PrimaryKey)或唯一约束(UniqueCo... 目录1. 什么是外键?​​ ​​​​2. 外键的语法​​​​3. 外键的约束行为​​​​4. 多列外键​

Java进行日期解析与格式化的实现代码

《Java进行日期解析与格式化的实现代码》使用Java搭配ApacheCommonsLang3和Natty库,可以实现灵活高效的日期解析与格式化,本文将通过相关示例为大家讲讲具体的实践操作,需要的可以... 目录一、背景二、依赖介绍1. Apache Commons Lang32. Natty三、核心实现代

使用Python自动化生成PPT并结合LLM生成内容的代码解析

《使用Python自动化生成PPT并结合LLM生成内容的代码解析》PowerPoint是常用的文档工具,但手动设计和排版耗时耗力,本文将展示如何通过Python自动化提取PPT样式并生成新PPT,同时... 目录核心代码解析1. 提取 PPT 样式到 jsON关键步骤:代码片段:2. 应用 JSON 样式到

Maven 插件配置分层架构深度解析

《Maven插件配置分层架构深度解析》:本文主要介绍Maven插件配置分层架构深度解析,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录Maven 插件配置分层架构深度解析引言:当构建逻辑遇上复杂配置第一章 Maven插件配置的三重境界1.1 插件配置的拓扑

全解析CSS Grid 的 auto-fill 和 auto-fit 内容自适应

《全解析CSSGrid的auto-fill和auto-fit内容自适应》:本文主要介绍了全解析CSSGrid的auto-fill和auto-fit内容自适应的相关资料,详细内容请阅读本文,希望能对你有所帮助... css  Grid 的 auto-fill 和 auto-fit/* 父元素 */.gri

Maven 依赖发布与仓库治理的过程解析

《Maven依赖发布与仓库治理的过程解析》:本文主要介绍Maven依赖发布与仓库治理的过程解析,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下... 目录Maven 依赖发布与仓库治理引言第一章:distributionManagement配置的工程化实践1

MySQL复合查询从基础到多表关联与高级技巧全解析

《MySQL复合查询从基础到多表关联与高级技巧全解析》本文主要讲解了在MySQL中的复合查询,下面是关于本文章所需要数据的建表语句,感兴趣的朋友跟随小编一起看看吧... 目录前言:1.基本查询回顾:1.1.查询工资高于500或岗位为MANAGER的雇员,同时还要满足他们的姓名首字母为大写的J1.2.按照部门

Spring三级缓存解决循环依赖的解析过程

《Spring三级缓存解决循环依赖的解析过程》:本文主要介绍Spring三级缓存解决循环依赖的解析过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、循环依赖场景二、三级缓存定义三、解决流程(以ServiceA和ServiceB为例)四、关键机制详解五、设计约

Redis实现分布式锁全解析之从原理到实践过程

《Redis实现分布式锁全解析之从原理到实践过程》:本文主要介绍Redis实现分布式锁全解析之从原理到实践过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、背景介绍二、解决方案(一)使用 SETNX 命令(二)设置锁的过期时间(三)解决锁的误删问题(四)Re

Qt实现网络数据解析的方法总结

《Qt实现网络数据解析的方法总结》在Qt中解析网络数据通常涉及接收原始字节流,并将其转换为有意义的应用层数据,这篇文章为大家介绍了详细步骤和示例,感兴趣的小伙伴可以了解下... 目录1. 网络数据接收2. 缓冲区管理(处理粘包/拆包)3. 常见数据格式解析3.1 jsON解析3.2 XML解析3.3 自定义