PSNet: Privacy and Spectral Analysis of Social Networks

Social networks are of significant importance in various application domains. Most previous studies are focused on revealing interesting properties of networks and discovering efficient and effective analysis methods. However, there has been little work dedicated to privacy preserving social network analysis. In this project, we investigate the application of graph perturbation techniques to protect privacy of individual nodes and their sensitive link relationships. We conduct theoretical study and empirical evaluation on the tradeoff between utility and privacy of various graph randomization techniques as well as investigation of various potential attacking methods from adversaries. To quantify the utility loss, we focus on the change of the spectrum and eigenvectors since they have inherent relation with many real space graph characteristics. We expect to develop some spectrum/utility preserving randomization techniques which can better preserve graph utility without sacrificing much privacy protection.      

People

• Xintao Wu (PI)
• Leting Wu(Ph.D. student)
• Yue Wang(Ph.D. student)
• Xiaowei Ying (Ph.D. graduate)

Paper

• Line Orthogonality in Adjacency Eigenspace with Application to Community Partition.
  Leting Wu, Xiaowei Ying, Xintao Wu, and Zhi-Hua Zhou.
  In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI11), Barcelona, Spain, July 16-22,2011.
  PDF     Slides
• Spectral Analysis of k-balanced Signed Graphs.
  Leting Wu, Xiaowei Ying, Xintao Wu, Aidong Lu and Zhi-Hua Zhou.
  In Proceedings of the 15th Pacific-Asia Conference on Knowledge Discovery and Data Mining(PAKDD11), Shenzhen, China, May 24-27,2011.
  PDF     Slides
• Spectrum Based Fraud Detection in Social Networks.
  Xiaowei Ying, Xintao Wu, and Daniel Barbara.
  In Proceedings of the 27th IEEE International Conference on Data Engineering(ICDE11), Hannover, Germany, April 11-16,2011.
  PDF     Slides
• Spectrum Based Fraud Detection in Social Networks.
  Xiaowei Ying, Xintao Wu, and Daniel Barbara.
  In Proceedings of the 17th ACM International Conference on Computer and Communications Security, Chicago, Oct 4-8,2010 (poster).
  PDF (3-page) PPT(poster)      
• Reconstruction from Randomized Graph via Low Rank Approximation.
  Leting Wu, Xiaowei Ying, and Xintao Wu.
  In Proceedings of the 10th SIAM Conference on Data Mining(SDM), Columbus, Ohio, April 29-May 1, 2010.
  PDF     Slides
• A Spectrum-based Framework for Quantifying Randomness of Social Networks..
  Xiaowei Ying, Leting Wu, and Xintao Wu.
  IEEE Transactions on Knowledge and Data Engineering, 2010. (To appear, as an extended version of SDM09 paper).
  PDF    
• A Survey of Algorithms for Privacy-Preservation of Graphs and Social Networks.
  Xintao Wu, Xiaowei Ying, Kun Liu, and Lei Chen.
  Invited book chapter, Managing and Mining Graph Data, editors Charu C. Aggarwal and Haixun Wang, August 2009.
  PDF    
• Anaylzing Soci-technical Networks: a Spectrum Perspective.
  Xintao Wu, Xiaowei Ying, and Leting Wu.
  Invited book chapter, Socio-technical Networks: Science and Engineering Design, editors Fei Hu, Ali Mostashari, and Jiang Xie, July 2009.
  PDF    
• Comparisons of Randomization and K-degree Anonymization Schemes for Privacy Preserving Social Network Publishing.
  Xiaowei Ying, Kai Pan, Xintao Wu and Ling Guo.
  In Proceedings of the 3rd SIGKDD Workshop on Social Network Mining and Analysis (SNA-KDD), Paris, France, June 28, 2009.
  PDF     Slides
• On the Quantification of Identity and Link Disclosures in Randomizing Social Networks.
  Xiaowei Ying, Xintao Wu, Kai Pan and Ling Guo.
  Invited book chapter, Advances in Information & Intelligent Systems, editors Z.W. Ras and W. Ribarsky, May 2009.
  PDF    
• Graph Generation with Prescribed Feature Constraints.
  Xiaowei Ying and Xintao Wu.
  In Proceedings of the 9th SIAM Conference on Data Mining(SDM), Sparks, Nevada, April 30-May 2, 2009.
  PDF     Slides
• On Randomness Measures for Social Networks.
  Xiaowei Ying and Xintao Wu.
  In Proceedings of the 9th SIAM Conference on Data Mining(SDM), Sparks, Nevada, April 30-May 2, 2009.
  PDF     Slides   
• On Link Privacy in Randomizing Social Networks.
  Xiaowei Ying and Xintao Wu.
  In Proceedings of the 13th Pacific-Asia Conference on Knowledge Discovery and Data Mining(PAKDD), Bangkok, Thailand, April 27-30, 2009.
  PDF     Slides  An extended version was invited to KAIS, to appear 2010.
• Randomizing Social Networks: a Spectrum Preserving Approach.
  Xiaowei Ying and Xintao Wu.
  In Proceedings of the 8th SIAM Conference on Data Mining(SDM),Atlanta, Georgia, April 2008, pp.739-750.
  PDF    Slides

References

• Related paper and projects
  

Acknowledgements

This material is based upon work supported by National Science Foundation under CNS-0831204. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.

Data Privacy Lab  
University of North Carolina at Charlotte