基于形式概念分析的博客社区发现 (2013年)
需积分: 10 196 浏览量
2021-05-21
01:47:34
上传
评论
收藏 355KB PDF 举报
Journal of Cornputer Applications
计算机应用，
2013
，
33(
1)
: 189 -
191
, 198
ISSN
1001-9081
CODEN JYIIDU
2013-01-01
http://www.joca.cn
文章编号
:1001
-9081
(2013)01
-0189
-03
doi:l0.
3724/SP.
J.
1087.2013.00189
基于形式概念分析的博害社区发现
刘兆庆，伏玉琛，凌兴宏，熊湘云
(苏州大学计算机科学与技术学院，江苏苏州
215006)
(
*通信作者电子邮箱
20104227072@
suda. edu.
cn)
摘
要:针对拖网算法存在的发现
Web
社区数量过多、社区间页面重复率较高以及严格的社区定义形成孤立社
区等问题，提出一种基于形式概念分析
(FCA)
的博客社区发现算法。根据博客网络之间的链接关系构造概念格，通过
格的代数消解对原始概念格进行等价划分，度量每个划分中概念间外延和内涵的结构相似性进而合并社区核心形成
社区。实验结果表明:测试数据集中社区核心的网络密度大于
40%
的占全部的
83.420%
，合并非土区的网络直径为
3
，
且社区内容丰富程度得到提高。所捉弄法可以有效地运用于博客、微博等社交网络的社区发现，具有显著的应用价
值和现实意义。
关键词:博容丰土区;社区发现;形式概念分析:链接分析;社交网络
中图分类号:
T
P3
9
1.
3;
T
凹
93.094
文献标志码
:A
BIog
community detection based on formal concept analysis
Ll
U
Zhaoqi
吨，
FU
Yuchen
,
Ll
NG
Xinghong
,
XIONG
Xiangyun
(School
0/
Computer
Scie
时
eα
nd
Techrwlogy
,
Sooc
怡甜
University
，
S
田
hou
jiangsu
215
∞
6
，
China)
Abstract:
Several problerns exist in trawling algorithrn, such as
too
rnany Web cornrnunities, high repetition rate between
cornrnunity-cores and isolated cornrnunity forrned by strict definition of cornrnunity.
Th
us, an algorithrn detecting Bl
og
cornrnunity based
on
Forrnal Concept Analysis
(FCA)
was
proposed. FirsÙy, concept lattice was forrned according
to
the
linkage relations between Bl
ogs
, then clusters were divided
frorn
the lattice based on equivalence relation, finally cornrnunities
were clustered in each cluster based on the sirnilarity of concepts. The experirnental results show that, the cornrnunity-cores,
which network density is greater than
40%
, occupied
83.420%
of all in testing data set, the network diarneter of cornbined
cornrnunity is 3
, and the content of cornrnunity gets enriched significanÙy. The proposed algorithrn can be effectively used
to
detect cornrnunities in Blog, rnicro-Bl
og
and other social networks, and it
h
臼
significant
application value and practical
rneanmg.
Key
words:
Blog cornrnunity; cornrnunity detection; Forrnal Concept Analysis
(FCA);
link analysis; social network
0
引言
随着
Web2.0
应用的普及，Bl
og
间通过频繁的链接和信
息交互已经在互联网上建立了一个快速发展的社会网络
[1]
。
通过社区的发现可以帮助用户找到感兴趣的信息，从而对互
联网信息进行组织和分类，以加速用户自发聚集形成社区的
过程，有着显著的现实意义
[2]
。
Web
社区发现算法，主要集中于根据
Web
的链接特性发
现社区
[3]
。典型的链接分析方法包括基于超链接诱导主题
搜索
(Hyperlink-Induced
Topic Search , HITS)
[4]
算法、基于有
向二分图的拖网(
trawling)
[5]
算法和基于流量技术
[6]
的算法。
在基于皿
TS
算法的技术中，社区被看作是由中心页面和
权威页面构成的双视图，对不同主题产生根集合后计算网页
的分值，用主特征向量和非主特征向量分别表示主要的和次
要的社区，但在
Web
环境下计算代价太大，且容易产生主题
偏移
[7]
基于有向二分图的技术将社区抽象为一个二分有向
图，稠密的二分有向图可能包含至少一个社区，通过发现二分
有向图中的完全二分子图来代表社区核心，结果是客观的，且
与主题无关
[8]
基于网络流量的技术将社区定义为社区内页
面之间的链接密度大于社区之间页面链接的密度，将社区的
识别问题等同于解决网络的最大流量/最小割集问题，但是计
算时间受到检索页面的时间影响
[9]
。
其中，拖网算法在穷尽所有二分子图的处理过程中时间
复杂度过高、社区内容匮乏、社区重复率较高以及严格的
Web
社区定义会导致孤立社区[凹]。
针对拖网算法的缺点，本文提出基于形式概念分析的
Blog
社区发现算法，根据Bl
og
网络链接关系构建概念格，通
过格的等价关系对格划分，给定每个划分中社区核心的合并
条件及合并社区的合理性数学推导，从而快速、准确地发现
Blog
社区。
1
形式概念分析
概念格，也称为
Galois
格，又叫作形式概念分析(
Forrnal
Concept Analysis
, FCA)
[11]
，格上每个节点是一个概念，由两
部分组成:外延，即概念所覆盖的实例;内涵，即概念覆盖实例
的共同特征。概念格通过
Hasse
图生动和简洁地体现了这些
概念之间的泛化和特化关系。因此，概念格是进行数据分析
的有力工具。
定义
1
一个形式背景(f
orrnal
context)
是一个三元组
(G,M
,I)
，
其中
:G
是对象的集合
，
M
是属性的集合
，1
是
G
和
M
收稿日期
:2012-07-30
;f~回日期
:2012-08-27
。
基金项目:国家自然科学基金资助项目
(61070122)
。
作者简介:文1J兆庆(1
987
- )
，男，江苏徐州人，硕士研究生，主要研究方向
:Web
数据挖掘、社区发现;
伏玉琛(1
968-)
，男，江苏徐州人，副
教授，博士，主要研究方向:机器学习、智能信息处理;
凌兴宏(1
968
- )
，男，江苏宝应人，副教授，博士，主要研究方向:语义
Web
、机器学习;
熊湘云(1
987
斗，女，江苏连云港人，硕士研究生，主要研究方向:社区结构、
Web
数据挖掘。
评论0
最新资源