Research On Community Discovery Methods For Privacy Protection In Dynamic Social Networks

With the rapid expansion of the size of online social networking sites,real-world social networks have naturally entered the field of dynamic networks.A dynamic network is a complex evolutionary graph of a particular structure,where changes frequently appear over time.On the one hand,it will inevitably affect the local structure of the network.On the other hand,dynamic evolution over a period of time may cause the entire a major change in the structure of the community.Identifying the community structure of dynamic social networks not only provides unique insights for developing effective community-aware solutions,but also enables a wide range of applications such as routing strategies in mobile ad hoc networks(MANETs)and worms in online social networks control.However,along with the mining of social network structure,private information such as the location,interests,or other personal data of a large number of individuals has also been leaked.Nowadays,most communities find that the application research of privacy protection focuses on static social networks and does not consider the dynamic evolution characteristics of social networks.At present,since most methods of privacy protection of dynamic social networks do not consider the similarity between network topology and nodes,they are vulnerable to attacks by third parties and it is difficult to ensure the usefulness of mining data.The differential privacy protection model provides rigorous mathematical theoretical support and quantitative risk representation for privacy leakage,which greatly protects the privacy and security of network data.The application of differential privacy technology will help solve the problem of privacy information leakage in the process of community discovery by dynamic social networks.Based on the multi-modality of the community evolution structure and the segmentation of the network sub-graphs,and combined with differential privacy technology,the community discovery algorithm based on dynamic social networks is designed and implemented respectively.The main tasks completed are as follows:(1)Aiming at the problem of subgraph information leakage in local high-order subgraphs in the process of clustering and partitioning,a privacy protection community discovery algorithm based on local high-order subgraphs is proposed in combination with differential privacy technology.The multimodality of local high-order subgraphs effectively reflects the characteristics of social network structure.First,construct a sequential network motif sequence to interfere with the allocation of privacy budget to the change of the motif adjacency matrix in the time stamp range.Second,use an approximate personalized page rank algorithm to random walk on the disturbed adjacency matrix and perform a sweep procedure to output with the smallest conductance,and cluster the social nodes to achieving clustering of non-overlapping social individuals.(2)Aiming at the problem of implementing overlapping community division in dynamic social networks and ignoring the similarity between network topology and nodes,a privacy protection community discovery algorithm based on preference learning is proposed.According to the uncertainty of the evolution of the dynamic social network structure,the evolution parameter is assigned to the node preference degree so that the node selects the tags for iterative update according to the priority relationship of the preference degree.In order to avoid the leakage of private information during the propagation of node tags,Laplacian noise is added to the node's preference during the iteration process to make it effectively implement overlapping community detection while providing better privacy effect for node tags.(3)In order to verify the utility of overlapping and non-overlapping community partitioning algorithms,theoretical analysis such as time complexity,privacy,and algorithm utility were performed.Through comparative experiments and formal proofs,it is verified that the two proposed algorithms can satisfy the definition of differential privacy and have superior utility.At the same time,the commonly used community discovery evaluation indicators such as extended mutual information function,F-metrics,motif conductance,and modularity are verified on real social network datasets.The experimental results show that the two algorithms can effectively protect the privacy information of social individuals while achieving efficient mining of dynamic community structures.