Network Analysis中評估網絡節點重要性的指標

用network來整合生物醫學資料並且使用它來探勘知識是一個非常好的方法，且network的建構具有高度的自由度和知識領域特異性，實際上，有一些拓墣學上的指標可以用來描述特定節點的重要性，這邊介紹11種可以用來描繪節點之於整個網絡關係的算法指標：

Local-based methoed

Local-based的方法一次只考慮單一個節點和他周遭的關係

Degree

最基礎的指標，單個節點的連接數
Deg(v)=|N(v)|

Jeong H, Mason SP, Barabasi AL, Oltvai ZN: Lethality and centrality in protein networks. Nature. 2001, 411: 41-42. 10.1038/35075138.

Maximum Neighborhood Component

MNC(v)=|V(MC(v)|, where MC(v) \ is \ a \ maximum \ connected \ component\ of\ the\ G[N(v)]

Density of Maximum Neighborhood Component

DMNC(v)=|E(MC(v))|/|V(MC(v))|^{ \varepsilon },\varepsilon =1.7

Lin CY, Chin CH, Wu HH, Chen SH, Ho CW, Ko MT: Hubba: hub objects analyzer–a framework of interactome hubs identification for network biology. Nucleic Acids Res. 2008, 36: W438-443. 10.1093/nar/gkn257.

Maximal Clique Centrality (proposed in this paper)

MCC(v)= \sum\nolimits_{C \in S(v)} (|C|-1)!
Przulj N, Wigle DA, Jurisica I: Functional topology in a network of protein interactions. Bioinformatics. 2004, 20: 340-348. 10.1093/bioinformatics/btg415.

Global-based methods

這邊主要是six node ranking method的實現，細節可以閱讀shortest path algorithm和它的generalized form k shortest path algorithm。

Closeness

Clo(v)= \sum_{w \in V}\frac{1}{dist(v,w)}
Sabidussi G: The centrality index of a graph. Psychometrika. 1966, 31: 581-603. 10.1007/BF02289527.

EcCentricity

EC(v)=\frac{|V(C(v)|}{|V|}\times \frac{1}{max\begin{Bmatrix}dist(v,w);w \in C(v)\end{Bmatrix}}

Hage P, Harary F: Eccentricity and centrality in networks. Social Networks. 1995, 17: 57-63. 10.1016/0378-8733(94)00248-9.

Radiality

Rad(v)=\frac{|V(C(v))|}{|V(C(v))|}\times \frac{\sum_{w \in C(v)}( \Delta_{C(v)}+1 - dist(v,w) )}{max\begin{Bmatrix}dist(v,w);w\in C(v)\end{Bmatrix}}
Valente TW, Foreman RK: Integration and radiality: Measuring the extent of an individual’s connectedness and reachability in a network. Social Networks. 1998, 20: 89-105. 10.1016/S0378-8733(97)00007-5

BottleNeck(BN)

BN(v)=\sum_{s \in V}p_{s}(v),where\ p_{s}(v) = 1 \ if\ more\ than\ |V(T_{s})|/4\ paths\ from\ node\ s\ to\ other\ nodes\ in\ T_{s}\ meet\ at\ the\ vertex\ v;otherwise\ p_{s}(v)=0

Stress

Str(v)=\sum\nolimits_{s \neq t \neq v \in C(v)}\delta_{st}(v),where\ \delta_{st}(v)\ is\ the\ number\ of\ shortness\ paths\ from\ node\ s\ to\ node\ t\ which\ use\ the\ node\ v
Shimbel A: Structural parameters of communication networks. The bulletin of mathematical biophysics. 1953, 15: 501-507. 10.1007/BF02476438.

Betweenness

BC(v)=\sum\nolimits_{s \neq t \neq v \in C(v)}\frac{\delta_{st}(v)}{\delta_{st}},where\ \delta_{st}(v)\ is\ the\ number\ of\ shortness\ paths\ from\ node\ s\ to\ node\ t\ which\ use\ the\ node\ v
Freeman L: A Set of Measures of Centrality Based on Betweenness. Sociometry. 1977, 40: 35-41. 10.2307/3033543.

Edge Percolated Component

EPC(v)=\frac{1}{|V|}\sum\nolimits_{k=1}^{1000}\sum\nolimits_{t \in V} \delta_{vt}{k}

Chin CS, Samanta MP: Global snapshot of a protein interaction network-a percolation based approach. Bioinformatics. 2003, 19: 2413-2419. 10.1093/bioinformatics/btg339.

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入：

Gravatar
WordPress.com 標誌

您的留言將使用 WordPress.com 帳號。 ( 登出 /  變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 ( 登出 /  變更 )

取消

連結到 %s