data / information

計算機科學當中，數據的本身稱作「資料」或「数据」，數據的含義稱作「資訊」或「信息」。

data science

分析數據、挖掘資訊的學問。

這個領域早期稱作data analysis，屬於統計學。近期稱作data science，屬於交叉學科。

大家利用數學知識，替數據設計各種指標，然後證明指標的準確程度，形成統計學。

大家再利用計算機科學知識，替數據創造各種演算法，然後觀察數據的特殊性質，形成資料科學。

data retrieval

資料檢索。存取資料。

data query processing

查詢。從資料庫撈出想要的資料。兩大方向：

query optimization：設計資料結構、設計查詢指令。

top-k query processing：參考各欄位的數值大小，分析利弊，找到前幾名的資料。經典演算法是Fagin's algorithm。

data stream processing

串流。應付源源不絕的資料。兩大方向：

data stream processing：平行處理、分散式處理的機制。

data stream algorithm：即時處理資料，獲得各項統計指標。經典演算法是count-min sketch和HyperLogLog。

database concurrency control

並行。各個資料庫，內容同步一致。

conflict-free replicated data type (CRDT)：並行資料結構與演算法。分為兩種：可交換CmRDT、可整併CvRDT。

data mining（knowledge discovery）

資料探勘。從資料獲得資訊，甚至從資訊獲得知識。經過組織、具備架構的資訊，稱作知識。

資料探勘的工程經驗遠多於科學理論。大多數的方法，缺乏理論依據、缺乏嚴謹的數學證明，想怎麼說、就怎麼說。

這裡收集一些乍聽是專業術語，但是其實缺乏內涵、或者無法使用數學描述、或者源自其他領域，看看就好：

data collection        採集
data curation          庋用
data storage           存儲
data warehousing       倉儲
data integration       整合
data aggregation       聚合
data analysis          分析
data modeling          建模
data acquisition       擷取
data dredging          挖掘
data wrangling         角力
data cleansing         清洗
data augmentation      增強
data publishing        發佈
data compression       壓縮
data transmission      傳輸
data integrity         完整
information security   安全
information retrieval  檢索
information seeking    尋求
information management 管理

frequent pattern mining（association rule mining）

頻率樣式。已知大量集合，找到經常出現的子集合。找到經常出現的資料組合。找到資料欄位的關聯。

用於廣告投放、風險投資、社會研究。從大量資料當中得到資訊，決定政策方針，甚至利用資訊不對稱來獲利。經典範例是尿布、啤酒、星期五。

apriori algorithm：窮舉法。從尺寸最小的子集合開始窮舉。

ECLAT algorithm：改良版本。圖論的DFS。

FP-growth algorithm：改良版本。子集合形成poset。

UVa 12560

ranking（learning to rank）（link analysis）

排名。有向圖的節點排名。每個點賦予名次（分數）。

用於網頁排名、文件關鍵字排名、兩兩比賽結果預測。

大家便宜行事，將名次（連續整數）改成了分數（任意實數）。大家創造浮誇的術語learning to rank，沿用既有的迴歸、分類演算法，鮮少創造演算法，換湯不換藥。

Bradley–Terry model：P(i > j) = sᵢ / (sᵢ+sⱼ)。i勝過j的機率。簡易的人造公式。

PageRank：sᵢ = sum (sⱼ / kⱼ)。各點的分數，等於鄰點分數總和（分數需要除以多重邊數量）。視作馬可夫鏈走∞步，答案是特徵向量。Page是谷歌創辦人的姓名。

hyperlink-induced topic search (HITS)：改良版本，同時使用兩種指標。

SpringRank：min sum (sᵢ - sⱼ - 1)²。均勻繪圖。當i勝過j，則限制相對位置為1。

LambdaMART：迴歸樹。

similarity（similarity learning）

相似度。二分圖的節點間距。每條邊賦予距離。

SimRank：s(a,b) = avg s(in(a),in(b))。各邊的相似度，等於所有入邊兩端點的相似度平均。

recommendation（collaborative filtering）

推薦。二分圖補足成完全二分圖。每條邊賦予分數。

用於購物平台、影音平台、社群平台、搜尋引擎。掌握流行趨勢，發掘第一名、最後一名。根據用戶喜好，推薦喜歡的人事物，以增加人流金流。經典範例是Netflix推薦系統。

explicit feedback：人對物打分數的矩陣，實施矩陣分解。

implicit feedback：人與物是否互動的矩陣，實施矩陣分解。

UVa 12420

data summarization

摘要。歸納資料重點。

下面這段1959年的影片，球隊經理高德納用電腦分析球員投籃位置，整理成一份統計報表。比賽關鍵時刻，教練依據統計報表，派出在某地點命中率最高、投籃最穩定的選手，實施戰術，一舉得勝。本來總是輸球的球隊，當年的勝率由6/16 (37.5%)進步到11/14 (78.6%)。

network

「網路」。就是圖論的圖。

現實世界當中，有許多事物可以表示成網路：社會網路（傳播學）、語義網路（語言學）、生物網路（生態學）、代謝網路（生理學）、運輸網路（運輸學）、通訊網路（電信工程）、……。

network science

分析事物關聯的學問。

這個領域早期稱作social network analysis，屬於人文學科。近期稱作network science甚至complex system，屬於交叉學科。

社群網站興起，大家利用圖論演算法挖掘資訊。然而既有演算法的時間複雜度太高，無法投入實用。因此大家重新創造自己想要的數學性質、重新發明時間複雜度極低的近似演算法，形成新流派。

知名函式庫NetworkX。知名工具Neo4j。

network measure

度量指標。大家發明各種指標，描述網路蘊含特質。

對象：一個點、一對點、一張圖。
原理：度數（鄰邊數量、鄰邊權重總和）
　　　路徑（最短路徑數量、最短路徑長度）

已經有人整理了許多指標。以下是論文名稱。

Graph Measures and Network Robustness
Graph Metrics for Network Robustness—A Survey
Characterization of Complex Networks: A Survey of Measurements
Network Robustness Revisited

已經有人整理了許多方向。以下是論文名稱。

Sampling from Large Graphs

這個主題早期稱作social cohesion，近期稱作network measure甚至complex network characterization。

network measure: degree

援引了圖論的度數。時間複雜度約O(V+E)。

degree: deg(i) = ∑j { Aᵢⱼ }

度數。一個點的鄰邊數量。

neighbor connectivity: n(i) = ∑j∈adj(i){ deg(j) } / deg(i)

鄰居連結程度。鄰點度數平均。

reciprocity: r(i,j) = AᵢⱼAⱼᵢ / E

互惠程度。來回邊（長度為2的環）、所有邊，數量比值。

clustering coefficient: c(i) = triangle(i) / P(deg(i),2)

where triangle(i) = ∑j,k { AᵢⱼAⱼₖAₖᵢ }

合群程度。三角形、兩鄰邊（三角形數量上限），數量比值。

network measure: degree correlation

援引了統計學的相關係數。時間複雜度約O(V²)。

common neighbors: n(i,j) = ∑k { AᵢₖAₖⱼ } = [A²]ᵢⱼ

共同鄰居數量。相鄰矩陣，橫條與直條的點積。

matching index: m(i,j) =∑k≠i,j{ AᵢₖAⱼₖ } / (∑k≠j{ Aᵢₖ } + ∑k≠i{ Aⱼₖ } )

匹配程度。共同鄰邊、其餘鄰邊，數量比值。

neighbor similarity: s(i,j) = Cos[[—Aᵢₖ—], [—Aₖⱼ—]] = n(i,j) / sqrt(deg(i)deg(j))

鄰居相似程度。相鄰矩陣，橫條與直條的Salton's consine similarity。

X = [ Aᵢ₀ Aᵢ₁ ... ]
Y = [ A₀ⱼ A₁ⱼ ... ]
Dot[X,Y] = sum XₖYₖ
Norm[X] = sqrt(Dot[X,X])
Cos[X,Y] = Dot[X,Y] / (Norm[X] Norm[Y])

assortativity: a(G) = Corr[[—indeg(i)—], [—outdeg(i)—]]

相配程度。入度與出度的Pearson correlation coefficient。

常見用法：計算兩群點的相配程度。兩個導出子圖，點數相同，一個取出度，一個取入度，計算相關係數。

X = [ indeg(v₀)  indeg(v₁)  ... ]
Y = [ outdeg(v₀) outdeg(v₁) ... ]
E[X] = ∑ { indeg(i) } / V
E[Y] = ∑ { outdeg(i) } / V
Cov[X,Y] = E[(X-E[X])(Y-E[Y])]
Var[X] = E[(X-E[X])²]
Corr[X,Y] = Cov[X,Y] / sqrt(Var[X] Var[Y])

modularity: m(G) = ∑i,j { edge(i,j) - (deg(i) × deg(j) / 2E) } / 2E

模組程度。任意兩點之間的邊數、期望邊數，兩者差距。

原理是Markov chain走k步，一次泰勒近似。詳情請見專著《A Guide to Temporal Networks》。

常見用法：計算一種分割方式的模組程度。每份導出子圖分別計算模組程度，求得總和。

network measure: shortest path

援引了組合最佳化的最短路徑。時間複雜度約O(V(V+E))。

efficiency: e(i,j) = 1 / dist(i⤳j)

效率程度。兩點之間的最短路徑長度倒數。

communicability: c(i,j) = #{ dist(i⤳j) = k }

溝通程度。兩點之間長度為k的最短路徑數量。

closeness: c(i) = 1 / ∑j≠i dist(i⤳j)

封閉程度。一個點到其他點的最短路徑長度總和倒數。

betweenness: b(i) = ∑s,t≠i{ #(s⤳i⤳t) / #(s⤳t) }

中介程度。穿過一個點的最短路徑數量，所佔比值。

network measure: random walk

援引了代數圖論的相鄰矩陣和遞移閉包、線性代數的特徵值、機率論的隨機過程和馬可夫鏈。時間複雜度約O(V³)，實在太高，實務上鮮少使用這類指標。

reachability: Aᵏ

抵達程度。一個點走k步可以到哪些點。

transitivity: A* = I + A + A² + ... = (I - A)⁻¹

遞移程度。一個點分別走1...∞步可以到哪些點。

Katz centrality: katz(i) = ∑j [(I - αA)⁻¹]ᵢⱼ

核心程度。一個點分別走1...∞步可以走到多少點。步數越大、該點權重越小，呈指數倒數成長。求加權後的點數總和。

PageRank: pr(i) = (1-d)/V + d ×∑i∈adj(j){ pr(j) / outdeg(j) }

擴散程度。均勻分布，均勻擴散∞步，最終分布。

原理是Markov chain走∞步。transition matrix的某個特徵向量。初始向量在每個特徵向量上面的分量，比例最大者。

eigenvector centrality: x(i) = ∑j∈adj(i){ x(j) } / λ

均衡程度。adjacency matrix最大的特徵值。

algebraic connectivity

連結程度。Laplacian matrix第二小的特徵值。

network robustness

穩健程度。大家發明各種指標，描述網路結構強弱。

network robustness: sampling

援引了圖論的隨機圖。時間複雜度約O((V+E)T)。

reliability: r(G) = ∑i (1-p)ⁱ pᴱ⁻ⁱ f(i)

依賴程度。2ᴱ種子圖，其為「連通圖」的數量（平均值）。並考慮子圖各邊出現機率（原圖各邊刪除機率）。

邊故障機率p。剩下i條邊的機率(1-p)ⁱ pᴱ⁻ⁱ。剩下i條邊仍然連通的可能性數量f(i)。

site percolation: s(G) = ∑i C(V,i) (1-p)ⁱ pⱽ⁻ⁱ s(i)

滲濾程度。2ⱽ種導出子圖，其「最大連通分量」的點數（平均值）。並考慮導出子圖各點出現機率（原圖各點刪除機率）。

點故障機率p。剩下i個點的機率(1-p)ⁱ pⱽ⁻ⁱ，任取i個點的可能性數量C(V,i)。其最大連通分量點數（平均值）s(i)。

因為導出子圖數量呈階乘成長，所以演算法採用隨機抽樣。此處介紹Newman–Ziff percolation algorithm。

特定p：掃描所有點，各點刪除機率均為p。遍歷所有點，計算最大連通分量點數。重複T次，統計平均值，作為s(G)。

所有p：逐次增加一點，各點機率均等。disjoint-sets forest，計算最大連通分量點數。重複T次，各種點數的導出子圖，分別統計平均值，作為s(i)。代入公式，得到s(G)。

network generation

生成。建立網路。

Erdős–Rényi model (binomial graph)：完全圖，每條邊出現機率均為p，選出m條。特色是完全隨機。

triadic network：每回合添加一個點i，再添加m>1條鄰邊，第一條連往隨機點j。其他條以機率p連往j點隨機鄰居、機率1-p連往隨機點。特色是容易形成三角形，朋友的朋友也是朋友。

Barabási–Albert model (scale-free network)：最初有m₀個點。每回合添加一個點i，再添加m≤m₀條鄰邊ij。每條邊以機率pᵢⱼ = deg(j) / ∑ { deg(k) }連接成功。特色是密者越密，成群結黨。

Watts–Strogatz model (small-world network)：所有點排成一圈。每個點添加k條邊，連向最鄰近的k個點。每條邊以機率p連接成功、機率1-p連往圖上隨機點。特色是形成大量相鄰小團體。

community detection

社群偵測。社群是緊密連接的子圖，內部聯繫強，外部聯繫弱。社群的相關詞彙還有cluster、topical locality、homophily。社群沒有標準定義，大家視情況而定。比方來說：

community：內部度數高、外部度數低。
strong community：內部各點鄰邊數量，皆多於外部。
weak community：內部各點鄰邊總和，多於外部。

label propagation algorithm：各點貼上不同標籤，逐步統一標籤。隨機順序掃描各點，該點標籤變成鄰居眾數。若眾數不只一個，則任選一個。不斷重新掃描，直到所有標籤不再改變。即是後面章節的majority model。

Louvain method (modularity optimization)：各點隸屬不同社群，逐步統一社群。隨機順序掃描各點，該點社群變成其中一個鄰居，使得modularity上升最多。不斷重新掃描，直到所有社群不再改變。

community structure finding

尋找社群架構。建立階層架構圖。

可以沿用上個小節的演算法，收縮社群、得到新圖、遞迴求解。

highly connected subgraphs clustering：minimum cut，兩側分別遞迴。

common nearest neighbors clustering：逐步連接common neighbors最多的那一條邊。

Girvan–Newman algorithm：逐步刪除betweenness最大的那一條邊。

community decomposition

社群分解。建立架構圖。

breadth-first search tree：距離相同的點，位於相同的層。

k-shell decomposition (k-core decomposition)：從k = 0開始，刪除所有度數小於等於k的點，刪除的點形成k-shell，未刪除的點形成(k+1)-core。k逐步加一，直到刪除所有點。

k-clique percolation：找到所有大小為k的clique，作為社群。社群共用k-1點，就連一條邊。

network dynamics

動態系統。大家發明各種規則，描述網路傳播。

總共N種狀態，每個點擁有一種狀態。每個回合，根據規則，將自身狀態複製給其他點。換句話說，將自身狀態設定成其他點。

這個主題早期稱作social influence，近期稱作network dynamics甚至complex network system。

network dynamics: neighbor

援引了微分方程的動態系統。時間複雜度約O((V+E)T)。

voter model：自己變成隨機鄰居。

majority model：自己變成鄰居眾數。

threshold model：鄰居眾數達到臨界值，才變成鄰居眾數。

independent cascade model：自己感化每個鄰居，成功機率pᵢⱼ，然後自己永久失效。換句話說，自己被每個鄰居感化，成功機率p(i) = 1 - ∏j is active{ 1 - Pⱼᵢ }。

兩種狀態：有效、失效。
active：感化每個鄰居，成功機率pᵢⱼ，然後變成inactive。
inactive：不再感化與被感化。

SIR model：傳染疾病模型。

三種狀態：易感染susceptible、感染infectious、康復免疫recovered。
機率a，最初讓susceptible變成infectious。
機率b，分別讓infectious的每個鄰居從susceptible變成infectious。
機率c，讓infectious變成recovered，往後不再改變自己狀態與別人狀態。

coevolution model：共同演化模型。

隨機順序掃描各點。各點任選一條鄰邊，選擇狀態不同者。
selection：機率p，起點改成連向終點鄰居，選擇狀態相同者。
influence：機率1-p，起點狀態變成終點狀態。