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

Orion's Blog 2023-03-28 原文

1 度分布

网络的度分布\(p(k)\)表示了一个随机选择的节点拥有度\(k\)的概率。我们设度为\(k\)的节点数目\(N_k = \sharp\text{ nodes with degree } k\)，除以节点数量\(N\)则可得到归一化后的概率质量分布：

\[P(k)=N_k / N(k\in \mathbb{N}) \]

我们有：\(\sum_{k \in \mathbb{\mathbb{N}}} P(k)=1\)。
对于下面这个网络：

其归一化后的度分布直方图可表示如下：

2 路径

2.1 图的路径

图的路径(path)指一个节点序列，使得序列中的每个节点都链接到序列中的下一个节点(注意：这里的术语不同教材不一样，有的教材把这里的路径定义为漫游(walk)，而将术语“路径”保留给简单路径)。路径可以用以下方式进行表示：

\[P_n=\left\{i_0, i_1, i_2, \ldots, i_n\right\} \quad P_n=\left\{\left(i_0, i_1\right),\left(i_1, i_2\right),\left(i_2, i_3\right), \ldots,\left(i_{n-1}, i_n\right)\right\} \]

一个路径可以通过经过同一条边多次而和它自身相交。如下面这个图中更多路径ABDCDEG就和自身相交。

注意，在有向图中路径只能沿着边的方向。

2.2 路径的条数

路径的条数定义为节点\(u\)和\(v\)之间的路径数量。我们发现邻接矩阵的幂和路径的条数之间有着关系。

长度 \(h=1\)(这里的h可理解为跳数hops)的路径计数矩阵: 只需要考察\(u\)和\(v\)之间是否存在长度为\(1\)的链接，即
\[H_{uv}^{(1)} = A_{uv} \]
长度 \(h=2\)的路径计数矩阵：需要考察\(u\)和\(v\)之间是否存在长度为\(2\)的路径，即对满足\(A_{u k}A_{k v}=1\)的\(k\)进行计数。
\[H_{u v}^{(2)}=\sum_{k=1}^N A_{u k} A_{k v}=\left[A^2\right]_{u v} \]
长度 \(h\)的路径计数矩阵：需要考察\(u\)和\(v\)之间是否存在长度为\(h\)的路径，即对满足\(A_{u k_1} A_{k_1 k_2} \ldots . A_{k_{h-1} v}=1\)的所有\(\langle k_1,k_2,\cdots, k_{h-1}\rangle\)序列进行计数。
\[H_{u v}^{(h)}=\left[A^h\right]_{u v} \]

上述结论对有向图和无向图都成立。上述定理解释了如果\(u\)和\(v\)之间存在最短路径，那么它的长度就是使\(A^k_{uv}\)非零的最小的\(k\)。
进一步推论可知，在一个\(n\)个节点的图中找到所有最短路径的一个简单方法是一个接一个地对图的邻接矩阵\(A\)做连续的幂计算，知道第\(n-1\)次，观察使得每一个元素首次变为正值的幂计算。这个思想在Folyd-Warshall最短路径算法中有着重要应用应用。

2.3 距离

图中两个节点之间的距离(distance)定义为两个点最短路径中的边数（如果两个点没有连通，距离通常定义为无穷大）。
如对下面这个图我们有\(B\)、\(D\)之间的距离\(H_{B,D}=2\)，\(A\)、\(X\)之间的距离\(h_{A, X}=\infty\)。

注意，在有向图中距离必须沿着边的方向。这导致有向图中的距离不具有对称性。比如下面这个图中我们就有\(h_{A, C} \neq h_{C, A}\)。

我们定义两两节点之间距离的最大值为图的直径（diameter）。

2.4 平均路径长度

无向连通图（连通分量）或有向强连通图（强连通分量）的平均路径长度（average path length）定义为：

\[\bar{h}=\frac{1}{2 E_{\max }} \sum_{i, j \neq i} h_{i j} \]

这里\(h_{ij}\)是节点\(i\)到\(j\)的距离。\(E_{max}=\frac{n(n-1)}{2}\)，这里\(2E_{max}\)中的系数\(2\)可要可不要，不同教材定义方法不一样。
在计算平均路径长度时，我们通常只计算连通节点之间的距离（也即忽略长度为“无穷”的路径）

2.5 寻找最短路径

对于无权图，我们可以由宽度优先搜索(BFS)搜寻图的最短路径。

从节点\(u\)开始，将其标注为\(h_u(u)=0\)，并将其加入队列。
当队列不为空时：
- 将队首元素\(v\)移出队列，将其未标注的邻居加入队列并标注为\(h_u(w) = h_u(v) + 1\)。
- 循环往复。

对于带权图，我们当然就得寻求Dijkstra、Bellman-Ford等算法啦,此处不再赘述.

3 节点中心性

节点\(i\)的中心性(centrality)可以用于度量节点\(i\)的重要程度。节点的中心性有许多种类，下面我们介绍介数中心性(betweeness centrality)和接近中心性(closeness centrality)。

3.1 介数中心性

介数中心性基于这样一个思想：如果一个节点在许多其它节点之间的最短路径上，那么这个节点就是重要的。于是我们可以将节点\(i\)的介数中心性定义为：

\[c_v=\sum_{s \neq v \neq t} \frac{\#(\text { shortest paths betwen } s \text { and } t \text { that contain } v)}{\#(\text { shortest paths between } s \text { and } t)} \]

以下面这个图为例：

\[c_A=c_B=c_E=0\\ c_C=3\\ (\text{A-C-B}, \text{A-C-D}, \text{A-C-D-E})\\ c_D=3\\ (\text{A-C-D-E}, \text{B-D-E}, \text{C-D-E}) \]

3.2 接近中心性

接近中心性基于这样一个思想：如果一个节点到其它所有节点的最短路径长度都很小，那么这个节点就是重要的。于是我们可以将节点\(i\)的接近中心性定义为：

\[c_v=\frac{1}{\sum_{u \neq v} \text { shortest path length between } u \text { and } v} \]

还是以上面那个图为例，在该图中有：

\[c_A=1 /(2+1+2+3)=1 / 8 \\ (\text{A-C-B}, \text{A-C}, \text{A-C-D},\text{A-C-D-E})\\ c_D=1 /(2+1+1+1)=1 / 5 \\ (\text{D-C-A}, \text{D-B}, \text{D-C}, \text{D-E}) \]

4 聚类系数

节点\(i\)的聚类系数(clustering coefficient)可以直观地理解为节点\(i\)的邻居有多大比例是互相连接的。设节点\(i\)的度为\(k_i\)，则其聚类系数\(C_i\)定义为

\[C_i=\frac{2 e_i}{k_i\left(k_i-1\right)} \]

这里\(e_i\)为节点\(i\)邻居之间的边数，我们有\(C_i\in[0, 1]\)。下面展示了聚类系数的一些实例：

图的平均聚类系数（average clustering coefficient）定义为：

\[C=\frac{1}{N} \sum_i^N C_i \]

5 真实世界网络的属性

接下来我们来看一MSN收发信息网络(有向)的实例。

该网络中245 million用户注册，180 million用户参与了聊天，拥有超过30 billion个回话。超过 255 billion条交互信息。
连通性

度分布

其度分布高度倾斜，平均度为\(14.4\)。

log-log度分布

聚类系数

这里为了方便出图，我们定义横坐标为度\(k\)，对应的纵坐标\(C_k\)为度为\(k\)的节点的聚类系数\(C_i\)的平均值，即\(C_k=\frac{1}{N_k} \sum_{i: k_i=k} C_i\)。

整个网络的平均聚类系数为\(0.11\)。

距离分布

其中平均路径长度为\(6.6\)，\(90\%\)的节点可以在\(8\)跳之内到达。

参考

[1] http://web.stanford.edu/class/cs224w/
[2] Easley D, Kleinberg J. Networks, crowds, and markets: Reasoning about a highly connected world[M]. Cambridge university press, 2010.
[3] Barabási A L. Network science[J]. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 2013, 371(1987): 20120375.
[4] 《图论概念梳理》

挖掘图 span class inline 人工智能

有关图数据挖掘：网络的常见度量属性的更多相关文章

ruby - 解析 RDFa、微数据等的最佳方式是什么，使用统一的模式/词汇(例如 schema.org)存储和显示信息 - 2
我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i
ruby-on-rails - 如果为空或不验证数值，则使属性默认为 0 - 2
我希望我的UserPrice模型的属性在它们为空或不验证数值时默认为0。这些属性是tax_rate、shipping_cost和price。classCreateUserPrices8,:scale=>2t.decimal:tax_rate,:precision=>8,:scale=>2t.decimal:shipping_cost,:precision=>8,:scale=>2endendend起初，我将所有3列的:default=>0放在表格中，但我不想要这样，因为它已经填充了字段，我想使用占位符。这是我的UserPrice模型:classUserPrice回答before_val
ruby-on-rails - 在混合/模块中覆盖模型的属性访问器 - 2
我有一个包含模块的模型。我想在模块中覆盖模型的访问器方法。例如:classBlah这显然行不通。有什么想法可以实现吗？最佳答案您的代码看起来是正确的。我们正在毫无困难地使用这个确切的模式。如果我没记错的话，Rails使用#method_missing作为属性setter，因此您的模块将优先，阻止ActiveRecord的setter。如果您正在使用ActiveSupport::Concern(参见thisblogpost)，那么您的实例方法需要进入一个特殊的模块:classBlah
ruby - 多个属性的 update_column 方法 - 2
我有一个具有一些属性的模型:attr1、attr2和attr3。我需要在不执行回调和验证的情况下更新此属性。我找到了update_column方法，但我想同时更新三个属性。我需要这样的东西:update_columns({attr1:val1,attr2:val2,attr3:val3})代替update_column(attr1,val1)update_column(attr2,val2)update_column(attr3,val3) 最佳答案您可以使用update_columns(attr1:val1,attr2:val2
ruby - Nokogiri 剥离所有属性 - 2
我有这个html标记:我想得到这个:我如何使用Nokogiri做到这一点？最佳答案 require'nokogiri'doc=Nokogiri::HTML('')您可以通过xpath删除所有属性:doc.xpath('//@*').remove或者，如果您需要做一些更复杂的事情，有时使用以下方法遍历所有元素会更容易:doc.traversedo|node|node.keys.eachdo|attribute|node.deleteattributeendend 关于ruby-Nokog
ruby-on-rails - Rails 模型——非持久类成员或属性？ - 2
对于Rails模型，是否可以/建议让一个类的成员不持久保存到数据库中？我想将用户最后选择的类型存储在session变量中。由于我无法从我的模型中设置session变量，我想将值存储在一个“虚拟”类成员中，该成员只是将值传递回Controller。你能有这样的类(class)成员吗？最佳答案将非持久属性添加到Rails模型就像任何其他Ruby类一样:classUser扩展解释:在Ruby中，所有实例变量都是私有(private)的，不需要在赋值前定义。attr_accessor创建一个setter和getter方法:classUs
ruby - Ruby 有 `Pair` 数据类型吗？ - 2
有时我需要处理键/值数据。我不喜欢使用数组，因为它们在大小上没有限制(很容易不小心添加超过2个项目，而且您最终需要稍后验证大小)。此外，0和1的索引变成了魔数(MagicNumber)，并且在传达含义方面做得很差(“当我说0时，我的意思是head...”)。散列也不合适，因为可能会不小心添加额外的条目。我写了下面的类来解决这个问题:classPairattr_accessor:head,:taildefinitialize(h,t)@head,@tail=h,tendend它工作得很好并且解决了问题，但我很想知道:Ruby标准库是否已经带有这样一个类？最佳
ruby - 用 Ruby 编写一个简单的网络服务器 - 2
我想在Ruby中创建一个用于开发目的的极其简单的Web服务器(不，不想使用现成的解决方案)。代码如下:#!/usr/bin/rubyrequire'socket'server=TCPServer.new('127.0.0.1',8080)whileconnection=server.acceptheaders=[]length=0whileline=connection.getsheaders想法是从命令行运行这个脚本，提供另一个脚本，它将在其标准输入上获取请求，并在其标准输出上返回完整的响应。到目前为止一切顺利，但事实证明这真的很脆弱，因为它在第二个请求上中断并出现错误:/usr/b
ruby - 我如何添加二进制数据来遏制 POST - 2
我正在尝试使用Curbgem执行以下POST以解析云curl-XPOST\-H"X-Parse-Application-Id:PARSE_APP_ID"\-H"X-Parse-REST-API-Key:PARSE_API_KEY"\-H"Content-Type:image/jpeg"\--data-binary'@myPicture.jpg'\https://api.parse.com/1/files/pic.jpg用这个:curl=Curl::Easy.new("https://api.parse.com/1/files/lion.jpg")curl.multipart_form_
世界前沿3D开发引擎HOOPS全面讲解——集3D数据读取、3D图形渲染、3D数据发布于一体的全新3D应用开发工具 - 2
无论您是想搭建桌面端、WEB端或者移动端APP应用，HOOPSPlatform组件都可以为您提供弹性的3D集成架构，同时，由工业领域3D技术专家组成的HOOPS技术团队也能为您提供技术支持服务。如果您的客户期望有一种在多个平台（桌面/WEB/APP，而且某些客户端是“瘦”客户端）快速、方便地将数据接入到3D应用系统的解决方案，并且当访问数据时，在各个平台上的性能和用户体验保持一致，HOOPSPlatform将帮助您完成。利用HOOPSPlatform，您可以开发在任何环境下的3D基础应用架构。HOOPSPlatform可以帮您打造3D创新型产品，HOOPSSDK包含的技术有：快速且准确的CAD