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 <[email protected]>
- 维护者：Carter T. Butts <[email protected]>
- 依赖：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 <[email protected]>
- 依赖: 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/.