1、生物分子網(wǎng)絡(luò)基本概念網(wǎng)絡(luò)的表示方法頂點(A B C D E F)和頂點之間的邊集(AB BC BD CE DE EF)組成的圖： (a) 節(jié)點和邊組成的圖；(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社會網(wǎng)絡(luò)：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介數(shù)（Betweenness）介數(shù)（Betweenness）介數(shù)分為頂點介數(shù)和邊介數(shù)兩種 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.鄰居節(jié)點連接個數(shù)和所有可能連接個數(shù)的比值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.平均節(jié)點度為： d = (N 1)p. 聚類系數(shù)為：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”規(guī)則網(wǎng)絡(luò)回顧一下小世界的由來，可以發(fā)現(xiàn)它隱含著兩層含義：點與點距離短，聚類系數(shù)大（朋友與朋友相互認識）兩層含義是矛盾的模型的提出WS模型：規(guī)則與隨機之間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.層次網(wǎng)絡(luò)Many highly connected small