DPCAG: A Community Affiliation Graph Generation Model for Preserving Group Relationships

Graph data has been widely applied due to its powerful expressive capabilities. The release of raw graph data without preprocessing may lead to privacy information leakage. Thus, generating privacy-protected graphs is necessary for data analysis. Current privacy protection methods in graphs focus on securing attributes like degree distribution, triangle counts, and node information, but they often overlook the need to protect user group relationships. Additionally, some privacy-preserving graph publishing methods introduce significant noise due to the chosen graph generation techniques and the points at which noise is added. This paper aims to propose an effective graph synthesis algorithm by using differential privacy named DPCAG (Differentially Private Community Affiliation Graph Generation Model) for protecting user group relationships. Firstly, it is observed that there are numerous small probabilities in the adjacency matrix D generated by the affiliation matrix F, directly utilizing it to construct graph G would result in the generation of a substantial number of redundant edges. Therefore, we introduce a generating threshold theta to filter out unnecessary edges. Secondly, to achieve a better balance between data availability and the level of privacy protection, two budget allocation schemes are designed based on the introduction of k-truss to describe the tightness of group relationships. Lastly, we demonstrate the proposed model satisfies differential privacy mathematically and the effectiveness of DPCAG is validated using four real graph datasets.