图数据挖掘:网络中的级联行为

数据挖掘,网络,级联,行为 · 浏览次数 : 486

小编点评

**3.1 传播实例** 给定一个图,我们设每个人最开始都采取的行为\\(B\\)。设存在一个由行为\\(A\\)的早采纳者所组成的小子集\\(S\\),且我们假定他们是顽固派(Hard-wire),也即他们始终会采取行为\\(A\\)而不管使用多少回报来企图改变他们。我们假定有以下的回报设置:对于一个节点而言,如果他的朋友中有大于\\(q=50\\%\\)的人采取行为\\(A\\),则他也采取行为\\(A\\)。这也就意味着\\(a=b-\epsilon\\)(\\(\epsilon>0\\)是一个小的正常数)且\\(q=\frac{1}{2}\\)。 我们接下来看传播的模拟情况。初始时,\\(S=\\{u,v\\}\\),它们采取行为\\(A\\),被标记为红色。如果我的朋友超过\\(q=50\\%\\)是红色,则我也为红色。于是下一步该网络变化为:又过了一个时间步变为:最后,网络变化为:4 级联的启动者与k-core分解一个成功级联的启动者会具有怎样的特征呢?我们猜想它会在网络中的核心位置。而寻找网络中的核心节点就需要用到\\(k\\text{-core}\\)分解。 图\\(G\\)的\\(k\\text{-core}\\)是指\\(G\\)中的一个极大连通子图,其中所有节点的度都至少为\\(k\\)。寻找图的\\(k\\text{-core}\\)的方法就是重复移除度小于\\(k\\)的所有节点,直到不能再移除为止(注意这是一个动态过程,移除节点后其相邻节点的度也会跟着变化,还需要根据变化后的度来考虑是否移除其邻居)。节点的\\(k\\text{-core}\\)值越高意味着它越核心。一个图\\(k\\text{-core}\\)分解的示例如下:下图展示了对一个真实网络的\\(k\\text{-core}\\)分解:其中红色节点启动了成功的级联,而且拥有更高的\\(k\\text{-core}\\)值。所以,成功级联的启动者在网络中是核心的,并且链接到同样紧密联系的用户。参考[1] Granovetter M. Threshold models of collective behavior[J]. American journal of sociology, 1978, 83(6): 1420-1443.[2] O'Gorman H J, Garry S L. Pluralistic ignorance—A replication and extension[J]. Public Opinion Quarterly, 1976, 40(4): 449-458.[3] http://web.stanford.edu/class/cs224w/[4] Easley D, Kleinberg J. Networks, crowds, and markets: Reasoning about a highly connected world[M]. Cambridge university press, 2010.

正文

1 网络中的传播

1.1 一些传播的例子

我们现在来研究网络中的传播。事实上,在网络中存在许多从节点到节点级联的行为,就像传染病一样。这在不同领域中都有所体现,比如:

  • 生物学 传染性疾病

  • 信息技术 级联故障,信息的传播

  • 社会学 谣言、新闻、新技术的传播,虚拟市场

下图就展示了一个信息经由媒体扩散(diffusion)的过程:

迁移学习和多任务学习之间的区别

1.2 基于网络构建传播模型

接下来我们看如何基于网络构建传播模型。以传染病为例,传染病会沿着网络的边进行传播。这种传播形成了一个传播树,也即级联,如下图所示:

迁移学习和多任务学习之间的区别

我们定义一些术语:将其中传播的对象为contagion;被传染这一事件称为adoption、infection或activation;已被传染的节点称为infected/active nodes或adoptors。

接下来我们来看如何为扩散进行建模。目前已经提出了决策模型概率模型两种模型。

  • 决策模型 在这种模型中每个节点会先观察其邻居的决策,然后再以此为依据做出自己的决策。比如若我的\(k\)个朋友去参加了游行,那么我就去。
  • 概率模型 在这种模型中一个已被传染的节点会以一定概率传染其它没有被传染的节点。比如我有几个邻居已经被传染,那么我也有一定概率被传染。这种模型通常用于影响或疾病传播建模。

本篇文章我们介绍决策模型中的集体行动模型和协调博弈模型,下篇文章我们再介绍概率模型。

2 集体行动模型

2.1 模型介绍

Granvetter于1978年提出了集体行动(collective action)模型[1]。在这种模型中,每个人都可以看见任何人的行为并以此为依据进行行动(这也就意味着我们假设网络是完全图)。该模型在日常生活中的一些常见例子包括:在剧院鼓掌或起身离开、在股市中是否存钱以及日常生活中的抗议、罢工等等。接下来我们来探究参与某个给定活动的人数是如何随着时间的推移而增减的。

设有\(n\)个人且每个人可以观测到彼此的行动。对每个人\(i\)都有一个阈值\(t_i(0\leq t_i \leq 1)\)。当且仅当至少有占比\(t_i\)的人采取了某个行为时,节点\(i\)也会采取该行为。事实上\(i\)节点采取行动的概率是如下的阶跃函数(横轴是采取行动的人数比例):

迁移学习和多任务学习之间的区别

小的\(t_i\)也就意味着\(i\)是一个早采纳者(early adopter),而大的\(t_1\)则意味着\(i\)是一个迟采纳者(late adopter)。我们假设这里的时间步是离散的。

我们设\(\{t_1,\cdots, t_n\}\)为所有人的行动阈值集合。设\(F(x)\)为阈值\(t_i\leq x\)的人数比例(\(F(\cdot)\)事先已给定,它是传染一个的属性),它是非递减的,即满足:

\[F(x+\varepsilon) \geq F(x) \]

该模型是一个动态的模型,采取行动的人数会一步步地变化,如下图所示:

迁移学习和多任务学习之间的区别

图中\(F(x)\)表示阈值\(t_i\leq x\)的人数比例,\(s(t)\)表示在\(t\)时刻已加入行动的人数比例。我们发现行动人数的变化速率并不均匀:中间最陡,说明大多数人的阈值比较集中,而左右两端则可分别视为早采纳者和晚采纳者的阈值。

我们模拟\(s(t)\)随着\(t\)的迭代过程:

\[\begin{aligned} &s(0)=0 \\ &s(1)=F(0) \\ &s(2)=F(s(1))=F(F(0)) \end{aligned} \]

我们进一步地进行模拟,有:

\[s(t+1)=F(s(t))=F^{t+1}(0) \]

直观地理解该迭代,就是\(t\)时刻已加入的行动人数\(s(t)\)会在\(t+1\)时刻带动更多的人(\(F(s(t))\))加入行动。最终模型会收敛到不动点(fixed point)\(F(x)=x\),如下图所示:

迁移学习和多任务学习之间的区别

当然,可能也存在其它不动点。不过从\(0\)开始我们只能到达其中的第一个。

如果我们想要从某个其它的地方开始这个过程,则可以往上/往下移动到下一个不动点:

迁移学习和多任务学习之间的区别

如下图所示,不动点有稳定不动点和不稳定不动点之分。稳定不动点周围坡度较为平缓,不稳定不动点周围坡度较为陡峭。

迁移学习和多任务学习之间的区别

2.2 不连续的过渡

我们假设每个节点的阈值\(t_1\)是独立地从分布\(F(x)=\operatorname{Pr}[\text { thresh } \leq x]\)中采样得到的。假定该分布为\(\mu=45\)的截断(truncated)正态分布,则\(F(x)\)的图像会根据该分布的方差进行变化,如下图所示:

迁移学习和多任务学习之间的区别

可以看见,大的方差会使早采纳者和主流人群之间的过渡更为平稳。

我们尝试再增大方差则不动点会升高,然而如果我们再进一步增大方差则不动点又会降低:

迁移学习和多任务学习之间的区别

2.3 模型的弱点

首先,该网络缺少一些社交网络中的概念。比如在社交网络中有一些人是易受影响的。而这直接关系到谁是早采纳者,而不仅仅是早采纳者有多少。

此外,该模型仅仅是建模了人们对参与人数的认识,而不是实际参与人数的多少。也即和“你认为谁会采取该行为”和“谁实际采取了该行为”的区别。这会导致人们在一段时间被“锁定”在某些选择上。

最后,在对阈值的建模上,我们还可以探索更多的分布,或者从一些基础理论(如博弈论模型)来对阈值进行推导。

2.4 多元无知现象

上述的模型需要假设网络是完全图的。然而在现实世界,每个人接受的信息其实大都是片面的,而这会导致他们根据周围的信息来对集体行动做出的决定并不靠谱。比如若某个专制政府限定公民之间的沟通,那么就算已经有足够大的人口比例想反对当前政府并采取极端措施,他们也会觉得自己是一个小群体,并认为这种反抗有很大风险。

多元无知(pluralistic ignorance) 是指人们普遍地错误估计整个民众对一些意见的反应。这是一个使用广泛的原则,不仅仅是在一个中央集权制度限制信息的流通环境。例如,1970年在美国进行的一项调查表明(同一时期实施的几个调查也得到了类似的结果),虽然那个时期只有少数美国白人主张种族隔离,大大超过\(50\%\)的人认为他们所在地区大多数美国白人支持这个主张[2]

3 协调博弈模型

3.1 模型介绍

该模型基于两个玩家的协调博弈(coordination game)理论,假设每人只能从行为\(A\)\(B\)中选一个来采纳,且如果你和你的朋友采取了相同的行为,则你会获得回报(payoff)。

迁移学习和多任务学习之间的区别

我们定义一个如下图所示的关于节点\(v\)\(w\)的回报矩阵,使得当\(v\)\(w\)都采取行为\(A\)的时候,它们获得回报\(a>0\);当\(v\)\(w\)都采取行为\(B\)的时候,它们获得回报\(b>0\);当\(v\)\(w\)采取相反行为的时候,它们获得\(0\)回报。

w-A w-B
v-A \(a,a\) \(0,0\)
v-B \(0,0\) \(b,b\)

每个节点\(v\)和会和所有其邻居进行一次这个游戏,最终算将每次进行游戏的回报进行求和。

接下来我们来看节点\(v\)如何做出决策。

迁移学习和多任务学习之间的区别

我们设节点\(v\)拥有\(d\)个邻居,\(p\)为其邻居中采取行动\(A\)所占的数量,\((1-p)d\)为其邻居中采取行动\(B\)所占的数量。则\(v\)采取行动\(A\)\(B\)分别获得的总回报分别为:

\[\begin{aligned} \text { Payoff }_v &=a \cdot p \cdot d & & \text { if } v \text { chooses } A \\ &=b \cdot(1-p) \cdot d & & \text { if } v \text { chooses B } \end{aligned} \]

\(a \cdot p \cdot d>b \cdot(1-p) \cdot d\)\(v\)会采取行为\(A\)。进一步化简得到

\[p>\frac{b}{a+b} \]

我们设\(q=\frac{b}{a+b}\)为回报阈值,即当\(p>q\)\(v\)会选择行为\(A\)

3.2 传播实例

接下来我们来看一个协调博弈模型的传播实例。给定一个图,我们设每个人最开始都采取的行为\(B\)。设存在一个由行为\(A\)的早采纳者所组成的小子集\(S\),且我们假定他们是顽固派(Hard-wire),也即他们始终会采取行为\(A\)而不管使用多少回报来企图改变他们。

我们假定有以下的回报设置:对于一个节点而言,如果他的朋友中有大于\(q=50\%\)的人采取行为\(A\),则他也采取行为\(A\)。这也就意味着\(a=b-\epsilon\)(\(\epsilon>0\)是一个小的正常数)且\(q=\frac{1}{2}\)

我们接下来看传播的模拟情况。初始时,\(S=\{u,v\}\),它们采取行为\(A\),被标记为红色。

迁移学习和多任务学习之间的区别

如果我的朋友超过\(q=50\%\)是红色,则我也为红色。于是下一步该网络变化为:

迁移学习和多任务学习之间的区别

又过了一个时间步变为:

迁移学习和多任务学习之间的区别

最后,网络变化为:

迁移学习和多任务学习之间的区别

4 级联的启动者与k-core分解

一个成功级联的启动者会具有怎样的特征呢?我们猜想它会在网络中的核心位置。而寻找网络中的核心节点就需要用到\(k\text{-core}\)分解。

\(G\)\(k\text{-core}\)是指\(G\)中的一个极大连通子图,其中所有节点的度都至少为\(k\)。寻找图的\(k\text{-core}\)的方法就是重复移除度小于\(k\)的所有节点,直到不能再移除为止(注意这是一个动态的过程,移除节点后其相邻节点的度也会跟着变化,还需要根据变化后的度来考虑是否移除其邻居)。节点的\(k\text{-core}\)值越高意味着它越核心。

一个图\(k\text{-core}\)分解的示例如下:

迁移学习和多任务学习之间的区别

下图展示了对一个真实网络的\(k\text{-core}\)分解:

迁移学习和多任务学习之间的区别

其中红色节点启动了成功的级联,而且拥有更高的\(k\text{-core}\)值。所以,成功级联的启动者在网络中是核心的,并且链接到同样紧密联系的用户。

参考

  • [1] Granovetter M. Threshold models of collective behavior[J]. American journal of sociology, 1978, 83(6): 1420-1443.

  • [2] O'Gorman H J, Garry S L. Pluralistic ignorance—A replication and extension[J]. Public Opinion Quarterly, 1976, 40(4): 449-458.

  • [3] http://web.stanford.edu/class/cs224w/

  • [4] Easley D, Kleinberg J. Networks, crowds, and markets: Reasoning about a highly connected world[M]. Cambridge university press, 2010.

  • [5] Barabási A L. Network science[J]. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 2013, 371(1987): 20120375.

与图数据挖掘:网络中的级联行为相似的内容:

图数据挖掘:网络中的级联行为

我们现在来研究网络中的传播。事实上,在网络中存在许多从节点到节点级联的行为,就像传染病一样。这在不同领域中都有所体现,比如生物中的传染性疾病;信息技术中的级联故障与信息的传播;社会学中的谣言、新闻、新技术的传播以及虚拟市场。其中在信息技术中信息就会经由媒体来进行扩散(diffusion)。接下来我们看如何基于网络构建传播模型。以传染病为例,传染病会沿着网络的边进行传播。这种传播形成了一个传播树,也

《爆肝整理》保姆级系列教程-玩转Charles抓包神器教程(15)-Charles如何配置反向代理

1.简介 在App开发的过程当中,抓包是一个很常见的需求,而有些app的请求不会在网络设置代理时被抓到数据包,这里若是需要抓包就需要搭建反向代理。 2.什么是代理? 什么是代理,来一张图了解一下。 代理又分为正向代理和反向代理。 3.什么是正向代理? 先来看张图~ 【再举个栗子】 某同学喜欢面向搜索

图数据挖掘:网络的常见度量属性

网络的度分布p(k)表示了一个随机选择的节点拥有度k的概率。我们设度为k的节点数目Nk =#nodes with degree k,除以节点数量N则可得到归一化后的概率质量分布 p(k) = Nk/N。图的路径(path)指一个节点序列,使得序列中的每个节点都链接到序列中的下一个节点,一个路径可以通过经过同一条边多次而和它自身相交。

图数据挖掘:小世界网络模型和分散式搜索

哈佛大学心理学教授斯坦利·米尔格拉(Stanley Milgram)早在1967年就做过一次连锁实验,他将一些信件交给自愿的参加者,要求他们通过自己的熟人将信传到信封上指明的收信人手里。他发现,296封信件中有64封最终送到了目标人物手中。而在成功传递的信件中,平均只需要5次转发,就能够到达目标。也就是说,在社会网络中,任意两个人之间的“距离”是6。这就是所谓的六度分隔理论,也称小世界现象。尽管他

NebulaGraph实战:2-NebulaGraph手工和Python操作

图数据库是专门存储庞大的图形网络并从中检索信息的数据库。它可以将图中的数据高效存储为点(Vertex)和边(Edge),还可以将属性(Property)附加到点和边上。本文以示例数据集basketballplayer为例,通过nGQL操作和Python脚本两种方式构建图谱。数据[10]和代码[9]详

Fabric配置块结构解析

本文是区块链浏览器系列的第二篇。 上一篇介绍了交易块中的数据结构,这一篇介绍区块链网络中的配置块数据结构。 这两种区块中数据结构内容的区别主要Payload结构体中的Data域中的内容,接下来将以类图的形式来解析Data域包含的信息: classDiagram class Payload{ Head

.NET爬取美图官网首页数据实战

## 前言: 在当今信息化社会,网络数据分析越来越受到重视。而作为开发人员,掌握一门能够抓取网页内容的语言显得尤为重要。在此篇文章中,将分享如何使用 .NET构建网络抓取工具。详细了解如何执行 HTTP 请求来下载要抓取的网页,然后从其 DOM 树中选择 HTML 元素,进行匹配需要的字段信息,从中

[转帖]eBPF介绍

https://blog.51cto.com/u_15155099/2767325 1.BPF起源BPF源头起源于一篇1992年的论文,这篇论文主要提出一种新的网络数据包的过滤的框架,如下图所示。提出bpf的原因其实也很简单,早期我们从网卡中接收到很多的数据包,我们要想从中过滤出我们想要的数据包,我

安装、学习protobuf

Protobuf是什么? 类似于json的一种数据格式,独立于语言,而且是二进制方式,所以比json更快,而且还可以直接存储一些图、树 序列化和反序列化 持久化(存到磁盘硬盘)领域中,数据存到磁盘叫序列化,从磁盘读取出来叫反序列化 网络传输领域中,数据块转字符串叫序列化,对端把字符串解析为数据块叫反

能快速构建和定制网络拓扑图的WPF开源项目-NodeNetwork

大家好,我是沙漠尽头的狼,今天介绍一个WPF开源项目-NodeNetwork,它可以帮助我们快速构建和定制网络拓扑图。 一、前言 在现代软件开发中,数据可视化和可交互性越来越受到关注。为了实现这一点,通常需要使用各种图表、表格、网络拓扑图等控件。然而,对于某些特殊的场景,这些控件可能无法满足需求,此