Week1 是圖論上的基礎，和一些特別的圖例如 bipartite graph, 它的L-Bipartite graph (weighted) projection。解釋過什麼是Graph、Node、Edge、Degree等基本詞彙後，網絡和圖的稱呼會交替出現。
要引用一張圖，可以有以下方法：
https://networkx.github.io/documentation/networkx-1.10/reference/readwrite.html
import networkx as nx import numpy as np import pandas as pd %matplotlib notebook G1 = nx.Graph() G1.add_edges_from([('A', 'B'), ('A', 'C'), ('A', 'D'), ('A', 'E'), ('B', 'D'), ('B', 'E'), ('D', 'E'), ('C', 'F'), ('C', 'K'), ('F', 'H'), ('F', 'K'), ('F', 'J'), ('J', 'K')]) G2 = nx.read_edgelist('G_self_edgelist.txt', delimiter=',', data=[('Weight', int)]) G_df = pd.read_csv('G_self_edgelist.txt',delimiter=','header=None, names=['n1', 'n2', 'weight']) G3 = nx.from_pandas_dataframe(G_df, 'n1', 'n2', edge_attr='weight') nx.info(G) G.nodes(data=True) G.edges(data=True) nx.draw_networkx(G),
Week 2
「群聚分析」研究的是，網絡中的點互相連結形成群聚的程度。典型由多人形成的群聚，會是圖中一部分由所有點互相連結的完全子圖。而最簡單的一個群聚是由互相認識的三個人形成的「Triadic Closure」，對更複雜的圖的幾種群聚系數，量度的設計是由這形式推展出來的。
首先是圖中某個頂點的「局部群聚系數」－Local Clustering Coefficient，它的大概主意是去計算：與某頂點相連的近鄰們，能夠互相連結成配對的比例。即以下兩者之比：
$v$的近鄰間實際形成的邊數：$|(X,Y)| s.t. X,Y \in N(v)$
$v$的近鄰間最大可能形成的邊數：$\frac{d_v(d_v - 1)}{2}$
當考慮整個圖的整體群聚程度－「全局群聚系數」時，有兩種方法，一個是所有點的局部群聚系數平均起來－「Average Local Clustering Coefficient」。另一個稱為 「Transitivity」 的量度方法是數算圖中由三點形成的「閉三角組」和「開三角組」的比例:
Transitivity = 3 * number triangle / number of opera triad
而兩套方法的分別是對 Transitivity 對 高Degree 的點有較大比重。
nx.average_clustering(G)
nx.transitivity(G)
「距離」的量度方面，與圖的有關的名詞定義有以下：
Distance(u,v): u,v 的最短路徑上的邊數
Average Distance(G): 一張圖所有點之間的平均距離
Eccentricity(u)：從某點出發，到達最遠一點的距離
Diameter(G)：最大的eccentricity
Radius(G)：最小的eccentricity
Periphery(G)：Diameter的點
Center(G)：Radius的點
nx.shortest_path_length(G, node)
nx.average_shortest_path_length(G)
nx.diameter(G)
nx.periphery(G)
nx.center(G)「連結度」是一個在例如交通航線方面會留意的量度，因為這些網絡的一個關注，是網絡會否容易囚個別點線的受攻擊而斷開。在 Undirected graph 容易一眼看清楚一張圖是否相連；但在邊是有方向性的 Directed Graph 中，可以分為 weakly connected 和 strongly connected。 如果從任何一點出發，按邊的方向走可以到達任何點的話，才算是strongly connected。
Node Connectivity 是指要移走多少個點，才可以令網絡分離。
Edge Connectivity 是指要移走多少條邊，才可以令網絡分離。
當一幅網絡要移走更多的點／邊，才可以令網絡分離的話，就會形容網絡為更「Robust」。
nx.is_connected(G.to_undirected())
nx.is_strongly_connected(G)
nx.strongly_connected_component_subgraphs(G)
nx.minimum_node_cut(G, center, node)Week 3
中心性分析是找出圖的「中心」，以下是三種關於中心的定義：
「點度中心性」 - Degree Centrality 認為網絡的中心點，應該是最多點連接著的。如果一個節點與其他節點之間存在直接聯繫，那麼該節點就居於中心地位
$C_{deg}(v) = \frac{d_v}{|N|-1}$
「接近中心性」 - Closeness Centrality 認為網絡的中心點，應該是儘量對圖的每一點來說都是接近的。
$C_{close}(v) = \frac{|N|-1}{\sum_{u\in N\setminus{v}}d(u,v))}$
「中間中心性」 - Betweenness Centrality 認為網絡的中心點，應該是把其他點連結起來的。
$C_{btw} = \sum_{s,t\in N}\frac{\sigma_{s,t}(v)}{\sigma_{s,t}}$
$\sigma_{s,t}(v)$ 是 連結 s,t 的最短路徑，而路徑上包括 v 在內的數目。因為點的數目愈多，中心性的計算出來的值會愈大，所以有這樣的 Normalization: divided by: 1/2(N-1)(N-1) in undirected graph; (N-1)(N-1) in directed graph
nx.degree_centrality(G1)[node]
nx.closeness_centrality(G1, normalized=True)[node]
nx.betweenness_centrality(G1, endpoints=False, normalized=True)[node]
「Page Rank」 和 「HITS」 是兩套計算網絡中各個節點地位的演算法。Page Rank 出名在於是 Google 起步時所研發的演算法的基礎，由 Google 創辦人 Larry Page 建立，為網絡上每個網頁計算一個評分，讓人可以搜尋到更有用的網頁，令 Google 超越當時已有的其他互聯網入門網站，以強大搜尋引擎的身份開始逐間漸在 IT 業領先。網絡世界上除非你直接知道網址，否則多數時間都是透過層層的連結去到達某網頁。Page Rank 認為，愈多被別人所指向的網頁，應該有更高的排名。想像開始時有人隨便進入一個網頁，然後隨機按頁面中的一條連結進入另一個網頁，如是不斷重複，step n 足夠大的話，他身處某頁面的機率是跟這個網絡的結構有關的。愈多被人引用的頁面有愈高機會有某人停留，愈少人指向的頁面就排名愈低。
HITS (Hyper-link-induced topic search) 為每個節點計算兩個分數 －「Hub Score」、「Authority Score」。Hubs 反映的是它能否指向其他好的節點；Authority 反映的是其他高品質節點如何指向它；開始時賦予每個節點的hub值和authority值都為 1，然後重複更新：
Hubs = Sum of the authority scores of each node that it points to.
Auth = Sum of the hub scores of each node that points to it.
# Page Rank pr = nx.pagerank(G2, alpha=0.85)# HITShits = nx.hits(G2) hits[0][node], hits[1][node]
Week 4
除了Descriptive外，一個有關Predictive的問題是，能否預測新的連結會在哪些點之間發生呢？ 例如，Facebook應該推薦什麼人給你，認為他們是你可能認識的人?
一個建立新連結的模型是 「Preferential Attachment Model」，它符合一個現實世界的觀察：多朋友的人，給他更多朋友；愈少朋友的人，就愈小機會有新的朋友。如果把這種圖的 Degree Distribution 繪劃出來，有一個稱為 Power Law的 觀察：$P(k)=C k^{-\alpha}$。要模仿這種特徵的一個模型是，對選定的一個新節點，它連接到另外某點的機率，正比於該另外的點的Degree。
除了這個對"我的朋友很少"的人的殘酷的現實觀察外，「Small World Network」形容了兩個特徵：短的 Average Shortest Path 和 大的 Clustering Coefficient。雖然世界上大部分人並不相識，但要把任意兩個人連結起來時所需的中間人數量，比隨機的連結情況下所想像的少，這個發現就像是Milgram的6度分隔的社會實驗結果。 而 Clustering 的現象就是通常你有幾個朋友圈，圈中的人互相認識－形成群聚的。
要隨機生成這類圖：
# 方法一：Preferential Attachment Model。產生n個點的網絡，每次產生的新點有m個連結。G = nx.barabasi_albert_graph(n, m)# 方法二：G = watts_strogatz_graph(n, k, p)從n點的圓環，而每個點連著最接近的k點開始。然後，每條邊有p的機會被改寫。Small World Network。#方法二的變奏 connected_watts_strogatz_graph(n, k, p, t) newman_watts_strogatz_graph(n, k, p)
而對於一個既有的網絡，就可以為任意兩點計算評分，以衡量之間最有可能形成新連結的兩點。
Preferential Attachment Score : 用上面提到的想法，愈高Degree的點之間愈容易出現連結。
$\text{pref_attach}(X,Y) = |N(X)||N(Y)|$
Common Neighbors：取決於共同近鄰的數目多寡
$\text{com_neigh}(X,Y) = |N(X) \cap N(Y)|$
Jaccard Coefficient：Normalized 的Common Neighbors
$\text{Jacc_coeff}(X,Y) = \frac{N(X) \cap N(Y)}{N(X) \cup N(Y)}$
Resource Allocation：信息可以透個共同近鄰而傳遞的比率
$\text{Res_alloc}(X,Y) = \sum_{u\in N(X) \cap N(Y)} \frac{1}{|N(u)|}$
Adamic Adar Index：用log計算的Resource Allocation
$\text{Adamic_adar}(X,Y) = \sum_{u\in N(X) \cap N(Y)} \frac{1}{log|N(u)|}$
有時有些網絡上的點可以分組，而同組之間較容易形成連結的話。對於這種已知節點有"community label"的情況，又有兩套變種方法：當 u 與 X,Y 同組時，f(u)=1；否則 f(u)=0；
Common Neighbor Soundarajan-Hopcroft：
$\text{cn_soundarajan_hopcroft}(X,Y) = |N(X) \cap N(Y)| + \sum_{u\in N(X) \cap N(Y)} f(u)$
Resource Allocation Soundarajan：
$\text{ra_soundarajan_hopcroft}(X,Y) = \sum_{u\in N(X) \cap N(Y)} \frac{f(u)}{|N(u)|}$
nx.preferential_attachment(G)
nx.adamic_adar_index(G)
nx.resource_allocation_index(G)
nx.jaccard_coefficient(G)
nx.within_inter_cluster(G)
nx.cn_soundarajan_hopcroft(G)
nx.ra_index_soundarajan_hopcroft(G)
沒有留言:
張貼留言