【免费】基于标签传播的语义重叠社区发现算法

需积分: 0 75 浏览量 2022-08-03 17:29:42 上传评论收藏 1.44MB PDF 举报

资源详情

资源评论

资源推荐

第 40 卷第 10 期自动化学报 Vol. 40, No. 10

2014 年 10 月 ACTA AUTOMATICA SINICA Octob er, 2014

基于标签传播的语义重叠社区发现算法

辛宇

杨静

谢志强

摘要语义社会网络 (Semantic social network, SSN) 是一种由信息节点及链接关系构成的新型复杂网络, 为此以节点邻

接关系为挖掘对象的传统社会网络社区发现算法无法有效处理语义社会网络重叠社区发现问题. 由此提出标签传播的语义

重叠社区发现算法, 该算法以标签传播算法 (Latent Dirichlet allocation, LDA) 模型为语义信息模型, 利用 Gibbs 取样法建

立节点语义信息到语义空间的量化映射; 提出可度量节点间相似性的主成分 (Semantic coherent neighborhood propinquity,

SCNP) 模型和语义影响力 (Semantic impact, SI) 模型; 以 SCNP 作为标签传播的权重, 以 SI 作为截断值的参数, 提出一种

改进的 Semantic-LPA (Semantic label propagation algorithm) 算法; 提出可度量语义社区发现结果的语义模块度模型, 并通

过实验分析, 验证了算法及语义模块度模型的有效性及可行性.

关键词语义社会网络, 重叠社区, LDA 模型, 标签传播算法

引用格式辛宇, 杨静, 谢志强. 基于标签传播的语义重叠社区发现算法. 自动化学报, 2014, 40(10): 2262−2275

DOI 10.3724/SP.J.1004.2014.02262

An Overlapping Semantic Community Structure Detecting Algorithm by

Label Propagation

XIN Yu

YANG Jing

XIE Zhi-Qiang

Abstract Since the semantic social network (SSN) is a new kind of complex networks consisting of information nodes

and link relationships, the traditional community detection algorithms which depend on the adjacency in social networks

are not eﬃcient in the SSN. To solve this problem, an overlapping community structure detecting method in semantic

so cial network is proposed based on label propagation. Firstly, the algorithm utilizes the Gibss sampling method to

establish the quantization mapping by which semantic information in nodes can b e mapped into the semantic space, with

the latent Dirichlet allocation (LDA) as the semantic model. Secondly, a principal component SCNP model is proposed

which could measure the propinquity between nodes and the semantic impact model. Thirdly, an improved semantic label

propagation algorithm is put forward, with SCNP as the weight of propagation and SI as the parameter of threshold.

Finally, a semantic model by which the community structure of SSN can be measured is presented. The eﬃciency and

feasibility of the algorithm and the semantic mo dularity are veriﬁed by experimental analysis.

Key words Semantic social network (SSN), overlapping community, latent Dirichlet allocation (LDA), label propagation

algorithm (LPA)

Citation Xin Yu, Yang Jing, Xie Zhi-Qiang. An overlapping semantic community structure detecting algorithm by

lab el propagation. Acta Automatica Sinica, 2014, 40(10): 2262−2275

随着网络通信的发展, 电子社交网络, 如 Face-

收稿日期 2013-08-12 录用日期 2014-02-12

Manuscript received August 12, 2013; accepted February 12,

2014

国家自然科学基金 (61370083, 61073043, 61073041, 61370086,

61402126), 国家教育部博士点基金 (20112304110011, 20122304110

012) 资助

Supported by National Natural Science Foundation of China

(61370083, 61073043, 61073041, 61370086, 61402126) and Na-

tional Research Foundation for the Doctoral Program of Higher

Education of China (20112304110011, 20122304110012)

本文责任编委赵铁军

Recommended by Associate Editor ZHAO Tie-Jun

1. 哈尔滨工程大学计算机科学与技术学院哈尔滨 150001 2. 哈尔

滨理工大学计算机科学与技术学院哈尔滨 150080

1. College of Computer Science and Technology, Harbin En-

gineering University, Harbin 150001 2. College of Computer

Science and Technology, Harbin University of Science and Tech-

nology, Harbin 150080

book、Twitter 等, 已成为人们日常生活中不可分割

的社交渠道. 为丰富用户的 Web 社区生活, 各社交

网站推出了 “社区推荐” 及 “好友圈” 服务. 由此而

生的社区划分及社区推荐算法, 已成为社会网络数

据挖掘研究的热点. 社区划分算法的研究内容可分

为硬社区划分、重叠社区划分及语义社区划分 3 个

阶段. 其中硬社区划分和重叠社区划分研究的出发

点是根据社会网络中节点的关系属性划分关系紧密

“社交群落”, 该领域早期的研究为硬社区划分, 即将

社会网络拆分为若干个不相交的网络

[1]

. 代表算法

如 GN (Girvan-Newman)

[2]

、FN (Fast Newman)

[3]

算法. 随着社会网络应用的发展, 社区结构开始出

现彼此包含的关系, 为此, Palla 等提出了具有重叠

(Overlapping) 特性的社区结构, 并设计了面向重叠

10 期辛宇等: 基于标签传播的语义重叠社区发现算法 2263

社区发现的 CPM (Clique percolation method) 算

法

[4]

. 此后, 许多经典算法孕育而生, 如 EAGLE

[5]

、

LFM (Lancichinetti Fortunato method)

[6]

、COP-

RA (Community overlap propagation algori-

thm)

[7]

、UEOC (Unfold and extract overlapping

communities)

[8]

、蚁群算法

[9]

, 拓扑势算法

[10]

等.

近年来, 社区划分又派生出新的方法, 如遗传算

法

[11−12]

、广义网络社区挖掘算法

[13]

等.

语义社区划分研究的出发点是根据社会网络中

节点语义信息内容 (如微博、社会标签等), 将具有

相似信息内容的节点划分为同一社区. 由于划分的

社区结构基于信息相似性, 所以划分结果更能体现

社区的凝聚性. 又因语义信息需以文本分析为基础,

因此目前的语义社区划分算法大多以 LDA (Latent

Dirichlet allocation) 模型

[14]

作为语义处理的核心

模型. 根据 LDA 模型的应用方式算法可分为 3 类:

1) 关系语义信息的 LDA 分析, 此类算法以网

络拓扑结构作为语义对象, 利用改进的 LDA 模型分

析节点的语义相似性, 将 LDA 分析结果作为社区

推荐及社区划分参数. Zhang 等提出了 SSN-LDA

(Simple social network LDA) 算法, 将节点编号及

关系作为语义信息内容, 将节点的关系相似性作为

训练结果

[15]

. Henderson 等在 SSN-LDA 模型的基

础上融入了 IRM (Inﬁnite relational models)

[16]

模

型, 提出了 LDA-G 算法, 该算法有效地将 LDA 与

图模型相结合, 在社区发现的基础上可进行社区间

的链接预测

[17]

. 随后 Henderson 等在 LDA-G 的

基础上加入了节点多元属性分析, 提出了 HCDF

(Hybrid community discovery framework) 算法,

增加了社区发现结果的稳定性

[18]

. Zhang 等也

在 SSN-LDA 算法的基础上提了面向有权网络的

GWN-LDA (Generic weighted network LDA) 算

法

[19]

及面向层次划分的 HSN-PAM (Hierarchical

social network — Pachinko allocation model)

[20]

算法. 此类算法的优点是结构模型简单, 需要的信息

量较少, 适合处理大规模数据. 缺点是利用的语义信

息并非文本信息, 挖掘的社区不具有文本内容相关

性, 属于利用语义分析的方法进行关系社区划分.

2) 关系 – 话题语义信息的 LDA 分析, 此类算

法以节点的文本信息作为语义对象, 将相邻节点的

文本信息作为先验信息, 使得 LDA 分析的语义相似

性接近现实. 此类算法均以 AT (Author-topic) 模

型

[21]

作为 LDA 分析的基本模型, 代表算法有 Mc-

Callum 等提出的 ART (Author recipient topic) 模

型, 该模型在 AT 模型的基础上加入了链接 (Recip-

ient) 关系采样, 将 AT 模型引入了语义社会网络

分析领域

[22]

. 随后 McCallum 等在 ART 模型的

基础上加入了角色分析过程, 提出了 RART (Rule

author recipient topic) 模型, 扩展了 ART 模型的

在社会计算领域的应用

[23]

. Zhou 等在 AT 模型

中加入了用户节点 (User) 分布取样, 提出了 CUT

(Community user topic) 模型

[24]

. Cha 等根据社

交网络中跟帖人的话题 (Topic) 信息抽取出树状关

系模型, 并利用层次 LDA 算法对树状关系模型中

的文本信息进行建模, 提出了 HLDA (Hierarchical

LDA) 语义社会网络分析模型, 该模型可有效处理

论坛类 (非熟人关系) 网站的用户分类问题

[25]

. 此类

算法的优点是在节点关系基础上结合了文本信息分

析, 其划分的社区具有较高的内部相似性. 缺点是此

类算法仅在文本取样时考虑了网络的关系特性, 缺

少对网络局部社区特性的考虑, 使得划分的社区结

果中出现不连通的现象.

3) 社区 – 话题语义信息的 LDA 分析, 此类算

法在关系 – 话题类算法的基础上加入了社区因素,

将 LDA 模型从邻接关系取样转向了局部区域取

样, 有效避免了关系 – 话题类算法的局部区域不连

通现象, 是成熟化的语义社区划分算法. 代表算法

有 Wang 等提出的 GT (Group topic) 模型, 该模

型是 ART 模型的扩展, 将组 (Group) 取样替代了

ART 模型的链接取样

[26]

. 随后 Pathak 等论述了

链接取样的必要性, 并在 ART 模型的基础上加入

了社区 (Community) 取样, 提出了 CART (Com-

munity author recipient topic) 模型

[27]

. 近年来,

话题 – 社区的关系成为 LDA 模型研究的重点, Mei

等将社区话题分布与社区模块度相结合, 提出了

TMN (Topic modeling with network structure) 模

型并建立了话题 – 社区关系函数, 以指导社区的优

化过程

[28]

. Sachan 等和 Yin 等分别从话题 – 社区分

布和社区 – 话题分布角度, 在社区与话题间构建关

联, 并将其引入了 LDA 模型, 分别提出了 TURCM

(Topic user recipient community model)

[29−30]

及

LCTA (Latent community topic analysis) 模型

[31]

在增加社区划分结果的话题差异性的同时, 增加了

社区划分结果的合理性. 此类算法的优点是语义社

区划分准确性高. 缺点是模型复杂容易产生过拟合

的现象, 由于 LDA 模型需要预先确定先验参数的维

数, 因此, 划分的社区数量需要预先设定, 且不同的

预设社区数量产生的社区划分结果差异较大.

语义社会网络是语义网络和社会网络的结合体,

是由信息节点及社会关系构成的新型复杂网络, 其

宏观概念上具有社会网络的链接关系属性, 微观上

每个节点具有语义信息属性. 因此, 语义社会网络

的语义社区发现算法需要兼顾两方面条件: 1) 语

义社区内部链接关系紧密; 2) 语义社区内部节点的

语义信息相似度高. 为此本文设计了面向语义社

会网络的重叠社区发现算法, 创新建立节点语义信

2264 自动化学报 40 卷

息到语义空间的量化映射, 通过构建可度量节点间

相似性的主成分 (Semantic coherent neighborhood

propinquity, SCNP) 模型以及语义影响力 (Seman-

tic impact, SI) 模型, 建立一种改进的标签传播社

区发现算法, 并提出了评价语义社区划分结果的 SQ

(Semantic Q-modularity) 模型, 最后通过实验, 分

析本文算法参数取值及算法有效性.

1 语义社会网络的 LDA 关系建模

1.1 LDA 关系表示

语义社会网络的语义信息体现在各节点的文本

信息内容上, 每个节点具有节点内部的局部语义信

息, 各节点的信息集合构成网络总体语义信息. 本节

对语义社会网络中的局部语义信息和总体语义信息

的 LDA 建模过程进行描述, 涉及的数学符号如表 1

所示.

LDA 语义数据分别利用 w

w, d

d, z

z 三个向量进行

存储, 其中 w

, d

, z

分别为关键字 i 的编号、所属

节点号及所属话题号, 图 1 为 LDA 算法的 w

w, d

d, z

数据存储结构, 其中阴影部分表示集合内的相同元

素, 如图 1 所示, w

= w

说明 w

, w

为同一单词, d

= d

说

明 w

, w

是同一节点 d

的关键字, 且关

键字 w

在 d

中出现 2 次, z

= z

说明

, w

隶属同一话题 z

, 且关键字 w

在 z

中出现 2 次, z

分别隶属于 d

, d

从对图 1 的分析可知, w

w, d

d, z

z 三者间存在三层

贝叶斯关系, 根据文献 [14] 的文本分析可知, w

w, d

z 的数学描述如下:

1) θ ∼ Dirichlet(α), 节点的话题分布 θ 服从参

数为 α 的狄利克雷分布;

图 1 w

w, d

d, z

z 数据存储结构

Fig. 1 The data storage structure of w

w, d

d, z

2) z

|θ

)

∼ Multinomial(θ

)

), 节点 d

在特

定话题分布下, 出现话题 z

的概率服从多项式分布;

3) λ ∼ Dirichlet(β), 关键字服从参数为 β 的狄

利克雷分布;

4) w

, λ

)

∼ Multinomial(λ

)

), 话题 z

在

特定话题分布下, 出现关键字 w

的概率服从多项式

分布. 图 2 为关键字 w

w, d

d, z

z 的贝叶斯关系图, 其中

箭头指示了 w

, d

, z

的贝叶斯表达过程, 并以 α 和

β 作为全局参数.

图 2 w

w, d

d, z

z 的贝叶斯关系图

Fig. 2 The Bayesian diagram of w

w, d

d, z

1.2 Gibbs 迭代过程

w, z

z 的贝叶斯关系表达式为

P (z

= j|w

)P (w

) = P (w

= j)P (z

= j) (1)

表 1 数学符号说明

Table 1 Mathematical symbols

变量名变量说明

G 全局网络, G

表示网络中的节点 i

|G| 语义社会网络中的节点个数

N 语义社会网络中的关键字个数, N

表示节点 G

的关键字个数

w 关键字的向量, w

为向量 w

w 中第 i 个关键字所对应的编号

d 与关键字的向量 w

w 对应的节点编号向量, d

表示 w

所隶属的节点编号

z 与关键字的向量 w

w 对应的话题编号向量, z

表示 w

所隶属的话题编号, 其最大编号为话题个数 k

)

节点 d

的话题分布概率

(j)

话题 j 中关键字的分布, λ

(j)

表示 w

隶属某一话题 j 的概率, λ

(j)

= P (w

= j)

α 各节点的话题分布先验参数

β 某一话题内部, 关键字分布的先验参数

剩余13页未读，继续阅读

评论收藏

内容反馈

小明斗

粉丝: 25
资源: 329

基于标签传播的语义重叠社区发现算法_辛宇1

评论0

最新资源

基于标签传播的语义重叠社区发现算法_辛宇1

评论0

基于标签传播的语义重叠社区发现算法

一种新的基于标签传播的重叠社区发现算法1

基于标签传播算法在重叠社区发现中的改进1

一种面向语义重叠社区发现的Link_Block算法_辛宇1

基于局部语义聚类的语义重叠社区发现算法_辛宇1

基于随机游走的语义重叠社区发现算法_辛宇1

私募猛人辛宇：市值从5000万干到120亿的“秘笈”.doc.pdf

论文研究-基于LeaderRank的多标签传播重叠社区发现算法.pdf

一种面向语义重叠社区发现的Link-Block算法

基于标签传播概率的重叠社区发现算法_刘世超1

重叠社区检测的加权标签传播算法

基于节点优化复制的重叠社区发现算法

基于野外采样的语义重叠社区检测算法

基于ARTs多采样模型的重叠语义社区检测算法

Hadoop下基于边聚类的重叠社区发现算法研究_方木云1

基于Node2Vec的重叠社区发现算法

基于最大团的层次化重叠社区发现算法_孙成成

基于拓扑结构的密度峰值重叠社区发现算法

最新版ISO/IEC 27001:2022、ISO 27002:2022中英文合集

Goby红队版-win-x64-2.4.7版本

Chrome Header Editor 插件

ISO SAE 21434-2021 中文版.pdf

OpenVAS GVM 中文翻译补丁

安全认证cisp教材全套

现代永磁同步电机控制原理及MATLAB仿真__袁雷编著1

STM32F103C8T6核心板-电路原理图1.PDF

最新资源