Journal of Frontiers of Computer Science and Technology ›› 2017, Vol. 11 ›› Issue (10): 1629-1641.DOI: 10.3778/j.issn.1673-9418.1607025

Previous Articles     Next Articles

Measuring Similarity Between Vertices and Its Application in Social Network

CHEN Xiao1,2,3, GUO Jingfeng1,3+, ZHANG Chunying4   

  1. 1. College of Information Science and Engineering, Yanshan University, Qinhuangdao, Hebei 066004, China
    2. College of Qian'an, North China University of Science and Technology, Qian’an, Hebei 064400, China
    3. The Key Laboratory for Computer Virtual Technology and System Integration of Hebei Province, Qinhuangdao, Hebei 066004, China
    4. College of Science, North China University of Science and Technology, Tangshan, Hebei 063009, China
  • Online:2017-10-01 Published:2017-10-20

社会网络顶点间相似性度量及其应用

陈  晓1,2,3,郭景峰1,3+,张春英4   

  1. 1. 燕山大学 信息科学与工程学院,河北 秦皇岛 066004
    2. 华北理工大学 迁安学院,河北 迁安 064400
    3. 河北省计算机虚拟技术与系统集成重点实验室,河北 秦皇岛 066004
    4. 华北理工大学 理学院,河北 唐山 063009

Abstract: Set pair analysis as the mathematical theory of dealing with the interaction system of certainty and uncertainty, can be used to deal with the complexity social network of uncertain relationship. Firstly, based on the application of set pair analysis theory, this paper takes social network as an identical-different-contrary system (certain and uncertain system). Based on set pair connection degree to descript the identical, different and contrary relations between vertices, considering the contribution of local features and the topological structure to the vertex similarity, this paper defines the similarity between vertices based on the relation connection degree taking into account weight and clustering coefficient. The measurement can better describe network structure characteristics, overcome the under-estimating for some similarity between vertices based on traditional local structures, and reduce the computational complexity of global similarity indices. Secondly, in order to utilize the similarity indices to community discovering, combined with agglomerative hierarchical clustering algorithm, it is applicable to detect community structures in complex networks with any object that has similarity measurement. Finally, through the experiment of community mining on the social network, and compared with the typical algorithms of community discovering, the experimental results verify the correctness and effectiveness of the similarity measurement.

Key words: social network, similarity, set pair, identical-different-contrary relations, community discovering

摘要: 集对分析作为处理系统确定性与不确定性相互作用的数学理论,可用来处理存在不确定关系的复杂社会网络。首先,应用集对分析理论,将社会网络作为一个同异反系统(确定不确定系统),采用集对联系度刻画顶点间的同异反关系,综合考虑顶点的局部特征和拓扑结构对顶点相似性的贡献,提出加权聚集系数联系度的顶点间相似性度量方法。该度量方法可以更好地刻画网络结构特征,克服传统局部相似性度量指标对某些顶点间相似性值的低估,降低全局相似性度量指标的计算复杂度。其次,为了将该相似性度量指标应用于社区发现,与凝聚型层次聚类算法相结合,使其适用于具有相似性度量对象的复杂网络社区发现问题。最后,在社会网络上进行社区挖掘实验,并与经典社区发现算法进行比较,实验结果表明了该相似性度量指标的正确性及有效性。

关键词: 社会网络, 相似性, 集对, 同异反关系, 社区发现