网络药理学的研究思路与方法

目前，网络药理学的研究方法大致分为两类：一是根据公共数据库和公开发表的已有数据，建立特定药物作用机制网络预测模型，预测药物作用靶点，并从生物网络平衡的角度解析药物作用机制。如Cu J[12]等运用虚拟筛选和网络预测技术成功地预测了大黄二蒽酮A、大黄二蒽酮C、番泻苷C等几种从未报道过的具有抗2型糖尿病作用的成分。

网络药理学的研究离不开生物网络的构建。生物网络是采用数学领域图论的研究手段，借助复杂网络的研究方法，将生物体中各种物质及其相互作用加以抽象。

常用的网络拓扑学分析内容包括度、介数、最短路径、瓶颈、中心节点、模块、楔点等。在生物网络中，大多数节点度较小，而一小部分节点度很大，度值大的节点被认为是中心节点。介数是网络中所有最短路径中经过该节点的路径的数目占最 短路径总数的比例。

复杂网络（Complex Network），具有自组织、自相似、吸引子、小世界、无标度中部分或全部性质的网络称为复杂网络。

复杂网络研究的内容主要包括：网络的几何性质，网络的形成机制，网络演化的统计规律，网络上的模型性质，以及网络的结构稳定性，网络的演化动力学机制等问题。其中在自然科学领域，网络研究的基本测度包括：度（degree）及其分布特征，度的相关性，集聚程度及其分布特征，最短距离及其分布特征，介数(betweenness)及其分布特征，连通集团的规模分布。

这么火的原因主要是因为：通过对复杂网络的研究，人们可以对模糊世界进行量化和可预测，目前只有基于复杂网络的研究成果，能够在一定的范围内对事物的发展和运行进行简单预测，并且能够对网络崩溃进行一定的预告。同时对复杂网络研究的过程中，会产生大量的实际可用的模型，而且这些模型已经在实际的生产和组织结构中进行了大量的应用，取得了大量的实际成果。

国内最早在这方面有所建树的是钱学森院士，这个东东实在不是我等老百姓能玩的了的。、

钱老对复杂网络的定义：具有自组织、自相似、吸引子、小世界、无标度中部分或全部性质的网络称为复杂网络。

复杂网络分析方法可以用于研究股票市场的稳定性和风险传播机制。以下是一些可能的方法：

1 构建股票市场的网络模型。可以根据股票市场的交易数据，构建一个由股票和其交易关系构成的网络模型。可以使用网络科学中的图论方法，如节点度中心性、介数中心性、紧密中心性等指标来描述股票的重要性和影响力。

2 分析网络拓扑结构。可以使用复杂网络分析方法来分析股票市场网络的拓扑结构，如小世界网络、无标度网络等。这些结构对于市场的稳定性和风险传播具有重要影响。

3 研究网络动力学。可以使用复杂网络动力学模型来研究股票市场的演化和变化。可以通过模拟网络中节点的演化和交互，来研究市场的稳定性和风险传播机制。

4 分析网络中的风险传播路径。可以使用复杂网络分析方法来分析股票市场中的风险传播路径。可以通过分析网络中节点之间的关系和交互，来确定风险传播的路径和影响程度。

5 研究网络中的系统性风险。可以使用复杂网络分析方法来研究股票市场中的系统性风险。可以通过分析网络中节点之间的关系和交互，来确定系统性风险的来源和影响程度。

总之，复杂网络分析方法可以为研究股票市场的稳定性和风险传播机制提供有力的工具和方法。

主要内容：三元闭包关系的强度及其与网络结构的关系

一、图论

1、图：包含一组元素以及他们之间连接关系的集合

（1）节点（vertex，node，point）

边（链接，连接，关系，联系；edge，link，tie）

邻居

（2）常用的图：合作图、即时通信图、信息链接图

（3）有向图（节点、有向边）、无向图

2、图的同构：画法不同，但本质上（结构上）相同

节点的连接关系比节点的位置更重要。

题目下面哪些图是同构的？

题目

3、路径、最短路径、距离、圈

①路径：一个节点序列的集合，且序列中任意两个相邻节点都有一条边相连。

两点之间可有多条路径。

路径的长度：一条路径所包含的边数

②最短路径-->又叫两点之间的距离

③距离-->最短路径的长度

题目下图中节点A和节点B之间的距离是多少？

④圈

环状结构；至少三条边，起点与终点相同，所有节点均不重复。

部署网络的一个原则：要求每条边都至少在一个圈里（为了保证连通性，带来冗余）。eg：ARPANET的每条边都在圈里

4、连通性

（1）连通图：一个图中任意两点间有路径相通；每条边都在一个圈里。

（2）非连通图

（3）连通分量

若图G的节点子集满足：①连通性：子集中任意两个节点间均有路径相连；②独立性：该子集不是其他满足条件1的子集的一部分；则称G的节点子集是连通分量

题目下面指出的哪些节点集合不对应这个6节点图的一个连通分量？

（4）超大连通分量（giant component）

非形式化地对于包含其中大部分节点的连通分量的称谓。

Q：全世界友谊图是否为连通图？A：即使本身不具备联通性，其中的连通分量也是巨大的。

5、距离与广度优先搜索法

深度搜索和广度搜索的算法复杂度相同，但是深度搜索用的多，因为广度搜索对存储的要求高，一层中节点太多。

广度优先：从一个节点开始，沿着相连的边，将图的节点一一列举。

二、弱联系和强联系

1、三元闭包（triadic closure）

在一个社交圈内，如果两个互不认识的人有了一个共同的朋友，则他们将来成为朋友的可能性会提高。

三元闭包是社交网络演化的基本结构性原因。

三语闭包产生的原因：机会、信任、动机

三元闭包原理扩展：

①“量”的方面

两个人的共同朋友越多，他们成为朋友的可能性越高

②“质”的方面

两个人与共同朋友的关系越密切，则他们成为朋友的可能性越高。

2、聚集系数

节点A的聚集系数：A的任意两个朋友彼此也是朋友的概率

总对数=节点的度（节点度-1）/2

聚集系数就是三元闭包在一个节点上的属性测度，表示“凝聚力”的大小

聚集系数随时间的变化体现了三元闭包对网络结构的影响趋势。节点附近的三元闭包过程越强，其聚集系数就越大。

题目

3、三元闭包原理的大数据验证

（1）三元闭包原理的表达（定量）

最初表述：如果两个互不认识的人有了一个共用朋友，则他们在未来成为朋友的可能性增加。

转变成：两个互不认识的人的共同朋友数越多，则他俩在未来成为朋友的可能性越大。

（2）验证数据：电子邮件网络≈社会网络

（3）考察网络的演化：考察两个相继的网络快照

考察三元闭包现象的测度：当前共同朋友数与后来成为朋友的概率关系。

得到一个图-->找不连接的边-->计算不连接节点他们的共同朋友-->过一定的时间再做。

题目

4、弱联系的力量

（1）桥：一张图中，已知A和B相连，若去掉连接A和B的边，会导致A和B属于不同的连通分量，则该边称为桥。（断开就不通）

（2）捷径（local bridge）：若边A-B的端点A和B没有共同朋友，则称边A-B为捷径。（断开距离>2）

（3）跨度：没有捷径时的距离。

如果A和B的跨度>2，则A和B之间的边是捷径。

跨度很大的捷径的作用类似于桥。

通过捷径联系的人更可能为你提供工作信息。（找工作问题的第一个解释）

5、强三元闭包

捷径很大程度上可能是弱联系

考虑社交网络中关系的强度-->边的属性

边属性的一种测度：强-弱（强度可以使连续变量）

（1）强三元闭包原理（架设）：如果A-B和A-C之间的关系为强联系，则B-C之间形成边的可能性应该很高

若A有两个强联系邻居B和C，但B-C之间没有任何关系（s或w，即strengh或weak），则称节点A违背了强三元闭包原理。反之，则称A符合强三元闭包原理。

（2）在一定条件下：捷径-->弱联系

若节点A符合强三元闭包，且至少有两个强联系邻居，则与A相连的任何捷径必定是弱联系。

（假设A-B是s，而A有个强联系邻居C，即A-C为s，那么根据强三元闭包，一段时间后B-C会有联系，A-B的跨度为2，与捷径的定义矛盾）

连接关系：强联系、弱联系

结构关系：捷径、非捷径

三元闭包将连接关系和结构关系连接起来了。

（两人的关系强度如何，与两人是否有共同好友相关，但不等价）捷径意味着没有共同朋友，强度为“弱”。

（3）统计推论：共同朋友越多，关系强度越高

6、邻里重叠度

（1）社交网络中，桥、捷径一般不存在-->邻里重叠度（Neighborhood Overlap）

①捷径是邻里重叠度为0的边

②可以把邻里重叠地很低的边粗略的视为捷径

③一种很好的从二到多的数学抽象的例子

目标3：弱联系起到将包含大量强联系的紧密社区连接起来的作用。（方法：从强度最强的关系边开始，按强度的降序逐渐删边；从强度最弱的关系边，按强度的升序，逐渐删除边。发现：从弱的开始删，网络崩的快）

（2）社交网络实验

Facebook的三种连接：相互连接、单向连接、保持关系。

社交网络中好友数目：尽管一个用户可声明关注大量（几百）其，但实际关注的大约在50以下，而真正有联系的则更少，在20以下。

社会网络是用弱系连起来的若干紧密群体。

7、结构洞

（1）嵌入性：一条边的嵌入性为其两个端点共同的邻居数

①嵌入性就是邻里叠度的分子

②捷径就是嵌入性0的边

③嵌入性越大的边相互间的信任就越强；嵌入性越强的边社会资本也越多

节点A：

①聚集系数较高（7/10）

②A关联的边多数具有较大的嵌入性

③处于一个相对比较诚实可信的群体

节点B：

①聚集数较（2/10）

②他关联的边多数具有较小的嵌入性

③结构洞： 两个没有紧密联系的节点集合之间的“空地”

节点B具有的优势：

①信息优势： 可以较早地获得网络中多个互不交叉部分的信息

②创新优势： 处在捷径的一端对创造性有放大功能

③权力优势：所处位置具有某种社交“把关”的机会

启示：有效破坏网络的连通性（以最快最小的代价）：破坏处于结构洞位置的节点或捷径（关键连接）

（2）数字大炮（一种DDoS）（攻的是路由器的BGP协议）

边界网关协议（BGP）

主要用于两个自治系统（AS）间交换路由信息

使用矢量路径机制，路由信息格式：<目的站， AS有序列表（由AS构成的路径） >

UPDATE报文：（发生时机：发生变化时，发送UPDATE报文）

“数字大炮”攻击示意：

攻击的基本原理：

数字大炮的攻击步骤：

① 构建僵尸网络（可预先构建）

② 启动僵尸网络中的计算机之间流量发送，建立它们之间的“路径地图” （拓扑发现），找到众多路共用的连接（关键链路）（可预先构建）

③ 由僵尸网络对关键链路两端路由器BGP协议发动ZMW攻击，使得关键链路处于断开状态

④ 附近路由器会对此作出回应，发送BGP更新消息

⑤ 很短的时间之后，这两个被切断的路由器可能会重新连接，并发送BGP更新信息

⑥ 不断重复（3） ~（5），最后互联网上每一台路由器都会接收到超出自身处理能力的更新消息，从而导致互联网瘫痪

数字大炮的攻击效果：

选好节点，靠网络自身的扩散功能。实验不错，但是实际中很难。这几年很少用，DDoS多用放大协议，即受到的包不大，但是会回过来一个很大的包。

（3）如何找到重要的边

①桥，捷径，邻里叠度很低的边，……

②许多节点之间的最短路径都要经过它

8、介数

节点介数定义为网络中所有最短路径中经过该节点的路径的数目占最短路径总数的比例。

边介数定义为网络中所有最短路径中经过该边的路径的数目占最短路径总数的比例。

（本课中，后面说的介数，都是指最短路径数）

（1）介数：一条边承载的一种“流量”

①两个节点A和B，设想1个单位的流量从A到B，均分到它们之间所有的最短路径上

②K条路径，则每条路径上分得1/k，

③若一条边被m条路径共用，则在它面流过m/k

④所有节点对都考虑后，一条边上的累记流量就是它的介数（betweenness）

（2）破坏连通性

①Girvan-Neman方法： 逐步删除高介数边

（3）介数计算的一种方法-->广度搜索

路径的数目从上往下算

下图：因为A给每个人都发了一个单位流量（可以想数据包），所以每个节点都会留下1个单位流量

介数：很适合描述实际网络中，承载流量的边的信息

三、回顾总结

我的微信公众号是“黄泓图计算分享”，很多朋友反映公众号上看文章不方便，就在上同步一份

图包含两大要素：节点和边。节点和边上都可以有属性，边既可以有方向也可以无向。对于图的建模，可以包含结构上的特征和聚集的特征。特征表征的粒度，可以是节点，边，子图等等。

本文先从最常见的情况讲起：以节点为粒度的结构特征。以节点为粒度的结构特征，往往同时会作为图嵌入（Graph Embedding）算法的输入，从而得到描述节点所在的局部结构的向量。例如度以及三角形的个数，可以作为Role2vec[5]或者GraphSage[6]的输入。这些后面再详谈。

以节点为粒度的结构特征，最简单的是度（degree），也就是一个节点关联的邻居节点的个数。在很多应用中，想必大家都有意无意用过这个特征。

节点的重要性

描述节点重要性的特征，一般有两类：一类是基于一定的定义直接描述的特征，如度，介数中心性和紧密中心性等等。另外一类是源于互联网链接分析的算法，如HITS算法和PageRank算法。

根据定义直接描述的节点重要性

介数中心性（betweeness） 描述的是一个节点作为枢纽节点的重要程度。描述一个节点作为枢纽的重要程度还有别的方法（如HITS，下面会提到），介数中心性采用的是最粗暴的定义方法：一个节点的介数中心性是经过这个节点的最短路径条数与所有最短路径条数的比值。因为定义简单粗暴，所以计算起来也比较麻烦。如果要进行分布式计算的话需要设计特殊的算法。比较好的一个实现来自sparkling graph：

https://githubcom/sparkling-graph/sparkling-graph/tree/master/operators/src/main/scala/ml/sparkling/graph/operators/measures/vertex/betweenness

这里betweeness使用了两个实现，分别是Edmonds[1]和Hua[2]。亲测Hua的实现效率更加高一些，奈何话题太冷，论文没什么人引用。

紧密中心性（closeness centrality） 描述一个节点到图中其他节点的难易程度。取的是这个节点到图中其他节点的距离平均数的倒数。如果这个值比较大，那么说明这个节点到其他节点大部分都是经过很少的几步就行，整个图结构比较紧密。对于这个指标，sparkling graph也有比较好的实现。

三角形计数（triangle count）  是用来描述一个图中的顶点之间聚集密集程度的系数。节点所在的局部结构越密集，三角形个数越多。对于这个指标，spark graphx有比较好的实现。

基于链接分析的节点重要性特征

HITS算法和PageRank算法最初的提出都是用于衡量Web图模型中页面的重要程度。他们基于不同的假设。

用户浏览网页的随机游走模型(Random Surfer Model)

用户浏览网页的随机游走模型(Random Surfer Model)假设用户随机游走网页由两部分构成：

（1）直接跳转：用户进入一个网页a，并且以等概率访问这个网页的链接（假设这个网页有d个链接，则为1/d）

（2）远程跳转（teleporting）：用户浏览到某个程度之后决定不再继续深入，而是输入另外一个网址重新浏览。

PageRank算法

假设：

（1） 数量假设： 一个页面节点接收到的入链数量越多，他就越重要

（2） 质量假设： 如果指向一个页面节点的页面节点重要，这个页面就越重要

基于这样的假设以及random surfer model可以得到PageRank的迭代公式。首先一个页面节点a可能以两者方式受到访问：一种是远程跳转，一种是直接跳转。

假设图中有N个节点，用户有概率1-p会进行远程跳转，则远程跳转的概率是：

进入远程跳转的概率 x 选中这个节点的概率=(1-p)x(1/N)

第二种方式是有其他节点等概率跳转而来。假设节点a的一个邻居b，b自己有degree(b)个邻居，b自己的page rank分数为PR(b)，则b能够给a的分数为PR(b)/degree(b)。a的所有邻居能分给a的page rank分数加起来，再乘以用户进入直接跳转的概率p，就是在直接跳转这种方式下节点a能够得到的page rank分数。

远程跳转和直接跳转两部分分数结合起来，也就是大家一般在博客里看到的page rank迭代公式。

HITS算法

HITS算法认为节点有两个特性：一是节点本身的重要程度，即权威度（Authority）。二是节点作为引向重要节点的枢纽节点的重要程度，即枢纽度（Hub）。

假设：

（1）一个Authority值高的节点应该有很多Hub值高的节点指向

（2）一个Hub值高的节点应该指向很多Authority值高的节点

HITS的迭代方式就是这样Authority值和Hub值迭代相互增强：

（1）一个节点的Authority值是指向他的节点的hub值之和（对应假设1）

（2）一个节点的Hub值是他指向的节点的Authority值之和（对应假设2）

执行1，2直到收敛

如果没有种子集合，HITS的初始值可以所有节点的authority和hub值都设置为1。如果有种子集合，则构图方式为对种子集合进行扩充，凡是和种子集合里面的节点有直接指向关系的节点都扩充进来，然后使用上述的迭代步骤。

应用场景

PageRank可以用于仅仅依靠链接指向判断图中的重要节点。HITS和page rank值本身也可以作为节点特征输入分类模型。例如对于企业违约风险的预测当中，[3]提到基于企业之间的担保关系可以构建一个有向图。这个论文使用了不同的图特征作为输入，发现HITS得到的authority和hub值的特征权重比较大。作者对此的解释是：风险大的企业，需要找很多公司担保，从而authority值高，最后违约率高。风险低，稳健的企业，倾向于担保很多企业，Hub值就会很高。其实单纯从这个角度来讲，直接用节点的出度和入度做特征也是可以的。HITS得到的好处在于可以实现Hub和Authority分值的相互增强。

HITS与PageRank在应用场景上的一个重要区别是HITS可以从一个有标注的种子集合向外扩充得到其他同样相关的节点中的重要节点。[4]使用HITS从一个专家标注的与“时尚”有关的网页地址的种子集合进行扩充，自动对外部关联的网页与“时尚”的相关性进行排序。重要的一点是作者提到PageRank和HITS在使用场景上的重要区别：

（1）PageRank在你有比较完整的链接信息的时候才有效，而HITS可以在链接信息不完整的时候也发挥作用

（2）HITS可以利用人工标注的样本进行挖掘，PageRank不行（除非personalized page rank，不过那是另一个故事了）

引用

[1]Edmonds N , Hoefler T , Lumsdaine A  A space-efficient parallel algorithm for computing betweenness centrality in distributed memory[C]// 2010 International Conference on High Performance Computing, HiPC 2010, Dona Paula, Goa, India, December 19-22, 2010 IEEE, 2010

[2] Hua Q S , Fan H , Ai M , et al Nearly Optimal Distributed Algorithm for Computing Betweenness Centrality[C]// IEEE International Conference on Distributed Computing Systems IEEE, 2016

[3] Niu Z, Cheng D, Yan J,et al A hybrid approach for riskassessment of loan guarantee network[J] Papers, 2017

[4]https://wwwconfluentio/blog/ranking-websites-real-time-apache-kafkas-streams-api/

[5]Ahmed N K , Rossi R , Lee J B , et al Learning Role-based Graph Embeddings[J] 2018

[6]Hamilton W L , Ying R , Leskovec J  Inductive Representation Learning on Large Graphs[J] 2017