生物分子网络-基本概念

1、生物分子网络基本概念网络的表示方法顶点(A B C D E F)和顶点之间的边集(AB BC BD CE DE EF)组成的图： (a) 节点和边组成的图；(b) 链表；(c) 邻接矩阵 Distance最短距离 The Distance between two vertices u and v in a graph G is the length of a shortest path between them. When u and v are identical, their distance is defined to be 0. When u and v are unreachable

2、 from each other, their distance is defined to be infinity.“small world” property of short-pathsPeterJaneSarahRalph社会网络：6度分离WWW: 16次点击分离Small wordOne of the phenomenons of real networks is that the average distance through the network from one vertex to another is small compared to the network size.

3、Average Path Length (APL)Small wordAverage distances l for various real networks with size indicated as n介数（Betweenness）介数（Betweenness）介数分为顶点介数和边介数两种 Let st = ts to be the number of shortest paths between two nodes s and t (ss = 1).Let st (v) be the number of shortest paths between two nodes s and t

4、 that goes through node v.Then, the betweenness centrality Cb(v) of any vertex v can be computed as:Clustering CoefficientClustering coefficients take values in the range and it measures the tendency of the network to form highly interconnected regions called Clusters.邻居节点连接个数和所有可能连接个数的比值where d is

5、the degree of v and t is the number of vs trianglesCalculating clustering coefficient of a vertex.vertex v above has d = 6, e = 3 and therefore：Most of My friends know each other!Network modulesER(random) graphsErds和Rnyi in the 1950s and 1960sDegree distribution of a random graph, and an example of

6、such a graph.A random graphFor each pair of vertices (u, v) in the graph: Connect the two vertices with an edge by chance p and do not connect the two vertices by chance 1 p.平均节点度为： d = (N 1)p. 聚类系数为：C = p.Random graphsRandom graphs are a very useful model to compare with the real networks behaviort

7、he ER model differs from real networks in two crucial ways: small network clustering Poisson degree distribution.小世界模型（WS模型）Duncan J. Watts and Steven H. Strogatz ：“Collective dynamics of small-world networks”规则网络回顾一下小世界的由来，可以发现它隐含着两层含义：点与点距离短，聚类系数大（朋友与朋友相互认识）两层含义是矛盾的模型的提出WS模型：规则与随机之间The Scale-free

8、model by Barabsi and AlbertPower-law degree distribution in log-log representation.Power-law degree distribution is characterized by a small number of highly connected hubs. Due to the existence of the central hubs, Scale Free networks are highly connected as compared to a random network.层次网络Many highly connected small