A novel subgraph -isomorphism method in social network based on graph similarity detection

作者：Rong, Huan; Ma, Tinghuai^*; Tang, Meili; Cao, Jie

来源：Soft Computing, 2018, 22(8): 2583-2601.

DOI：10.1007/s00500-017-2513-y

• Social network
• Subgraph similarity detection
• Subgraph K-anonymization
• Privacy preservation
• Maximum common subgraph

In this paper, we propose a novel -isomorphism method to achieve K-anonymization state among subgraphs or detected communities in a given social network. Our proposed -isomorphism method firstly partitions the subgraphs we have detected into some similar-subgraph clusters followed by graph modification conducted in every cluster. In this way, it is feasible to publish preserved structures of communities or subgraphs and every preserved structure actually represents a cluster of at least K subgraphs or communities which are isomorphic to each other. The contributions of this paper are listed as follows: On the one hand, we improve a maximum common subgraph detection algorithm, MPDV, which is a core technique for graph similarity detection involved in partition phase of our proposed -isomorphism method; on the other hand, with minor adjustment, we utilize some current techniques as an innovative combination to finish the partition and modification of similar-community cluster in -isomorphism method. The experiments have shown that the improved MPDV method has much better efficiency to search larger common subgraphs with acceptable performance compared with its prototype and other techniques. Moreover, our proposed -isomorphism method can achieve the K-isomorphism state with less modification of original network structure, or lower anonymization cost compared to the current K-isomorphism method.

• 出版日期2018-4
• 单位南京信息工程大学