R 中的資料探勘演算法/聚類/K-核心
在社交網路分析中，主要關注點之一是識別網路中演員的凝聚子群[檢查拼寫]。例如，友誼關係、出版物引用等等。許多研究和調查都集中在社交網路分析上，包括資料探勘。在大型線上社交網路的行為中找到模式非常重要，這樣幕後的公司就能建立更好的機制以更低的成本處理所有資訊。
像 Orkut、Facebook、Twitter 這樣的線上服務擁有數百萬使用者同時使用他們的服務並與他人互動。即使在不同的服務中，網路行為也是相似的。
人們傾向於以與現實生活中相同的方式互動，在一個稱為“小世界”的結構中，社交網路中的人可以透過少於七步聯絡到任何其他人。這種行為可以用來研究如何預防疾病傳播或預測資訊在社會中傳播的速度。
為了正式描述凝聚群體，引入了幾個概念：集團、n-集團、n-氏族、n-俱樂部、k-復形、k-核心、lambda 集...... 對於大多數這些概念來說，它們在演算法上是困難的，被歸類為 NP 難題。但是，對於核心，存在非常有效的演算法。
處理社交網路時，有幾個任務。上面列出了一些。
基於連結的物件分類 - 我們可以根據物件連結對其進行分類。
物件型別預測 - 我們可以根據連結到該物件的物體來預測物件的型別。
連結型別預測 - 這裡我們想根據連線它的物體來預測連結型別。
預測連結存在性 - 現在我們不想知道關於連結的任何資訊，而是它的存在性。如何預測兩個物體之間何時存在連結？這就是這裡要解決的問題。
連結基數估計 - 有多種方法可以估計連結的基數，例如計算物件的連結數量，或者計算經過物件的最小路徑數量。
物件協調 - 任務是基於連結和屬性檢查兩個物件是否相同。刪除重複例項在許多應用中都是有用的。
群體檢測 - 一項聚類任務。這裡我們想知道一組物體何時屬於同一組。
子圖檢測 - 子圖識別是在網路中找到特徵子圖。這是一種圖搜尋形式。
元資料探勘 - 元資料是關於資料的資料。
本文將解釋的技術是關於社交網路中群體檢測，基於網路中每個節點的度。
圖論中的 K-核心由 Seidman 在 1983 年和 Bollobas 在 1984 年提出，作為一種（破壞性地）簡化圖拓撲結構以幫助分析和視覺化的方法。Batagelj 等人最近將它們定義為以下內容：給定一個圖 G = {V,E}>，其中 V 是頂點集，E 是邊集，K-核透過修剪所有度數小於 K 的頂點（及其對應的邊）來計算。這意味著如果頂點 u 的度數為 du，並且它有 n 個鄰居的度數小於 K，則 u 的度數變為 du − n，如果 K > du − n，它也將被修剪。
此操作對於過濾或研究圖的某些屬性很有用。例如，當你計算圖 G 的 2-核時，你正在切割圖的樹部分中的所有頂點。（樹是一個沒有迴圈的圖）。
注意，圖 G 的 K-核有一個精煉（可能為空），其中任何兩對頂點之間至少存在 K 條路徑。這個概念在社會學[1]中被稱為結構凝聚力，在圖論中被稱為頂點連通性，它透過門格爾定理等價於 K-連通分量，K-連通分量是一個無法透過少於 K 個節點斷開的最大圖。
Butts (2010) 中提出了核的概念如下
令 G = (V, E) 為一個圖，令 f (v, S, G) 對 v ∈ V, S ⊆ V 為一個實值頂點屬性函式（用 Batagelj 和 Zaversnik 的語言）。然後，如果 H 是一個最大集合，使得對所有 v ∈ H，f (v, H, G) ≥ k，則一些集合 H ⊆ V 是 f 的廣義 k-核。通常，f 被選擇為相對於 S 的度量（例如，與 S 中的頂點的連線數）。在這種情況下，得到的 k-核具有直觀的特性，即它們是最大集合，使得每個集合成員都與集合中至少 k 個其他成員相連（以適當的方式）。
基於度的 k-核是識別大型圖中良好連線結構的簡單工具。令頂點 v 的核心數為包含 v 的最高價值核的值。然後，直觀地說，核心數高的頂點屬於相對良好連線的集合（在具有高最小內部度的集合的意義上）。重要的是要注意，雖然給定的 k-核不一定是連通的，但它由本身良好連通的子集組成；因此，k-核可以被認為是相對凝聚子群的並集。由於 k-核是巢狀的，因此自然地認為每個 k-核代表 G 上一個假設的“凝聚表面”的“切片”。（事實上，k-核通常以這種方式視覺化）。
kcores 函式生成基於度的 k-核，用於各種度量（有或沒有邊值）。返回值是基於所選度量的 V 的核心數向量。對於度計算目的，缺失（即 NA）邊將被刪除。
Butts (2010) 提供了一系列關於社交網路分析演算法的 R 實現。這些實現使用“sna”包，如下所示
- 包：‘sna’
- 版本: 2.0-1
- 日期: 2009-06-07
- 標題：社交網路分析工具
- 作者：Carter T. Butts <buttsc@uci.edu>
- 維護者：Carter T. Butts <buttsc@uci.edu>
- 依賴：R (>= 2.0.0), utils
- 建議：network, rgl, numDeriv, SparseM, statnet
- 描述：一系列社交網路分析工具，包括節點和圖級別指標、結構距離和協方差方法、結構等價性檢測、p* 模型、隨機圖生成以及 2D/3D 網路視覺化。
- 許可證：GPL (>= 2)
- URL：http://erzuli.ss.uci.edu/R.stuff
- 倉庫：CRAN
- 日期/釋出: 2009-06-08 07:08:51
要安裝“sna”包，請參見 http://erzuli.ss.uci.edu/R.stuff
kcores 使用 cmode 中指示的中心性度量計算輸入網路的 k-核結構。
kcores(dat, mode = "digraph", diag = FALSE, cmode = "freeman", ignore.eval = FALSE)
one or more (possibly valued) graphs.
dat
"digraph" for directed data, otherwise "graph".
mode
logical; should self-ties be included in the degree calculations?
diag
the degree centrality mode to use when constructing the cores.
cmode
logical; should edge values be ignored when computing degree?
ignore.eval
一個向量，包含每個頂點的最大核心成員資格。
function (dat, mode = "digraph", diag = FALSE, cmode = "freeman",
ignore.eval = FALSE)
{
dat <- as.edgelist.sna(dat, as.digraph = TRUE, suppress.diag = TRUE)
if (is.list(dat))
return(lapply(dat, kcores, dat = dat, mode = mode, diag = diag,
cmode = cmode, ignore.eval = ignore.eval))
if (mode == "graph")
cmode <- "indegree"
n <- attr(dat, "n")
m <- NROW(dat)
corevec <- 1:n
dtype <- switch(cmode, indegree = 0, outdegree = 1, freeman = 2)
if (!(cmode %in% c("indegree", "outdegree", "freeman")))
stop("Illegal cmode in kcores.\n")
solve <- .C("kcores_R", as.double(dat), as.integer(n), as.integer(m),
cv = as.double(corevec), as.integer(dtype), as.integer(diag),
as.integer(ignore.eval), NAOK = TRUE, PACKAGE = "sna")
if (is.null(attr(dat, "vnames")))
names(solve$cv) <- 1:n
else names(solve$cv) <- attr(dat, "vnames")
solve$cv
}
為了說明 k-cores 演算法，將展示一個簡單的案例研究。
想象一群學生在吃飯。他們每個人都可以選擇另一個同學和他一起坐。每個學生都是一個節點，每個坐在一起的可能性都是一條邊。我們想將他們分別分組為朋友。
輸入資料是一個鄰接矩陣，表示學生和友誼的網路。
V1 V2 V3 V4 V5 V6 V7 V8 V9 V10 V11 V12 V13 V14 V15 V16 V17 V18 V19 V20 V21 1 0 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 1 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 1 0 2 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 1 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 1 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 1 0 7 0 0 0 0 0 2 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 8 0 0 0 0 2 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 9 0 0 0 0 0 1 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 1 0 0 0 11 0 0 2 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 12 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 2 0 13 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 14 0 0 0 0 0 0 0 0 2 0 0 0 0 0 1 0 0 0 0 0 0 15 0 0 0 0 0 0 0 0 2 1 0 0 0 0 0 0 0 0 0 0 0 16 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 1 0 0 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 1 18 0 0 0 0 0 0 0 0 2 0 0 0 0 1 0 0 0 0 0 0 0 19 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 2 20 0 0 0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 0 0 0 0 21 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 2 0 0 22 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 1 0 0 0 0 23 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 24 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 1 0 25 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 2 0 0 0 0 26 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 V22 V23 V24 V25 V26 1 0 0 0 0 0 2 0 0 0 0 0 3 0 0 0 0 0 4 0 0 0 0 0 5 0 0 0 0 0 6 0 0 0 0 0 7 0 0 0 0 0 8 0 0 0 0 0 9 0 0 0 0 0 10 0 0 0 0 0 11 0 0 0 0 0 12 0 0 0 0 0 13 1 0 0 0 0 14 0 0 0 0 0 15 0 0 0 0 0 16 0 0 0 0 0 17 0 0 0 0 0 18 0 0 0 0 0 19 0 0 0 0 0 20 0 0 0 0 0 21 0 0 0 0 0 22 0 0 0 0 0 23 0 0 1 0 0 24 0 0 0 0 0 25 0 0 0 0 0 26 0 0 2 0 0
當值為 1 時，表示第一個選擇，而值為 2 表示第二個選擇。
為了從網路中確定每個頂點的最大 k-core，我們有
kcores(people)
其中 "people" 是矩陣。
一個向量，包含每個頂點的最大核心成員資格。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
由於它是一個小型網路，最大 k-core 對應於 k=2，因此沒有明確的組定義。
- 包: ‘RBGL’
- 版本: 1.26.0
- 日期: 2010-10-26
- 標題: 對 BOOST 圖形庫的介面
- 作者: Vince Carey, Li Long, R. Gentleman
- 維護者: Li Long <li.long@isb-sib.ch>
- 依賴: graph, methods
- 建議: Rgraphviz
- 描述: 對 BOOST 庫中包含的圖形演算法的相當廣泛而全面的介面。
BOOST 庫。
- 許可證: Artistic-2.0
- URL: http://www.bioconductor.org
- 倉庫：CRAN
- 日期/釋出: 2010-10-26 12:22:53
kCores(g, EdgeType=c("in", "out"))
- g: 圖形類的例項
- EdgeType: 當 g 為有向圖時，要考慮哪些型別的邊
該實現基於 V. Batagelj 和 M. Zaversnik 於 2002 年提出的演算法。snacoreex.gxl 示例來自 V. Batagelj 和 M. Zaversnik 於 2002 年發表的論文。
一個包含 g 中所有節點的核心編號的向量。
library(RBGL)
con1 <- file(system.file("XML/snacoreex.gxl",package="RBGL"))
kcoex <- fromGXL(con1)
close(con1)
kCores(kcoex)
A C B E F D G H J K I L M N O P Q R S T U
1 2 1 2 3 3 3 3 3 3 3 3 2 2 1 1 2 2 2 2 0
con2 <- file(system.file("XML/conn2.gxl",package="RBGL"))
kcoex2 <- fromGXL(con2)
close(con2)
kCores(kcoex2)
A B C D E G H F
3 3 3 3 3 3 3 3
kCores(kcoex2, "in") A B C D E G H F 0 0 0 0 0 0 0 0
kCores(kcoex2, "out") A B C D E G H F 0 0 0 0 0 0 0 0
BATAGELJ, V. & MRVAR, A. (2002). Generalized Cores. Journal of ACM, v. 5, 2002.
BATAGELJ, V. & MRVAR, A. (2003). An O(m) Algorithm for Cores Decomposition of Networks.
CAREY, V. & LONG, L. & GENTLEMAN, R. (2010). An Interface to the BOOST graph library. http://www.bioconductor.org/packages/release/bioc/html/RBGL.html.
BUTTS, C. T. (2010). Tools for Social Networks Analysis. http://erzuli.ss.uci.edu/R.stuff/.