Network Science

本文作为网络科学学习的笔记

记录下对网络科学大概的整体认识

Resources used

我目前发现R和Python上有一些开源的不错的网络分析的库, 如igraph, epimodel, networkx. Matlab方面则有Brain connectivity toolbox, matlabGBL. 还有斯坦福的SNAP平台.

可视化工具则有Gephi和PAJEK.

数据库方面

KONECT
NetWIKI
Stanford Large Network Dataset Collection

国际会议有

NetSci
European Conference on Complex Systems (ECCS)
CompleNet
Network Frontier Workshop

Books

网络科学导论汪小帆
复杂网络算法与应用司守奎
complex networks course
List of Resources for Complex Network Analysis

Thesis

综述性的论文

周涛的一些论文

传播源定位论文

待定…

主要的思路是提出一种方法, 之后和五种最常见(度, 介,接近数, pagerank, k壳分解)的节点重要性指标得到的结果进行比较, 用SIR模型在现实网络或者人造网络中测试, 还可能有一些其他的方法, 然后得出结论.

Notes for Network Science: An Introduction

本书主要分为四个部分

网络基本概念(第2章), 主要是图论上的一些概念
网络拓扑性质(第3-5章), 刻画出网络拓扑结构性质的一些量
网络拓扑模型(第6-8章), 主要分为三种模型, 随机网路, 小世界网络, 无标度网络, 用以理解网络统计性质的意义和产生的机理
网路动力学(第9-11章), 主要为三个部分, 网络传播动力学, 网络博弈行为以及网络上的同步与控制问题.

1. 复杂网络问题

主要研究的方向有

Internet
WWW网页
电力与交通网络
生物网络
经济与金融网络
社会网络
科研与教育的网络化

复杂网络的复杂性体现在

结构复杂性, 网络连接结构错综复杂, 并且连接结构随时间变化.
节点复杂性, 每一个节点可能是具有分岔和混沌等复杂非线性行为的动力系统.
结构与节点的相互影响. “近朱者赤近墨者黑”
网络之间的相互影响. 各种重要基础设施是相互影响的.

研究内容

发现. 揭示刻画网络系统结构的拓扑性质, 以及度量这些性质的合适方法, 目前最重要的模型包含小世界和无标度. 事实上大规模发杂网络的社团结构分析是一个NP问题. 并且现实世界中的得到网络数据都会丢失连边或者虚假连边. 这点需要预处理, 在不完整的网络结构情况下在多大程度上能进行外推.
建模. 建立合适的模型, 一般常见的模型为随机网络, WS小世界网络, BA无标度网络.
分析. 基于上面的讨论, 分析和预测网络的行为.典型的包括传播, 博弈和同步行为.
设计. 提出改善网络性能和设计新网络的有效方法.
网络科学到网络工程. 应用到实际中.

2. 网络与图

主要讲了经典图论的一些性质.

网络的图表示和计算机表示,

在计算机中, 一般使用邻接表和邻接矩阵$A$, 其中邻接表的形式更加有效率.

一个典型的性质是

共引网络. $C=A^TA$
耦合网络. $B=AA^T$

路径与连通性

连通性分析

当两个节点i和j之间存在长度为r的路径的当且仅当$(A^r)_{ij}>0$, 判断连通性, 有$(I+A+A^2+\dots+A^{N-1})$是正矩阵

矩阵的割集

包含点割集和边割集

Menger定理
s,t不相邻的两个顶点.

最小点割集数目等于连接顶点s和顶点t的独立的简单路径的最大数目
最小边割集的边数目等于连接s与t的不相交的简单路径的最大数目

独立是指两调路径公共顶点只有s,t.
不相交是没有相同的边, 但是可以有相同的顶点.

树与最小生成树

有两个算法, prim和kruskal算法,前者时间复杂度$O(M+NlogN)$适合边稠密, 后者复杂度$O(MlogM)$, 适合边稀疏.

二分图与稳定匹配

二分从属网络.

人员合作网络. 如人与文章
学生选课网络. 如学生与课
用户推荐网络. 如用户与商品
在线社区网络. 如用户与话题

二分图可以隐射成单分图, 然后研究单分图的拓扑性质

延伸的另外一个问题是匹配问题, 即稳定匹配

可以采用G-S算法, 该算法在最多在$N^2$次迭代后收敛, 得到的集合是一个完全匹配.

两边节点数目相同的完全匹配存在的条件是不存在抑制集, 即有老师没人愿意选, 该理由为不存在完全匹配的唯一理由!

3. 网络基本拓扑结构

描述一个网络最基本的拓扑属性包括三个

度分布
平均路径长度
聚类系数

连通性: 无向网络的巨片, 有向网络的蝴蝶结结构

对于一个无向网络, 一般存在连接大部分节点的巨片, 以及小部分的孤立片

对于一个有向网路, 按照结构, 一般可以形成一个蝴蝶结结构, 其即非强连通的也非弱连通的. 这里强连通性是指任何一个节点都可以到达其他任意节点. 弱连通则是讲有向网路转换成无向网络是连通的就可以.

蝴蝶结结构包括

强连通核(SCC)
入部(IN)
出部(OUT)
卷须(tendrils), 即无法从SCC到达也不能到达SCC的节点.
管子(Tube), 不经过SCC直接从IN到OUT的节点.

需要注意的是, SCC并不一定是节点最多的部分

网路的度, 入度, 出度, 平均度都是网络的性质, 其中要注意的是网络的稀疏化特性, 一般$=\frac{2M}{N}=(N-1)p$, 其中M是边数, N是节点数目. 所以当M与N是线性的, 那么平均度随规模是不变的, 但是非线性的话, 网络会变稠密

网络小世界性质: 平均路径长度和聚类系统

平均路径长度: 任意两个节点之间的距离的平均值
直径: 任意两个节点的距离的最大值

一般不直接使用直径, 而使用有效直径, 即当该长度大于90%的节点对之间的路径时, 认为它是有效直径.

对大规模网络, 实际上随规模变大, 直径和有效直径都会变小,这称为直径收缩(shrinking diameters)

Dijkstra算法, 用来求解单源最短路, 思路是一个起点出发, 贪婪选取最小连边, 不断扩散到全局, 该算法只使用连边为非负, 有负边, 可以使用Bellman-Ford算法.

聚类系数的定义是对单个节点, 之后对网络取平均, 用来定量刻画一个节点的任意两个连接节点之间也是连接节点的概率.

泊松度分布与幂律度分布

最常见的离散分布包括泊松分布, 二项分布, 超几何分布其实是可以看做正太分布的变形, 其特征是具有特征标度, 即大部分数据都落在均值附近, 用标准差衡量与均值差距. 68%, 96%, 99.7%表示1,2,3个标准差.都具有钟型分布.

而对于幂律分布, 其分布是具有无标度特性的, 也就是说具有长尾分布的一个特性.当度分布具有该特性, 我们称为非均匀网络, 也称为异质网络. 对于泊松分布, 我们称为均匀分布.

幂律分布的检验可以通过双对数坐标系, 当有线性关系时, 其斜率就是指数, 可以采用最小二乘拟合, 另外一种方法就是累计度分布, 可以平滑化.

需要注意的是, 一般认为只有当幂指数较小(<=3)的时候才是非均匀网络,当幂指数变大时, 非均匀网络会变成均匀网络.非均匀网路即认为是无标度网络

4. 度相关性和社团结构

度相关性

对于前面分析的平均度, 度分布, 可以分别看做0阶度分布, 1阶度分布, 而度相关性可以看做2阶度分布, 度相关性是指, 任何两个节点的连接与两个节点的度数是无关的.

对于度相关网络, 这里引入两个性质

同配网络(Assortative), 度大的节点连接度大的节点
异配网络(Disassortative), 度大的节点倾向于连接度小的节点

科研网络等具有同配性, 而生物蛋白质等网络具有异配性.

余度分布,度为k的节点的邻居的平均度, 就是度为k的节点的余度分布.

从余度分布是正还是负可以看出是同配网路还是异配网络

社团结构

社团结构划分是一类NP难题, 一般使用的算法可以根据是从网路中添加边还是移除边分为两类

凝聚方法(Agglomerative method)
分裂方法(Divisive method)

进行划分需要给定一个优化目标, 这里引入模块度的概念, 一般使用零模型的概念进行比较,

具有相同连边数而度为均匀分布的ER随机图为0阶零模型.
一阶零模型使用具有相同度分布的随机图.

5. 节点重要性与相似性

无向网络节点重要性指标: 度值, 介数, 接近数, k-壳值, 特征向量

度中心性. ${DC}_i=\frac{k_i}{N-1}$
介数中心性. 经过某个节点的最短路径的数目来刻画节点重要性. 表示了对于网络中节点对之间沿最短路传输信息的控制能力.${BC}_i$
接近中心性.
${CC}_i=\frac{1}{di}=\frac{N}{\sum^N{j=1}d_{ij}}$

引入一个简单的10节点风筝网络, 上面三个中心性最大的点分别为3个不同的节点.

k-壳与k-核
k-壳分解为递归过程, 不断去除度为1的点, 直到不能去除, 去除的点就是1-壳(1-shell), 后面同理, 对于孤立节点就是(0-shell)

进行分解后, 可以看成三个部分

核心(Nucleus), 最重要的核心, 与70%的节点相连
对等连通片(Peer-connected component), 由$(k_max-1)$-皮的最大连通片构成.70%
孤立片(Isolated component), 30%, 只能通过核心与其他节点进行联系.

特征向量中心性
中心想法是, 一个节点的重要性取决于邻居的数量也取决于邻居的重要性, 是一个迭代过程

临接矩阵的最大特征值对应的特征向量就是各节点重要性. 对于有向网络, 可以使用hits和pagerank算法进行迭代.

有向网节点重要性排序算法

HITS算法

基于权威性和枢纽性(hub)

PageRank算法
基于随机游走

节点相似性和链路预测

节点相似性一个典型的应用就是链路预测.包含

丢失链接的预测
未来链接的预测

一个基本的假设就是相似性越大, 连接的可能性就越大

衡量一个链路预测算法的精准度使用两种指标

AUC(基于分数比较的方法)
precision(基于成功率的方法)

研究思路有基于马尔科夫链和机器学习

相似性指标

基于局部信息的节点相似性指标
局域全局信息的节点相似性指标
基于随机游走的相似性指标

6. 随机网络模型

典型的随机网络模型

具有给定平均度的随机图模型.即ER随机图, 任何连边连接的概率相同
具有给定度分布的广义随机图. 即配置模型
具有给定度相关特性的基于随机重连的零模型.

通过随机重连来生成, 具有一定的给定阶次度分布的随机网络, 称为零模型.

可以看到的是,
1. ER随机图可以看作0阶零模型
2. 配置模型看做1阶零模型
3. 度相关特性的模型为2阶零模型

7. 小世界网络模型

主要研究两个问题

如何构建具有较大的聚类系数同时较小的平均路径长度的小世界网络. 一般通过在规则网络上对连边进行少许随机重连得到WS小世界网络, 直接添加少量连边形成NW小世界网络模型.
什么样的小世界网络才能实现有效搜索. 即找到任意两个节点之间的最短路径

8. 无标度网络模型

ER随机图和WS小世界图的特征就是网络的度分布都是近似泊松分布的. 称为均匀网络. 但是一个典型的被忽略的性质是无标度性质

BA无标度模型.
更加一般的PRICE无标度模型
推广的局部模型
BA模型的鲁棒性和脆弱性. 两个性质是并存的, 即对随机故障的鲁棒性和蓄意攻击的脆弱性.

9. 网络传播动力学

经典传染病模型

主要包含经典的传染病模型: SI, SIS, SIR模型

其中S是susceptible, I是infected, R是removed

SI模型是logistic增长形式, 会不断的传染不停止, 一般在现实世界较少存在.其解为~~(不知道为什么这个公式老是让hexo崩溃…)~~其中$i_0=i(0)$. SIR模型, 引入$\lambda=\frac{\beta}{\mu}$, 当其小于1时, 那么病毒无法传播, 大于1时候会发生传播. 称为基本再生数, 一般称为$R_0$.

SIS模型, 当$\lambda>1$时, 稳态值为$i=1-\frac{1}{\lambda}$, 当其小于1时, 将趋于0, 病毒不能传播, 因此$\lambda$也是SIS模型的基本再生数, 也是传播的临界值.

但是这三个模型都是基于完全混合假设, 但现实世界的节点只能与网络中很少的节点进行接触.

几类网络传播临界值分析

均匀网络

一般认为每个节点的度近似等于$$, 基于平均场理论, 我们有传播临界值${\lambda}_c=\frac{1}{}$这说明, 在均匀网络中存在一个有限的正的传播临界值, 当小于该指的时候, 感染个体数呈指数衰减, 无法扩张, 当大于这个值得时, 病毒能够扩散并使得网络感染个体数维持在一定的水平.

非均匀网络

不同的是, 我们考虑节点度有明显区别的网络. 我们有结论为${\lambda}_c=\frac{}{}$这表明, 在规模趋向于无穷大的BA无标度网络中, 只要传播率大于0, 病毒就是传播并维持在一定的水平, 也可以看到, 当$\lambda$ 比较小时, 病毒传播范围是比较小的, 到了后面WS小世界网络后来居上.

复杂网络的免疫策略

随机免疫
目标免疫
熟人免疫

节点传播影响力

对于单传播源, Hub节点往往是k-壳值最大的节点, 而非度, 介数最大的节点.
对于多传播源, Hub节点一般是度数大的节点

这是因为k-壳值大的节点往往相互连接, 导致传播影响力减少, 而度数大的分布更加广泛, 传播也更为广泛.

对于行为传播, 有实验结论为高聚类系数比低平均距离对传播范围的影响力更大.