Press "Enter" to skip to content

知识图谱:社区发现算法leiden

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

算法为王系列文章,涵盖了计算机算法,数据挖掘(机器学习)算法,统计算法,金融算法等的多种跨学科算法组合。在大数据时代的背景下,算法已经成为了金字塔顶的明星。一个好的算法可以创造一个伟大帝国,就像Google。

 

算法为王的时代正式到来….

 

关于作者:

张丹, 分析师/程序员/Quant: R,Java,Nodejs
blog:http://blog.fens.me
email: [email protected]

转载请注明出处:

http://blog.fens.me/r-graph-leidan/

 

前言

 

基于知识图谱的技术,已经越来越普遍的应用于各种业务场景中了,比如互联网领域的搜索推荐、智能客服;金融领域的智能风控、反欺诈识别;水利领域的最近的数字孪生建设规划也加入了知识平台的建设。

 

图算法方向,有很多的算法模型,本文将介绍Leiden算法,用于社区检测,帮助我们了解大型复杂网络的结构。新的技术趋势已经打开,抓住时代的机遇,用技术提升社会生产力。

 

目录

 

 

    1. Leiden算法介绍

 

    1. 用R语言加载leidenAlg包

 

 

1. Leiden算法介绍

 

社区检测通常用于了解大型复杂网络的结构。Leiden 算法是一种在大型关系网络上的社区检测算法,leiden算法计算社区之间的节点和边的关系,保证社区内部连接的有效性,并实现社区的分隔。当迭代应用 Leiden 算法时,它收敛到一个分区,在该分区中所有社区的所有子集都被局部最优分配,从而产生保证连接的社区。

 

leidan算法的论文: https://www.nature.com/articles/s41598-019-41695-z

 

Leiden 算法是为了改进 Louvain 算法的缺陷,Louvain 算法可能会发现任意连接不良的社区。 因此,Leiden保证了社区之间的良好连接, 而且算法速度更快,可扩展性更好,并且可以在数百万个节点的图上运行(只要它们可以放入内存)。

 

Leiden 算法包括三个阶段:

 

 

    1. 节点局部移动,快速找到分区

 

    1. 分区细化

 

    1. 基于细化分区的网络聚合,利用非细化分区为聚合网络创建初始分区。 迭代步骤直到收敛。

 

 

2. leidenAlg包算法实现

 

R语言中,已经有了Leiden算法的实现,Leiden算法是在2019年刚推出,R社区的开发效率真是很高!我们可以加载leidanAlg包来使用Leiden算法,结合igraph进行社区发现可视化展示。

 

项目地址: https://github.com/kharchenkolab/leidenAlg

 

首先,安装和加载leidanAlg包。安装过程很简单,如果igraph之前装过,可能会需要升级igraph到高版本。

 

# 安装leidenAlg 和 igraph包
> install.packages("leidenAlg")
> install.packages("igraph")
# 加载程序包
> library(leidenAlg)
> library(igraph)
# 设置工作目录
> setwd("C:/work/R/graph")

 

2.1 社区发现算法

 

首先,我先使用leidenAlg提供的一个数据集exampleGraph,进行算法的测试。

 

# 加载数据集exampleGraph
> data(exampleGraph)
# 查看数据集数据
> exampleGraph
IGRAPH 05dba3a UNW- 100 242 -- 
+ attr: name (v/c), weight (e/n), type (e/n)
+ edges from 05dba3a (vertex names):
 [1] MantonBM1_HiSeq_1-GGAACTTCACTGTCGG-1--MantonBM2_HiSeq_1-CTGATAGAGCGTTCCG-1
 [2] MantonBM1_HiSeq_1-ACGCCAGAGTACCGGA-1--MantonBM2_HiSeq_1-GGAAAGCCAGACGCCT-1
 [3] MantonBM1_HiSeq_1-ATCACGAAGGAGTCTG-1--MantonBM2_HiSeq_1-TTTGCGCGTAGCGCTC-1
 [4] MantonBM2_HiSeq_1-TTTGCGCGTAGCGCTC-1--MantonBM1_HiSeq_1-TTGGCAATCTTGAGAC-1
 [5] MantonBM2_HiSeq_1-TTTGCGCGTAGCGCTC-1--MantonBM1_HiSeq_1-ACGGGTCTCCACGACG-1
 [6] MantonBM2_HiSeq_1-TTTGCGCGTAGCGCTC-1--MantonBM1_HiSeq_1-GTCATTTGTCAGATAA-1
 [7] MantonBM2_HiSeq_1-TTTGCGCGTAGCGCTC-1--MantonBM1_HiSeq_1-CAGGTGCTCCACGTGG-1
 [8] MantonBM2_HiSeq_1-TTTGCGCGTAGCGCTC-1--MantonBM1_HiSeq_1-TTGGCAAGTCAGAATA-1
+ ... omitted several edges

 

可视化展示数据集的网路关系

 

> e<-exampleGraph
# 不现实节点名
> V(e)$label<-""
# 画图
> plot(e)

 

 

从上图中,可以看到整个网络是由多个小的社区组成的,肉眼是可以明显进行划分的。接下来,通过leiden算法,进行社区自动化的分隔。

 

# leidan算法计算
> lc<-leiden.community(e)
# 把不同的社区涂上不同的颜色
> library(RColorBrewer)
> node.cols <- brewer.pal(max(c(3, lc$membership)),"Pastel1")[lc$membership]
Warning message:
In brewer.pal(max(c(3, lc$membership)), "Pastel1") :
  n too large, allowed maximum for palette Pastel1 is 9
Returning the palette you asked for with that many colors
# 画图
> plot(e, vertex.color = node.cols, vertex.label="")

 

 

涂色后,可以直接进行观察,每个社区都刚好形成独立的颜色。leiden算法,可以自动地进行社区的识别。

 

2.2 递归聚类

 

递归 leiden算法, 使用 rleiden.community()函数 构建一个 n 步递归聚类,并返回树型图,用来展示社区各个对象之间的聚类关系。

 

建立深度为2的社区树型结构。

 

> r2 = rleiden.community(e, n.cores=1,max.depth=2)
> rs2<-as.dendrogram.fakeCommunities(r2)
> plot(rs2)

 

 

2.3 权重设置

 

构建一个新的网络关系图谱,我们用于边的权重,对社区划分的计算的影响。

 

首先,建立10节点的图谱,并设置边的连接和方向。

 

# 建立节点
> g <- make_star(10) 
> g<-add_edges(g,c(2,3,3,4, 4,5,2,4,2,5))
> g<-add_edges(g,c(6,7,6,8,6,9))
> E(g)$arrow.size<-0.2
> E(g)$arrow.width<-0.2
# 查看图谱结构
> g
IGRAPH d3bc7a7 D--- 10 17 -- In-star
+ attr: name (g/c), mode (g/c), center (g/n), arrow.size (e/n), arrow.width (e/n)
+ edges from d3bc7a7:
 [1]  2->1  3->1  4->1  5->1  6->1  7->1  8->1  9->1 10->1  2->3  3->4  4->5  2->4  2->5  6->7  6->8  6->9
# 画图
> plot(g)

 

 

给边设置权重,分别把1,2,3以随机数的方式,设置到不同的边上。

 

# 取随机权重,设置边的大小,设置边的颜色
> E(g)$width <- sample(1:3,ecount(g),replace = TRUE)
> E(g)$color<-E(g)$width
> E(g)$width 
 [1] 1 2 1 1 2 1 3 1 3 3 2 3 3 2 3 1 2
# 画图
> plot(g)

 

 

上图中,按照权重的关系,我们把边凃上了颜色,可以查看图中节点和边的值。

 

# 查看图中节点和边的值
> as_data_frame(g)
   from to arrow.size arrow.width width color
1     2  1        0.2         0.2     1     1
2     3  1        0.2         0.2     2     2
3     4  1        0.2         0.2     1     1
4     5  1        0.2         0.2     1     1
5     6  1        0.2         0.2     2     2
6     7  1        0.2         0.2     1     1
7     8  1        0.2         0.2     3     3
8     9  1        0.2         0.2     1     1
9    10  1        0.2         0.2     3     3
10    2  3        0.2         0.2     3     3
11    3  4        0.2         0.2     2     2
12    4  5        0.2         0.2     3     3
13    2  4        0.2         0.2     3     3
14    2  5        0.2         0.2     2     2
15    6  7        0.2         0.2     3     3
16    6  8        0.2         0.2     1     1
17    6  9        0.2         0.2     2     2

 

最后,用leiden算法进行对节点的社区划分并涂色,就能看到最后,被社区分隔的结果。

 

# 根据权重进行社区划分计算,设置节点的颜色
> V(g)$color<-find_partition(g, E(g)$width)
# 画图
> plot(g)

 

 

权重的设置,可以改进leiden算法的社区发现的识别结果,自动地帮我们把强关联社区进行锁定,可以提升智能化的社区发现效率。

 

好的技术,用在合适的场景中,事半功倍。

Be First to Comment

发表回复

您的电子邮箱地址不会被公开。