基于动态有噪网络的增量社团发现算法

doi:10.3969/j.issn.1000-3428.2014.02.036

计算机工程

基于动态有噪网络的增量社团发现算法

董哲，伊鹏，扈红超

(国家数字交换系统工程技术研究中心，郑州 450002)

收稿日期:2012-12-06 出版日期:2014-02-15 发布日期:2014-02-13
作者简介:董哲(1989－)，男，硕士，主研方向：复杂网络；伊鹏，副教授；扈红超，讲师、博士
基金资助:
国家“863”计划基金资助项目“面向三网融合的统一安全管控网络”(2011AA01A103)

Incremental Community Detection Algorithm Based on Dynamic Noisy Network

DONG Zhe, YI Peng, HU Hong-chao

(National Digital Switching System Engineering & Technological R&D Center, Zhengzhou 450002, China)

Received:2012-12-06 Online:2014-02-15 Published:2014-02-13

摘要/Abstract

摘要： 在动态社会网络中，诸如垃圾邮件之类的噪声会影响网络的稳定性，导致其社团结构难以被准确发现。针对该问题，提出一种采用增量结构的社团发现算法。利用相对熵处理噪声，通过改进的增量算法发现社团结构。实验结果表明，该算法针对不同动态社会网络的发现性能均优于传统动态社团发现算法，其模块度可达到0.8左右，互信息值变化也较平稳，可有效避免噪声对算法性能的影响。

关键词: 动态社会网络, 社团结构, 稳定性, 噪声滤除, 相对熵, 增量算法

Abstract: The exist noises like junk mails in dynamic social network which affect the stability of the dynamic social network. The existed dynamic community detection algorithms cannot identify this kind of community structure correctly. Aiming at this problem, an algorithm called preFilter is proposed to solve the problems that the community structure cannot be identified correctly with the noise in the dynamic social network. It uses the relative entropy to filtering the noise in dynamic social network, then an improved incremental algorithm is proposed to identify community structure in the dynamic social network. Experimental results show that preFilter can reach a better performance than other dynamic algorithms, and get a stable NMI value and the modularity Q value which reaches about 0.8. This algorithm can avoid the influence of the noise effectively and performs effectively and accurately in identifying community structures in dynamic social networks.

Key words: dynamic social network, community structure, stability, noise filtering, relative entropy, incremental algorithm

中图分类号:

TP18

董哲，伊鹏，扈红超. 基于动态有噪网络的增量社团发现算法[J]. 计算机工程, doi: 10.3969/j.issn.1000-3428.2014.02.036.

DONG Zhe, YI Peng, HU Hong-chao. Incremental Community Detection Algorithm Based on Dynamic Noisy Network[J]. Computer Engineering, doi: 10.3969/j.issn.1000-3428.2014.02.036.

http://www.ecice06.com/CN/Y2014/V40/I2/166

参考文献

参考文献 [1] Han Jiawei, Kamber M. Data Mining: Concepts and Tech- niques[M]. San Francisco, USA: Morgan Kaufmann Publishers, 2001. [2] Girvan M, Newman M E J. Community Structure in Social and Biological Networks[J]. Proceedings of the National Academy Sciences, 2002, 99(12): 7821-7826. [3] Palla G, Pollner P, Barabasi A, et al. Social Group Dynamics in Networks[M]//Adaptive Networks. [S. l.]: Springer, 2009: 11-38. [4] Newman M E J, Girvan M. Finding and Evaluating Com- munity Structure in Networks[J]. Physical Review E, 2004, 69(2). [5] Alper C, Yao So-Zen. Spectral Partitioning: The More Eigenvectors, The Better[C]//Proceedings of ACM/IEEE Design Automation Conference. San Diego, USA: [s. n.], 1994: 195-200. [6] Rosvall M, Bergstrom C T. An Information Theoretic Frame- work for Resolving Community Structure in Complex Networks[J]. Proceedings of the National Academy of Sciences, 2007, 104(18): 7327-7331. [7] van Dongen S. Graph Clustering by Flow Simulation[D]. Utrecht, Holland: University of Utrecht, 2000. [8] Berger-Wolf T Y, Sata J. A Framework for Analysis of Dynamic Social Networks[C]//Proc. of ACM SIGKDD’06. New York, USA: ACM Press, 2006: 523-528. [9] Tantipathananandh C, Berger-Wolf T, Kemne D. A Framework for Community Identification in Dynamic Social Networks[C]// Proceedings of ACM SIGKDD’07. New York, USA: ACM Press, 2007: 717-726. [10] Sun J, Faloutsos C, Papadimitriou S, et al. Graphscope: Parameter-free Mining of Large Time-evolving Graphs[C]// Proceedings of the 13th ACM SIGKDD. New York, USA: ACM Press, 2007: 687-696. [11] Duan Dongsheng, Li Yuhua, Jin Yanan, et al. Community Mining on Dynamic Weighted Directed Graphs[C]// Proceedings of the 1st ACM International Workshop on Complex Networks Meet Information & Knowledge Management. New York, USA: ACM Press, 2009: 11-18. [12] Nguyen N P, Dinh T N, Xuan Ying, et al. Adaptive Algorithms for Detecting Community Structure in Dynamic Social Networks[C]//Proceedings of INFCOM’11. Shanghai, China: [s. n.], 2011. [13] 吴斌, 王柏. 基于事件的社会网络演化分析框架[J]. 软件学报, 2011, 22(7): 1488-1502. [14] Newman M E J. Fast Algorithm for Detecting Community Structure in Networks[J]. Physical Review E, 2004, 69(6). [15] Li Jingyong, Huang Lan, Bai Tian, et al. CDBIA: A Dynamic Community Detection Method Based on Incremental Analysis[C]//Proceedings of IEEE International Conference on Systems and Informatics. Changchun, China: [s. n.], 2012. [16] Dinh T N, Xuan Y, Thai M T. Towards Social-aware Routing in Dynamic Communication Networks[C]//Proceedings of IPCCC’09. Phoenix, USA: [s. n.], 2009. 编辑金胡考

选择文件类型/文献管理软件名称

选择包含的内容

基于动态有噪网络的增量社团发现算法

Incremental Community Detection Algorithm Based on Dynamic Noisy Network

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	李晨曦, 任建国. 基于点对群网络反馈机制的恶意代码传播模型[J]. 计算机工程, 2023, 49(1): 163-172.
[2]	余进, 严华. 基于数据更新间隔的NAND闪存垃圾回收算法[J]. 计算机工程, 2022, 48(3): 54-59.
[3]	都繁杰, 李静, 郭志勇, 任颖文, 尹晓宇, 董小菱. 基于瓶颈感知的多级反馈队列Coflow调度机制[J]. 计算机工程, 2022, 48(10): 193-201,211.
[4]	沈国良, 翟江涛, 戴跃伟. 基于Markov模型的HTTP参数排序隐蔽信道检测方法[J]. 计算机工程, 2020, 46(2): 154-158,169.
[5]	傅伟, 周新力. 无人机网络中基于博弈模型的数据转发优化算法[J]. 计算机工程, 2019, 45(8): 146-151.
[6]	蔡秀梅, 刘超, 黄贤英. 不同输入率与移出率的蠕虫病毒传播模型[J]. 计算机工程, 2019, 45(8): 35-41.
[7]	杨晨晨,马春梅,朱金奇. 基于智能手机的跌倒行为识别算法研究[J]. 计算机工程, 2019, 45(2): 178-183.
[8]	谭阳红, 张婧, 李肖. 基于复杂网络理论的电网节点重要度评估[J]. 计算机工程, 2019, 45(11): 281-286,297.
[9]	兰涯雯, 李强, 邓淑桃, 黄诗雅. 基于多属性关联决策的WSN故障检测方法[J]. 计算机工程, 2019, 45(10): 84-89.
[10]	赵英,韩春昊. 马尔科夫模型在网络流量分类中的应用与研究[J]. 计算机工程, 2018, 44(5): 291-295.
[11]	杨昳,吴兆峰,胡谷雨. 基于TeXCP的多路径流量工程协议[J]. 计算机工程, 2018, 44(4): 149-153.
[12]	李昕冉,周金和. 基于复杂网络的绿色CDN社团结构划分[J]. 计算机工程, 2018, 44(3): 119-126.
[13]	杨路,朱显,王诗言. 一种基于期望传输时间的多径OLSR路由协议[J]. 计算机工程, 2018, 44(11): 95-99,104.
[14]	张晶,孙少杰,范洪博. 一种基于开销优化的高稳定性任务调度算法[J]. 计算机工程, 2017, 43(7): 60-63,69.
[15]	沈玮阳,刘强,欧阳峰. 基于节点稳定性与跨层优化的MANET路由设计[J]. 计算机工程, 2017, 43(10): 44-49,55.

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

基于动态有噪网络的增量社团发现算法

Incremental Community Detection Algorithm Based on Dynamic Noisy Network

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价