大规模社交网络社区发现及可视化算法

发布时间：2019-10-11 23:51

【摘要】：针对现有社区发现算法存在社区质量不满足图可视化要求和算法效率低的问题,提出一种改进的启发式社区发现算法.该算法基于模块度优化,通过结合预先选取种子节点的方法,抑制算法中大社区的过度合并,同时及时合并小的社区;然后针对力导引布局算法存在社区结构不明显和布局效率低问题,提出一种展示大规模社区结构的社区布局算法,通过引入社区引力促使同一社区中的节点聚拢,优化了社区引力建模,简化了布局算法步骤.实验结果表明,文中算法能够清晰、高效地展示大规模社交网络数据.
【图文】：

334计算机辅助设计与图形学学报第29卷a.Louvain算法b.改进的社区发现算法图1Facebook1数据集社区划分结果可视化对比a.Louvain算法b.改进的社区发现算法图2Hamsterster数据集社区划分结果可视化对比a.Louvain算法b.改进的社区发现算法图3Facebook2数据集社区划分结果可视化对比对于Hamsterster数据集,Louvain算法结果中有131个社区,本文改进算法划分结果为30个社区.从图2可以看出,相对于Louvain算法,本文改进的社区发现算法的划分结果中小社区的数量较少;Louvain算法在迭代过程中存在小社区未及时合并到大社区的现象,而本文改进算法改善了这一现象.对于Facebook2数据集,Louvain算法结果中有7个社区,本文改进算法划分结果为14个社区,社区数量多于Louvain算法.对比表3可以看出,本文改进算法模块度评价指标优于Louvain算法,Louvain算法在迭代过程中存在过度合并大社区的现象,而本文改进的社区发现算法改善了这一现象.4.2.2社区布局算法实验及分析按照上述的实验方案,针对数据集Zachary和Dolphins,对比基于复杂社区划分的可视化布局算法[4]和结合k-means提出的CGDA算法[3],可视化结果如图4~5所示.可以看出,朱志良等[4]算法的可视化结果中,社区结构不够明显,同时不同社区的节点之间排列紧密;CGDA算法社区结构相对较明显,但是在布局中由于没有加入重力,导致布局会呈现拉伸形状;本文社区布局算法中,社区结构明显,社区内的节点排列紧密且社区间边界分明.相对于朱志良等[4]提出的布局算法和吴渝等[3]提出的CGDA算法,本文改进算法布局效率更高,耗时更少,对比结果如表4所示.在较大数据集布局

334计算机辅助设计与图形学学报第29卷a.Louvain算法b.改进的社区发现算法图1Facebook1数据集社区划分结果可视化对比a.Louvain算法b.改进的社区发现算法图2Hamsterster数据集社区划分结果可视化对比a.Louvain算法b.改进的社区发现算法图3Facebook2数据集社区划分结果可视化对比对于Hamsterster数据集,Louvain算法结果中有131个社区,本文改进算法划分结果为30个社区.从图2可以看出,相对于Louvain算法,本文改进的社区发现算法的划分结果中小社区的数量较少;Louvain算法在迭代过程中存在小社区未及时合并到大社区的现象,而本文改进算法改善了这一现象.对于Facebook2数据集,Louvain算法结果中有7个社区,本文改进算法划分结果为14个社区,社区数量多于Louvain算法.对比表3可以看出,本文改进算法模块度评价指标优于Louvain算法,Louvain算法在迭代过程中存在过度合并大社区的现象,而本文改进的社区发现算法改善了这一现象.4.2.2社区布局算法实验及分析按照上述的实验方案,针对数据集Zachary和Dolphins,对比基于复杂社区划分的可视化布局算法[4]和结合k-means提出的CGDA算法[3],可视化结果如图4~5所示.可以看出,朱志良等[4]算法的可视化结果中,社区结构不够明显,同时不同社区的节点之间排列紧密;CGDA算法社区结构相对较明显,但是在布局中由于没有加入重力,导致布局会呈现拉伸形状;本文社区布局算法中,社区结构明显,社区内的节点排列紧密且社区间边界分明.相对于朱志良等[4]提出的布局算法和吴渝等[3]提出的CGDA算法,本文改进算法布局效率更高,耗时更少,对比结果如表4所示.在较大数据集布局
【作者单位】： 重庆邮电大学计算机科学与技术学院;
【基金】：国家自然科学基金(61572092) 重庆教委科学技术研究项目(KJ130518) 国家社会科学基金(13CGL146)
【分类号】：TP301.6

【相似文献】

相关期刊论文 前10条

1 ;基于位置的手机社交网络“贝多”正式发布[J];中国新通信;2008年06期

2 曹增辉;;社交网络更偏向于用户工具[J];信息网络;2009年11期

3 ;美国:印刷企业青睐社交网络营销新方式[J];中国包装工业;2010年Z1期

4 李智惠;柳承烨;;韩国移动社交网络服务的类型分析与促进方案[J];现代传播(中国传媒大学学报);2010年08期

5 贾富;;改变一切的社交网络[J];互联网天地;2011年04期

6 谭拯;;社交网络:连接与发现[J];广东通信技术;2011年07期

7 陈一舟;;社交网络的发展趋势[J];传媒;2011年12期

8 殷乐;;全球社交网络新态势及文化影响[J];新闻与写作;2012年01期

9 许丽;;社交网络:孤独年代的集体狂欢[J];上海信息化;2012年09期

10 李玲丽;吴新年;;科研社交网络的发展现状及趋势分析[J];图书馆学研究;2013年01期

相关会议论文 前10条

1 赵云龙;李艳兵;;社交网络用户的人格预测与关系强度研究[A];第七届（2012）中国管理学年会商务智能分会场论文集（选编）[C];2012年

2 宫广宇;李开军;;对社交网络中信息传播的分析和思考——以人人网为例[A];首届华中地区新闻与传播学科研究生学术论坛获奖论文[C];2010年

3 杨子鹏;乔丽娟;王梦思;杨雪迎;孟子冰;张禹;;社交网络与大学生焦虑缓解[A];心理学与创新能力提升——第十六届全国心理学学术会议论文集[C];2013年

4 毕雪梅;;体育虚拟社区中的体育社交网络解析[A];第九届全国体育科学大会论文摘要汇编(4)[C];2011年

5 杜p，

本文编号：2547750