链路预测

2018-11-05 本文已影响0人在彼处

书中金典的程序与算法链接：经典算法

主要内容：

如何通过观察到的节点的连接，来重现因为数据的缺失尚未过程到的连接，或者预测未来将要出现的连接。

第一章：复杂网络基本概述

度分布： p(k)为网络中度为k的节点数占节点总数的比例

很多网络的度分布，近似遵从幂函数的形式：

p 趋于k^(-r),r称为幂指数

随机网络：

传统的随机网络（如ER模型），尽管连接是随机设置的，但大部分节点的连接数目会大致相同，即节点的分布方式遵循钟形的泊松分布，有一个特征性的“平均数”。连接数目比平均数高许多或低许多的节点都极少，随着连接数的增大，其概率呈指数式迅速递减。故随机网络亦称指数网络。

图

无标度网络：

详解：无标度网络理解

现实世界的网络大部分都不是随机网络，少数的节点往往拥有大量的连接，而大部分节点却很少，一般而言他们符合zipf定律，(也就是80/20马太定律)。人们给具有这种性质的网络起了一个特别的名字——无标度网络。这里的无标度是指网络缺乏一个特征度值（或平均度值），即节点度值的波动范围相当大。

现实世界的网络大部分都不是随机网络，少数的节点往往拥有大量的连接，而大部分节点却很少，一般而言他们符合二八定律。将度分布符合幂律分布的复杂网络称为无标度网络。

局部结构

局部结构模型

三角形

簇系数：

节点的簇系数：在复杂网络中，某个节点的簇系数（Clustering Coefficient）是指该节点的邻居中彼此相连的概率。

$C_{i} = \frac{2l_{i} }{k_{i}(k_i - 1) }$ ki表示节点vi的度，（ $l_{i}$ ）表示节点vi的ki个邻居之间的连边数目

整个网络的簇系数：所有节点簇系数的平均值。

$C = \frac{1}{N}\Sigma Ci$ ,其中N代表所有度大于1的节点的数目

完全子图

c阶派系：由c个节点和c（c-1）/2条边组成的完全图

派系度：刻画一个节点周围的派系密度

节点和链路的中心性

衡量节点重要性

最短路劲有关的衡量一个节点的重要性

介数中间性(betweenness)：（社交达人）该节点与其他节点的中转作用。“中间性”是衡量相邻节点之间的紧密程度的指标，中间性越高，说明节点对相邻节点的影响越大，起到了信息中转站的作用

介数中间性

接近中间性：节点与网络中其他节点最短距离的平均值。值越小，说明节点更重要。也可理解为利用信息在网络中的传播时间来确定节点的重要性。

衡量边度重要性

衡量标准

群落结构：网络的一部分----模块化程度衡量

模块化程度的特征图

模块结构：意味着节点存在次级群体，一节点内的连接紧密，节点间的连接较松散

群落结构没有本质的定义，只有数学上的定义，也就是在子图中每一个节点的内部度偶大于或者大于该节点的外部度。

关联性

研究一条边所连接的两个节点度之间的关联。

基本的网络模型

复杂网络：真实的网络既不是规则网咯，也不是随机网络，统称为复杂网络