基于SimRank全局矩阵平滑收敛的网络社区发现
作者:
作者单位:

1.南京信息职业技术学院网络与通信学院,南京 210023;2.南京邮电大学计算机学院,南京 210023

作者简介:

通讯作者:

基金项目:

国家自然科学基金( 61672297 )资助项目; 2019年中国特色高水平高职学校和专业建设计划(教职成函〔2019〕14号)资助项目;2019年度高校“青蓝工程”优秀教学团队(苏教师[2019]3号)资助项目。


Hierarchical Community Detection Based on Global Smooth Convergence Using SimRank
Author:
Affiliation:

1.School of Network and Communication, Nanjing Vocational College of Information Technology, Nanjing 210023, China;2.School of Computer Science, Nanjing University of Posts and Telecommunications, Nanjing 210023, China

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
    摘要:

    SimRank方法是一种基于图的拓扑结构信息来衡量任意两个对象间相似程度的方法,针对在真实的大规模社交网络中节点与节点之间的迭代计算过程需要消耗大量的时间,提出了一种基于SimRank全局矩阵平滑收敛的网络社区发现方法(SimRank global smooth convergence,SGSC)。首先,该算法通过经典度量来识别网络中的初始核心节点;然后利用矩阵平滑收敛来计算SimRank得到最终核心节点;最后,基于全局收敛矩阵,将社区聚集在核心节点周围,使用Closeness指数合并两个社区,通过递归的重复该过程,聚类出最终社区。在3种真实的不同规模的社交网络中将SGSC和其他2种具有代表性的方法进行比较,并验证了提出的算法在不同规模的社交网络中社区划分的准确率和算法运行的时间性能上有所提升。

    Abstract:

    SimRank is a method based on the topological structure information of the graph to measure the similarity between any two objects. However, in real large-scale social networks, the iterative computation between nodes is time-consuming. Here we propose a hierarchical community detection algorithm based on global matrix smooth convergence using SimRank, called SGSC. First, the SGSC algorithm identifies the initial core nodes in a network by classical measurement.Then, it smoothly converges a matrix to calculate SimRank to obtain original core nodes. Based on the global convergence matrix, we cluster the communities around the core nodes and use a closeness index to merge two communities. By recursively repeating the process, a dendrogram of the communities is eventually constructed. We validate the performance of SGSC by comparing its results with those of two representative methods for three real-world networks with different scales, and comparison results show that the proposed SGSC algorithm improves the accuracy in community division and reduces running time in social networks of different scales.

    表 1 测试数据集Table 1 Test datasets
    表 4 Facebook网络中社区划分结果以及模块度Table 4 Community division results and modularity of the divided communities (Facebook network)
    表 3 阈值的选择对于核心节点的影响(Facebook网络)Table 3 Effect of the threshold value on core nodes (Facebook network)
    表 2 阈值的选择对于核心节点的影响(American College Football网络)Table 2 Effect of the threshold value on core nodes (American College Football network)
    图1 不同的网络中社区划分的模块度Fig.1 Modularity of the divided communities in different networks
    图2 不同的网络中各算法运行的时间Fig.2 Comparisons of complexity
    表 5 Deezer社交网络中社区划分结果以及模块度Table 5 Community division results and modularity of the divided communities (Deezer social network)
    参考文献
    相似文献
    引证文献
引用本文

李维勇,孔枫,张伟,陈云芳.基于SimRank全局矩阵平滑收敛的网络社区发现[J].数据采集与处理,2021,36(2):314-323

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
历史
  • 收稿日期:2020-12-10
  • 最后修改日期:2021-02-15
  • 录用日期:
  • 在线发布日期: 2021-03-25