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

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

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