We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A novel subgraph K+-isomorphism method in social network based on graph similarity detection.
- Authors
Rong, Huan; Ma, Tinghuai; Tang, Meili; Cao, Jie
- Abstract
In this paper, we propose a novel K+<inline-graphic></inline-graphic>-isomorphism method to achieve <italic>K</italic>-anonymization state among subgraphs or detected communities in a given social network. Our proposed K+<inline-graphic></inline-graphic>-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 <italic>K</italic> 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, MPD-<inline-graphic></inline-graphic>V, which is a core technique for graph similarity detection involved in partition phase of our proposed K+<inline-graphic></inline-graphic>-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 K+<inline-graphic></inline-graphic>-isomorphism method. The experiments have shown that the improved MPD-<inline-graphic></inline-graphic>V method has much better efficiency to search larger common subgraphs with acceptable performance compared with its prototype and other techniques. Moreover, our proposed K+<inline-graphic></inline-graphic>-isomorphism method can achieve the <italic>K</italic>-isomorphism state with less modification of original network structure, or lower anonymization cost compared to the current <italic>K</italic>-isomorphism method.
- Subjects
SUBGRAPHS; GRAPH theory; ISOMORPHISM (Mathematics); SOCIAL networks; DATA analysis
- Publication
Soft Computing - A Fusion of Foundations, Methodologies & Applications, 2018, Vol 22, Issue 8, p2583
- ISSN
1432-7643
- Publication type
Article
- DOI
10.1007/s00500-017-2513-y