基于核心标签的可重叠微博网络社区划分方法

doi:10.3969/j.issn.0372-2112.2017.04.001

电子学报 ›› 2017, Vol. 45 ›› Issue (4): 769-776.DOI: 10.3969/j.issn.0372-2112.2017.04.001

• 学术论文 • 下一篇

基于核心标签的可重叠微博网络社区划分方法

马慧芳^1,2, 谢蒙¹, 何廷年^1,3, 蔺想红¹

1. 西北师范大学计算机科学与工程学院, 甘肃兰州 730070;
2. 中国科学院计算技术研究所智能信息处理重点实验室, 北京 100190;
3. 北京师范大学信息科学与技术学院, 北京 100875

收稿日期:2016-01-08 修回日期:2016-08-01 出版日期:2017-04-25
- 作者简介:
- 马慧芳 女,1981年7月出生,甘肃兰州人.博士,硕士生导师,现为西北师范大学计算机科学与工程学院副教授.研究领域为人工智能、数据挖掘与机器学习.E-mail:mahuifang@yeah.net;谢蒙男,1990年6月出生,河北邢台人.西北师范大学计算机科学与工程学院硕士.研究方向为:互联网数据挖掘与机器学习.E-mail:xiemengh@hotmail.com
- 基金资助:
- 国家自然科学基金 (No.61363058，No.61163039）; 甘肃省青年科技基金 (No.145RJYA259，No.1606RJYA269）; 甘肃省自然科学研究基金 (No.145RJZA232）; 中国科学院计算技术研究所智能信息处理重点实验室开放基金 (No.IIP2014-4）

An Overlapping Microblog Community Detection Algorithm via Core Tags

MA Hui-fang^1,2, XIE Meng¹, HE Ting-nian^1,3, LIN Xiang-hong¹

1. College of Computer Science and Engineering, Northwest Normal University, Lanzhou, Gansu 730070, China;
2. Key Laboratory of Intelligent Information Processing, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China;
3. College of Information Science and Technology, Beijing Normal University, Beijing 100875, China

Received:2016-01-08 Revised:2016-08-01 Online:2017-04-25 Published:2017-04-25
- Supported by:
- National Natural Science Foundation of China (No.61363058, No.61163039); Youth Science and Technology Fund of Gansu Province (No.145RJYA259, No.1606RJYA269); Natural Science Research Fund of Gansu Province (No.145RJZA232); Open Fund of Key Laboratory of Intelligent Information Processing of Institute of Computing Technology, Chinese Academy of Sciences (No.IIP2014-4)

摘要/Abstract

摘要：

针对传统微博社区发现算法内聚低重叠度不可控制等问题，以自顶向下的策略，提出一种基于核心标签的可重叠微博社区发现策略Tag Cut.先利用用户标签的共现关系及逆用户频率对标签进行加权，并基于标签之间的内联及外联关系并将用户的标签进行扩充，然后在整体社区中提取包含某一标签的用户作为临时分组并利用评价函数评估划分的优劣，最后选出最合适的核心标签根据其对应分组与其他分组距离的远近来决定将其划分为新的分组还是并入其他分组.用此策略反复迭代直到满足要求.该算法划分的组由若干个拥有核心标签的分组组成且综合利用微博用户已声明的及隐含的兴趣、用户之间的关注规律、结果的实用性对划分结果进行修正.经真实数据实验表明该方法内聚高社区重叠度可控且拥有实际意义.

关键词: 微博网络, 可重叠社区划分, 核心标签, 用户关注关系, 标签划分

Abstract:

The traditional microblog community detection algorithm has the characteristic of low coupled clustering and the overlapping degree can not be controlled.In this paper,we present a divisive approach for overlapping microblog community detection algorithm via core tags.Firstly,the key idea is to develop a tag weighing strategy by taking advantage of the co-occurrence of tags and inverse user frequency.Then tag correlation can be exploited,which investigates both inter and intra correlation of tags,and the tags for users can therefore be expanded.Users containing certain tag in the whole community are extracted as a temporary group and the quality value is calculated under the current partition.The most appropriate core tag is selected and the corresponding group is then updated until certain requirements are satisfied.The community detected by this algorithm share common core tags and the partition results can be revised based on the explicit and implicit interest of users,together with the users' attention and practical application.Experimental results show that the method is effective and has practical significance.

Key words: microblog network, overlapping community detection, core tag, user attention relationship, tag cut

中图分类号:

TP393.092

马慧芳, 谢蒙, 何廷年, 等. 基于核心标签的可重叠微博网络社区划分方法[J]. 电子学报, 2017, 45(4): 769-776.

MA Hui-fang, XIE Meng, HE Ting-nian, et al. An Overlapping Microblog Community Detection Algorithm via Core Tags[J]. Acta Electronica Sinica, 2017, 45(4): 769-776.

参考文献

[1] Fortunato S.Community detection in graphs[J].Physics Reports,2009,486(3-5):75-174.
[2] Girvan M,Newman M E J.Community structure in social and biological networks[J].Proceedings of National Academy of Science of the United States of America,2001,99(12):7821-7826.
[3] Newman M E.Fast algorithm for detecting community structure in networks[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2004,69(6):066133-1-066133-5.
[4] Palla G,Derényi I,Farkas I,et al.Uncovering the overlapping community structure of complex networks in nature and society[J].Nature,2005,435(7043):814-818.
[5] Latouche P,Birmelé E,Ambroise C.Overlapping stochastic block models with application to the french political blogosphere[J].The Annals of Applied Statistics,2011,5(1):309-336.
[6] Shi C,Cai Y,Fu D,et al.A link clustering based overlapping community detection algorithm[J].Data & Knowledge Engineering,2013,87(9):394-404.
[7] 冷作福.基于贪婪优化技术的网络社区发现算法研究[J].电子学报,2014,42(4):723-729. Leng Zuofu.Discovery algorithm optimization technique based on greed online community[J].Acta Electronica Sinica,2014,42(4):723-729.(in Chinese)
[8] 张桂杰,张健沛,杨静,等.基于链接相似性聚类的重叠社区识别[J].电子学报,2015,43(7):1329-1335. Zhang Guuijie,Zhang Jianpei,Yang Jing,et al.Overlapping community detection based on link similarity clustering[J].Acta Electronica Sinica,2015,43(7):1329-1335.(in Chinese)
[9] 于海,赵玉丽,崔坤,等.一种基于交叉熵的社区发现算法[J].计算机学报,2015,38(8):1574-1581. Yu Hai,Zhao Yuli,Cui kun,et al.Community detection algorithm basedon cross-entropy method[J].Chinese Journal of Computers,2015,38(8):1574-1581.(in Chinese)
[10] 王诗懿,董一鸿,李志超.大规模复杂网络下重叠社区的识别[J].电子学报,2015,43(8):1575-1582. Wang Shiyi,Dong Yihong,Li Zhichao.The identification of over lapping communities in large-scale complex networks[J].Acta Electronica Sinica,2015,43(8):1575-1582.(in Chinese)
[11] 张引,张斌,高克宁,等.面向自主意识的标签个性化推荐方法研究[J].电子学报,2012,40(12):2353-2359. Zhang Yin,Zhang Bin,Gao Kening,et al.Autonomy oriented personalized tag recommendation[J].Acta Electronica Sinica,2012,40(12):2353-2359.(in Chinese)
[12] Ahn Y Y,Bagrow J P,Lehmann S.Link communities reveal multiscale complexity in networks[J].Nature,2010,466(7307):761-764.
[13] 周小平,梁循,张海燕.基于R-C模型的微博用户社区发现[J].软件学报,2014,25(12):2808-2823. Zhou Xiaoping,Liang Xun,Zhang Haiyan.User community detection on micro-blog using R-C model[J].Journal of Software,2014,25(12):2808-2823.(in Chinese)
[14] 孙怡帆,李赛.基于相似度的微博社交网络的社区发现方法[J].计算机研究与发展,2014,51(12):2797-2807. Sun Yifan,Li Sai.Similarity-based community detectionin social network of microblog[J].Journal of Computer Research and Development,2014,51(12):2797-2807.(in Chinese)
[15] Ma Huifang,Jia Meihuizi,Xie meng,et al.A microblog recommendation algorithm based on multi-tag correlation[A].International conference on Knowledge Science Engineering and Management[C].Chongqing,2015.483-488.
[16] 尹丹,高宏,邹兆年.一种新的高效图聚集算法[J].计算机研究与发展,2011,48(10):1831-1841. Yin Dan,Gao Hong,Zou Zhaonian.A novel efficient graph aggregation algorithm[J].Journal of Computer Research and Development,2011,48(10):1831-1841.(in Chinese)
[17] 张伟哲,王佰玲,何慧,等.基于异质网络的意见领袖社区发现[J].电子学报,2012,40(10):1927-1932. Zhang Weizhe,Wang Bailing,He Hui,et al.Public opinion leader community mining based on the heterogeneous network[J].Acta Electronica Sinica,2012,40(10):1927-1932.(in Chinese)

基于核心标签的可重叠微博网络社区划分方法

An Overlapping Microblog Community Detection Algorithm via Core Tags

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

编辑推荐

Metrics

[1]	马慧芳, 陈海波, 赵卫中, 邴睿, 黄乐乐. 融合标签平均划分距离和结构关系的微博用户可重叠社区发现[J]. 电子学报, 2018, 46(11): 2612-2618.
[2]	朱江, 王柏, 吴斌, 李小明. 一种微博用户情感影响者发现模型[J]. 电子学报, 2015, 43(12): 2497-2504.