计算机工程与应用 ›› 2019, Vol. 55 ›› Issue (21): 79-86.DOI: 10.3778/j.issn.1002-8331.1807-0287

• 大数据与云计算 • 上一篇    下一篇

基于动态距离的模糊社区识别算法

杨壹,何明,周波,牛彦杰,王勇   

  1. 1.中国人民解放军陆军工程大学 指挥控制工程学院,南京 210002
    2.军事科学院 系统工程研究院 网络信息研究所,北京 100071
  • 出版日期:2019-11-01 发布日期:2019-10-30

Fuzzy Community Detection Algorithm Based on Dynamic Distance

YANG Yi, HE Ming, ZHOU Bo, NIU Yanjie, WANG Yong   

  1. 1.College of Command and Control Engineering, The Army Engineering University of PLA, Nanjing 210002, China
    2.Institute of Network Information, Academy of Systems Engineering, Academy of Military Sciences, Beijing 100071, China
  • Online:2019-11-01 Published:2019-10-30

摘要: 社区识别技术是公共安全领域潜在危害行为预警预测和已发生危害行为追踪溯源的基础,针对传统社区识别算法将社区视作单一集合而无法描述社区主次成员的问题,提出一种基于动态距离的模糊社区识别算法。该算法将传统的单一社区结构划分为核心区域和边际区域,以边际区域来描述社区的模糊区间。该算法首先将网络设想为动态演变模型,网络中的任意节点均会与其他节点产生互动,互动将改变各节点间距离,距离也反过来影响互动。在阈值的界定下,受到多个社区吸引的节点被划分到边际区域,最终距离分布趋于稳定,各个社区结构得以显现。通过对比实验验证了CDFDD算法在社区识别上的有效性。

关键词: 动态距离, 模糊社区, 社区识别, 网络分析

Abstract: Community identification technology is the basis for the early warning and prediction of potential harmful behaviors in the public security field and the traceability of harmful behaviors. The traditional community identification algorithm treats the community as a single set and cannot describe the problems of the community’s primary and secondary members. This paper proposes a fuzzy community recognition algorithm based on dynamic distance. The algorithm divides the traditional single community structure into core areas and marginal areas, and describes the fuzzy intervals of the community by marginal areas. The algorithm conceives the network as a dynamic evolution model. Any node in the network will interact with other nodes. The interaction will change the distance between nodes, and the distance will in turn affect the interaction. Under the definition of the threshold, the nodes attracted by multiple communities are divided into marginal regions, and the final distance distribution tends to be stable, and the various community structures are revealed. The effectiveness of CDFDD algorithm in community identification is verified by comparative experiments.

Key words: dynamic distance, fuzzy community, community detection, network analysis