社交网络影响力最大化2(Influence Maximization)

2023-10-09 03:40

本文主要是介绍社交网络影响力最大化2(Influence Maximization),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

2.2 近几年研究进展及算法讲解

2.2.1 RIS(Reverse Influence Sampling)

2014年的Maximizing Social Influence in Nearly Optimal Time

2014年的Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency

2015年的Influence Maximization in Near-Linear Time: A Martingale Approach

2016年的Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in Billion-scale Networks

        以上我列出了四篇采用反向影响力采样方法的论文,该方法大幅度改善了影响力最大化的速度,并使得影响力最大化算法在大型(上百万甚至上亿个节点)社交网络上得以运行。接下来我具体介绍它们的基本思路。

首先是一些定义:

DEFINITION 1 (REVERSE REACHABLE SET). Let v be a node in G, and g be a graph obtained by removing each edge e in G with 1−p(e) probability. The reverse reachable (RR) set for v in g is the set of nodes in g that can reach v. (That is, for each node u in the RR set, there is a directed path from u to v in g.)

反向可达集:节点v是图G中的一个节点,将G中所有边以1-p(e)的概率删去得到图g。在图g中能够到达节点v的节点集合就是节点v的反向可达集。

DEFINITION 2 (RANDOM RR SET). Let G be the distribution of g induced by the randomness in edge removals from G. A random RR set is an RR set generated on an instance of g randomly sampled fromG, for a node selected uniformly at random from g.

随机反向可达集:图g是从图G中随机采样生成的,节点也是随机均匀地选择的。

       通过以上定义可知,如果节点u出现在节点v的反向可达集中,那么从u到v一定存在一条路径,也就是u有一定概率能够影响v。那么覆盖更多RR set就意味着能影响更多的节点,基于以上的思想算法如下:

  • (采样过程)生成一定数量的RR set;
  • (节点选择过程)贪婪地选择节点。每次选出一个覆盖RR集合最多的节点,选中后对整体数据结构进行更新(遍历该节点所覆盖的RR集,对每一个覆盖相同RR集的节点覆盖数减一),然后继续选择下一个节点。

        当然该选择生成多少RR set才能满足理论上的近似保证是这几篇文章最关键的地方。生成RR set越少,时间性能就越好。当然实验的评估标准除了时间还有内存消耗以及影响力大小。

这几篇文章有的是直接生成指定数量的RR set,有的是不断生成测试满足条件就不再生成。具体数学细节有兴趣的同学可以去下载这四篇文章去看下。

 

 

 

 

转载于:https://www.cnblogs.com/xctcherry/p/8447486.html

这篇关于社交网络影响力最大化2(Influence Maximization)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Linux 网络编程 --- 应用层

一、自定义协议和序列化反序列化 代码: 序列化反序列化实现网络版本计算器 二、HTTP协议 1、谈两个简单的预备知识 https://www.baidu.com/ --- 域名 --- 域名解析 --- IP地址 http的端口号为80端口,https的端口号为443 url为统一资源定位符。CSDNhttps://mp.csdn.net/mp_blog/creation/editor

ASIO网络调试助手之一:简介

多年前,写过几篇《Boost.Asio C++网络编程》的学习文章,一直没机会实践。最近项目中用到了Asio,于是抽空写了个网络调试助手。 开发环境: Win10 Qt5.12.6 + Asio(standalone) + spdlog 支持协议: UDP + TCP Client + TCP Server 独立的Asio(http://www.think-async.com)只包含了头文件,不依

poj 3181 网络流,建图。

题意: 农夫约翰为他的牛准备了F种食物和D种饮料。 每头牛都有各自喜欢的食物和饮料,而每种食物和饮料都只能分配给一头牛。 问最多能有多少头牛可以同时得到喜欢的食物和饮料。 解析: 由于要同时得到喜欢的食物和饮料,所以网络流建图的时候要把牛拆点了。 如下建图: s -> 食物 -> 牛1 -> 牛2 -> 饮料 -> t 所以分配一下点: s  =  0, 牛1= 1~

poj 3068 有流量限制的最小费用网络流

题意: m条有向边连接了n个仓库,每条边都有一定费用。 将两种危险品从0运到n-1,除了起点和终点外,危险品不能放在一起,也不能走相同的路径。 求最小的费用是多少。 解析: 抽象出一个源点s一个汇点t,源点与0相连,费用为0,容量为2。 汇点与n - 1相连,费用为0,容量为2。 每条边之间也相连,费用为每条边的费用,容量为1。 建图完毕之后,求一条流量为2的最小费用流就行了

poj 2112 网络流+二分

题意: k台挤奶机,c头牛,每台挤奶机可以挤m头牛。 现在给出每只牛到挤奶机的距离矩阵,求最小化牛的最大路程。 解析: 最大值最小化,最小值最大化,用二分来做。 先求出两点之间的最短距离。 然后二分匹配牛到挤奶机的最大路程,匹配中的判断是在这个最大路程下,是否牛的数量达到c只。 如何求牛的数量呢,用网络流来做。 从源点到牛引一条容量为1的边,然后挤奶机到汇点引一条容量为m的边

配置InfiniBand (IB) 和 RDMA over Converged Ethernet (RoCE) 网络

配置InfiniBand (IB) 和 RDMA over Converged Ethernet (RoCE) 网络 服务器端配置 在服务器端,你需要确保安装了必要的驱动程序和软件包,并且正确配置了网络接口。 安装 OFED 首先,安装 Open Fabrics Enterprise Distribution (OFED),它包含了 InfiniBand 所需的驱动程序和库。 sudo

【机器学习】高斯网络的基本概念和应用领域

引言 高斯网络(Gaussian Network)通常指的是一个概率图模型,其中所有的随机变量(或节点)都遵循高斯分布 文章目录 引言一、高斯网络(Gaussian Network)1.1 高斯过程(Gaussian Process)1.2 高斯混合模型(Gaussian Mixture Model)1.3 应用1.4 总结 二、高斯网络的应用2.1 机器学习2.2 统计学2.3

网络学习-eNSP配置NAT

NAT实现内网和外网互通 #给路由器接口设置IP地址模拟实验环境<Huawei>system-viewEnter system view, return user view with Ctrl+Z.[Huawei]undo info-center enableInfo: Information center is disabled.[Huawei]interface gigabit

H5漂流瓶社交系统源码

一个非常有创意的H5漂流瓶社交系统源码,带完整前端h5和后台管理系统。 环境:Nginx 1.20.1-MySQL 5.6.50-PHP-7.3 代码下载

Golang 网络爬虫框架gocolly/colly(五)

gcocolly+goquery可以非常好地抓取HTML页面中的数据,但碰到页面是由Javascript动态生成时,用goquery就显得捉襟见肘了。解决方法有很多种: 一,最笨拙但有效的方法是字符串处理,go语言string底层对应字节数组,复制任何长度的字符串的开销都很低廉,搜索性能比较高; 二,利用正则表达式,要提取的数据往往有明显的特征,所以正则表达式写起来比较简单,不必非常严谨; 三,使