引用本文

李慧, 马小平, 张舒, 施珺, 李存华, 仲兆满. 基于时间加权的重叠社区检测算法研究.自动化学报, 2021, 47(4): 933-942 doi: 10.16383/j.aas.c180559

Li Hui, Ma Xiao-Ping, Zhang Shu, Shi Jun, Li Cun-Hua, Zhong Zhao-Man. Research of overlap community detection algorithm based on time-weighted. Acta Automatica Sinica, 2021, 47(4): 933-942 doi: 10.16383/j.aas.c180559

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c180559

关键词

社会网络，加权，重叠，社区，检测 

摘要

随着网络结构的不断扩大和日益复杂, 重叠社区发现技术对挖掘复杂网络深层潜在结构具有重要意义. 本文提出一种基于时间加权的重叠社区检测算法. 该方法考虑了用户兴趣的时间因素, 构建带有时间加权链接的用户-用户图. 接着, 基于网络节点的影响力计算用户全局相似度, 在此基础上通过计算节点的中心度作为度量节点对社区结构影响力的重要性指标, 从而提出一种社区中心点的选取方法. 最后, 通过效用函数的迭代计算实现重叠社区检测. 利用人工网络和真实网络对提出的算法进行验证, 实验结果表明: 相对于传统的社区发现方法, 该算法在社区发现质量和计算效率方面都优于许多已有重叠社区发现算法.

文章导读

社区结构是复杂网络的重要特性, 在网络中发现社区就是把相似节点划分为一个集合, 使得集合内节点之间的相互作用比它们与集合外节点的相互作用更强, 即同一社区内部节点间的链接较为稠密, 不同社区之间的链接较为稀疏[1]. 但是社会化网络中用户的多重社会属性导致用户可以同时从属于多个社区, 因此基于可重叠聚类的社区发现算法效果更佳. 发现高质量的社区有助于理解真实的复杂网络, 尤其是动态地分析社区重叠结构, 对社区管理和演化具有重要意义[2-4].

在传统的社区发现方法中, 网络可以作为静态拓扑图处理而不用考虑节点间的信息交互因素, 在微博等社交网络中已经不再适用. 在微博及其应用所构成的社交网络中频繁地使用不同节点间的信息交互; 拓扑结构仅代表用户之间交互的可能性, 而实际交互的程度则由节点之间的信息流动情况决定. 这种社区划分方法由于仅仅依赖拓扑结构, 却忽略了社交网络中的信息流动, 因此表现出明显的局限性, 这已经与现代社交网络的特征相背离, 除此之外, 社区划分结果在这种体系下也无法得到较高的准确性.

本文的重叠社区检测算法是针对传统的社区发现方法在解决社交网络中社区划分时所面临的问题所提出的,称为基于时间加权关联规则的时域重叠社区检测算法(Time-weighted overlapping community detection, TWOCD). TWOCD算法的主要创新点在于重叠社区检测时充分考虑了用户兴趣的时间因素,根据带有时间加权链接的用户-用户图实现重叠社区检测.

本文第1节介绍了重叠社区检测的相关工作, 并描述了一些主流的重叠社区发现算法; 第2节具体地阐述了重叠社区的检测算法及社区合并方案; 第3节是算法性能验证实验; 第4节是我们的工作的总结以及对未来研究工作的展望.

图 1  Polblogs数据集中参数α对Q值的影响结果

图 3  重叠社区的模块度随社区数量的变化情况

图 5  真实数据集上各算法性能对比实验

本文提出一种新颖的重叠社区发现算法TWOCD, 该算法充分考虑了用户兴趣的时间因素, 根据带有时间加权链接的用户-用户图实现重叠社区检测. 在社区发现迭代计算时选择中心度最大的节点为种子节点, 提高了社区发现在精准度. 最后通过重叠度计算将重叠过多的社区进行合并, 从而提高了算法执行的效率. 在仿真实验中, 利用人工网络数据和真实网络数据进行有效性验证, 实验结果表明, 本文提出的算法在社区发现质量和计算效率上优于已有算法. 未来的工作计划将该算法应用于为各类复杂网络提供社区识别服务, 进而为用户提供更加个性化的社区服务.

作者简介

李慧

博士, 江苏海洋大学计算机工程学院副教授. 主要研究方向为个性化推荐, 社会网络分析. E-mail: shufanzs@126.com

张舒

江苏海洋大学商学院讲师. 主要研究方向为智能信息处理. E-mail: lih@cumt.edu.cn

施珺

江苏海洋大学计算机工程学院教授. 主要研究方向为智能信息处理. E-mail: sj_lfg@hotmail.com

李存华

博士, 江苏海洋大学计算机工程学院教授. 主要研究方向为数据挖掘. E-mail: cli2000@126.com

仲兆满

博士, 江苏海洋大学计算机工程学院副教授. 主要研究方向为中文信息处理. E-mail: zhongzhaoman@163.com

马小平

博士, 中国矿业大学信电学院教授. 主要研究方向为智能计算. 本文通信作者. E-mail: xpma@cumt.edu.cn